Abstract FR:

Ce mémoire propose une approche originale au trace automatique des interconnexions d'un circuit intégré constitue de blocs fonctionnels rectangulaires. On y retrouve les articulations habituelles des approches hiérarchiques propres à ce domaine: routage des alimentations, routage global et routage local. Néanmoins chacune de ces étapes est traitée de manière nouvelle, avec le souci de répondre aux insuffisances des travaux précédents. Le routeur local appartient à la famille des routeurs de boitiers de connexion. Il suppose l'existence de deux niveaux d'interconnexion. Sa stratégie est la suivante: 1) dans un premier temps les équipotentielles à traiter sont décomposées en sous-équipotentielles. Déterminer une trace pour chacune d'elles revient alors à résoudre un ensemble de sous-problèmes interdépendants, 2) ces interdépendances sont analysées par un ensemble d'experts qui permettent conjointement d'ordonner le traitement des sous-problèmes et de leur trouver une solution. Le routage global du circuit est effectué sur un nouveau partage de l'espace disponible. Celui-ci, associe au routeur local précédemment introduit, permet de gérer efficacement les intersections de canaux. Les propriétés de ce découpage sont analysées, notamment sa résistance en cours de routage aux déplacements de blocs. Une nouvelle technique de traitement des alimentations est décrite. Elle garantit une solution sans croisement si celle-ci existe. Les deux alimentations sont routées indépendamment dans un premier temps. Les croisements sont ensuite repérés puis élimines itérativement par reconfiguration de l'une ou de l'autre équipotentielle. Des détails d'implémentation sont présentes et discutes. De nombreux exemples significatifs sont rapportés et compares.