Scheduling Nested Loops with the Least Number of Processors.

T. Andronikos, M. Kathalas, F.M. Ciorba, P. Theodoropoulos, G. Papakonstantinou, and P. Tsanakas


UET model, lower bound, upper bound,optimal execution time, scheduling.


Usually the most computationally intensive part of a pro gram is attributed to the nested loops it contains. It is therefore of interest to try to parallelize the nested loops in order to reduce the overall computation time. A special category of FOR(DO) nested loops are the uniform de pendence loops, which yield efficient parallelization tech niques and are the focus of this paper. The primary goals in this area of research are: (1) achieving the optimal par allel time and (2) minimizing the number of processing elements required for the execution of the parallel pro gram. In this paper we present a new dynamic lower bound on the number of processors needed for scheduling and we use a decision algorithm to verify that all uniform dependence loops can achieve this bound.

Important Links:

Go Back