Scheduling inverse trees under the communication model of the LogP-machine

AbstractExisting scheduling strategies for task graphs mainly assume machine models that ignore properties of existing parallel architectures. The overhead on the processors for communication and the bandwidth of the interconnection network are neglected. The LogP-machine better reflects these properties. Much about scheduling task graphs is known, if the overhead (o) and the bandwidth per processor (1/g) are ignored and only latencies are considered. Then for some classes of task graphs it is possible that an optimal schedule can be computed in polynomial time (e.g. coarse grained trees), while for other classes (e.g. fine grained trees) this problem is NP-hard. The aim of this article is to extend the results onto the LogP-machine. Restricting us to linear schedules (i.e. no two independent tasks are scheduled on the same processor) we show that for inverse tree-like task graphs (which include inverse trees) optimal linear schedules can be found in polynomial time when g t- o is constant, and the minimal computation time of a task is at least g t- o (no matter whether the trees are coarse grained or not). The same result holds for optimal linear restricted schedules, where a schedule is restricted if for each task at least one of its direct predecessors (if it exists) is scheduled on the same processor. On the other hand we show that it is an NP-complete problem to find optimal (restricted) schedules for inverse trees even when g = 0