Amdahl's Law
Statistics: That’s Math, Right
Computer systems researchers have a somewhat tortured relationship with statistics and math.
-
On a good day:
-
For extra-special bonus points:
First, Predict
Before performing an experiment and collecting data it is helpful to make predictions.
-
One way to do this is to draw sketches of the graphs you expect to produce.
-
After collecting real results you can compare them against your predictions as a way of developing intuition about your system.
-
(Predictions about simple cases are also good ways to validate models and simulators.)
Understand Your Data
Beware the premature use of summary statistics--means, medians, etc.
As an example, the following data from two experiments could have the same mean and median:
|
|
Love Your Outliers
-
They may just be weird remnants of your measurement harness.
-
They may have a lot more to tell you.
-
Understand them either way.
Deciding What to Improve
Improve the slowest part, right?
-
(Even if it were this simple, getting programmers to work on any one specific thing can be hard. Frequently they decide to optimize something simply because "they want to".)
-
foowhich takes 5 minutes to execute. -
barwhich takes 5 seconds to execute.
Why Not foo?
What two elements have we missed in our overly-simplistic decision?
-
Significance: how much does
foomatter? -
Difficulty: how hard is it going to be to improve
foo?
-
Significance, so let’s start there.
Amdahl’s Law
The impact of any effort to improve system performance is constrained by the performance of the parts of the system not targeted by the improvement.
-
Reducing the execution time of
foofrom + 5 minutes → 1 minute. -
Reducing the execution time of
barfrom + 5 seconds → 4 seconds.
foo is better:-
absolutely (4 minutes v. 1 second) and
-
proportionally (80% v. 20%).
Not So Fast (Pun Intended)
-
Reducing the execution time of
foofrom + 5 minutes → 1 minute. -
Reducing the execution time of
barfrom + 5 seconds → 4 seconds.
But what if our program spends 95% of its time running bar but
only 0.1% running foo?
-
foospeedup: 0.001 * 240 seconds = 0.24 seconds. -
barspeedup: 0.95 * 1 = 0.95 seconds.
Amdahl’s Law
Even more colloquially:
Ignore the thing that looks the worst and fix the thing that is doing the most damage.
Systems Are More Complicated Than Algorithms
(Don’t tell Atri.)
-
"The external interface (that is, the requirement) is less precisely defined, more complex, and more subject to change."
-
"The system has much more internal structure, and hence many internal interfaces."
-
"The measure of success is much less clear."
I have designed and built a number of computer systems, some that worked and some that didn’t. I have also used and studied many other systems, both successful and unsuccessful. From this experience come some general hints for designing successful systems. I claim no originality for them; most are part of the folk wisdom of experienced designers. Nonetheless, even the expert often forgets, and after the second system [6] comes the fourth one.
