Allocation of precedence-constrained tasks to parallel processors for optimal execution

Abstract

The present work describes two methods for allocating m precedence-constrained tasks to n identical processors for optimal execution, uniform static load balancing and minimum interprocessor communication. The comparative studies made between two methods, the Simulated Annealing and a well-chosen Heuristic, indicate the suitability of the latter for complex precedence graphs. Examples from Matrix algebra have been chosen for the experiments. The resulting methods can be readily applied to optimize performance of practical problems on distributed memory parallel processor systems such as transputer-based systems.