Measuring computer performance. A practitioner's guide

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Goals......Page 13
Philosophy......Page 14
Organization......Page 15
Suggestions for using this text......Page 16
Acknowledgements......Page 17
1.1 Measuring performance......Page 19
1.2 Common goals of performance analysis......Page 20
1.3 Solution techniques......Page 22
1.5 Exercises......Page 25
2.1 What is a performance metric?......Page 27
2.2 Characteristics of a good performance metric......Page 28
2.3.1 The clock rate......Page 30
2.3.2 MIPS......Page 31
2.3.3 MFLOPS......Page 32
2.3.4 SPEC......Page 33
2.3.5 QUIPS......Page 34
2.3.6 Execution time......Page 35
2.5 Speedup and relative change......Page 37
2.6 Means versus ends metrics......Page 39
2.8 For further reading......Page 41
2.9 Exercises......Page 42
3.1 Why mean values?......Page 43
3.2.1 The sample mean......Page 44
3.2.2 The sample median......Page 45
3.2.4 Selecting among the mean, median, and mode......Page 46
3.3.1 Characteristics of a good mean......Page 47
3.3.2 The arithmetic mean......Page 48
3.3.3 The harmonic mean......Page 49
3.3.4 The geometric mean......Page 50
3.4 Quantifying variability......Page 53
3.5 Summary......Page 57
3.6 For further reading......Page 58
3.7 Exercises......Page 59
4.1 Accuracy, precision, and resolution......Page 61
4.2 Sources of errors......Page 63
4.3 A model of errors......Page 64
4.4 Quantifying errors......Page 65
4.4.1.1 Case 1: When the number of measurements is large…......Page 66
4.4.1.2 Case 2: When the number of measurements is small (n < 30)......Page 68
4.4.2 Determining the number of measurements needed......Page 70
4.4.3 Confidence intervals for proportions......Page 71
4.4.4 Normalizing data for confidence intervals......Page 73
4.6 For further reading......Page 75
4.7 Exercises......Page 76
5 Comparing alternatives......Page 79
5.1 Comparing two alternatives......Page 80
5.1.1 Before-and-after comparisons......Page 81
5.1.2 Noncorresponding measurements......Page 82
5.1.3 Comparing proportions......Page 87
5.2.1 Analysis of variance (ANOVA)......Page 89
5.2.2 Contrasts......Page 96
5.4 For further reading......Page 98
5.5 Exercises......Page 99
6.1 Events and measurement strategies......Page 100
6.1.2 Measurement strategies......Page 101
6.2 Interval timers......Page 104
6.2.1 Timer overhead......Page 106
6.2.2 Quantization errors......Page 108
6.2.3 Statistical measures of short intervals......Page 109
6.3 Program profiling......Page 110
6.3.1 PC sampling......Page 111
6.3.2 Basic-block counting......Page 113
6.4 Event tracing......Page 115
6.4.1 Trace generation......Page 116
6.4.2 Trace compression......Page 118
6.4.2.2 Compression of data......Page 119
6.4.2.3 Abstract execution......Page 120
6.4.2.4 Trace sampling......Page 121
6.5 Indirect and ad hoc measurements......Page 122
6.6 Perturbations due to measuring......Page 123
6.7 Summary......Page 125
6.8 For further reading......Page 126
6.9 Exercises......Page 127
7 Benchmark programs......Page 129
7.1.2 Instruction-execution mixes......Page 130
7.1.3 Synthetic benchmark programs......Page 132
7.1.5 Program kernels......Page 133
7.1.6 Application benchmark programs......Page 134
7.2.1 Fixed-computation benchmarks......Page 135
7.2.1.1 Amdahl's law......Page 136
7.2.2 Fixed-time benchmarks......Page 138
7.2.2.1 Scaling Amdahl's law......Page 139
7.2.3 Variable-computation and variable-time benchmarks......Page 140
7.3.1.1 Livermore loops......Page 143
7.3.1.3 LINPACK......Page 144
7.3.1.5 SPEC CPU......Page 145
7.3.1.6 Whetstone and Dhrystone......Page 147
7.3.2 Transaction processing......Page 148
7.3.3.2 SPECweb......Page 149
7.4 Summary......Page 150
7.5 For further reading......Page 153
7.6 Exercises......Page 155
8.1 Least squares minimization......Page 157
8.2 Confidence intervals for regression parameters......Page 160
8.3.1 The coefficient of determination......Page 163
8.3.2 The correlation coefficient......Page 164
8.3.3 Correlation and causation......Page 165
8.4 Multiple linear regression......Page 166
8.5 Verifying linearity......Page 168
8.6 Nonlinear models......Page 169
8.8 For further reading......Page 173
8.9 Exercises......Page 174
9 The design of experiments......Page 175
9.2 Terminology......Page 176
9.3.1 Interaction of factors......Page 177
9.3.2 ANOVA for two-factor experiments......Page 178
9.3.3 The need for replications......Page 183
9.4 Generalized m-factor experiments......Page 186
9.5.1 Two factors......Page 190
9.5.2 More than two factors......Page 193
9.7 For further reading......Page 195
9.8 Exercises......Page 196
10 Simulation and random-number generation......Page 199
10.1 Simulation-efficiency considerations......Page 200
10.2.1 Emulation......Page 201
10.2.2 Static (Monte Carlo) simulation......Page 202
10.2.3.1 The event scheduler......Page 203
10.2.3.4 Event generation......Page 204
10.2.3.6 The simulation algorithm......Page 207
10.3.1 Uniformly distributed sequences......Page 208
10.3.1.1 Choosing the constants......Page 210
10.3.1.2 Cautions and suggestions......Page 211
10.3.2 Nonuniformly distributed random numbers......Page 212
10.3.2.1 Inverse transformation......Page 213
10.3.2.2 The alias method......Page 215
10.3.2.3 Decomposition......Page 216
10.3.2.4 Special characterization......Page 218
10.3.2.5 The accept–reject method......Page 219
10.4.1 Validation......Page 221
10.4.1.2 Analytical results......Page 222
10.4.2 Verification......Page 223
10.4.4 Stochastic verification......Page 224
10.4.4.1 Goodness-of-fit testing......Page 225
10.4.4.2 Tests of independence......Page 228
10.5 Summary......Page 230
10.6 For further reading......Page 231
10.7 Exercises......Page 232
11 Queueing analysis......Page 235
11.1 Queueing-network models......Page 236
11.2 Basic assumptions and notation......Page 238
11.3.1 The utilization law......Page 239
11.3.2 Little's law......Page 241
11.4 Stochastic analysis......Page 243
11.4.1 Kendall's notation......Page 244
11.4.2 The single-queue, single-server (M/M/1) system......Page 246
11.4.3 The single-queue, multiple-server (M/M/c) system......Page 251
11.5 Summary......Page 253
11.7 Exercises......Page 255
Appendix A Glossary......Page 257
B.1 The Bernoulli distribution......Page 260
B.3 The geometric distribution......Page 261
B.6 The Poisson distribution......Page 262
B.7 The exponential distribution......Page 263
B.8 The Gaussian (normal) distribution......Page 264
B.10 The Pareto distribution......Page 265
B.11 For further reading......Page 266
C.1 Critical values of Student's t distribution......Page 267
C.2 Critical values of the F distribution......Page 269
C.3 Critical values of the chi-squared distribution......Page 273
C.4 For further reading......Page 275
Index......Page 276