Description
Date depot: 1 janvier 1900
Titre: Nouveaux modèles de partitionnement de graphes pour le placement/routage sur architectures massivement parallèles
Directeur de thèse:
Renaud SIRDEY (CEA)
Directeur de thèse:
Michel MINOUX (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
L’apparition, ces dernières années, d’architectures de processeur dites « many-core », c’est-à-dire intégrant plusieurs centaines voire milliers de cœurs de calcul au sein d’une même puce, a ouvert un nouveau domaine d’application pour les problèmes de partitionnement de graphes. En effet, cette classe de problèmes est au cœur de l’étape dite de placement/routage d’applications (souvent mais pas nécessairement flot de données) sur ces architectures. Pour se fixer les idées, une application, dans un système many-core, est souvent modélisée un réseau de processus de type « flot de données » (dataflow process network). Ce dernier consiste simplement en des ensembles de tâches qui communiquent via des canaux FIFO unidirectionnels de données non bornés. Un tel réseau peut être modélisé par un graphe orienté dont les sommets sont les tâches et dont les arcs sont les canaux de communication. L’affectation concrète des calculs dans un tel système commence en première phase par une partition du réseau de processus en clusters respectant des contraintes de ressources de type sac à dos (mémoires, taux d’occupation de processeurs) et minimisant les communications inter-clusters sur tout le réseau. Ce problème dans sa version la plus simple (une seule ressource à partager) est amplement étudié et connu sous le nom de Node Capacitated Graph Partionning Problem dans la littérature. Le problème dans le contexte multi-contraintes (plusieurs ressources différentes à partager, e.g. mémoires, taux d’occupation de processeur…etc.) est plus complexe, et peut être soumis à des facteurs aléatoires comme par exemple le taux d’occupation de processeur. La résolution de ce problème a été objet de nombreux travaux notamment au sein de l’équipe « Calcul intensif embarqué » au CEA-Saclay [1]. Cependant, les premiers modèles étudiés ne reflètent que partiellement la complexité des architectures sous-jacentes et de nouveaux modèles plus complets sont nécessaires, modèles qui donnent lieu à de nouvelles variantes du problème de partitionnement de graphe qui seront étudiées dans le cadre de la thèse et pour lesquelles il conviendra de proposer des algorithmes adaptés.
Un premier objectif de la thèse est donc d’améliorer le réalisme des modèles par l'introduction de nouvelles contraintes par exemple destinées à garantir l'équilibre des communications inter-clusters dans le réseau, à prendre en compte d’autres type de contraintes de ressource, en particulier sur les arcs incidents aux partitions, ou encore à fournir des garanties de faisabilité quant au calcul des chemins de routage, post partitionnement. On étudiera également la possibilité d’intégrer dans les modèles étudiés des contraintes de nature probabiliste [5] ; de telles contraintes apparaissent naturellement dans les applications où par exemple la durée des tâches à placer sur les différents processus est aléatoire. Dans ce cas, on cherchera à satisfaire les contraintes de capacité avec un niveau de probabilité suffisamment proche de 1. On pourra également envisager l’application de modèle robuste [6],[7]. L'introduction de telles contraintes change significativement les propriétés mathématiques des modèles et requiert l'étude de nouveaux algorithmes de résolution.
Le second objectif sera d'établir de nouveaux algorithmes de résolution exacte pour les problèmes avec les nouvelles contraintes. On étudiera notamment les approches polyédrales et par branch-and-cut en s'inspirant des travaux précédents réalisés par nos équipes [1] [2] [3] [4], notamment par exemple résultats récents sur les méthodes de projection [2] obtenus sur un problème voisin.
Les problèmes de partitionnement étant fondamentalement très difficiles, la taille des applications que les méthodes exactes peuvent traiter est limitée par la complexité des algorithmes. Très certainement, les instances de taille réaliste, pouvant aller jusqu’au partitionnement de graphes à plusieurs milliers de sommets en plusieurs dizaines voire centaines de clusters , ne peuvent pas être résolues à l'optimum exact. Le troisième objectif de la thèse sera de concevoir des heuristiques efficaces pour le problème de partitionnement prenant en compte les nouvelles contraintes. Les algorithmes exacts précédemment mis au point serviront de références pour certifier expérimentalement la qualité des solutions heuristiques obtenues. On s’attachera tout particulièrement à obtenir des bornes globales permettant de s’assurer de la qualité des résultats fournis par les heuristiques proposées.
Bibliographie
1. Renaud Sirdey. « Contributions à l'optimisation combinatoire pour l'embarqué : des autocommutateurs cellulaires aux microprocesseurs massivement parallèles », Habilitation à Diriger des Recherches, Université de Technologie de Compiègne, 2011.
2. P. Bonami, V. H. Nguyen, M. Klein and M. Minoux 'On the Solution of a Graph Partitioning Problem under Capacity Constraints'. In LNCS, Vol. 7422, pp. 285-296 Spring
Doctorant.e: Nguyen Dang Phuong