Une vieille défaillance débusquée dans un algorithme classique

De nombreuses industries, dont les télécommunications, l’automobile, l’aérospatiale et la physique des particules, s’appuient sur un type particulier de puce appelé FPGA (Field-Programmable Gate Array, réseau de portes programmables in situ). Contrairement aux puces traditionnelles, les FPGA peuvent être reconfigurés presque à l’infini, ce qui les rend indispensables dans les domaines en pleine évolution où la conception d’une puce personnalisée prendrait des années et coûterait une fortune. Mais cette flexibilité s’accompagne d’un inconvénient: l’efficacité des FPGA dépend beaucoup du logiciel utilisé pour les programmer.

Depuis la fin des années 1990, un algorithme connu sous le nom de PathFinder est la base du routage FPGA. Sa tâche: connecter des milliers de petits composants de circuit sans créer de chevauchements. Pendant des décennies, il a si bien fonctionné qu’il est devenu la norme. Cependant, à mesure que les circuits grossissaient, les ingénieurs ont commencé à faire face à des ralentissements frustrants et à des défaillances ponctuelles. Les modèles qui auraient dû fonctionner étaient souvent étiquetés «impossibles à router».

Avec des collègues de l’Université de Novi Sad et du fabricant de semi-conducteurs AMD le Laboratoire d’architecture de systèmes parallèles (PARSA) de la Faculté informatique et communications ont fait un nouveau pas pour démêler les rouages de cet algorithme classique.

Dans leur article, qui a reçu le prix du meilleur article lors du 33^esymposium international de l’IEEE sur les machines informatiques personnalisées programmables sur le terrain, ils ont révélé pourquoi ces défaillances se produisent et comment les limites de PathFinder peuvent être surmontées.

Échecs de l’algorithme

«En fait, il n’est pas surprenant que PathFinder échoue parfois», explique Shashwat Shrivastava, doctorant au PARSA et principal auteur de l’article. «Très tôt, les équipes ont montré que le problème derrière le routage des FPGA est extrêmement complexe. Plus tard, les créatrices et créateurs de l’algorithme original, avec quelques collaboratrices et collaborateurs, ont trouvé des cas où PathFinder ne réussirait jamais, mais ils ont noté que de tels cas n’apparaîtraient pas dans la pratique.» Pendant des décennies, il semblait avoir raison – PathFinder fonctionnait étonnamment bien.

«PathFinder fonctionnait si bien que lorsqu’il échouait, les gens remettaient rarement en question l’algorithme. Au lieu d’aller voir ce qui se passait à l’intérieur, ils en ont modifié les paramètres, modifié les circuits ou sont passés à des FPGA plus grands», ajoute Stefan Nikolić, alumni de l’EPFL et aujourd’hui professeur à l’Université de Novi Sad. «Cela s’explique en partie par le fait qu’il est plutôt difficile de comprendre ce que fait PathFinder sur des exemples d’importance pratique. Les circuits modernes sont si grands que leurs signaux forment une véritable jungle sur puce.»

Bienvenue dans la forêt

«Nous devions donc regarder chaque arbre de cette jungle», poursuit Shashwat Shrivastava, et je parle bien d’arbres. «Chaque signal, c’est-à-dire une connexion qui transporte des informations entre les composants du circuit, doit atteindre plusieurs destinations sans chevaucher d’autres signaux. Le routage des FPGA consiste essentiellement à créer un arbre pour chaque signal sur la puce.»

Alors qu’elle travaillait sur un autre projet qui s’appuyait sur PathFinder, l’équipe continuait à obtenir des résultats qui défiaient l’intuition. Au début, les scientifiques ont rejeté la faute sur des facteurs externes, pas sur l’algorithme lui-même. Finalement, ils se sont rendu compte qu’ils avaient besoin d’exemples contrôlés: des petits cas difficiles où une solution existait certainement, et dans lesquels PathFinder devait réussir.

«Nous avions besoin d’exemples réels et pratiques, et en grande quantité, pour comprendre ce qui se passait réellement, explique Shashwat Shrivastava. Nous avons donc créé un cadre pour extraire automatiquement de petits problèmes difficiles de circuits réels. En observant comment PathFinder gérait ces problèmes, nous en avons découvert d’autres qui étaient restés cachés pendant très longtemps.»

La force du partenariat

«Cette avancée aurait été beaucoup plus difficile à réaliser sans le soutien de l’industrie», déclare Mirjana Stojilović, conseillère doctorante de Shashwat Shrivastava. «Dès le début, nous avons collaboré avec Chirag Ravishankar et Dinesh Gaitonde d’AMD. Ils nous ont aidés à modéliser les FPGA au plus près des dispositifs commerciaux, garantissant ainsi l’impact réel de nos découvertes.»

Une fois le cadre prêt, les choses ont évolué rapidement. L’équipe a constaté que PathFinder créait souvent des arbres de routage plus grands que nécessaire, augmentant ainsi le risque de chevauchement. Le problème venait de l’ordre dans lequel il créait et ajoutait de nouvelles branches aux arbres.

«Rétrospectivement, c’est intuitif, mais d’une manière ou d’une autre, cela est passé largement inaperçu pendant de nombreuses années», indique Shashwat Shrivastava. «Notre première solution était simple: essayer différents ordres et choisir celui qui donne le plus petit arbre. Expérimentalement, cela a étonnamment bien fonctionné.»

Perspectives d’avenir

L’équipe étudie maintenant des solutions plus évolutives. «Je suis particulièrement fière que les stagiaires du programme Summer@EPFL aient apporté une contribution significative. L’un d’eux, Sun Tanaka, est également coauteur de l’article», ajoute Mirjana Stojilović. «Notre découverte pourrait redéfinir la façon dont des millions de FPGA sont programmés et influencer la conception des futures générations de ces puces reconfigurables.»

Lire l’article: https://doi.ieeecomputersociety.org/10.1109/FCCM62733.2025.00060