Abstract FR:

Cette these concerne les systemes multiprocesseurs mimd sans memoire partagee, le reseau de communications pouvant etre: soit a liaisons point-a-point, soit a proprietes sensiblement isotropes, par exemple un reseau local. Elle vise a l'optimisation en moyenne de l'execution d'une classe de programmes paralleles, assez generale, dont on ne connait pas le graphe de dependances causales detaille entre taches, mais seulement le graphe non oriente des volumes globaux de communications. En effet les programmes comportent des boucles et alternatives, et le comportement, qui depend des donnees, n'est previsible que statistiquement. On recherche une maximisation de la quantite moyenne de traitements effectues en moyenne par unite de temps. L'optimisation est recherchee par le groupement des taches en des agregats de taches communiquant beaucoup entre elles, et peu ou moins avec celles des autres agregats. Ce groupement est obtenu par un multipartitionnement du graphe de communications, en des parties de nombre et de cardinalites non fixes a priori. La these etablit, selon un modele d'execution approche largement accepte, la possibilite de definir un nombre optimum de processeurs lorsque le graphe presente un caractere de localite. Elle precise des criteres d'evaluation d'un multipartitionnement, et ameliore une methode pour l'obtenir. Elle propose deux parallelisations de la methode, sur deux architectures multiprocesseurs de principes differents: une machine mimd sans memoire partagee, une machine massivement parallele de type simd. On peut ainsi obtenir un groupement de taches, sur une des machines-cible elle-meme, ou sur un serveur de calcul parallele si le reseau en comporte un. Les gains possibles sur l'execution des programmes paralleles places ainsi par simple groupement, sont de l'ordre d'un facteur 2. Cette evaluation experimentale est obtenue par des simulations de portee generale, adaptee a la classe de programmes visee representes par des graphes de communications aleatoires et deroulees en situation reelle sur une des machines-cible