SPARTAN: speculative avoidance of register allocations to transient values for performance and energy efficiency

ABSTRACT

High-performance microprocessors use large, heavily-ported physical register files (RFs) to increase the instruction throughput. The high complexity and power dissipation of such RFs mainly stem from the need to maintain each and every result for a large number of cycles after the result generation. We observed that a significant fraction (about 45%) of the result values are never read from the register file and are not required to recover from branch mispredictions. In this paper, we propose SPARTAN - a set of micro-architectural extensions that predicts such transient values and in many cases completely avoids physical register allocations to them. We show that the transient values can be predicted as such with more than 97% accuracy on the average across simulated SPEC 2000 benchmarks. We evaluate the performance of SPARTAN on a variety of configurations and show that significant improvements in performance and energy-efficiency can be realized. Furthermore, we directly compare SPARTAN against a number of previously proposed schemes for register optimizations and show that our technique significantly outperforms all those schemes.

REFERENCES

• 1: Haitham Akkary , Ravi Rajwar , Srikanth T. Srinivasan, Checkpoint Processing and Recovery: Towards Scalable Large Instruction Window Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.423, December 03-05, 2003
• 2: A. Azevedo , I. Issenin , R. Cornea , R. Gupta , N. Dutt , A. Veidenbaum , A. Nicolau, Profile-Based Dynamic Voltage Scheduling Using Program Checkpoints, Proceedings of the conference on Design, automation and test in Europe, p.168, March 04-08, 2002
• 3: Saisanthosh Balakrishnan , Gurindar S. Sohi, Exploiting Value Locality in Physical Register Files, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.265, December 03-05, 2003
• 4: 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
• 5: Eric Borch , Srilatha Manne , Joel Emer , Eric Tune, Loose Loops Sink Chips, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.299, February 02-06, 2002
• 6: Bracy, A., et.al., "Exploiting Data-Flow Mini-Graphs in Superscalar Processors", in the Proceedings of MICRO-37, 2004.
• 7: Burger, D. and Austin, T. M., "The SimpleScalar tool set: Version 2.0", Tech. Report, Dept. of CS, Univ. of Wisconsin-Madison, June 1997.
• 8: J. Adam Butts , Gurindar S. Sohi, Use-Based Register Caching with Decoupled Indexing, Proceedings of the 31st annual international symposium on Computer architecture, p.302, June 19-23, 2004, München, Germany
• 9: J. Adam Butts , Gurindar S. Sohi, Characterizing and predicting value degree of use, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 10: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 11: 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
• 12: Oguz Ergin , Deniz Balkan , Dmitry Ponomarev , Kanad Ghose, Increasing Processor Performance Through Early Register Release, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.480-487, October 11-13, 2004
• 13: Oguz Ergin , Deniz Balkan , Kanad Ghose , Dmitry Ponomarev, Register Packing: Exploiting Narrow-Width Operands for Reducing Register File Pressure, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.304-315, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.29]
• 14: 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
• 15: 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
• 16: Gonzalez Gonzalez , Adrian Cristal , Daniel Ortega , Alexander Veidenbaum , Mateo Valero, A Content Aware Integer Register File Organization, Proceedings of the 31st annual international symposium on Computer architecture, p.314, June 19-23, 2004, München, Germany
• 17: S. Gopal , T. Vijaykumar , J. Smith , G. Sohi, Speculative Versioning Cache, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.195, January 31-February 04, 1998
• 18: Hinton, G., et.al., "The Microarchitecture of the Pentium 4 Processor", Intel Technology Journal, Q1, 2001.
• 19: 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
• 20: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465 ]
• 21: Ilhyun Kim , Mikko H. Lipasti, Understanding Scheduling Replay Schemes, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.198, February 14-18, 2004 [doi>10.1109/HPCA.2004.10011]
• 22: Nam Sung Kim , Trevor Mudge, Reducing register ports using delayed write-back queues and operand pre-fetch, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782839]
• 23: Masaaki Kondo , Hiroshi Nakamura, A Small, Fast and Low-Power Register File by Bit-Partitioning, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.40-49, February 12-16, 2005 [doi>10.1109/HPCA.2005.3]
• 24: Mikko H. Lipasti , Brian R. Mestan , Erika Gunadi, Physical Register Inlining, Proceedings of the 31st annual international symposium on Computer architecture, p.325, June 19-23, 2004, München, Germany
• 25: Luis A. Lozano , Guang R. Gao, Exploiting short-lived variables in superscalar processors, Proceedings of the 28th annual international symposium on Microarchitecture, p.292-302, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 26: 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
• 27: José F. Martínez , Jose Renau , Michael C. Huang , Milos Prvulovic , Josep Torrellas, Cherry: checkpointed early resource recycling in out-of-order microprocessors, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 28: 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
• 29: Teresa Monreal , Victor Vinals , Jose Gonzalez , Antonio Gonzalez , Mateo Valero, Late Allocation and Early Release of Physical Registers, IEEE Transactions on Computers, v.53 n.10, p.1244-1259, October 2004 [doi>10.1109/TC.2004.79]
• 30: Teresa Monreal , Víctor Viñals , Antonio González , Mateo Valero, Hardware Schemes for Early Register Release, Proceedings of the 2002 International Conference on Parallel Processing (ICPP'02), p.5, August 18-21, 2002
• 31: Enric Morancho , José María Llabería , Àngel Olivé, Recovery Mechanism for Latency Misprediction, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.118, September 08-12, 2001
• 32: Mayan Moudgill , Keshav Pingali , Stamatis Vassiliadis, Register renaming and dynamic speculation: an alternative approach, Proceedings of the 26th annual international symposium on Microarchitecture, p.202-213, December 01-03, 1993, Austin, Texas, United States
• 33: Il Park , Michael D. Powell , T. N. Vijaykumar, Reducing register ports for higher speed and lower energy, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 34: Vlad Petric , Tingting Sha , Amir Roth, RENO: A Rename-Based Instruction Optimizer, Proceedings of the 32nd annual international symposium on Computer Architecture, p.98-109, June 04-08, 2005
• 35: Dmitry Ponomarev , Gurhan Kucuk , Oguz Ergin , Kanad Ghose, Reducing Datapath Energy through the Isolation of Short-Lived Operands, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.258, September 27-October 01, 2003
• 36: Amir Roth , Gurindar S. Sohi, Register integration: a simple and efficient implementation of squash reuse, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.223-234, December 2000, Monterey, California, United States [doi>10.1145/360128.360151]
• 37: Peter G. Sassone , D. Scott Wills, Dynamic Strands: Collapsing Speculative Dependence Chains for Reducing Pipeline Communication, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.7-17, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.16]
• 38: Simha Sethumadhavan , Rajagopalan Desikan , Doug Burger , Charles R. Moore , Stephen W. Keckler, Scalable Hardware Memory Disambiguation for High ILP Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.399, December 03-05, 2003
• 39: James E. Smith , Andrew R. Pleszkun, Implementation of precise interrupts in pipelined processors, Proceedings of the 12th annual international symposium on Computer architecture, p.36-44, June 17-19, 1985, Boston, Massachusetts, United States
• 40: Srikanth T. Srinivasan , Ravi Rajwar , Haitham Akkary , Amit Gandhi , Mike Upton, Continual flow pipelines, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 41: L. Tran , N. Nelson , Fung Ngai , S. Dropsho , M. Huang, Dynamically reducing pressure on the physical register file through simple register sharing, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.78-87, March 10-12, 2004
• 42: Jessica H. Tseng , Krste Asanović, Banked multiported register files for high-frequency superscalar microprocessors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 43: 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
• 44: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460 ]
• 45: Yingmin Li , David Brooks , Zhigang Hu , Kevin Skadron, Performance, Energy, and Thermal Considerations for SMT and CMP Architectures, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.71-82, February 12-16, 2005 [doi>10.1109/HPCA.2005.25]
• 46: Adi Yoaz , Mattan Erez , Ronny Ronen , Stephan Jourdan, Speculation techniques for improving load related instruction scheduling, Proceedings of the 26th annual international symposium on Computer architecture, p.42-53, May 01-04, 1999, Atlanta, Georgia, United States
• 47: Meyrem Kyrman , Nevin Kyrman , Jose F. Martynez, Cherry-MP: Correctly Integrating Checkpointed Early Resource Recycling in Chip Multiprocessors, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.245-256, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.15]
• 48: Timothy M. Jones , Michael F. P. O'Boyle , Jaume Abella , Antonio Gonzalez , Oğuz Ergin, Compiler Directed Early Register Release, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.110-122, September 17-21, 2005 [doi>10.1109/PACT.2005.14]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Design, Performance

Keywords:
energy-efficiency, register files