Characterizing and Predicting Value Degree of Use
Authors:
J. Adam Butts and Gurindar S. Sohi
Computer Science Department
University of Wisconsin-Madison
Abstract:
A value's degree of use--the number of dynamic uses of that value--provides
the most essential information needed to optimize its communication. We
present simulation results demonstrating the properties of degree of use
of values, including their predictability: most static instructions
generate values with few degrees of use and these exhibit temporal
locality. We use these results to guide the design of a degree of use
predictor. The development and detailed design of this predictor is the
focus of this paper. Our predictor leverages future control flow
information (e.g., branch predictions) to select among different possible
degrees of use. We study the effect of several optimizations and
variations in the predictor's algorithms to tune the predictor for maximum
performance. The resulting predictor generates correct degree of use
predictions for over 92% of all dynamic values and has a misprediction
rate below 2.5%. Such a predictor has a wide range of potential
applications in optimizing value communication.
Web Site
http://www.cs.wisc.edu/~mscalar