Problèmes de plus courts chemins dans les NoC et leurs extensions aux cas difficiles

We define and study a combinatorial optimization problem that models multi-path routing in a Network-on-Chip with guaranteed traffic. Based on time division multiplexing, the model allows to avoid collisions, deadlocks and livelocks in irregular network topologies, while minimizing latency. An extension of this multi-path problem is also presented that allows dynamic reconfigurable routing at execution time. In that case, independent sets of valid routes are pre-computed in such a way they can be interchanged during execution with no impact on the existing traffic, while reusing all the vacant time-slot resources. A time-expanded graph approach is retained for the solution process. First, we present a set of basic shortest paths computation operators. They can be a greedy parallel construction heuristic, neighborhood operators, or a modified Dijkstra algorithm for single path computation in pseudo-polynomial time. Then, operators are introduced and combined within two heuristic methods able to address both problems, that is, an iterated construction heuristic and a population based evolutionary algorithm. Experiments are done on a set of benchmarks representative of real life applications, they illustrate the accuracy of the method.Nous définissons et étudions un problème d'optimisation combinatoire et un programme linéaire en nombres entiers, qui modélise le routage multi-chemin dans un réseau sur puce à garantie de trafic. Basé sur le multiplexage temporel et l'émission cyclique des messages, le modèle permet d'éviter les collisions, les blocages statiques et dynamiques dans des réseaux à topologie irrégulière, tout en minimisant les temps de latence. Une extension de ce problème de routage multi-chemin, qui permet une reconfiguration dynamique du routage au moment de l'exécution est également présentée. Dans ce cas, des ensembles indépendants de chemins valides sont pré-calculés de telle sorte qu'ils peuvent être inter-changés en cours d'exécution sans impact sur le trafic courant, tout en réutilisant tous les intervalles de temps dont les ressources sont vacantes ou libérées. L'approche du graphe spatio-temporel étendu est retenue dans les processus de résolution. Tout d'abord, nous présentons un ensemble d'opérateurs de base de calcul de plus courts chemins. Se sont une heuristique de construction parallèle gloutonne, un opérateur de voisinage, et un algorithme de Dijkstra modifié dans un graphe spatio-temporel étendu qui calcul un chemin unique dans un NoC occupé en temps pseudo-polynomial. Ensuite, pour résoudre l'ensemble des problèmes, les opérateurs sont introduits et combinés dans trois méthodes de recherche locale itérée capable de générer rapidement des solutions admissibles, un algorithme évolutionnaire à base de population solutions conférant une grande diversité à la recherche de solutions et un algorithme mémétique, tirant partie des avantages des deux précédents. Les expériences sont réalisées sur un ensemble d'instances d'applications réelles, et d'instances d'applications artificielles générées aléatoirement à partir des cas réels, pour illustrer les performances et la robustesse des méthodes de recherche