An Efficient Scheduling of Uniform Dependence Loops
T. Andronikos, Marios Kalathas, Florina M. Ciorba, P. Theodoropoulos, G. Papakonstantinou · 2003
Usually the most computationally intensive part of a program is attributed to the nested loops it contains. It is therefore of interest to try to parallelize nested loops in order to reduce the overall computation time. A special category of FOR(DO) nested loops are the uniform dependence loops, which are the focus of this paper. The primary goals in this area of research are: (1) achieving the optimal parallel time and (2) minimizing the number of processing elements. In this paper we present an algorithm for the efficient assignment of computations onto the minimum number of processing elements that guarantees the optimal makespan. The proposed algorithm is polynomial in the size of the index space and performs a binary search between a lower and an upper bound of the optimal number of processors. We provide experimental results that demonstrate the feasibility of our algorithm.