Storageless value prediction using prior register values

ABSTRACT

This paper presents a technique called register value prediction (RVP) which uses a type of locality called register-value reuse. By predicting that an instruction will produce the value that is already stored in the destination register, we eliminate the need for large value buffers to enable value prediction. Even without the large buffers, register-value prediction can be made as or more effective than last-value prediction, particularly with the aid of compiler management of values in the register file.Both static and dynamic register value prediction techniques are demonstrated to exploit register-value reuse, the former requiring minimal instruction set architecture changes and the latter requiring a set of small confidence counters. We show an average gain of 12% with dynamic RVP and moderate compiler assistance on a next generation processor, and 15% on a 16-wide processor.

REFERENCES

• 1: Brad Calder , Peter Feller , Alan Eustace, Value profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.259-269, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 2: G, Chaitin, M. Auslander, A. Chandra, J, Cocke, M. Hopkins, and P. Markstein. Register allocation via coloring. Programming Lan+ guages, 6(1 ):47-57, 1981.
• 3: Chao-Ying Fu , Matthew D. Jennings , Sergei Y. Larin , Thomas M. Conte, Value speculation scheduling for high performance processors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.262-271, October 02-07, 1998, San Jose, California, United States
• 4: E Gabbay and A. Mendelson, Speculative execution based on value prediction. EE Department TR 1080, Technion - Israel Institue of Technology, Nov. 1996.
• 5: Freddy Gabbay , Avi Mendelson, Can program profiling support value prediction?, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.270-280, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 6: Stephen Jourdan , Ronny Ronen , Michael Bekerman , Bishara Shomar , Adi Yoaz, A novel renaming scheme to exploit value temporal locality through physical register reuse and unification, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.216-225, November 1998, Dallas, Texas, United States
• 7: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France
• 8: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• 9: Jack L. Lo , Sujay S. Parekh , Susan J. Eggers , Henry M. Levy , Dean M. Tullisen, Software-Directed Register Deallocation for Simultaneous Multithreaded Processors, IEEE Transactions on Parallel and Distributed Systems, v.10 n.9, p.922-933, September 1999 [doi>10.1109/71.798316]
• 10: Milo M. Martin , Amir Roth , Charles N. Fischer, Exploiting dead value information, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.125-135, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 11: Andreas Moshovos , Gurindar S. Sohi, Streamlining inter-operation memory communication via data dependence prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.235-245, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 12: G. Reinman, B. Calder, D. Tullsen+ G. Tyson, and T. Austin. Profile guided load marking for memory renaming. Technical Report Technical Report UCSD+CS98-593, University of California, San Diego, July ! 998.
• 13: Yiannakis Sazeides , James E. Smith, The predictability of data values, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.248-258, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 14: D. Tullsen. Simulation and modeling of a simultaneous multithreading processor, in 22nd Annual Computer Measurement Group Conference, Dec. 1996.
• 15: D. TulIsen and B. Calder. Computing along the critical path. Technical report, University of California, San Diego, Oct. 1998.
• 16: Gary S. Tyson , Todd M. Austin, Improving the accuracy and performance of memory communication through renaming, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.218-227, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 17: Kai Wang , Manoj Franklin, Highly accurate data value prediction using hybrid predictors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 01-03, 1997, Research Triangle Park, North Carolina, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Design, Measurement, Performance