Optimally maximizing iteration-level loop parallelism

Duo Liu, Yi Wang, Zili Shao, Minyi Guo, Jingling Xue

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)


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.
Original languageEnglish
Article number5887315
Pages (from-to)564-572
Number of pages9
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number3
Publication statusPublished - 1 Mar 2012


  • Data dependence graph
  • Iteration-level parallelism
  • Loop parallelization
  • Loop transformation
  • Retiming

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Optimally maximizing iteration-level loop parallelism'. Together they form a unique fingerprint.

Cite this