Advanced Backend Optimization

Appendix 7

Appendix of the Speedup-Test Protocol

A7.1. Why is the observed minimal execution time not necessarily a good statistical estimation of program performances?

Considering the minimum value of the n observed execution times is sometimes used in the literature but can be discussed:

– Nothing guarantees that this minimum execution time is an ideal execution of the program.

– Nothing guarantees that the minimum execution time over multiple runs represents the run with the least noise.

– Nothing guarantees that this minimum execution time is a consequence of the optimization technique under study. Maybe this minimum execution time is an accident, or a consequence of dynamic voltage scaling, or anything else.

– If this minimal execution time is a rare event, all the statistics based on the minimum describe rare speedups. So, they easily become non-reproducible.

In addition to the above arguments, there is a mathematical argument against using the minimal execution time. Indeed, contrary to the sample average or the sample median, the sample minimum does not necessarily follow a normal distribution. That is, the sample minimum does not necessarily converge quickly toward its theoretical value. The variance of the sample minimum may be pretty high for an arbitrary population. Formally, if θ is the theoretical minimal execution time, then the sample min_i x_i may be far from θ; everything depends on the distribution function of X. For an illustration, see Figure A7.1 for two cases ...