Résumé:
Avec l'avènement du développement technologique, il est actuellement possible d'intégrer des millions de transistors sur la même puce. Outre cet avantage, les délais des portes logiques deviennent de plus en plus courts à cause de la commutation rapide des transistors due à des tensions de seuil des transistors de plus en plus réduites. A côté de ces avantages, il existe malheureusement de nombreux problèmes auxquels les concepteurs doivent y faire face. Nous nous contentons de citer uniquement le problème en relation avec le contexte de ce projet. Les courbes de l’ITRS (International Technology Roadmap for Semiconductors) concernant les délais des portes logiques et des interconnexions montrent clairement que le premier type de délais ne cesse de s'améliorer au fur et à mesure que la longueur du canal du transistor se réduit. Malheureusement, ceci n'est pas le cas pour les interconnexions : la communication devient de plus en plus lente avec le développement technologique. Bien que des solutions partielles aient été trouvées telles que l'insertion d'amplificateurs, le remplacement de l'Aluminium par du Cuivre (IBM 2001), le problème se pose toujours. De plus, avec les systèmes actuels devenant de plus en plus complexes et se caractérisant par un fort degré de communications, il est devenu impossible d'utiliser un bus classique du fait que celui-ci est une ressource critique et partagée, ce qui considérablement réduit la bande passante. Une solution intermédiaire a été trouvée (utilisation de barres croisées -cross-bars-) mais reste néanmoins insuffisante. Il a donc fallu opter pour une meilleure solution, celle consistant à concevoir un réseau spécifique à l'application, répondant aux contraintes de largeur de bande, de consommation de puissance et de surface. Plusieurs méthodologies ont été proposées, dont les principales sont celles reposant sur les Fat Trees, les Mesh Networks et d'autres variantes de ces méthodologies. Dans le cadre d'un projet mené au CDTA, une autre méthodologie a été proposée et pour laquelle des tâches la réalisant sont en cours de développement.
Parmi ces tâches, une méthode de placement des IPs (composants) (Intellectual Property) du système a été réalisée. C'est une méthode exhaustive qui a pour avantage d'être exacte, mais ne peut être utilisée pour un nombre appréciable d'IPs du fait du temps CPU qu'elle engendre.
Afin que cette tâche de placement soit valable pour un système comportant un nombre quelconque de composants, ce travail consiste à développer une heuristique qui résou ce problème en un temps polynomiale.
Mots clés : heuristique, kernighan-lin, VLSI, optimisation combinatoire, partitionnement de graphes
