Thread criticality predictors for dynamic performance, power, and resource management in chip multiprocessors

ABSTRACT

With the shift towards chip multiprocessors (CMPs), exploiting and managing parallelism has become a central problem in computing systems. Many issues of parallelism management boil down to discerning which running threads or processes are critical, or slowest, versus which are non-critical. If one can accurately predict critical threads in a parallel program, then one can respond in a variety of ways. Possibilities include running the critical thread at a faster clock rate, performing load balancing techniques to offload work onto currently non-critical threads, or giving the critical thread more on-chip resources to execute faster.

This paper proposes and evaluates simple but effective thread criticality predictors for parallel applications. We show that accurate predictors can be built using counters that are typically already available on-chip. Our predictor, based on memory hierarchy statistics, identifies thread criticality with an average accuracy of 93% across a range of architectures.

We also demonstrate two applications of our predictor. First, we show how Intel's Threading Building Blocks (TBB) parallel runtime system can benefit from task stealing techniques that use our criticality predictor to reduce load imbalance. Using criticality prediction to guide TBB's task-stealing decisions improves performance by 13-32% for TBB-based PARSEC benchmarks running on a 32-core CMP. As a second application, criticality prediction guides dynamic energy optimizations in barrier-based applications. By running the predicted critical thread at the full clock rate and frequency-scaling non-critical threads, this approach achieves average energy savings of 15% while negligibly degrading performance for SPLASH-2 and PARSEC benchmarks.

REFERENCES

• 1: Intel Threading Building Blocks 2.0, 2008
• 2: Umut A. Acar , Guy E. Blelloch , Robert D. Blumofe, The data locality of work stealing, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.1-12, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341801]
• 3: Abhishek Bhattacharjee , Gilberto Contreras , Margaret Martonosi, Full-system chip multiprocessor power evaluations using FPGA-based emulation, Proceeding of the 13th international symposium on Low power electronics and design, August 11-13, 2008, Bangalore, India [doi>10.1145/1393921.1394010]
• 4: Christian Bienia , Sanjeev Kumar , Jaswinder Pal Singh , Kai Li, The PARSEC benchmark suite: characterization and architectural implications, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454128]
• 5: C. Bienia, S. Kumar, and K. Li. PARSEC vs SPLASH-2: A Quantitative Comparison of Two Multithreaded Benchmark Suites on Chip Multiprocessors, IEEE Intl. Symp. on Workload Characterization, 2008
• 6: Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999 [doi>10.1145/324133.324234]
• 7: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Journal of Parallel and Distributed Computing, v.37 n.1, p.55-69, Aug. 25, 1996 [doi>10.1006/jpdc.1996.0107]
• 8: Shekhar Borkar , Tanay Karnik , Siva Narendra , Jim Tschanz , Ali Keshavarzi , Vivek De, Parameter variations and impact on circuits and microarchitecture, Proceedings of the 40th annual Design Automation Conference, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775920]
• 9: Qiong Cai , José González , Ryan Rakvic , Grigorios Magklis , Pedro Chaparro , Antonio González, Meeting points: using thread criticality to adapt multicore hardware to parallel regions, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454149]
• 10: Hongliang Chang , Sachin S. Sapatnekar, Full-chip analysis of leakage power under process variations, including spatial correlations, Proceedings of the 42nd annual Design Automation Conference, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065716]
• 11: David Chase , Yossi Lev, Dynamic circular work-stealing deque, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073974]
• 12: G. Contreras and M. Martonosi. Characterizing and Improving the Performance of Intel Threading Building Blocks. IEEE Intl. Symp. on Workload Characterization, 2008
• 13: James Donald , Margaret Martonosi, Techniques for Multicore Thermal Management: Classification and New Exploration, Proceedings of the 33rd annual international symposium on Computer Architecture, p.78-88, June 17-21, 2006
• 14: Brian Fields , Shai Rubin , Rastislav Bodík, Focusing processor policies via critical-path prediction, Proceedings of the 28th annual international symposium on Computer architecture, p.74-85, June 30-July 04, 2001, Göteborg, Sweden
• 15: Engin Ipek , Onur Mutlu , José F. Martínez , Rich Caruana, Self-Optimizing Memory Controllers: A Reinforcement Learning Approach, Proceedings of the 35th International Symposium on Computer Architecture, p.39-50, June 21-25, 2008
• 16: Canturk Isci , Alper Buyuktosunoglu , Chen-Yong Cher , Pradip Bose , Margaret Martonosi, An Analysis of Efficient Multi-Core Global Power Management Policies: Maximizing Performance for a Given Power Budget, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.347-358, December 09-13, 2006 [doi>10.1109/MICRO.2006.8]
• 17: Aamer Jaleel , William Hasenplaugh , Moinuddin Qureshi , Julien Sebot , Simon Steely, Jr. , Joel Emer, Adaptive insertion policies for managing shared caches, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454145]
• 18: Seongbeom Kim , Dhruba Chandra , Yan Solihin, Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.111-122, September 29-October 03, 2004 [doi>10.1109/PACT.2004.15]
• 19: W. Kim, M. S. Gupta, G. Y. Wei, and D. Brooks. System Level Analysis of Fast, Per-Core DVFS Using On-Chip Switching Regulators. Intl. Symp. on High Performance Computer Architecture, 2008
• 20: Sanjeev Kumar , Christopher J. Hughes , Anthony Nguyen, Carbon: architectural support for fine-grained parallelism on chip multiprocessors, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 21: 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]
• 22: Wi-fen Lin, Reducing DRAM Latencies with an Integrated Memory Hierarchy Design, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.301, January 20-24, 2001
• 23: 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]
• 24: Shaobo Liu , Qinru Qiu , Qing Wu, A probabilistic technique for full-chip leakage estimation, Proceeding of the 13th international symposium on Low power electronics and design, August 11-13, 2008, Bangalore, India [doi>10.1145/1393921.1393975]
• 25: K. Luo, J. Gummaraju, and M. Franklin. Balancing Throughput and Fairness in SMT Processors. Intl. Symp. on Performance Analysis of Systems and Software, 2001
• 26: Milo M. K. Martin , Daniel J. Sorin , Bradford M. Beckmann , Michael R. Marty , Min Xu , Alaa R. Alameldeen , Kevin E. Moore , Mark D. Hill , David A. Wood, Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105747]
• 27: Kyle J. Nesbit , James Laudon , James E. Smith, Virtual private caches, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 28: Kyle J. Nesbit , Nidhi Aggarwal , James Laudon , James E. Smith, Fair Queuing Memory Systems, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.208-222, December 09-13, 2006 [doi>10.1109/MICRO.2006.24]
• 29: Pierre Palatin , Yves Lhuillier , Olivier Temam, CAPSULE: Hardware-Assisted Parallel Execution of Component-Based Programs, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.247-258, December 09-13, 2006 [doi>10.1109/MICRO.2006.13]
• 30: Shekhar Srikantaiah , Mahmut Kandemir , Mary Jane Irwin, Adaptive set pinning: managing shared caches in chip multiprocessors, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 31: 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
• 32: Dongning Liang, Dynamic Prediction of Critical Path Instructions, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.185, January 20-24, 2001
• 33: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design, Performance

Keywords:
caches, dvfs, intel tbb, parallel processing, thread criticality prediction