Scheduling of Precedence-Constrained Tasks on Multiprocessors

A major factor in the intelligent utilization of multiprocessor systems is the determination of how to assign computational tasks among processors and to schedule their execution. To this end, we consider a set of precedence – constrained tasks, with arbitrary communication among them, in a network of identical processors. We investigate several approaches to statically assign and schedule the tasks in order to achieve maximum parallelism and minimum communication overhead in both fully-connected and hypercube multiprocessor ensembles. Three simple heuristic techniques and an adaptation of simulated annealing are described. Results of computational experimentation provide a comparative analysis of the performance of these heuristic approaches, and give insight into the appropriate application of each method for scheduling distributed task systems.