DÉCOMPOSITION D'UNE APPLICATION SUR UNE ARCHITECTURE BUS : PROPRIÉTÉS DES ORDONNANCEMENTS OPTIMAUX

摘要

Cet article porte sur des problèmes liés à l'exécution d'une application sur une machine multiprocesseurs à architecture bus ayant un processeur maître et des processeurs esclaves. Le problème le plus sérieux, est la congestion du bus : à tout instant seul un des processeurs esclaves peut communiquer avec le maître. Un second problème est de maintenir actifs les processeurs. L'application est supposée décomposable en tâches qui seront envoyées aux processeurs esclaves par le maître. De plus, par hypothèse, le temps de calcul de chaque tâche est une fonction linéaire de son volume de données. L'objectif est de minimiser la durée totale de l'exécution en tenant compte des temps de calcul et des temps de communication. Nous étudions d'abord les propriétés des ordonnancements optimaux. Puis nous nous intéressons à deux cas particuliers avec des temps de calcul proportionnels aux volumes de données : un processeur recevant plusieurs tâches et deux processeurs recevant une seule tâche. Pour conclure, nous remarquons que la méthodologie que nous avons élaborée pourrait s'appliquer sous des hypothèses plus générales.%A bus oriented multiprocessor contains one bus system to which all the processors are connected. There are one master and several slaves. The most serious problem is the bus bottleneck. At a time, only one slave can establish communications through the bus with the master. A second problem is to maintain busy each processor. We suppose we have to execute a task which uses a big amount of data and which can be split into several independent processes. Moreover, the processing time of each process is a linear function of its amount of data. The objective is to minimize the makespan by taking into account communication durations and processing times. At first, the properties of optimal schedules are studied. Next, two particular cases with task computation times proportional to their amounts of data are considered. In the first case, we have one slave and several processes sent to it. So, the processor can compute in masked time after the reception of the first amount of data. In the second case, we have two slaves and only one process is sent to both of them. Finally, we remark that this approach can be generalized.