OPTIMAL TIME AND EFFICIENT SPACE FREE SCHEDULING FOR NESTED LOOPS

The most important issue when parallelizing sequential programs is the efficient assignment of computations into different processing elemen ts. The most extensive, in terms of time execution, part of a program is the nested loops. Too many approaches have been devoted in parallel izing nested loops, and assigning the concurrent partitions of such a loop into different processors. In the past, all methods have been foc used upon linear schedules produced by manipulating the reduced depend ence graph, which in some cases achieve near optimal solutions. This p aper presents a new method of free scheduling loop computations into t ime, based on task graph scheduling techniques. It will be shown that this schedule is optimal in terms of time, outperforming all linear sc hedules. Furthermore, in terms of total number of processors, the pres ented method includes a heuristic refinement of the free schedule whic h 'shuffles' computations into time, without loss of the optimal time performance, to augment the mean processor utilization. In all cases, the proposed method uses less number of processors, while preserving t he optimal total execution time. The 'shuffling' of computations is ba sed on graph theory approaches, and uses PERT problem techniques. Such scheduling is convenient for parallelizing tools (such as compilers), but has practical interest for shared memory multiprocessor systems, where the communication delay imposed by such non-regular scheduling i s of no interest.