Adaptive reorder buffers for SMT processors

ABSTRACT

In SMT processors, the complex interplay between private and shared datapath resources needs to be considered in order to realize the full performance potential. In this paper, we show that blindly increasing the size of the per-thread reorder buffers to provide a larger number of in-flight instructions does not result in the expected performance gains but, quite in contrast, degrades the instruction throughput for virtually all multithreaded workloads. The reason for this performance loss is the excessive pressure on the shared datapath resources, especially the instruction scheduling logic. We propose intelligent mechanisms for dynamically adapting the number of reorder buffer entries allocated to each thread in an effort to avoid such allocations if they detrimentally impact the scheduler. We achieve this goal through categorizing the program execution into issue-bound and commit-bound phases and only performing the buffer allocations to the threads operating in commit-bound phases. Our adaptive technique achieves improvements of 21% in instruction throughput and 10% in the fairness metric compared to the best performing baseline configuration with static ROBs.

REFERENCES

• 1: D. Burger, T. Austin. "The SimpleScalar tool set: Version 2.0." Tech. Report, Dept. of CS, Univ. of Wisconsin-Madison, June 1997 and documentation for all Simplescalar releases.
• 2: Alper Buyuktosunoglu , David Albonesi , Stanley Schuster , David Brooks , Pradip Bose , Peter Cook, A circuit level implementation of an adaptive issue queue for power-aware microprocessors, Proceedings of the 11th Great Lakes symposium on VLSI, p.73-78, March 2001, West Lafayette, Indiana, United States [doi>10.1145/368122.368807]
• 3: Francisco J. Cazorla , Alex Ramirez , Mateo Valero , Enrique Fernandez, Dynamically Controlled Resource Allocation in SMT Processors, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.171-182, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.17]
• 4: F. Cazorla, et al. "Improving Memory Latency Aware Fetch Policies for SMT Processors." in Proc International Symposium on High Performance Computing, 2003.
• 5: Ali El-Moursy , David H. Albonesi, Front-End Policies for Improved Issue Efficiency in SMT Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.31, February 08-12, 2003
• 6: John L. Henning, SPEC CPU2000: Measuring CPU Performance in the New Millennium, Computer, v.33 n.7, p.28-35, July 2000 [doi>10.1109/2.869367]
• 7: K. Luo, et al. "Balancing Throughput and Fairness in SMT Processors." in Proc ISPASS, 2001.
• 8: Dmitry Ponomarev , Gurhan Kucuk , Kanad Ghose, Reducing power requirements of instruction scheduling through dynamic allocation of multiple datapath resources, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 9: Steven E. Raasch , Steven K. Reinhardt, The Impact of Resource Partitioning on SMT Processors, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.15, September 27-October 01, 2003
• 10: Behnam Robatmili , Nasser Yazdani , Somayeh Sardashti , Mehrdad Nourani, Thread-Sensitive Instruction Issue for SMT Processors, IEEE Computer Architecture Letters, v.3 n.1, p.5, January 2004 [doi>10.1109/L-CA.2004.9]
• 11: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 12: Dean M. Tullsen , Jeffery A. Brown, Handling long-latency loads in a simultaneous multithreading processor, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 13: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 14: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 15: Gautham K. Dorai , Donald Yeung, Transparent Threads: Resource Sharing in SMT Processors for High Single-Thread Performance, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.30, September 22-25, 2002
• 16: D. Marr, et al, "Hyperthreading Technology Architecture and Microarchitecture", Intel Tech. Journal, vol. 6, No.1, Feb. 2002.
• 17: 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
• 18: Smruti R. Sarangi , Wei Liu, Josep Torrellas , Yuanyuan Zhou, ReSlice: Selective Re-Execution of Long-Retired Misspeculated Instructions Using Forward Slicing, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.257-270, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.28]
• 19: 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]
• 20: Jared Stark , Mary D. Brown , Yale N. Patt, On pipelining dynamic instruction scheduling logic, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.57-66, December 2000, Monterey, California, United States [doi>10.1145/360128.360136]
• 21: 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
• 22: J. Sharkey, "M-Sim: A Flexible, Multi-threaded Simulation Environment." Tech. Report CS-TR-05-DP1, Department of Computer Science, SUNY Binghamton, 2005. http://www.cs.binghamton.edu/~jsharke/m-sim

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
reorder buffer, simultaneous multithreading