Quantifying instruction criticality for shared memory multiprocessors

ABSTRACT

Recent research on processor microarchitecture suggests using instruction criticality as a metric to guide hardware control policies. Fields et al. [3, 4] have proposed a directed acyclic graph (DAG) model for characterizing program microexecutions on uniprocessors. Under such a model, critical path analysis can be applied and instructions' slack values can be used to quantify instruction criticality. In this paper, we extend the uniprocessor DAG model to characterize parallel program executions on shared memory multiprocessor systems. We describe how critical path analysis can be applied, at a fine grain, in a multiprocessor system running both finite and continuous workloads. We provide detailed evaluations for various aspects of multiprocessor executions under the DAG model. To enable efficient offline critical path analysis, we propose a novel graph reduction technique that reduces a DAG to an equivalent but significantly smaller DAG.

REFERENCES

• 1: Alaa R. Alameldeen, Carl J. Mauer, Min Xu, Pacia J. Harper, Milo M. K. Martin, Daniel J. Sorin, Mark D. Hill, and David A. Wood. Evaluating Non-deterministic Multithreaded Commercial Workloads. In Proceedings of the Fifth Workshop on Computer Architecture Evaluation Using Commercial Workloads, pages 30--38, February 2002.
• 2: Carl Josef Beckmann, Hardware and software for functional and fine grain parallelism, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
• 3: Brian Fields , Rastislav Bodík , Mark D. Hill, Slack: maximizing performance under technological constraints, Proceedings of the 29th annual international symposium on Computer architecture, p.47, May 25-29, 2002, Anchorage, Alaska
• 4: 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
• 5: Kourosh Gharachorloo , Madhu Sharma , Simon Steely , Stephen Van Doren, Architecture and design of AlphaServer GS320, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.13-24, November 2000, Cambridge, Massachusetts, United States
• 6: Jeffrey K. Hollingsworth, Critical Path Profiling of Message Passing and Shared-Memory Programs, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.1029-1040, October 1998 [doi>10.1109/71.730530]
• 7: Jeffrey K. Hollingsworth and Barton P. Miller. Slack: A New Performance Metric for Parallel Programs. Technical Report 1260, Computer Sciences Department, University of Wisconsin--Madison, December 1994.
• 8: H. Kasahara and S. Narita. Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing. IEEE Transactions on Computers, C-33(11):1023--1029, November 1990.
• 9: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 10: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 11: Robert H. B. Netzer, Optimal tracing and replay for debugging shared-memory parallel programs, Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, p.1-11, May 17-18, 1993, San Diego, California, United States
• 12: Srikanth T. Srinivasan , Roy Dz-ching Ju , Alvin R. Lebeck , Chris Wilkerson, Locality vs. criticality, Proceedings of the 28th annual international symposium on Computer architecture, p.132-143, June 30-July 04, 2001, Göteborg, Sweden
• 13: 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
• 14: Eric Tune , Dean M. Tullsen , Brad Calder, Quantifying Instruction Criticality, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.104, September 22-25, 2002
• 15: 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
• 16: Cui-Qing Yang and Barton P. Miller. Critical Path Analysis for the Execution of Parallel and Distributed Programs. In Proceedings of the Seventh Conference on Distributed Memory Computer Systems, pages 366--373, June 1988.

INDEX TERMS

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

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
critical path analysis, shared memory multiprocessors, slack