Applications of Combinatorial Optimization, 2nd Edition

Chapter 2

The Task Allocation Problem

In this chapter, we present the task allocation problem for parallel programs. This problem, without any doubt one of the most important in the parallel computing domain, arises whenever we seek to improve the performance of a program executed on several machines. Indeed, what is the use of parallelizing a program if all the parts (tasks) are executed on the same machine, or if the communication time between machines cancels out the gain made on the execution time. Given the large variety of available physical architectures, it is impossible to give a model that is appropriate for all situations (architectures, objectives, program execution, etc.). Therefore, for more than 30 years, a large amount of research has tackled the different aspects (architectures, theory, practice) of this problem.

In what follows, after a quick general presentation which allows us to fix the terminology, we present the various elements to be taken into account in order to model this type of problem. We then give the various results for the problems generally accepted to be the fundamental models, and for certain special problems. We systematically give the principal methods and results but not all the references. We focus on those references that will allow us to obtain a complete bibliography quickly for a given approach.

We end with a presentation of a little-studied, but entirely realistic, example of an allocation problem, and we give a solution method.

2.1. ...