Estimating minimum parallel execution time of loops with loop-carried dependencies

Tsuneo Nakanishi, Kazuki Joe, Constantine D. Polychronopoulos, Keijiro Araki, Akira Fukuda

Research output: Contribution to journalArticlepeer-review


The article proposes a method of calculating the minimum parallel execution time of loops. The loop is completely unrolled and the task graph is considered. By assigning the execution time of the corresponding task and the communication time related to the dependency as costs to the nodes and edges of the task graph, the cost of the critical path which is the path for which the total cost of the nodes and edges composing the path is the maximum, gives the minimum parallel execution time of the loops. It is not desirable, however, in considering the computation time and the required memory capacity, to unroll the loops completely. The method presented here formulates the problem as the integer programming problem, and calculates the cost of the critical path without rolling the loops at all. In this study, a branch and bound algorithm that solves the integer programming problem is implemented. The implemented algorithm unrolls the loops and determines the critical path on the task graph. As a result of evaluation using Livermore's benchmark kernel, it is verified that the implemented algorithm can be executed in a sufficiently practical time, regardless of the size (number of iterations) of the loops.

Original languageEnglish
Pages (from-to)57-68
Number of pages12
JournalSystems and Computers in Japan
Issue number10
Publication statusPublished - Sept 1999

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Estimating minimum parallel execution time of loops with loop-carried dependencies'. Together they form a unique fingerprint.

Cite this