<div dir="ltr"><div class="gmail_quote">On Tue, Feb 1, 2011 at 12:09 PM, Nadav Har'El <span dir="ltr"><<a href="mailto:nyh@math.technion.ac.il">nyh@math.technion.ac.il</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
But if he runs his deterministic application 5 times and gets 5 different<br>
durations, each duration is composed of the deterministic run-time of<br>
the application plus a random delay caused by other things on the system.<br>
The *minimum* of these 5 durations is the one that had the minimum random<br>
delay, and is thus closest to the "true" run time. Presumably, if one runs<br>
the application on a machine which is as idle as humanly possible, you'd<br>
get something close to this minimum.<br>
<br></blockquote><div><br></div><div>See this paper[2] which is referred in the slides.</div><div>Maybe the minimal result you're getting is due to the UNIX environment variables?</div><div><br></div><div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
We see that something external and orthogonal</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
to the program, i.e., changing the size (in bytes) of an unused</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
environment variable, can dramatically (frequently by about</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
33% and once by almost 300%) change the performance of</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
our program. This phenomenon occurs because the UNIX</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
environment is loaded into memory before the call stack.</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
Thus, changing the UNIX environment size changes the</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
location of the call stack which in turn affects the alignment</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
of local variables in various hardware structures.</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
This simple example demonstrates that computer systems are sensitive: an insignificant and seemingly irrelevant change can dramatically affect the performance of the</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
system. As a consequence of this sensitivity, we will find</blockquote><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
that different experimental setups will produce different outcomes and thus cause measurement bias.</blockquote><div><br></div><div>The program they tested[1] is strictly CPU bound. BTW, standard deviation wouldn't work as well, but it shows (I think) that there's no such think as "ideal minimal runtime".</div>
</div><div><div><br></div><div>[1]</div><div>static int i = 0, j = 0, k = 0;</div><div>int main() {</div><div>int g = 0, inc = 1;</div><div>for (; g<65536; g++) {</div><div> i += inc;</div><div> j += inc;</div><div> k += inc;</div>
<div>}</div><div>return 0;</div><div>}</div></div><div><br></div><div>[2] <a href="http://www-plan.cs.colorado.edu/diwan/asplos09.pdf">http://www-plan.cs.colorado.edu/diwan/asplos09.pdf</a> </div></div></div>