Transcript 200905190218542

Predictive Design Space
Exploration Using Genetically
Programmed Response Surfaces
Henry Cook
Kevin Skadron
Department of Electrical Engineering and
Computer Science
University of California, Berkeley
Department of Computer Science
University of Virginia
[email protected]
[email protected]
Designs Are Growing More
Complex

More transistors = more complex designs




Superscalar, out-of-order execution
Chip multiprocessors, systems-on-a-chip
Heterogeneity, shared memory, interconnects…
Many interrelated design variables with emergent
interactions

Unclear whether analytic models can be
constructed based on a priori understanding
How can we find the best
design?
Detailed, cycle-accurate simulations
 Testing every option is time consuming


1 min. x 1 billion simulations = too long!
Even search requires too many
simulations
 Solution: Predict which designs are best
based on a small data sample

Why not heuristic search?

Every step of search requires at least one
full simulation


How many steps?
Predicting based on a predetermined
sample becomes increasingly efficient as
space grows
Assuming predictions are accurate
 Assuming sample is small enough

How can we address
complexity?


We need a tool to predict global performance
based on a data sample
Many techniques might do this, but we want to
use one that…




Is more accurate when using small samples
Finds the true optimal solutions
Gives the architect more insight
Not just ‘what’ the best answer is,
but also ‘why’ it is the best
How can we make
predictions?

Build a ‘response
surface’



A function that relates
design choices to a
performance measure
Predicts performance for
designs we did not ever
simulate
Must have high accuracy
to be useful
A simple response surface
Linear Regression:
A simple response surface
Linear Regression:
A simple response surface
Linear Regression:
A simple response surface
Non-linear models are more precise:
How to use response surfaces
The true performance data:
How to use response surfaces
Step 1: Run simulations to make a sample
How to use response surfaces
Step 2: Build the response surface
How to use response surfaces
Step 3: Predict which designs are optimal
How can we build the
surface?
Linear/polynomial regression
 Artificial neural networks
 Genetic Programming

Automated
 Robust
 Insightful

Genetic Programming


Creates non-linear, polynomial functions which
match sample data
Previous uses




Calcination of cement
Stress fractures in steel
Branch prediction strategy
Evolutionary algorithm


Natural selection
Survival of the fittest
Evolution and reproduction
Evaluate fitness
Remove lowest quality
of new individuals
individuals
Recombine best
individuals
Result: Explicit response surface functions which best match data
Evolution and reproduction
Expression trees define the structure of
the response surface equation
 Tuning parameters provide best possible
fit to collected data
 Candidates are evaluated based on
distance of predictions from sample
after tuning

Evolution and reproduction
Combine
Proving the GP technique

Took simulation data from previous studies
 Designs are realistic but (comparatively) simple

Ipek et. al (ASPLOS-XII)



12 design choices, 20K+ possible designs
Predicted IPC and cache performance of 11 applications
Lee and Brooks (ASPLOS-XII)


13 design choices, 1 billion+ possible designs
Predicted power and BIPS of 7 applications
How good are the predictions?

0.1% of possible designs

Branch prediction and L2 cache miss rate
• <1% mean error and <2% s.d.

Instructions per cycle
• 2.8-4.9% mean error, 2.2-3.4% s.d.

0.000002% of possible designs

Billions of instructions per second
• 1.1-6.1% mean, 2.3-9.9% s.d.

Power (W)
• 3.5-6.2% mean, 3.4-5.7% s.d.
How good are the predictions?
CDFs of prediction accuracy of BIPS/IPC
How good are the predictions?

Localized accuracy of IPC for Ipek
Can we find optimal designs?

Surface allows us to solve for the best values for
some variables analytically

Other variables have insignificant impact

When checked by exhaustive search, for most
benchmarks 100% of the optimal designs had the
analytically determined values

Worst design with those values still had
performance that was 97% of optimal
How does the technique
help architects?

Saves time




Creates response function automatically
Only need to simulate predetermined sample points
High accuracy means confidence in predictions
Provides insight


Which design choices are important
What the correct choices are
Limitations

Time to construct response surface via GPRS rather
than with ANNs

Hours rather than minutes on this space
• Still just an up front cost on the order of a single simulation


Feedback is an explicit, analytic expression
How to determine quality without exhaustive search?

Cross validation
Questions?
Thanks to John Lach, Paul Reynolds, Sally McKee, David
Brooks, Karan Singh, Benjamin Lee