Statement re-ordering for DOACROSS loops

Ding Kai Chen; Pen Chung Yew

doi:10.1109/ICPP.1994.186

Statement re-ordering for DOACROSS loops

Ding Kai Chen, Pen Chung Yew

Computer Science and Engineering

Research output: Contribution to journal › Conference article › peer-review

15 Scopus citations

Abstract

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 language	English (US)
Article number	5727757
Pages (from-to)	II24-II28
Journal	Proceedings of the International Conference on Parallel Processing
Volume	2
DOIs	https://doi.org/10.1109/ICPP.1994.186
State	Published - 1994
Event	23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States Duration: Aug 15 1994 → Aug 19 1994

Publisher link

10.1109/ICPP.1994.186

Find It

Find It at U of M Libraries

Cite this

@article{fda9c975c8f944fd9aebb5638e6257a7,

title = "Statement re-ordering for DOACROSS loops",

abstract = "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.",

author = "Chen, \{Ding Kai\} and Yew, \{Pen Chung\}",

year = "1994",

doi = "10.1109/ICPP.1994.186",

language = "English (US)",

volume = "2",

pages = "II24--II28",

journal = "Proceedings of the International Conference on Parallel Processing",

issn = "0190-3918",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "23rd International Conference on Parallel Processing, ICPP 1994 ; Conference date: 15-08-1994 Through 19-08-1994",

}

TY - JOUR

T1 - Statement re-ordering for DOACROSS loops

AU - Chen, Ding Kai

AU - Yew, Pen Chung

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0012526362

UR - https://www.scopus.com/inward/citedby.url?scp=0012526362&partnerID=8YFLogxK

U2 - 10.1109/ICPP.1994.186

DO - 10.1109/ICPP.1994.186

M3 - Conference article

AN - SCOPUS:0012526362

SN - 0190-3918

VL - 2

SP - II24-II28

JO - Proceedings of the International Conference on Parallel Processing

JF - Proceedings of the International Conference on Parallel Processing

M1 - 5727757

T2 - 23rd International Conference on Parallel Processing, ICPP 1994

Y2 - 15 August 1994 through 19 August 1994

ER -

Statement re-ordering for DOACROSS loops

Abstract

Publisher link

Find It

Other files and links

Fingerprint

Cite this