Statement re-ordering for DOACROSS loops

Ding Kai Chen, Pen Chung Yew

Research output: Contribution to journalConference articlepeer-review

15 Scopus citations


In this paper, we propose a new statement reordering algorithm for DOACROSS loops that overcomes some of the problems in the previous schemes. The new algorithm uses a hierarchical approach to locate strongly dependent statement groups and to order these groups considering critical dependences. A new optimization problem, dependence covering maximization, which was not discussed before is also introduced. It is shown that this optimization problem is NP-complete, and a heuristic algorithm is incorporated in our algorithm. This new statement re-ordering scheme, combined with the dependence covering maximization, can be an important compiler optimization to parallelize loop structures for large scale coarse and fine grain parallelism.

Original languageEnglish (US)
Article number5727757
Pages (from-to)II24-II28
JournalProceedings of the International Conference on Parallel Processing
StatePublished - 1994
Event23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States
Duration: Aug 15 1994Aug 19 1994


Dive into the research topics of 'Statement re-ordering for DOACROSS loops'. Together they form a unique fingerprint.

Cite this