On effective execution of nonuniform DOACROSS loops

Ding Kai Chen, Pen Chung Yew

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

It is extremely difficult to parallelize DOACROSS loops with nonuniform loop-carried dependences. In this paper, we present a static scheduling scheme with an accompanying synchronization strategy that can execute such DOACROSS loops effectively and efficiently. Our approach uses one of the parallelization techniques called Dependence Uniformization, which finds a small set of uniform dependence vectors to cover all possible nonuniform dependences in a DOACROSS loop. It differs from the previous schemes in that we demonstrate a better way to select the uniform dependence vectors. When used with the Static Strip Scheduling scheme, the proposed uniform dependence vector set allows us to enforce dependences with more locality, which reduces the requirement of explicit synchronization considerably while retaining most of the parallelism. This paper describes the uniform dependence vectors selection strategy and the static strip scheduling scheme. The performance analysis and examples are also presented.

Original languageEnglish (US)
Pages (from-to)463-476
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Volume7
Issue number5
DOIs
StatePublished - 1996

Bibliographical note

Funding Information:
This work was supported in part by the U.S. National Science Foundation under Grant Nos. NSF MIP94-96320 a n d NSF MIP93-07910.

Keywords

  • Compiler transformation
  • Data dependence
  • Loop parallelization
  • Parallelism
  • Scheduling
  • Synchronization

Fingerprint

Dive into the research topics of 'On effective execution of nonuniform DOACROSS loops'. Together they form a unique fingerprint.

Cite this