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
(please do not send requests to me, thanks!). 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.