Memory-level parallelism aware fetch policies for simultaneous multithreading processors

ABSTRACT

A thread executing on a simultaneous multithreading (SMT) processor that experiences a long-latency load will eventually stall while holding execution resources. Existing long-latency load aware SMT fetch policies limit the amount of resources allocated by a stalled thread by identifying long-latency loads and preventing the thread from fetching more instructions—and in some implementations, instructions beyond the long-latency load are flushed to release allocated resources.

This article proposes an SMT fetch policy that takes into account the available memory-level parallelism (MLP) in a thread. The key idea proposed in this article is that in case of an isolated long-latency load (i.e., there is no MLP), the thread should be prevented from allocating additional resources. However, in case multiple independent long-latency loads overlap (i.e., there is MLP), the thread should allocate as many resources as needed in order to fully expose the available MLP. MLP-aware fetch policies achieve better performance for MLP-intensive threads on SMT processors, leading to higher overall system throughput and shorter average turnaround time than previously proposed fetch policies.

REFERENCES

• 1: Anant Agarwal , John Kubiatowicz , David Kranz , Beng-Hong Lim , Donald Yeung , Godfrey D'Souza , Mike Parkin, Sparcle: An Evolutionary Processor Design for Large-Scale Multiprocessors, IEEE Micro, v.13 n.3, p.48-61, May 1993 [doi>10.1109/40.216748]
• 2: Anderson, D. W., Sparacio, F. J., and Tomasulo, R. M. 1967. The IBM system/360 model 91: machine philosophy and instruction-handling. IBM J. Res. Dev. 11, 1, 8--24.
• 3: Francisco J. Cazorla , Alex Ramirez , Mateo Valero , Enrique Fernandez, Optimising long-latency-load-aware fetch policies for SMT processors, International Journal of High Performance Computing and Networking, v.2 n.1, p.45-54, February 2004 [doi>10.1504/IJHPCN.2004.009267]
• 4: 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]
• 5: 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
• 6: Yuan Chou , Brian Fahs , Santosh Abraham, Microarchitecture Optimizations for Exploiting Memory-Level Parallelism, Proceedings of the 31st annual international symposium on Computer architecture, p.76, June 19-23, 2004, München, Germany
• 7: Jamison D. Collins , Hong Wang , Dean M. Tullsen , Christopher Hughes , Yong-Fong Lee , Dan Lavery , John P. Shen, Speculative precomputation: long-range prefetching of delinquent loads, Proceedings of the 28th annual international symposium on Computer architecture, p.14-25, June 30-July 04, 2001, Göteborg, Sweden
• 8: Adrián Cristal , Oliverio J. Santana , Mateo Valero , José F. Martínez, Toward kilo-instruction processors, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.4, p.389-417, December 2004 [doi>10.1145/1044823.1044825]
• 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: Stijn Everman , Lieven Eeckhout, A Memory-Level Parallelism Aware Fetch Policy for SMT Processors, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.240-249, February 10-14, 2007 [doi>10.1109/HPCA.2007.346201]
• 11: Stijn Eyerman , Lieven Eeckhout, System-Level Performance Metrics for Multiprogram Workloads, IEEE Micro, v.28 n.3, p.42-53, May 2008 [doi>10.1109/MM.2008.44]
• 12: Glew, A. 1998. MLP yes! ILP no! In Proceedings of the Architectural Support for Programming Languages and Operating Systems Wild and Crazy Idea Session.
• 13: John, L. K. 2006. Aggregating performance metrics over a benchmark suite. In Performance Evaluation and Benchmarking, L. K. John and L. Eeckhout Eds. CRC Press, Boca Raton, FL, 47--58.
• 14: Karkhanis, T. and Smith, J. E. 2002. A day in the life of a data cache miss. In Proceedings of the 2nd Annual Workshop on Memory Performance Issues (WMPI'02). ACM, New York.
• 15: Tejas S. Karkhanis , James E. Smith, A First-Order Superscalar Processor Model, Proceedings of the 31st annual international symposium on Computer architecture, p.338, June 19-23, 2004, München, Germany
• 16: E. J. McLellan , D. A. Webb, The Alpha 21264 Microprocessor Architecture, Proceedings of the International Conference on Computer Design, p.90, October 05-05, 1998
• 17: Claude Limousin , Julien Sebot , Alexis Vartanian , Nathalie Drach-Temam, Improving 3D geometry transformations on a simultaneous multithreaded SIMD processor, Proceedings of the 15th international conference on Supercomputing, p.236-245, June 2001, Sorrento, Italy [doi>10.1145/377792.377839]
• 18: Chi-Keung Luk, Tolerating memory latency through software-controlled pre-execution in simultaneous multithreading processors, Proceedings of the 28th annual international symposium on Computer architecture, p.40-51, June 30-July 04, 2001, Göteborg, Sweden
• 19: Luo, K., Gummaraju, J., and Franklin, M. 2001. Balancing throughput and fairness in SMT processors. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS'01). IEEE, Los Alamitos, CA, 164--171.
• 20: Onur Mutlu , Hyesoon Kim , Yale N. Patt, Techniques for Efficient Processing in Runahead Execution Engines, Proceedings of the 32nd annual international symposium on Computer Architecture, p.370-381, June 04-08, 2005
• 21: Onur Mutlu , Jared Stark , Chris Wilkerson , Yale N. Patt, Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-Order Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.129, February 08-12, 2003
• 22: Vijay S. Pai , Sarita Adve, Code transformations to improve memory parallelism, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.147-155, November 16-18, 1999, Haifa, Israel
• 23: Erez Perelman , Greg Hamerly , Brad Calder, Picking Statistically Valid and Early Simulation Points, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.244, September 27-October 01, 2003
• 24: Moinuddin K. Qureshi , Daniel N. Lynch , Onur Mutlu , Yale N. Patt, A Case for MLP-Aware Cache Replacement, Proceedings of the 33rd annual international symposium on Computer Architecture, p.167-178, June 17-21, 2006
• 25: 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
• 26: Ramirez, T., Pajuelo, A., Santana, O. J., and Valero, M. 2008. Runahead threads to improve SMT performance. In Proceedings of the 14th International Symposium on High-Performance Computer Architecture (HPCA'08). IEEE, Los Alamitos, CA, 149--158.
• 27: 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
• 28: Timothy Sherwood , Suleyman Sair , Brad Calder, Predictor-directed stream buffers, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.42-53, December 2000, Monterey, California, United States [doi>10.1145/360128.360135]
• 29: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 30: 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
• 31: Radhika Thekkath , Susan J. Eggers, The effectiveness of multiple hardware contexts, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.328-337, October 05-07, 1994, San Jose, California, United States
• 32: Nathan Tuck , Dean M. Tullsen, Multithreaded Value Prediction, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.5-15, February 12-16, 2005 [doi>10.1109/HPCA.2005.22]
• 33: Nathan Tuck , Dean M. Tullsen, Initial Observations of the Simultaneous Multithreading Pentium 4 Processor, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.26, September 27-October 01, 2003
• 34: Tullsen, D. 1996. Simulation and modeling of a simultaneous multithreading processor. In Proceedings of the 22nd Annual Computer Measurement Group Conference. Curran Associates, Red Hook, NY.
• 35: 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
• 36: 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
• 37: 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
• 38: Eric Tune , Rakesh Kumar , Dean M. Tullsen , Brad Calder, Balanced Multithreading: Increasing Throughput via a Low Cost Multithreading Hierarchy, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.183-194, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.8]
• 39: Huiyang Zhou , Thomas M. Conte, Enhancing memory level parallelism via recovery-free value prediction, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782859]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Experimentation, Performance

Keywords:
Fetch Policy, Memory-Level Parallelism (MLP), Simultaneous Multithreading (SMT)