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

We define and study a combinatorial optimization problem and mixed-integer linear programming, 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 and free time-slot resources. A time-expanded graph approach is retained for the solution process. First, we present a set of basic operators to compute shortest paths. They can be a greedy parallel construction heuristic, neighborhood operators, and a modified Dijkstra algorithm in a time expanded graph that allows computing a single path in an occupied Noc in pseudo-polynomial time. Then, to solve all the problems, operators are introduced and combined within three iterated local search methods that can quickly generate feasible solutions, an evolutionary algorithm based on population conferring diversity solutions in search of solutions and a memetic algorithm, taking advantage of the benefits of the previous two. Experiments are done on a set of benchmarks representative of real life applications, and instances of artificial applications randomly generated from real cases, to illustrate the performance and robustness of research methods.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.LORIENT-BU (561212106) / SudocSudocFranceF