Optimal loop parallelization for maximizing iteration-level parallelism

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

12 Citations (Scopus)

Abstract

This paper solves the open problem of extracting the maximal number of iterations from a loop that can be executed in 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 non-zero 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 non-optimal algorithms using a set of benchmarks frequently used in prior work.
Original languageEnglish
Title of host publicationEmbedded Systems Week 2009 - 2009 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES'09
Pages67-76
Number of pages10
DOIs
Publication statusPublished - 21 Dec 2009
EventEmbedded Systems Week 2009, ESWEEK 2009 - 2009 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES'09 - Grenoble, France
Duration: 11 Oct 200916 Oct 2009

Conference

ConferenceEmbedded Systems Week 2009, ESWEEK 2009 - 2009 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES'09
Country/TerritoryFrance
CityGrenoble
Period11/10/0916/10/09

Keywords

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

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software
  • Electrical and Electronic Engineering

Cite this