Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/29901
Title: Optimally maximizing iteration-level loop parallelism
Authors: Liu, D
Wang, Y
Shao, Z 
Guo, M
Xue, J
Keywords: Loop parallelization
Loop transformation
Retiming
Data dependence graph
Iteration-level parallelism
Issue Date: 2012
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on parallel and distributed systems, 2012, v. 23, no. 3, p. 564-572 How to cite?
Journal: IEEE transactions on parallel and distributed systems 
Abstract: Loops are the main source of parallelism in many applications. This paper solves the open problem of extracting the maximal number of iterations from a loop to run parallel on chip multiprocessors. Our algorithm solves it optimally by migrating the weights of parallelism-inhibiting dependences on dependence cycles in two phases. First, we model dependence migration with retiming and formulate this classic loop parallelization into a graph optimization problem, i.e., one of finding retiming values for its nodes so that the minimum nonzero edge weight in the graph is maximized. We present our algorithm in three stages with each being built incrementally on the preceding one. Second, the optimal code for a loop is generated from the retimed graph of the loop found in the first phase. We demonstrate the effectiveness of our optimal algorithm by comparing with a number of representative nonoptimal algorithms using a set of benchmarks frequently used in prior work and a set of graphs generated by TGFF.
URI: http://hdl.handle.net/10397/29901
ISSN: 1045-9219
EISSN: 1558-2183
DOI: 10.1109/TPDS.2011.171
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

8
Citations as of Sep 15, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
Citations as of Sep 5, 2017

Page view(s)

28
Last Week
2
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.