MINATEC

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 sur ces architectures.

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 sur ces architectures. 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 sur puce, à 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. 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, notamment par exemple des résultats récents sur les méthodes de projection obtenus sur un problème voisin. Enfin, pour les instances de grandes tailles, on s'intéressera à la conception d'heuristiques couplées à des bornes globales permettant de s'assurer de la qualité des résultats fournis par ces derniers algorithmes.