Optimal algorithm for tree scheduling with unit time communication delays

A program is usually designed to act as a set of interacting tasks that can be used to construct a graph. These tasks can be assigned to processing el ements in different ways. The scheduling problem is applied to defining an assignment of tasks in order to process elements that will optimise certain performance indices. One of the most important reasons for scheduling indi ces is to try to optimise the finishing time. The finishing time of a progr am is the result of two components: the computing time and communication de lays. An optimal schedule is defined as the one that assigns tasks to proce ssing elements in such a way as to finish at the earliest possible time. Co mpletion of the optimum solution for arbitrary directed acyclic task graphs (DAGs) has been shown to be NP-complete. However, for some special classes of DAGs (such as fork, join, coarse-grain trees and some fine grain trees) many algorithms have been introduced to find optimal schedules. Note that most of these algorithms do not take into consideration the delays due to m essage passing among the processors. In the paper, the authors study the in crease in time complexity due to communication delays. The particular probl em that is addressed is the scheduling problem of the in-forest/out-forest. This paper introduces the first known linear time algorithm for finding th e optimal schedule, for the special case of tree-like graphs, with unit tim e computation and unit time communication delays.