SDI Seminar

Speaker: Joel Emer, DEC

Date: October 30, 1997

Where & When: WeH 8220, Noon

A Language for Describing Predictors and Its Use to
Automatically Synthesize Them
or
Guessing with Darwin's Help

Abstract

As processor architectures have increased their reliance on speculative execution to improve performance, the importance of accurate prediction of what to execute speculatively has increased. Furthermore, the types of values predicted have expanded from the ubiquitous branch and call/return targets to the prediction of indirect jump targets, cache ways and data values.

In general, the prediction process is one of identifying the current state of the system, and making a prediction for some as yet uncomputed value based on that state. Prediction accuracy is improved by learning what is a good prediction for that state using a feedback process at the time the predicted value is actually computed. While there have been a number of efforts to formally characterize this process, we have taken the approach of providing a simple algebraic-style notation that allows one to express this state identification and feedback process. This notation allows one to describe a wide variety of predictors in a uniform way. It also facilitates the use of an efficient search technique called genetic programming, which is loosely modeled on the natural evolutionary process, to explore the design space.

In this paper we describe our notation and the results of the application of genetic programming to the design of branch and indirect jump predictors.


Dr. Joel S. Emer is a Senior Consulting Engineer in Digital's Semiconductor Engineering Group. He holds a Ph.D. in Electrical Engineering from the University of Illinois, and M.S.E.E. and B.S.E.E. degrees from Purdue University. He is a 18 year Digital employee, where he has worked on processor performance analysis and performance modeling methodologies for a number of VAX and Alpha CPUs, as well as researched heterogeneous distributed systems and networked file systems. His current research interests include multithreaded processor organizations, techniques for increased instruction level paralellism, instruction and data cache organizations, branch prediction schemes and data prefetch strategies for future Alpha processors.