Retour au site du LAAS-CNRS

Résumé

Ce mémoire d'Habilitation à Diriger des Recherches présente notre contribution à l'algorithmique parallèle. Il porte plus particulièrement sur l'étude théorique et pratique du concept d'asynchronisme, le choix du type de synchronisation entre les processus de calcul étant un des facteurs majeurs qui préside à la conception d'algorithmes itératifs parallèles efficaces. Les différents aspects liés à la modélisation mathématique, l'étude de la convergence et de la terminaison des algorithmes itératifs asynchrones sont tour à tour traités. Chaque fois, nos résultats sont situés par rapport aux principales contributions au domaine. Nous présentons également plusieurs mises en oeuvre des itérations asynchrones sur machines à mémoire distribuée telles que le supercalculateur Cray T3E et le Tnode, sur machine à mémoire partagée telle qu'un multiprocesseur symétrique, ainsi que sur un réseau de stations de travail. Diverses applications sont considérées : des problèmes d'optimisation de type flot dans les réseaux des systèmes Markoviens, et des problèmes aux limites. Les performances des algorithmes itératifs asynchrones sont étudiées en fonction de facteurs particulièrement importants tels que la granularité des tâches, l'équilibrage des charges, les bibliothèques de communication utilisées, et le type d'architecture.

Abstract

This dissertation presents our contribution to parallel computing. More precisely, it deals with the theoretical and practical study of the concept of asynchronism, the question whether to synchronize or not computational tasks being one of the major problems that occur in the design of efficient parallel iterative algorithms. Mathematical modelling, study of convergence and termination of asynchronous iterations are considered. At each time, the main contributions to the field are presented. Several implementations of asynchronous iterative algorithms on distributed memory architectures such as the Cray T3E and Tnode, shared memory machines such as a symmetric multiprocessor and also a network of workstations are presented Various applications are treated: minimum cost flow problems, Markovian systems, boundary value problems. The performance of asynchronous iterative algorithms is studied in function of important factors such as granularity of tasks, load balancing, communication library and type of architecture.

Mots-Clés / Keywords

Multiprocesseur symétrique; Cray T3E; Problèmes aux limites; Systèmes Markoviens; Problèmes de flot de coût minimum; Itérations asynchrones; Algorithmique parallèle; Parallel computing; Asynchronous iterations; Minimum cost flow problems; Markovian systems; Boundary value problems; Symmetric multiprocessor;