Retour au site du LAAS-CNRS

Résumé

L'interconnexion de ressources de calcul réparties sur différents sites par des réseaux longue distance à haut débit permet aujourd'hui de réaliser des plates-formes de calcul intensif pouvant atteindre plusieurs teraflops. L'exploitation efficace de telles architectures suppose l'utilisation de politiques de gestion des ressources permettant de dégager la puissance maximale disponible à tout instant. La complexité dans l'étude de telles politiques provient du caractère dynamique et aléatoire des accès concurrents aux ressources. Les travaux développés dans cette thèse se décomposent en 2 niveaux de problématique: la conception et l'exploitation optimale du réseau d'interconnexion inter-sites (dimensionnement, routage, modélisation des trafics) et l'exploitation optimale des ressources de calcul et de mémoire par les tâches des applications parallèles (placement de tâches, équilibrage de charge, adaptation du nombre de processeurs, gestion mémoire). Nous développons plusieurs modèles (linéaires et non-linéaires) pour la résolution du dimensionnement et du routage optimal dans les anneaux longue distance SDH. Ensuite, à partir de l'étude fine de plusieurs types de files d'attente, nous développons les équations différentielles régissant l'état moyen du système. Ces équations permettent de bâtir un modèle général dynamique du trafic dans les réseaux à commutation de paquets et à commutation de circuits multi-classes. Nous démontrons notamment de nouveaux résultats théoriques pour les files M/D/1/N. Sur la base de ces modèles généraux, nous résolvons le problème du routage optimal à travers des topologies quelconques et nous montrons que certaines approches classiques pour les machines parallèles sont très loin de l'optimum. Nous résolvons le problème de placement optimal de tâches en tenant compte de l'hétérogénéité des réseaux et de la charge dynamique du système. Nous étudions ensuite théoriquement le problème de l'équilibrage de charge optimal pour des méthodes itératives partitionnées. Cette partie se termine par l'étude du nombre de processeurs devant être alloués à plusieurs applications parallèles et du découpage de ces processeurs. D'un point de vue plus microscopique, nous traitons le problème de l'utilisation optimale de la mémoire des processeurs pour les échanges de messages entre tâches. Une des applications visées pour ce type d'architectures est la méthode de filtrage non-linéaire particulaire. Dans une dernière étape, nous développons un algorithme parallèle pour cette méthode. Nous présentons les résultats obtenus sur un cluster myrinet de PC et les comparons avec ceux des machines parallèles du marché. Ces résultats permettent d'extrapoler la taille de la machine distribuée susceptible de résoudre en temps réel des problèmes de filtrage.

Abstract

Distributed computing with the interconnection of several sites by wide area high-speed networks allows to build new architectures capable to deliver several Teraflops. However, the optimal exploitation of such architectures needs resource management policies allowing to get the maximum computing power avaible. The complexity in the study of these policies arise from the dynamical and random features of concurent resource accesses. The studies developped in this thesis adress the problems related to (1) the optimal design and exploitation of inter-sites network (capacity assignment, routing, traffic modeling) and (2) the optimal exploitation of the computing and storage resources (task mapping, load balancing, memory managment). We develop several models (linear and non-linear) to solve the capacity assignment and optimal routing problems in SDH wide area networks. Then, from the study of several queueing systems, we develop the differential equations governing the average state of the system. These equations allow to build a general dynamical traffic model for packet switched networks and multiclass circuit switched networks. We give a particular emphasis on M/D/1/N queues for which we derive new theoretical results. Using these general models, we solve the optimal routing problem in interconnection networks of parallel machines and show that some classical approaches are far from beeing optimal. Then we study the task mapping problem and we propose a new algorithm taking into account the heterogeneity of the interconnection networks and the system load dynamic. We then study the load balancing problem from a theoretical point of view in the case of iterative applications. We also study the optimal number of processors which has to be allocated to several parallel applications and how to share the processors among the applications. From a more microscopic point of view, we study the problem of optimal memory accesses scheduling. One of the application well suited for this kind of architecture is the particle non-linear filtering method. In the last part of the thesis, we develop a parallel algorithm for this method. We compare the results obtained on a myrinet cluster of PC with those obtained on several parallel machines. These results allow to extrapolate the size of the distributed computer allowing to solve real-time filtering problems.

Mots-Clés / Keywords

Parallelism; Particle filtering; Memory managment; Load balancing; Task mapping; Routing; Capacity assignment; Mathematical programing; Stochastic modeling; Parallélisation; Filtrage particulaire; Gestion mémoire; Equilibrage de charge; Placement de tâches; Routage; Dimensionnement; Programmation mathématique; Modélisation stochastique;