Measuring Computer Performance : A Practitioner's Guide

Measuring Computer Performance sets out the fundamental techniques used in analyzing and understanding the performance of computer systems. The emphasis is on practical methods of measurement, simulation, and analytical modeling. David Lilja discusses performance metrics and provides detailed coverage of the strategies used in benchmark programs. In addition to intuitive explanations of key statistical tools, he describes the general "design of experiments" technique and shows how the maximum amount of information can be obtained with minimum effort. Features include appendices listing common probability distributions and statistical tables and a glossary of important technical terms. Cover 1 Half-title 3 Title 5 Copyright 6 Dedication 7 Contents 9 Preface 13 Goals 13 Philosophy 14 Organization 15 Suggestions for using this text 16 Acknowledgements 17 1 Introduction 19 1.1 Measuring performance 19 1.2 Common goals of performance analysis 20 1.3 Solution techniques 22 1.4 Summary 25 1.5 Exercises 25 2 Metrics of performance 27 2.1 What is a performance metric? 27 2.2 Characteristics of a good performance metric 28 2.3 Processor and system performance metrics 30 2.3.1 The clock rate 30 2.3.2 MIPS 31 2.3.3 MFLOPS 32 2.3.4 SPEC 33 2.3.5 QUIPS 34 2.3.6 Execution time 35 2.4 Other types of performance metrics 37 2.5 Speedup and relative change 37 2.6 Means versus ends metrics 39 2.7 Summary 41 2.8 For further reading 41 2.9 Exercises 42 3 Average performance and variability 43 3.1 Why mean values? 43 3.2 Indices of central tendency 44 3.2.1 The sample mean 44 3.2.2 The sample median 45 3.2.3 The sample mode 46 3.2.4 Selecting among the mean, median, and mode 46 3.3 Other types of means 47 3.3.1 Characteristics of a good mean 47 3.3.2 The arithmetic mean 48 3.3.3 The harmonic mean 49 3.3.4 The geometric mean 50 3.3.5 Weighted means 53 3.4 Quantifying variability 53 3.5 Summary 57 3.6 For further reading 58 3.7 Exercises 59 4 Errors in experimental measurements 61 4.1 Accuracy, precision, and resolution 61 4.2 Sources of errors 63 4.3 A model of errors 64 4.4 Quantifying errors 65 4.4.1 Confidence intervals for the mean 66 4.4.1.1 Case 1: When the number of measurements is large... 66 4.4.1.2 Case 2: When the number of measurements is small (n < 30) 68 4.4.2 Determining the number of measurements needed 70 4.4.3 Confidence intervals for proportions 71 4.4.3.1 Determining the number of measurements needed 73 4.4.4 Normalizing data for confidence intervals 73 4.5 Summary 75 4.6 For further reading 75 4.7 Exercises 76 5 Comparing alternatives 79 5.1 Comparing two alternatives 80 5.1.1 Before-and-after comparisons 81 5.1.2 Noncorresponding measurements 82 5.1.3 Comparing proportions 87 5.2 Comparing more than two alternatives 89 5.2.1 Analysis of variance (ANOVA) 89 5.2.2 Contrasts 96 5.3 Summary 98 5.4 For further reading 98 5.5 Exercises 99 6 Measurement tools and techniques 100 6.1 Events and measurement strategies 100 6.1.1 Events-type classification 101 6.1.2 Measurement strategies 101 6.2 Interval timers 104 6.2.1 Timer overhead 106 6.2.2 Quantization errors 108 6.2.3 Statistical measures of short intervals 109 6.3 Program profiling 110 6.3.1 PC sampling 111 6.3.2 Basic-block counting 113 6.4 Event tracing 115 6.4.1 Trace generation 116 6.4.2 Trace compression 118 6.4.2.1 Online trace consumption 119 6.4.2.2 Compression of data 119 6.4.2.3 Abstract execution 120 6.4.2.4 Trace sampling 121 6.5 Indirect and ad hoc measurements 122 6.6 Perturbations due to measuring 123 6.7 Summary 125 6.8 For further reading 126 6.9 Exercises 127 7 Benchmark programs 129 7.1 Types of benchmark programs 130 7.1.1 The single-instruction-execution time 130 7.1.2 Instruction-execution mixes 130 7.1.3 Synthetic benchmark programs 132 7.1.4 Microbenchmarks 133 7.1.5 Program kernels 133 7.1.6 Application benchmark programs 134 7.2 Benchmark strategies 135 7.2.1 Fixed-computation benchmarks 135 7.2.1.1 Amdahl's law 136 7.2.2 Fixed-time benchmarks 138 7.2.2.1 Scaling Amdahl's law 139 7.2.3 Variable-computation and variable-time benchmarks 140 7.3 Example benchmark programs 143 7.3.1 Scientific and engineering 143 7.3.1.1 Livermore loops 143 7.3.1.2 NAS kernels 144 7.3.1.3 LINPACK 144 7.3.1.4 PERFECT club 145 7.3.1.5 SPEC CPU 145 7.3.1.6 Whetstone and Dhrystone 147 7.3.2 Transaction processing 148 7.3.3 Servers and networks 149 7.3.3.1 SFS/LADDIS 149 7.3.3.2 SPECweb 149 7.3.4 Miscellaneous benchmarks 150 7.4 Summary 150 7.5 For further reading 153 7.6 Exercises 155 8 Linear regression models 157 8.1 Least squares minimization 157 8.2 Confidence intervals for regression parameters 160 8.3 Correlation 163 8.3.1 The coefficient of determination 163 8.3.2 The correlation coefficient 164 8.3.3 Correlation and causation 165 8.4 Multiple linear regression 166 8.5 Verifying linearity 168 8.6 Nonlinear models 169 8.7 Summary 173 8.8 For further reading 173 8.9 Exercises 174 9 The design of experiments 175 9.1 Types of experiments 176 9.2 Terminology 176 9.3 Two-factor experiments 177 9.3.1 Interaction of factors 177 9.3.2 ANOVA for two-factor experiments 178 9.3.3 The need for replications 183 9.4 Generalized m-factor experiments 186 9.5 n2m experiments 190 9.5.1 Two factors 190 9.5.2 More than two factors 193 9.6 Summary 195 9.7 For further reading 195 9.8 Exercises 196 10 Simulation and random-number generation 199 10.1 Simulation-efficiency considerations 200 10.2 Types of simulations 201 10.2.1 Emulation 201 10.2.2 Static (Monte Carlo) simulation 202 10.2.3 Discrete-event simulation 203 10.2.3.1 The event scheduler 203 10.2.3.2 The global time variable 204 10.2.3.3 Event processing 204 10.2.3.4 Event generation 204 10.2.3.5 Recording and summarization of data 207 10.2.3.6 The simulation algorithm 207 10.3 Random-number generation 208 10.3.1 Uniformly distributed sequences 208 10.3.1.1 Choosing the constants 210 10.3.1.2 Cautions and suggestions 211 10.3.2 Nonuniformly distributed random numbers 212 10.3.2.1 Inverse transformation 213 10.3.2.2 The alias method 215 10.3.2.3 Decomposition 216 10.3.2.4 Special characterization 218 10.3.2.5 The accept–reject method 219 10.4 Verification and validation of simulations 221 10.4.1 Validation 221 10.4.1.1 Comparisons with real systems 222 10.4.1.2 Analytical results 222 10.4.1.3 Engineering judgement 223 10.4.2 Verification 223 10.4.3 Deterministic verification 224 10.4.4 Stochastic verification 224 10.4.4.1 Goodness-of-fit testing 225 10.4.4.2 Tests of independence 228 10.5 Summary 230 10.6 For further reading 231 10.7 Exercises 232 11 Queueing analysis 235 11.1 Queueing-network models 236 11.2 Basic assumptions and notation 238 11.3 Operational analysis 239 11.3.1 The utilization law 239 11.3.2 Little's law 241 11.4 Stochastic analysis 243 11.4.1 Kendall's notation 244 11.4.2 The single-queue, single-server (M/M/1) system 246 11.4.3 The single-queue, multiple-server (M/M/c) system 251 11.5 Summary 253 11.6 For further reading 255 11.7 Exercises 255 Appendix A Glossary 257 Appendix B Some useful probability distributions 260 B.1 The Bernoulli distribution 260 B.2 The binomial distribution 261 B.3 The geometric distribution 261 B.4 The discrete uniform distribution 262 B.5 The continuous uniform distribution 262 B.6 The Poisson distribution 262 B.7 The exponential distribution 263 B.8 The Gaussian (normal) distribution 264 B.9 The Erlang distribution 265 B.10 The Pareto distribution 265 B.11 For further reading 266 Appendix C Selected statistical tables 267 C.1 Critical values of Student's t distribution 267 C.2 Critical values of the F distribution 269 C.3 Critical values of the chi-squared distribution 273 C.4 For further reading 275 Index 276 Measuring Computer Performance sets out the fundamental techniques used in analyzing and understanding the performance of computer systems. Throughout the book, the emphasis is on practical methods of measurement, simulation, and analytical modeling. The author discusses performance metrics and provides detailed coverage of the strategies used in benchmark programmes. He gives intuitive explanations of the key statistical tools needed to interpret measured performance data. He also describes the general 'design of experiments' technique, and shows how the maximum amount of information can be obtained for the minimum effort. The book closes with a chapter on the technique of queueing analysis. Appendices listing common probability distributions and statistical tables are included, along with a glossary of important technical terms. This practically-oriented book will be of great interest to anyone who wants a detailed, yet intuitive, understanding of computer systems performance analysis In Measuring Computer Performance, the emphasis is on practical methods of measurement, simulation, and analytical modeling. David Lilja discusses performance metrics and the strategies used in benchmark programs.