Linear Time Algorithm to Schedule Trees with Communication Delays Optimally onTwo Machines

摘要

For the implementation of a parallel program, considered as a collection ofprocesses, on a parallel computer, one of the major problems is to determine which processor should execute which process and at what time; the purpose is that the moment of time that all processes have been executed (i.e., the execution of the parallel program has finished), occurs as early as possible. Besides the possibility that processes may have different execution lengths (possibly not exactly known in advance), processes might use (intermediate) results computed by other processes. Making these results available may require an additional (to the execution length) amount of time, the communication delay. During this communication delay processors may execute processes that have already obtained all necessary data. The paper uses the general approach of list scheduling that yields feasible schedules, and proves that under certain conditions the algorithm runs in linear time. Then it concentrates on the creation of the list, such that the list-scheduling algorithm yields an optimal schedule and runs in linear time.