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

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.