Coarse-grained thread pipelining: A speculative parallel execution model for shared-memory multiprocessors

Iffat H. Kazi, David J. Lilja

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


This paper presents a new parallelization model, called coarse-grained thread pipelining, for exploiting speculative coarse-grained parallelism from general-purpose application programs in shared-memory multiprocessor systems. This parallelization model, which is based on the fine-grained thread pipelining model proposed for the superthreaded architecture [11], [12], allows concurrent execution of loop iterations in a pipelined fashion with runtime data-dependence checking and control speculation. The speculative execution combined with the runtime dependence checking allows the parallelization of a variety of program constructs that cannot be parallelized with existing runtime parallelization algorithms. The pipelined execution of loop iterations in this new technique results in lower parallelization overhead than in other existing techniques. We evaluated the performance of this new model using some real applications and a synthetic benchmark. These experiments show that programs with a sufficiently large grain size compared to the parallelization overhead obtain significant speedup using this model. The results from the synthetic benchmark provide a means for estimating the performance that can be obtained from application programs that will be parallelized with this model. The library routines developed for this thread pipelining model are also useful for evaluating the correctness of the codes generated by the superthreaded compiler and in debugging and verifying the simulator for the superthreaded processor.

Original languageEnglish (US)
Pages (from-to)952-966
Number of pages15
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number9
StatePublished - Sep 2001

Bibliographical note

Funding Information:
An early version of this work was presented at the 1998 International Conference on Supercomputing [4]. This work is supported in part by the US National Science Foundation under Grant Nos. MIP-9610379, MIP-9971666, CDA-9502979, and CDA-941405.


  • Coarse-grained parallelization
  • Runtime parallelization
  • Shared-memory multiprocessors
  • Speculative execution
  • Superthreaded architecture
  • Thread pipelining


Dive into the research topics of 'Coarse-grained thread pipelining: A speculative parallel execution model for shared-memory multiprocessors'. Together they form a unique fingerprint.

Cite this