Characterizing and predicting value degree of use

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 characterization 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 effects 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.

REFERENCES

• 1: D. Burger and T. Austin. The SimpleScalar tool set, version 2.0. Technical Report CS-TR-97-1342, University of Wisconsin-Madison, June 1997.
• 2: J. Adam Butts , Guri Sohi, Dynamic dead-instruction detection and elimination, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 3: José-Lorenzo Cruz , Antonio González , Mateo Valero , Nigel P. Topham, Multiple-banked register file architectures, Proceedings of the 27th annual international symposium on Computer architecture, p.316-325, June 2000, Vancouver, British Columbia, Canada
• 4: Lieven Eeckhout , Koenraad De Bosschere, Hybrid Analytical-Statistical Modeling for Efficiently Exploring Architecture and Workload Design Spaces, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.25, September 08-12, 2001
• 5: Manoj Franklin , Gurindar S. Sohi, Register traffic analysis for streamlining inter-operation communication in fine-grain parallel processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.236-245, December 01-04, 1992, Portland, Oregon, United States
• 6: Ho-Seop Kim , James E. Smith, An instruction set and microarchitecture for instruction level distributed processing, Proceedings of the 29th annual international symposium on Computer architecture, p.71, May 25-29, 2002, Anchorage, Alaska
• 7: Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
• 8: J. Phillips , S. Vassiliadis, High-Performance 3-1 Interlock Collapsing ALU's, IEEE Transactions on Computers, v.43 n.3, p.257-268, March 1994 [doi>10.1109/12.272427]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Value of information

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Design, Performance