21-1©2006 Raj JainCSE567MWashington University in St. LouisTwo Factors Two Factors Full Factorial Design Full Factorial Design without Replicationswithout ReplicationsRaj Jain Washington University in Saint LouisSaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse567-06/21-2©2006 Raj JainCSE567MWashington University in St. LouisOverviewOverview! Computation of Effects! Estimating Experimental Errors! Allocation of Variation! ANOVA Table! Visual Tests! Confidence Intervals For Effects! Multiplicative Models! Missing Observations21-3©2006 Raj JainCSE567MWashington University in St. LouisTwo Factors Full Factorial DesignTwo Factors Full Factorial Design! Used when there are two parameters that are carefully controlled! Examples:" To compare several processors using several workloads." To determining two configuration parameters, such as cache and memory sizes! Assumes that the factors are categorical. For quantitative factors, use a regression model.! A full factorial design with two factors A and B having a and blevels requires ab experiments.! First consider the case where each experiment is conducted only once.21-4©2006 Raj JainCSE567MWashington University in St. LouisModelModel21-5©2006 Raj JainCSE567MWashington University in St. LouisComputation of EffectsComputation of Effects! Averaging the jth column produces:! Since the last two terms are zero, we have:! Similarly, averaging along rows produces:! Averaging all observations produces! Model parameters estimates are:! Easily computed using a tabular arrangement.21-6©2006 Raj JainCSE567MWashington University in St. LouisExample 21.1: Cache ComparisonExample 21.1: Cache Comparison!21-7©2006 Raj JainCSE567MWashington University in St. LouisExample 21.1: Computation of EffectsExample 21.1: Computation of Effects! An average workload on an average processor requires 72.2 ms of processor time.! The time with two caches is 21.2 ms lower than that on an average processor! The time with one cache is 20.2 ms lower than that on an average processor.! The time without a cache is 41.4 ms higher than the average21-8©2006 Raj JainCSE567MWashington University in St. LouisExample 21.1 (Cont)Example 21.1 (Cont)! Two-cache - One-cache = 1 ms.! One-cache - No-cache = 41.4-20.2 or 21.2 ms.! The workloads also affect the processor time required. ! The ASM workload takes 0.5 ms less than the average.! TECO takes 8.8 ms higher than the average.21-9©2006 Raj JainCSE567MWashington University in St. LouisEstimating Experimental ErrorsEstimating Experimental Errors! Estimated response:! Experimental error:! Sum of squared errors (SSE):! Example: The estimated processor time is:! Error = Measured-Estimated = 54-50.5 = 3.521-10©2006 Raj JainCSE567MWashington University in St. LouisExample 21.2: Error ComputationExample 21.2: Error ComputationThe sum of squared errors is:21-11©2006 Raj JainCSE567MWashington University in St. LouisExample 21.2: Allocation of VariationExample 21.2: Allocation of Variation! Squaring the model equation:! High percent variation explained ⇒ Cache choice important in processor design.21-12©2006 Raj JainCSE567MWashington University in St. LouisAnalysis of VarianceAnalysis of Variance! Degrees of freedoms:! Mean squares:! Computed ratio > F[1- α;a-1,(a-1)(b-1)]⇒A is significant at level α.21-13©2006 Raj JainCSE567MWashington University in St. LouisANOVA TableANOVA Table!21-14©2006 Raj JainCSE567MWashington University in St. LouisExample 21.3: Cache ComparisonExample 21.3: Cache Comparison! Cache choice significant.! Workloads insignificant21-15©2006 Raj JainCSE567MWashington University in St. LouisExample 21.4: Visual TestsExample 21.4: Visual Tests21-16©2006 Raj JainCSE567MWashington University in St. LouisConfidence Intervals For EffectsConfidence Intervals For Effects! For confidence intervals use t values at (a-1)(b-1) degrees of freedom21-17©2006 Raj JainCSE567MWashington University in St. LouisExample 21.5: Cache ComparisonExample 21.5: Cache Comparison! Standard deviation of errors:! Standard deviation of the grand mean:! Standard deviation of αj's:! Standard deviation of βi's:21-18©2006 Raj JainCSE567MWashington University in St. LouisExample 21.5 (Cont)Example 21.5 (Cont)! Degrees of freedom for the errors are (a-1)(b-1)=8.For 90% confidence interval, t[0.95;8]= 1.86.! Confidence interval for the grand mean:! All three cache alternatives are significantly different from the average.21-19©2006 Raj JainCSE567MWashington University in St. LouisExample 21.5 (Cont)Example 21.5 (Cont)! All workloads, except TECO, are similar to the average and hence to each other.21-20©2006 Raj JainCSE567MWashington University in St. LouisExample 21.5: CI for DifferencesExample 21.5: CI for Differences! Two-cache and one-cache alternatives are both significantly better than a no cache alternative. ! There is no significant difference between two-cache and one-cache alternatives.21-21©2006 Raj JainCSE567MWashington University in St. LouisCase Study 21.1: Cache Design AlternativesCase Study 21.1: Cache Design Alternatives! Multiprocess environment: Five jobs in parallel.ALL = ASM, TECO, SIEVE, DHRYSTONE, and SORT in parallel.! Processor Time:21-22©2006 Raj JainCSE567MWashington University in St. LouisCase Study 21.1 on Cache Design (Cont)Case Study 21.1 on Cache Design (Cont)Confidence Intervals for Differences:Conclusion: The two caches do not produce statistically better performance.21-23©2006 Raj JainCSE567MWashington University in St. LouisMultiplicative ModelsMultiplicative Models! Additive model:! If factors multiply ⇒ Use multiplicative model! Example: processors and workloads" Log of response follows an additive model! If the spread in the residuals increases with the mean response⇒ Use transformation21-24©2006 Raj JainCSE567MWashington University in St. LouisCase Study 21.2: RISC architecturesCase Study 21.2: RISC architectures! Parallelism in time vs parallelism in space! Pipelining vs several units in parallel! Spectrum = HP9000/840 at 125 and 62.5 ns cycle! Scheme86 = Designed at MIT21-25©2006 Raj JainCSE567MWashington University in St. LouisCache Study 21.2: Simulation ResultsCache Study 21.2: Simulation Results! Additive model: ⇒ No significant difference! Easy to see that: Scheme86 = 2 or 3 × Spectrum125! Spectrum62.5 = 2 × Spectrum125! Execution Time = Processor Speed × Workload Size⇒ Multiplicative model.! Observations
View Full Document
Unlocking...