Redundant synchronization elimination for DOACROSS loops

Ding Kai Chen, Pen Chung Yew

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Cross-iterations data dependences in DOACROSS loops require explicit data synchronizations to enforce them. However, the composite effect of some data synchronizations may cover the other dependences and make the enforcement of those covered dependences redundant. In this paper, we propose an efficient and general algorithm to identify redundant synchronizations in multiply nested DOACROSS loops which may have multiple statements and loop-exit control branches. Eliminating redundant sychronizations in DOACROSS loops allows more efficient execution of such loops. We also address the issues of enforcing data synchronizations in iterations near the boundary of the iteration space. Because some dependences may not exist in those boundary iterations, it adds complexity in determining the redundant synchronizations for those boundary iterations. The necessary and sufficient condition under which the synchronization is uniformly redundant is also studied. These results allow a parallelizing compiler to generate efficient data synchronization instructions for DOACROSS loops.

Original languageEnglish (US)
Pages (from-to)459-470
Number of pages12
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number5
StatePublished - 1999

Bibliographical note

Funding Information:
This work was supported in part by the U.S. National Science Foundation under Grant nos. NSF MIP-8920891, NSF MIP-9307910, and NSF MIP-9610379 and by the U.S. Department of Energy Grant no. DOE DE-FG02-85ER25001.

Fingerprint Dive into the research topics of 'Redundant synchronization elimination for DOACROSS loops'. Together they form a unique fingerprint.

Cite this