Models and algorithms for task allocation in a parallel environment

Abstract

A task allocation algorithm in a parallel system assigns tasks to each processor with a goal of minimizing both execution and communication costs. Previous research shows the need for algorithms which can approximate this problem efficiently as well as the need for a model which incorporates more fully the communication costs between tasks. The bulk-synchronous parallel (BSP) model proposed by Valiant is shown as a viable model for the task allocation problem. It is shown that the problem is strongly NP-Complete and that no fully polynomial approximation scheme is possible for solving the general problem. Performance results are possible, however, for certain restricted problems. Using the BSP model, approximation algorithms are given for both restricted and the general task allocation problems. Algorithms and performance bounds are also given for the more practical problem of allocating tasks which form precedence graphs. By relaxing previous restrictions used in algorithms for this problem, a practical model was designed which can be implemented on the XPRAM BSP architecture.