A Path-Driven Loop Scheduling Mapped onto Generalized Hypercubes

One of the important issues in automatic code par-allelization is the scheduling and mapping of nested loop iterations to different processors. The optimal scheduling problem is known to be NP-complete. Many heuristic static and dynamic loop scheduling techniques have been studied in the past. Here we propose a new static loop scheduling heuris-tic method called path-driven scheduling, under the as-sumption that the loop dependence graph has been gener-ated. This method clusters tasks according to the directed paths on the dependence graph and assigns them to pro-cessors in the target architecture. We make comparisons with the free scheduling and the refined free scheduling al-gorithms [8]. We schedule three widely used nested loops on a generalized hypercube architecture. Our algorithm ex-hibits the lowest communication cost compared to the other two algorithms, while the execution cost is the same for all three algorithms. Key Words: Loop scheduling, path-driven schedul-ing, path generation, path mapping, generalized hypercube