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

Existing 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 Log P-machine better reflects these properties. Much about scheduling task graphs is known, if the overhead to) and the ban dwidth per processor (1/g) are ignored and only latencies are considered. T hen 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 u s to linear schedules (i.e. no two independent tasks are scheduled on the s ame processor) we show that for inverse tree-like task graphs (which includ e inverse trees) optimal linear schedules can be found in polynomial time w hen g - o is constant, and the minimal computation time of a task is at lea st g - o (no matter whether the trees are coarse grained or not). The same result holds for optimal linear restricted schedules, where a schedule is r estricted if for each task at least one of its direct predecessors (if it e xists) is scheduled on the same processor. On the other hand we show that i t is an NP-complete problem to find optimal (restricted) schedules for inve rse trees even when g = o. (C) 1999-Elsevier Science B.V. All rights reserv ed.