An adaptive resource partitioning algorithm for SMT processors

ABSTRACT

Simultaneous Multithreading (SMT) increases processor throughput by allowing the parallel execution of several threads. However, fully sharing processor resources may cause resource monopolization by a single thread or other misallocations, resulting in overall performance degradation. Static resource partitioning techniques have been suggested, but are not as effective as dynamically controlling the resource usage of each thread since program behavior does change during its execution.

In this paper, we propose an Adaptive Resource Partitioning Algorithm (ARPA) that dynamically assigns resources to threads according to thread behavior changes. ARPA analyzes the resource usage efficiency of each thread in a time period and assigns more resources to threads which can use them in a more efficient way. The purpose of ARPA is to improve the efficiency of resource utilization, thereby improving overall instruction throughput. Our simulation results on a set of 42 multiprogramming workloads show that ARPA outperforms the traditional fetch policy ICOUNT by 55.8% with regard to overall instruction throughput and achieves a 33.8% improvement over Static Partitioning. It also outperforms the current best dynamic resource allocation technique, Hill-climbing, by 5.7%. Considering fairness accorded to each thread, ARPA attains 43.6%, 18.5% and 9.2% improvements over ICOUNT, Static Partitioning and Hill-climbing, respectively, using a common fairness metric.

REFERENCES

• 1: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 2: D. C. Burger and T. M. Austin, "The SimpleScalar Tool Set, Version 2.0," Technical Report CS-TR-1997-1342, University of Wisconsin, Madison, June 1997.
• 3: Hiroaki Hirata , Kozo Kimura , Satoshi Nagamine , Yoshiyuki Mochizuki , Akio Nishimura , Yoshimori Nakase , Teiji Nishizawa, An elementary processor architecture with simultaneous instruction issuing from multiple threads, Proceedings of the 19th annual international symposium on Computer architecture, p.136-145, May 19-21, 1992, Queensland, Australia
• 4: Wayne Yamamoto , Mario Nemirovsky, Increasing superscalar performance through multistreaming, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.49-58, June 27-29, 1995, Limassol, Cyprus
• 5: Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm , Dean M. Tullsen, Simultaneous Multithreading: A Platform for Next-Generation Processors, IEEE Micro, v.17 n.5, p.12-19, September 1997 [doi>10.1109/40.621209]
• 6: F. J. Cazorla, E. Fernández, A. Ramírez, and M. Valero, "Improving Memory Latency Aware Fetch Policies for SMT Processors," Proc. Fifth Int'l Symp. High Performance Computing, pp. 70--85, Oct. 2003.
• 7: 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]
• 8: Seungryul Choi , Donald Yeung, Learning-Based SMT Processor Resource Distribution via Hill-Climbing, Proceedings of the 33rd annual international symposium on Computer Architecture, p.239-251, June 17-21, 2006
• 9: 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
• 10: K. Luo, J. Gummaraju, and M. Franklin, "Balancing Throughout and Fairness in SMT Processors," Proc. Int'l Symp. Performance Analysis of Systems and Software, pp. 164--171, Nov. 2001.
• 11: D. T. Marr, F. Binns, D. L. Hill, G. Hinton, D. A. Koufaty, J. A. Miller, and M. Upton, "Hyper-Threading Technology Architecture and Microarchitecture," Intel Technology J., vol. 6, no. 1, pp. 4--15, Feb. 2002.
• 12: 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
• 13: S. Sair and M. Charney, "Memory Behavior of the SPEC2000 Benchmark Suite," Technical Report, IBM T.J. Watson Research Center, 2000.
• 14: Joseph Sharkey , Deniz Balkan , Dmitry Ponomarev, Adaptive reorder buffers for SMT processors, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152192]
• 15: Allan Snavely , Dean M. Tullsen , Geoff Voelker, Symbiotic jobscheduling with priorities for a simultaneous multithreading processor, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 16: 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
• 17: 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
• 18: 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
• 19: H. Wang, Y. Guo, I. Koren, and C. M. Krishna, "Compiler-Based Adaptive Fetch Throttling for Energy Efficiency," Proc. Int'l Symp. Performance Analysis of Systems and Software, pp. 112--119, Mar. 2006.
• 20: Seong-Won Lee , Jean-Luc Gaudiot, Throttling-Based Resource Management in High Performance Multithreaded Architectures, IEEE Transactions on Computers, v.55 n.9, p.1142-1152, September 2006 [doi>10.1109/TC.2006.154]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

General Terms:
Algorithms, Design, Performance

Keywords:
resource partitioning, simultaneous multithreading