2006-04-01

Applications of Randomness in System Performance Measurement

Here is a link to a PhD thesis entitled Applications of Randomness in System Performance Measurement. I haven't actually read the dissertation but the abstract is quite informative in itself. Here's a quote from the second paragraph:
For TCP/IP, changes of a few percent in link propagation delays and other parameters caused order of magnitude shifts in bandwidth allocation between competing connections. For memory systems, changes in the essentially arbitrary order in which functions were arranged in memory caused changes in runtime of tens of percent for single benchmarks, and of a few percent when averaged across a suite of benchmarks. In both applications the measured variability is larger than performance increases often reported for new improved designs, suggesting that many published measurements of the benefits of new schemes may be erroneous or at least irreproducible.

When I read this several papers came to my mind which I suddenly realize doesn't hold water. Just as the above text says these papers report improvements which might just as well be noise.
The abstract then goes on to explain the contributions of the thesis:
To make TCP/IP and memory systems measurable enough to make benchmark results meaningful and convincing, randomness must be added. [...] We show how to choose reasonable amounts of randomness based on measuring configuration sensitivity, and propose specific recipies for randomizing TCP/IP and memory systems. Substantial reductions in the configuration sensitivity are demonstrated, making measurements much more robust and meaningful. The accuracy of the results increases with the number of runs and thus is limited only by the available computing resources.

Next time I'm about to measure the efficiency of a computer program I'm going to read this dissertation carefully. Today's computer system with all their complex ways to trying to speed up things has made measurements much more difficult. It seems that a little bit of randomness at the right place is the key which can alleviate these problems.

No comments: