Conception d'une machine virtuelle pour les systèmes parallèles à diffusion

Performances of programs on distributed memory parallel machines are highly dependent of the efficiency of interprocessor communications. Parallel programming environments often offer poor support for high level communication models. This thesis deals with high level group communications in such architectures. This problem has two main aspects : first, correct and efficient handling of message exchanges for diffusion between processors, second, construction of group communication protocols for processes. We first address the problem of correct message passing within diffusion exchanges on top of efficient and correct routing functions. The proposed solution is general and is independent of the representation of the routing function, and it is independent from the topology of the interconnection network. Moreover constant memory space is required to prevent deadlocks in general networks. Futhermore, using interval labelling to represent the routing function, we show how our diffusion method can be integrated in a routing processor. Secondly, we consider the construction of high level diffusion protocols (synchronous, asynchronous), and propose a diffusing virtual machine for the parallel generic kernel ParX developped by our group. Our virtual machine is based on two diffusion protocols which can be used to correctly and efficiently build most of existing global communication schemes. The protocol interface offers primitives for coherent management of process groups, message exchanges and control (broadcasting and scattering). Our virtual machine is designed to be a minimal support to efficiently and correctly implement different existing group communication interfaces and libraries (PVM, MPI, etc.). The set of proposed solutions has been integrated in the prototype version of the ParX kernel, and some performances evaluated.Dans les machines parallèles les performances des programmes posent de manière cruciale le problème de l'efficacité des communications dans les réseaux d'interconnexion des processeurs d'une machine sans mémoire commune. Les communications point-à-point ne sont qu'un cas très particulier des schémas de communications complexes utilisés par les applications. Les communications globales, basées sur la construction correcte de protocoles à diffusion, sont une classe de ces schémas de communication. Ce problème comprend deux aspects : l'acheminement des messages pour la diffusion et la construction de protocoles de communication/synchronisation inter-processus. Nous considérons d'abord le problème de l'acheminement pour la diffusion, que nous construisons à partir d'une fonction de routage correcte pour des réseaux généraux de topologies quelconques. La famille d'algorithmes de diffusion obtenus s'adapte à la fois à la représentation de la fonction de routage, et à la topologie d'interconnexion entre processeurs. Un aspect de l'efficacité des algorithmes produits est l'espace mémoire nécessaire à une telle fonction de routage à diffusion. Nous développons des algorithmes qui requierent un espace mémoire constant et qui de plus, en utilisant une représention par intervalles de la fonction de routage, peuvent être intégrés dans un circuit routeur. Nous nous intéressons ensuite à la construction de divers types de protocoles à diffusion (synchrone et asynchrone) et proposons une machine virtuelle parallèle à diffusion (PDVM). Cette machine virtuelle s'inscrit dans l'architecture du micro-noyau pour systèmes parallèles ParX, développé par notre équipe, qui offre un support d'exécution générique pour de multiples machines virtuelles. PDVM se présente sous la forme de deux de protocoles nécessaires à l'élaboration de la plupart des schémas de communication par diffusion. L'interface d'accès à ces protocoles permet de gérer des groupes de processus à diffusion toujours cohérents. Dans sa conception cette machine virtuelle est un support minimal pour implémenter efficacement et correctement les diverses interfaces et bibliothèques de communications globales pour les standards de programmation parallèle qui émergent (PVM, MPI, etc.). L'ensemble des solutions proposées a été intégré dans le prototype de ParX; et leurs résultats d'évaluation de performances sont produits