Partitionnement de graphes pour de la simulation distribuée de réseaux de files d'attente

Encadrement :

Françoise Baude

Courrier électronique :

fbaude@sophia.inria.fr

Téléphone :

04 93 65 76 71

Adresse :

INRIA Sophia-Antipolis

Laboratoire d'accueil : INRIA Sophia Antipolis

Projet: SLOOP

Matériel et logiciel utilisé :

Unix, C, C++, PVM

Connaissances pré-requises :

Cours d'algorithmique parallèle et distribuée, PVM, C++, Simulation répartie, Aspects théoriques liés aux problèmes de partitionnement et placement de graphes de tâches

Objectifs :

Ecriture d'un outil de placement d'objets actifs C++ réalisant de la simulation distribuée de systèmes à événements discrets

Description du sujet :

L'objectif central du projet SLOOP est de développer des méthodes et des outils permettant l'utilisation efficace de machines multi-processeurs pour la simulation de systèmes à événements discrets. La réalisation de cet objectif implique la poursuite de recherches de haut niveau dans les domaines des langages à objets parallèles, des nouvelles méthodes de simulation et de la communication dans les architectures parallèles.

Le point clé d'une simulation efficace d'un réseau de files d'attente dépend du placement des différents objets actifs sur les processeurs disponibles. Ces objets actifs représentent des serveurs ou des clients leur demandant des services.

Pour ce faire, le travail consistera

• tout d'abord à construire un graphe pondéré par les coûts de service et les coûts de demande de service, représentant les interactions entre ces objets. Ce graphe pourra être construit à l'aide d'annotations du code C++ données par le programmeur, ou mieux grâce à une interface graphique adéquate.
• Ensuite, il faudra développer et analyser une ou plusieurs heuristiques de partitionnement de tels graphes en groupes (clusters) d'objets étant donné le nombre de processeurs disponibles et la vitesse des liens de communication les connectant. L'objectif de ce regroupement est de minimiser les coûts de communication tout en utilisant au mieux la puissance de calcul disponible.
• Finalement, comme le graphe initial construit peut ne pas refléter tout le comportement de la simulation (qui est probabiliste, et donc quelque peu imprévisible), il faut prévoir un mécanisme permettant de réactualiser le graphe en cours de simulation. Il est alors envisageable de stopper la simulation, de procéder à un nouveau partitionnement qui impliquera peut-être le déplacement de certains objets, puis de poursuivre la simulation.