The authors consider a set of n processors p1,p2,...,pn which communicate via a network and a modular program consisting of m tasks t1,t2,...,tm. Tasks can be assigned to any processor and some of them exchange data. The network configuration can be represented by a graph Gp=(Vp,Ep); the set of vertices V corresponds to the set of processors and two vertices are linked by an edge if the corresponding processors can communicate. Together with the set of tasks, we have a directed or undirected graph Gt=(Vt,Et), called the communication graph, whose vertices are the tasks of the program and such that there is an arc (or an edge) between two vertices if the corresponding tasks communicate. The authors study here the problem of determining an optimal assignment of the tasks which satisfies some constraints. They consider the three main classes of models studied in the bibliography. In the first class, the objective is to make the best use of resources and the objective function represents the global processing cost and the global communication cost. In the second class, the purpose is to minimize the total elapsed time between the beginning and the end of a program decomposed in tasks with precedence constraints. Finally, the third class concerns pipelined processing; in this case, the objective function represents the load of the most heavily loaded processor. The purpose of this paper is to present some recently published works about the particular (but interesting) case where the communication graph is a tree or a graph which generalizes the tree structure.
