ponder@lll-crg.llnl.gov (Carl Ponder) (01/08/91)
Subject: New Technical Reports Available **************************************************************************** The following LLNL technical reports are now available for external distribution. UCRL-ID-106077: Studies in Branch-Prediction UCRL-JC-106105: An Analytical Look at Linear Performance Models To receive copies, send your address with the report name & number to Offsite Request Desk, L-392 Lawrence Livermore National Laboratory PO Box 808 Livermore, CA 94550 (415) 422-5820 The abstracts are as follows: UCRL-ID-106077 Studies in Branch-Prediction by Carl Ponder Branch-prediction is the problem of guessing the destination of a conditional branch before the condition is fully evaluated. Deeply pipelined and Very Long Instruction Word (VLIW) architectures parallelize programs by rearranging their control-flow; this rearrangement must produce few redundant operations while preserving program semantics. Accurately guessing the paths of control-flow is important. In this study we use a simplified model to show the relationship between branch-prediction accuracy, pipeline utilization, and effective speedup. Using a collection of program traces, we show upper limits on the prediction accuracy possible using specific types of static and dynamic information. These upper limits determine the pipeline speedup and utilization possible under proposed methods of branch-prediction. The primary benefit is that certain branch-prediction strategies can be eliminated from consideration, based on the level of accuracy required. A side benefit is the derivation of a finite-state "superpredictor", which (for these traces) appears to be strictly more accurate and more stable than methods previously proposed. UCRL-JC-106105 An Analytical Look at Linear Performance Models by Carl Ponder Processor performance is commonly described using simple linear expressions. The popular MIPS, MOPS, MegaFLOPS, and LIPS measures are implicitly equivalent to 1-parameter linear models. An accurate linear performance model would allow us to predict the performance of benchmarks on machines without running them, reduce the size of a benchmark suite, make quantitative comparisons between the characteristics of systems or programs, and predict the effect of changes to a system design or workload. A unique property of the models constructed here is that they make no a priori association between the parameters and the components of the benchmarks and machines; instead they are designed to produce minimal prediction error. Methods of linear statistical analysis show, for real benchmark data, that 1-parameter linear models provide such a crude performance characterization that they may be undesirable. This crudeness of characterization is responsible for anomalies in single-number performance comparisons, which have hitherto been attributed to improper measurement or poor choice of benchmarks. Linear performance models with k parameters provide superior characterizations for increasing k. It is unclear what value of k is necessary for a generally applicable model. Benchmarks and machines are classified such that the timing data for each class is accurately reconstructed by a simple linear expression. The classification of the machines largely corresponds to our intuitions about families of architectures; the classification of the benchmarks is unintuitive, suggesting that we understand benchmarking less than we realize.