Transcription
Introduction to ExperimentalDesign and AnalysisDr. John Mellor-CrummeyDepartment of Computer ScienceRice Universityjohnmc@cs.rice.eduCOMP 528 Lecture 11 22 February 2005
Experimental Design and AnalysisUnderstand how to Design a experiments for measurement or simulationDevelop a model that describes the data obtainedEstimate the contribution of each factor to performanceIsolate measurement errorsEstimate confidence intervals for model parametersCheck if alternatives are significantly differentCheck if a model is adequate2
Goals for TodayUnderstand What are the benefits of experimental designTermsAvoiding mistakes in experimental designBasic taxonomy of experimental designs—simple design, factorial design, fractional factorial design Understand 22 factorial design and its analysis—sign table method—properties—analysis—allocating variation3
Why Experimental Design? Obtain maximum information from fewest experiments— minimize time spent gathering data Quantify effects from different factors using analysisDetermine if a factor’s effect is significant—differences might be random variations caused by– measurement errors– parameters not controlled4
Terms - I Response variable: outcome of an experiment—generally represents measured performance of the system—e.g. throughput: transactions/second, round-trip latency, etc. Factors: variables with alternatives that affect response—also called predictor variables or predictors—e.g. CPU type, memory size, # disk drives, workload used, etc. Levels: values a factor can assume—also called “treatment” in experimental design literature—e.g. CPU type levels: Itanium2, Alpha 21264, Opteron—e.g. memory size levels: 512MB, 1GB, 2GB, 4GB Primary factors: factors whose effects need to be quantifiedSecondary factors: factors that are not being quantified—they impact performance; we may not be interested in how much5
Terms - II Replication: repetition of some or all experiments—if all experiments repeated 3x, experiment is said to have 3 replications Experimental design: plan for experimentation—number of experiments, factor level combinations for each, replications Experimental unit: any entity used for experiments—workstations, patients, land in agriculture expts—goal of experimental design: minimize impact of variation among units Interaction: if level of A changes effect of level change of BNon-interactingB1B2A136A258lines parallel ingraph of A vs. BInteractingB1B2A136A259lines not parallel ingraph of A vs. B6
Common Mistakes in Experimentation - I Ignore variation due to experimental error—every measured value is a random variable—measured values change even if controllable vars kept constant—must compare variation due to factor vs. experimental error– don’t make decision about factor’s effect without this comparison! Fail to control important parameters—only some parameters selected as factors and varied—must control other variables expected to have a significant effect– e.g. if measuring impact of memory speed on performance, use same CPU type/speed for experiments if CPU not a factor Fail to isolate effects of different factors—if varying several factors are being varied simultaneously– design experiments so that effects of factors can be separated7
Common Mistakes in Experimentation - II Use simple one-factor-at-a-time designs—leads to too many experiments—yields too little information per experiment—proper design narrower confidence intervals with same # expts Ignore interactions between factors—cannot estimate interactions with one-factor-at-a-timeexperiments Conduct too many experiments—# experiments needed depends upon # factors, # factor levels—enormous single-step design vs. several steps– better to use multiple steps each with small designs and # levels– first step: test analysis assumptions and whether transformationsrequired– remaining steps: more factors and levels8
Types of Experimental Designs Simple designsFull factorial designFractional factorial design9
Simple Designs (Not recommended) What is a simple design?— start with a typical configuration— vary one factor at a time to see how performance changes Example: comparing workstation configurations1. run typical configuration using a benchmark2. run experiments to pick the best CPU by varying CPU only3. using the best CPU, run a set of experiments to find theminimum memory size yielding good performance4. using the best (CPU,memory) configuration, examine theimpact of disk RPM on the benchmark’s performance Given: k factors; ith factor has ni levelsk number ofexperimentsDrawbacksn 1 # (n i "1)i 1— if factors interact, may yield wrong conclusions— fails to make best use of # experiments: statistically inefficient 10!
Full Factorial Designs Explores every possible combination at all levels of factorsk number ofexperimentsExamplen " nii 1n (5 CPU types)(4 memory sizes)(2 disk RPMs)(4 workloads) 160 experiments Advantages—thorough: every possible configuration of workload is examined– !can find effect of every factor, secondary factors, and interactionsDisadvantages—cost: too many experiments, especially with repetitions Ways to reduce cost—reduce number of levels per factor (2 is very popular)—reduce # factors:––initially only examine a few levels of each factorprune unimportant factors, then try more factors per level—use fractional factorial designs11
Fractional Factorial Designs A full factorial design may require many experimentsHow can we get by with less: fractional factorial designExample—full factorial design (here, a 24 design)n (2 CPU types)(2 memory sizes)(2 disk RPMs)(2 workloads) 16 experiments—fractional factorial design (here a 24-1 loadCPUMemoryDiskWorkload“half replicatedesign”12
In Class Exercise A system’s performance depends upon the following factors—CPU type: Pentium4, Opteron, Athlon—OS type: Linux, Windows, Solaris—file compression utility: bzip2, gzip, zip How many experiments are necessary if:—there is significant interaction among the factors—the interactions are small compared to the main effects—there is no interaction among the factors13
Beginning2k Factorial Designs14
2k Factorial Designs What are they?—design to determine effect of k factors, each with 2 levels Why consider them?—easy to analyze—helps order factors based on impact—useful to identify– factors that have significant impact study with full factorial design– factors have little impact not of interest for quantitative study How to select 2 levels—if factor effect is expected to be unidirectional select min, max– performance increases or decreases with factor– e.g. performance improves with more memory15
22 Factorial Designs Special case of 2k factorial designs, k 2—two factors at two levels Utility—22 designs are simple to analyze with regression16
Example: a 22 DesignConsider impact of memory & cache sizes on performanceL3 Cache Size (MB)Memory Size - 1GBMemory Size - 2GB41.5 GFLOPS3.2 GFLOPS62.5 GFLOPS5.2 GFLOPSDefine 2 categorical variablesxA -1 1if 1GB memoryif 2GB memoryxB -1 1if 4MB cacheif 6MB cacheModel performance using a non-linear equation in xA and xBy q0 qA x A qB x B qAB x A x BSolve using regression17
Example: a 22 DesignRegress performance in GFLOPS on xA and xBy q0 qA x A qB x B qAB x A x BSubstitute y, xA and xB!1.5 q0 " qA " qB qAB3.2 q0 qA " qB " qAB2.5 q0 " qA qB " qAB5.2 q0 qA qB qAB4 equations, 4 unknowns: unique solutiony 3.1 1.1x A .75x B .25x A x BInterpretation!—mean performance:—effect of memory:!—effect of cache:—cache and memory interaction:3.1 GFLOPS1.1GFLOPS.75 GFLOPS.25 GFLOPS18
Computing Effects for 22 Designy q0 qA x A qB x B qAB x A x BSubstituting4 observationsinto the modely!1 q0 " qA " qB qABy 2 q0 qA " qB " qABy 3 q0 " qA qB " qABy 4 q0 qA qB qABSolving the equationsfor the qi’sq0 14 (y1 y 2 y 3 y 4 )qA 14 ("y1 y 2 " y 3 y 4 )qB 14 ("y1 " y 2 y 3 y 4 )qAB 14 ( y1 " y 2 " y 3 y 4 )Notice: expressions for qA, qB, qAB (contrasts) are linear combinations of responses sum of coefficients is!0Expt A1-1213-141B-1-111yy1y2y3y419
Calculating Effects with a Sign .25y1.53.22.55.2totaltotal/4All possible combinations of -1, 1AB is product of columns A and By is set of observationscompute product of each column and y;write product underneathdivide through totals by 4 to compute regression coefficients 20
Sign Table PropertiesI1111 B-1-111AB1-1-11Sum of entries in columns A, B, AB is 044"xAi 0i 1 4"xBi 0i 1"xAix Bi 0i 1Sum of squares of entries in each column is 44 A-11-11!4"x2Aii 1 4!4"xi 12Bi 4!"( xi 12Aix Bi ) 4Columns are orthogonal since inner product of column pairs is 04!"xi 14Aix Bi 0!4" x (xAii 1Aix Bi ) 0!" x (xBiAix Bi ) 0i 121!!!
Computing Sample Mean with Sign Table4sample meany 14"yii 14y 14" (q0 qA x Ai qB x Bi qAB x Ai x Bi )i 1444411! " q0 qA " x Ai 4 qB " x Bi 4 qAB " x Ai x Bi1414i 1i 1i 1i 1 q0!!22
Computing Total Variation with Sign Table4Total variation #( yi " y)i 124 " (qA x Ai qB x Bi qAB x Ai x Bi )i 14 " (qA x Ai )242A q422! " (qB x Bi ) " (qAB x Ai x Bi )i 1i 14"( x )Aii 122i 14 q2B product terms"( x )Bii 124 q2AB"( xAix Bi )2i 12 4qA2 4qB2 4qAB2224q 4q 4qSST SSA SSB SSAB ABAB2224q4q4qSSA SSB SSAB BAAB23
Allocating VariationImportance of a factor how much variation it explainsSST SSA SSB SSAB 4(1.1)2 4(.75)2 4(.25)2 7.34Variation due to A SSA 4(1.1)2 .66SST7.34Variation due to B SSB 4(.75)2 .31SST7.34SSAB 4(.25)2Variation due to interaction A & B .03SST7.3424
2 Experimental Design and Analysis Understand how to Design a experiments for measurement or simulation Develop a model that describes the data obtained Estimate the contribution of each factor to performance Isolate measurement errors Estimate confidence intervals for model parameters Check
