Full parallelism in uniform nested loops using multi-dimensional retiming

N. L. Passos; E. H.M. Sha

doi:10.1109/ICPP.1994.114

Full parallelism in uniform nested loops using multi-dimensional retiming

N. L. Passos
, E. H.M. Sha

University of Notre Dame

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

22 Scopus citations

Abstract

Most scientific and DSP applications are recursive or iterative. Uniform nested loops can be modeled as multi-dimensional data flow graphs (DFGs). To achieve full parallelism of the loop body, i.e., all the computational nodes executed in parallel, substantially decreases the overall computation time. It is well known that for one-dimensional DFGs retiming can not always achieve full parallelism. This paper shows an important and counter-intuitive result, which proves that we can always obtain full-parallelism for DFGs with more than one dimension. It also presents two novel multi-dimensional retiming techniques to obtain full parallelism.

Original language	English
Article number	5727774
Pages (from-to)	II130-II133
Journal	Proceedings of the International Conference on Parallel Processing
Volume	2
DOIs	https://doi.org/10.1109/ICPP.1994.114
State	Published - 1994
Externally published	Yes
Event	23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States Duration: 15 Aug 1994 → 19 Aug 1994

Access to Document

10.1109/ICPP.1994.114

Cite this

@article{06f4f1f20a304701a2f2026332f7a154,

title = "Full parallelism in uniform nested loops using multi-dimensional retiming",

abstract = "Most scientific and DSP applications are recursive or iterative. Uniform nested loops can be modeled as multi-dimensional data flow graphs (DFGs). To achieve full parallelism of the loop body, i.e., all the computational nodes executed in parallel, substantially decreases the overall computation time. It is well known that for one-dimensional DFGs retiming can not always achieve full parallelism. This paper shows an important and counter-intuitive result, which proves that we can always obtain full-parallelism for DFGs with more than one dimension. It also presents two novel multi-dimensional retiming techniques to obtain full parallelism.",

author = "Passos, \{N. L.\} and Sha, \{E. H.M.\}",

year = "1994",

doi = "10.1109/ICPP.1994.114",

language = "英语",

volume = "2",

pages = "II130--II133",

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 - Full parallelism in uniform nested loops using multi-dimensional retiming

AU - Passos, N. L.

AU - Sha, E. H.M.

PY - 1994

Y1 - 1994

N2 - Most scientific and DSP applications are recursive or iterative. Uniform nested loops can be modeled as multi-dimensional data flow graphs (DFGs). To achieve full parallelism of the loop body, i.e., all the computational nodes executed in parallel, substantially decreases the overall computation time. It is well known that for one-dimensional DFGs retiming can not always achieve full parallelism. This paper shows an important and counter-intuitive result, which proves that we can always obtain full-parallelism for DFGs with more than one dimension. It also presents two novel multi-dimensional retiming techniques to obtain full parallelism.

AB - Most scientific and DSP applications are recursive or iterative. Uniform nested loops can be modeled as multi-dimensional data flow graphs (DFGs). To achieve full parallelism of the loop body, i.e., all the computational nodes executed in parallel, substantially decreases the overall computation time. It is well known that for one-dimensional DFGs retiming can not always achieve full parallelism. This paper shows an important and counter-intuitive result, which proves that we can always obtain full-parallelism for DFGs with more than one dimension. It also presents two novel multi-dimensional retiming techniques to obtain full parallelism.

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

U2 - 10.1109/ICPP.1994.114

DO - 10.1109/ICPP.1994.114

M3 - 会议文章

AN - SCOPUS:1542489257

SN - 0190-3918

VL - 2

SP - II130-II133

JO - Proceedings of the International Conference on Parallel Processing

JF - Proceedings of the International Conference on Parallel Processing

M1 - 5727774

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

Y2 - 15 August 1994 through 19 August 1994

ER -

Full parallelism in uniform nested loops using multi-dimensional retiming

Abstract

Access to Document

Other files and links

Fingerprint

Cite this