Meeting points: using thread criticality to adapt multicore hardware to parallel regions

ABSTRACT

We present a novel mechanism, called meeting point thread characterization, to dynamically detect critical threads in a parallel region. We define the critical thread the one with the longest completion time in the parallel region. Knowing the criticality of each thread has many potential applications. In this work, we propose two applications: thread delaying for multi-core systems and thread balancing for simultaneous multi-threaded (SMT) cores. Thread delaying saves energy consumptions by running the core containing the critical thread at maximum frequency while scaling down the frequency and voltage of the cores containing non-critical threads. Thread balancing improves overall performance by giving higher priority to the critical thread in the issue queue of an SMT core. Our experiments on a detailed microprocessor simulator with the Recognition, Mining, and Synthesis applications from Intel research laboratory reveal that thread delaying can achieve energy savings up to more than 40% with negligible performance loss. Thread balancing can improve performance from 1% to 20%.

REFERENCES

• 1: Saisanthosh Balakrishnan , Ravi Rajwar , Mike Upton , Konrad Lai, The Impact of Performance Asymmetry in Emerging Multicore Architectures, Proceedings of the 32nd annual international symposium on Computer Architecture, p.506-517, June 04-08, 2005
• 2: OpenMP Architecture Review Board. Openmp application program interface, 2005.
• 3: S. Y. Borkar. Platform 2015: Intel processor and platform evolution for the next decode. Intel White Paper, 2005
• 4: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, ACM SIGARCH Computer Architecture News, v.28 n.2, p.83-94, May 2000
• 5: T. D. Burd , R. W. Brodersen, Energy efficient CMOS microprocessor design, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.288, January 04-07, 1995
• 6: 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]
• 7: T. J. Chaney , C. E. Molnar, Anomalous Behavior of Synchronizer and Arbiter Circuits, IEEE Transactions on Computers, v.22 n.4, p.421-422, April 1973 [doi>10.1109/T-C.1973.223730]
• 8: P. Chaparro, J. Gonzalez, G. Magklis, Q. Cai, and A. Gonzalez. Understanding the termal implications of multicore architectures. IEEE Transactions on Parallel and Distributed Systems, 18(8), 2007.
• 9: Tiberiu Chelcea , Steven M. Nowick, Robust interfaces for mixed-timing systems with application to latency-insensitive protocols, Proceedings of the 38th conference on Design automation, p.21-26, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378256]
• 10: Intel Corporation. Computer intenstive, highly parallel application and uses. Intel Technology Journal, 9(2), 2005.
• 11: Intel Corporation. Intel's tera-scale research prepares for tens, hundreds of cores, 2006.
• 12: 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
• 13: S. Fischer. Technical overview of the 45nm next generation intel core microarchitecture (penryn), 2007.
• 14: T. Fischer, J. Desai, B. Doyle, S. Naffziger, and B. Patella. A 90-nm variable frequency clock system for a power-managed itanium architecture processor. IEEE Journal of Solid-State Circuits, 41, 2006.
• 15: S. Gochman, R. Ronen, I. Anati, A. Berkovits, T. Kurts, A. Naveh, A. Saeed, Z. Sperber, and R. Valentine. The intel pentium m processor: Microarchitecture and performance. Intel Technology Journal, 7(2), 2003.
• 16: P. Hazucha, T. Karnik, B.A. Bloechel, C. Parsons, D. Finan, and S. Borkar. Area-efficient linear regulator with ultra-fast load regulation. Solid-State Circuits, IEEE Journal of, 40, 2005.
• 17: H. Homayoun, K.F. Li, and S. Rafatirad. Thread scheduling based on low-quality instruction prediction for simultaneous multithreaded processors. IEEE-NEWCAS Conference, 2005.
• 18: Chenming Hu. Low-voltage cmos device scaling. Solid-State Circuits Conference, 1994.
• 19: Anoop Iyer , Diana Marculescu, Power and performance evaluation of globally asynchronous locally synchronous processors, ACM SIGARCH Computer Architecture News, v.30 n.2, May 2002
• 20: Rohit Jain , Christopher J. Hughes , Sarita V. Adve, Soft Real- Time Scheduling on Simultaneous Multithreaded Processors, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.134, December 03-05, 2002
• 21: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 22: Rakesh Kumar , Keith I. Farkas , Norman P. Jouppi , Parthasarathy Ranganathan , Dean M. Tullsen, Single-ISA Heterogeneous Multi-Core Architectures: The Potential for Processor Power Reduction, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.81, December 03-05, 2003
• 23: Rakesh Kumar , Dean M. Tullsen , Parthasarathy Ranganathan , Norman P. Jouppi , Keith I. Farkas, Single-ISA Heterogeneous Multi-Core Architectures for Multithreaded Workload Performance, Proceedings of the 31st annual international symposium on Computer architecture, p.64, June 19-23, 2004, München, Germany
• 24: Jian Li , Jose F. Martinez , Michael C. Huang, The Thrifty Barrier: Energy-Aware Synchronization in Shared-Memory Multiprocessors, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.14, February 14-18, 2004 [doi>10.1109/HPCA.2004.10018]
• 25: Chun Liu , Anand Sivasubramaniam , Mahmut Kandemir , Mary Jane Irwin, Exploiting Barriers to Optimize Power Consumption of CMPs, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.5.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.211]
• 26: Jacob R. Lorch , Alan Jay Smith, Improving dynamic voltage scaling algorithms with PACE, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.50-61, June 2001, Cambridge, Massachusetts, United States
• 27: Grigorios Magklis , Pedro Chaparro , José González , Antonio González, Independent front-end and back-end dynamic voltage scaling for a GALS microarchitecture, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany [doi>10.1145/1165573.1165586]
• 28: Grigorios Magklis , Jose Gonzalez , Antonio Gonzalez, Frontend Frequency-Voltage Adaptation for Optimal Energy-Delay^2, Proceedings of the IEEE International Conference on Computer Design, p.250-255, October 11-13, 2004
• 29: Pedro Marcuello , Antonio González , Jordi Tubella, Speculative multithreaded processors, Proceedings of the 12th international conference on Supercomputing, p.77-84, July 1998, Melbourne, Australia [doi>10.1145/277830.277850]
• 30: T. Olsson, P. Nilsson, T. Meincke, A. Hemam, and M. Torkelson. A digitally controlled low-power clock multiplier for globally asynchronous locally synchronous designs. ISCAS 2000 Geneva.
• 31: K. Olukotun, B. A. Nayfeh, L. Hammond, K. Wilson, and K. Chang. The case for a single-chip multiprocessor. ACM SIGOPS Operating Systems Review, 30, 1996.
• 32: 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]
• 33: G. Semeraro, D. H. Albonesi, G. Magklis, M. L. Scott, S. Dropsho, and S. Dwarkadas. Hiding synchronization delays in a gals processor microarchitecture. Proceedings of the 10th International Symposium on Asynchronous Circuits and Systems, 2004.
• 34: 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, ACM SIGARCH Computer Architecture News, v.24 n.2, p.191-202, May 1996
• 35: R. Uhlig, R. Fishtein, O. Gershon, I. Hirsh, and H. Wang. Softsdv: A pre-silicon software development environment for the ia-64 architecture. Intel Technology Journal, 3(4), 1999.
• 36: Qiang Wu , Philo Juang , Margaret Martonosi , Douglas W. Clark, Voltage and Frequency Control With Adaptive Reaction Time in Multiple-Clock-Domain Processors, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.178-189, February 12-16, 2005 [doi>10.1109/HPCA.2005.43]
• 37: W. Zhu, J. del Cuvillo, and G. R. Gao. Performance characteristics of openmp language constructs on a many-core-on-a-chip architecuture. The 2nd International Workshop on OpenMP (IWOMP), 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

General Terms:
Design, Performance

Keywords:
critical threads, energy-aware, low-power, meeting point thread characterization, microarchitecture, multi-threaded application, thread balancing, thread delaying