Le placement de tâches sur des architectures parallèles. (Process allocation in parallel architectures). (French) Zbl 0654.68011

André, Françoise; Pazat, Jean-Louis

Tech. Sci. Inf. 7, No. 4, 385-401 (1988).

The article is an in-depth study on the subject of process allocation in multiprocessor architectures with fixed bindings.
The authors provide a clear and precise synthesis of the known general approaches. After defining the process assignment problem (the problem is NP-complete), the authors describe the methods of searching for the optimal assignment. The optimal assignment is defined as minimizing a function of costs. The assignment techniques are approximative methods, using algorithms based on heuristics; the authors present the fundamental methods with advantages and drawbacks. These algorithms offer a departure point for constructing an assignment tool. It is just a departure point as very few of the known algorithms have really been implemented in actual cases.
The authors’ great merit is that they examine an actual case, a pyramidal architecture with 21 processors, for which they analyze the efficiency of an assignment algorithm, the algorithm of S. H. Bokhari [IEEE Trans. Comput. C-30, 207-214 (1981)].
The research joins a study of the process assignment methods and algorithms, under consideration at the University of Bordeaux I. The objective of the study is the definition and the realization of a complete tool for the process assignment in multiprocessor architecture with separate memory (the CHEOPS computer). The tool is to be included in the programming environment of the multiprocessor CHEOPS.

Reviewer: E.Savin

MSC:

68N99

Theory of software

Keywords:

process allocation; multiprocessor architectures; process assignment; pyramidal architecture