Finding large-grain parallelism in loops with serial control dependencies

Research output: Contribution to journalConference articlepeer-review

Abstract

An automatic parallelization technique, control precomputation is discussed, whereby arbitrary sequential loops, including those with serializing control dependencies (i.e., general while loops) and/or irreducible flow graphs, may be transformed to permit relatively large-grain asynchronous parallel execution. The basic concept is for the compiler to isolate inherently sequential operations from the remainder of the loop, thereby enabling the remaining operations to be parallelized. Since there is a cost associated with splitting loops, not all loops can be profitably parallelized in this way. Compared to pipelining, however, this technique effectively reduces synchronization overhead by grouping high-frequency synchronization points within a single process; the reduction in synchronization overhead is approximately proportional to the parallelism width of the machine.

Original languageEnglish
Pages (from-to)114-121
Number of pages8
JournalProceedings of the International Conference on Parallel Processing
Volume2
StatePublished - 1988

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Finding large-grain parallelism in loops with serial control dependencies'. Together they form a unique fingerprint.

Cite this