Quantifying instruction criticality for shared memory multiprocessors

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Li, T; Lebeck, AR; Sorin, DJ

Published Date

  • January 1, 2003

Published In

  • Annual Acm Symposium on Parallel Algorithms and Architectures

Start / End Page

  • 128 - 137

Digital Object Identifier (DOI)

  • 10.1145/777412.777434

Citation Source

  • Scopus