Exploiting Value Locality in Physical Register Files

ABSTRACT

The physical register file is an important component of adynamically-scheduled processor. Increasing the amount of parallelismplaces increasing demands on the physical register file,calling for alternative file organization and management strategies.This paper considers the use of value locality to optimize theoperation of physical register files.We present empirical data showing that: (i) the value producedby an instruction is often the same as a value produced by anotherrecently executed instruction, resulting in multiple physical registerscontaining the same value, and (ii) the values 0 and 1 accountfor a considerable fraction of the values written to and read fromphysical registers. The paper then presents three schemes to exploitthe above observations.The first scheme extends a previously-proposed scheme to useonly a single physical register for each unique value. The secondscheme is a special case for the values 0 and 1. By restricting optimizationto these values, the second scheme eliminates many of thedrawbacks of the first scheme. The third scheme further improveson the second, resulting in an optimization that reduces physicalregister requirements with simple micro-architectural extensions.A performance evaluation of the three schemes is also presented.

REFERENCES

• 1: Rajeev Balasubramonian , Sandhya Dwarkadas , David H. Albonesi, Reducing the complexity of the register file in dynamic superscalar processors, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 2: Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, The anatomy of the register file in a multiscalar processor, Proceedings of the 27th annual international symposium on Microarchitecture, p.181-190, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192750]
• 3: [3] D. C. Burger and T. M. Austin. The Simplescalar tool set, version 2.0. Technical Report CS-TR-1997-1342, University of Wisconsin, Madison, 1997.
• 4: Robert P. Colwell , Robert P. Nix , John J. O'Donnell , David B. Papworth , Paul K. Rodman, A VLIW architecture for a trace scheduling compiler, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.180-192, October 1987, Palo Alto, California, United States
• 5: 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
• 6: Keith I. Farkas , Paul Chow , Norman P. Jouppi , Zvonko Vranesic, The multicluster architecture: reducing cycle time through partitioning, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.149-159, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 7: Keith I. Farkas , Paul Chow , Norman P. Jouppi, Register File Design Considerations in Dynamically Scheduled Processors, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.40, February 03-07, 1996
• 8: A. González , J. González , M. Valero, Virtual-Physical Registers, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.175, January 31-February 04, 1998
• 9: 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
• 10: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465 ]
• 11: 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
• 12: Teresa Monreal , Antonio González , Mateo Valero , José González , Victor Viñals, Delaying physical register allocation through virtual-physical registers, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.186-192, November 16-18, 1999, Haifa, Israel
• 13: 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
• 14: Matthew Postiff , David Greene , Steven Raasch , Trevor Mudge, Integrating superscalar processor components to implement register caching, Proceedings of the 15th international conference on Supercomputing, p.348-357, June 2001, Sorrento, Italy [doi>10.1145/377792.377859]
• 15: [15] S. Rixner, W. Dally, B. Khailany, P. Mattson, U. Kapasi, and J. Owens. Register organization for media processing. In Proc. of the 6th Intl. Symp. on High-Performance Computer Architecture, pages 375-386, 1999.
• 16: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 17: Avinash Sodani , Gurindar S. Sohi, An empirical analysis of instruction repetition, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.35-45, October 02-07, 1998, San Jose, California, United States
• 18: J. A. Swensen , Y. N. Patt, Hierarchical registers for scientific computers, Proceedings of the 2nd international conference on Supercomputing, p.346-354, June 1988, St. Malo, France [doi>10.1145/55364.55398]
• 19: Steven Wallace , Nader Bagherzadeh, A Scalable Register File Architecture for Dynamically Scheduled Processors, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.179, October 20-23, 1996
• 20: Jun Yang , Youtao Zhang , Rajiv Gupta, Frequent value compression in data caches, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.258-265, December 2000, Monterey, California, United States [doi>10.1145/360128.360154]
• 21: Robert Yung , Neil C. Wilhelm, Caching processor general registers, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.307-312, October 02-04, 1995
• 22: Huiyang Zhou , Jill Flanagan , Thomas M. Conte, Detecting global stride locality in value streams, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design

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

General Terms:
Design, Performance