TY - JOUR

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

AU - Nakanishi, Tsuneo

AU - Joe, Kazuki

AU - Polychronopoulos, Constantine D.

AU - Araki, Keijiro

AU - Fukuda, Akira

PY - 1999/9

Y1 - 1999/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0033365752&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033365752&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1520-684X(199909)30:10<57::AID-SCJ6>3.0.CO;2-N

DO - 10.1002/(SICI)1520-684X(199909)30:10<57::AID-SCJ6>3.0.CO;2-N

M3 - Article

AN - SCOPUS:0033365752

VL - 30

SP - 57

EP - 68

JO - Systems and Computers in Japan

JF - Systems and Computers in Japan

SN - 0882-1666

IS - 10

ER -