Scheduling Problems in a Practical Allocation Model

Lisa Hollermann, Tsan-sheng Hsu, Dian Lopez, Keith Vertanen

Journal of Combinatorial Optimization, 1997.

A parallel computational model is defined which addresses I/O contention, latency, and pipe-lined message passing between tasks allocated to different processors. The model can be used for parallel task-allocation on either a network of workstations or on a multi-stage inter-connected parallel machine. To study performance bounds more closely, basic properties are developed for when the precedence constraints form a directed tree. It is shown that the problem of optimally scheduling a directed one-level precedence tree on an unlimited number of identical processors in this model is NP-hard. The problem of scheduling a directed two-level precedence tree is also shown to be NP-hard even when the system latency is zero.

An approximation algorithm is then presented for scheduling directed one-level task trees on an unlimited number of processors with an approximation ratio of 3. Simulation results show that this algorithm is, in fact, much faster than its worst-case performance bound. Better simulation results are obtained by improving our approximation algorithm using heuristics. Restricting the problem to the case of equal task execution times, a linear-time algorithm is presented to find an optimal schedule.