Scheduling in and out forests in the presence of communication delays

The authors consider the problem of scheduling tasks on multiprocessor architectures in the presence of communication delays. Given a set of dependent tasks, the scheduling problem is to allocate the tasks to processors such that the pre-specified precedence constraints among the tasks are obeyed and certain cost-measures (such as computation time) are minimized. Several cases of the scheduling problem have been proven to be NP-complete. Nevertheless, there are polynomial time algorithms for several interesting special cases of the general scheduling problem. Most of these results, however, do not take into consideration the delays due to message passing among processors. The authors study the increase in time complexity of the scheduling problem due to the introduction of communication delays. In particular, they address the open problem of scheduling out-forests (in-forests) in a multiprocessor system of m identical processors when communication delays are considered. They present first known polynomial time algorithms for the computation of the optimal schedule when the number of available processors is given and bounded and both computation and communication delays are assumed to take one unit of time