🤖 AI

Order Matters: Unveiling the Hidden Impact of Macro Placement Sequences via Proxy-Guided LLM Evolution

Cet article présente OrderPlace, un cadre d'évolution de LLM guidé par proxy qui découvre automatiquement les séquences de placement de macros optimales pour surmonter les limites des heuristiques statiques, atteignant des réductions significatives de la longueur de câblage sur les benchmarks ISPD 2005 par rapport aux méthodes de pointe.

Auteurs originaux : Shibing Mo, Jing Liu, Jianchu Xu, Ruilin Wu

Publié 2026-06-09

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shibing Mo, Jing Liu, Jianchu Xu, Ruilin Wu

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de charger un camion de déménagement. Vous avez un mélange de vases fragiles, de canapés lourds et de boîtes aux formes irrégulières. Le but est de tout faire entrer sans rien casser et de s'assurer que les fils reliant vos appareils électroniques (comme une télévision et un système de sonorisation) ne soient pas trop tendus.

Dans le monde de la conception de puces informatiques, ce « camion de déménagement » est la puce elle-même, les « boîtes » sont les macros (les grands blocs de circuits) et les « fils » sont les connexions électriques. Le processus consistant à décider où placer ces blocs est appelé Placement de Macros (Macro Placement).

Pendant longtemps, les ingénieurs et les programmes informatiques se sont concentrés sur l'endroit où placer les blocs. Mais ils ont largement ignoré l'ordre dans lequel ils les placent. Ils supposaient que l'ordre n'avait pas beaucoup d'importance, ou ils choisissaient un ordre au hasard.

Cet article, intitulé « Order Matters » (L'ordre compte), soutient que l'ordre est en réalité l'élément le plus critique de l'énigme. Voici la décomposition de leur découverte et de leur solution :

1. L'effet domino d'un mauvais ordonnancement

Les auteurs expliquent que le placement de ces blocs est un processus séquentiel. On en place un, puis le suivant, puis le suivant.

L'analogie : Imaginez que vous essayiez de construire un château de cartes. Si vous placez les premières cartes aux mauvais endroits, vous pourriez vous empêcher de placer les cartes suivantes plus tard. Vous pourriez vous retrouver avec un tas qui semble correct au début, mais qu'il est impossible de terminer, ou vous devrez étirer les « fils » (les connexions) à travers toute la pièce juste pour connecter deux pièces qui ont été séparées trop tôt.
L'affirmation : L'article prouve mathématiquement que si vous choisissez un mauvais ordre dès le début, cela crée un « effet domino ». Cela force le reste du placement dans un état sous-optimal, rendant impossible la recherche de la meilleure solution, peu importe l'intelligence de l'ordinateur par la suite.

2. Le problème : Les tests sont trop lents

Si vous voulez trouver l'ordre parfait pour charger votre camion, vous pourriez vous dire : « Essayons tous les ordres possibles ! »

La réalité : Il y a trop de combinaisons. Tester chaque ordre possible pour voir lequel fonctionne le mieux prendrait des années à un supercalculateur. C'est trop coûteux et trop lent pour tester chaque idée.

3. La solution : OrderPlace (Le « Chef IA »)

Les auteurs ont construit un nouveau système appelé OrderPlace. Au lieu de laisser un humain deviner l'ordre, ou d'utiliser une règle simple (comme « mettre les objets les plus gros en premier »), ils ont utilisé un Modèle de Langage Étendu (LLM) — le même type d'IA qui écrit du code et répond à des questions — pour agir comme un « Chef IA » inventant de nouvelles recettes pour l'ordonnancement.

Voici comment cela fonctionne :

La cuisine évolutive : L'IA commence avec quelques « recettes » de base (des règles d'ordonnancement, comme « mettre les blocs les plus gros en premier » ou « mettre les blocs les plus connectés en premier »).
Le test de goût (Évaluation par procuration) : Au lieu de cuisiner tout le repas (exécuter le processus complet et lent de conception de la puce) pour voir si une recette est bonne, l'IA utilise une procuration légère (proxy). Considérez cela comme un « test de goût rapide ». Elle simule une version simplifiée du processus de placement pour voir si l'ordre semble prometteur. C'est rapide et peu coûteux.
L'évolution : L'IA examine les résultats des tests de goût. Elle prend les meilleures recettes, les mélange et se demande : « Comment puis-je rendre cela encore meilleur ? ». Elle génère ensuite de nouvelles règles (code) plus complexes à essayer. Elle répète ce processus, faisant évoluer de meilleures stratégies d'ordonnancement au fil du temps.

4. Ce qu'ils ont trouvé

L'IA n'a pas seulement trouvé une règle légèrement meilleure ; elle a découvert des manières de penser entièrement nouvelles concernant l'ordre, que les humains n'avaient pas envisagées.

Les résultats : Lorsqu'ils ont testé cela sur des jeux de données standards de conception de puces (les ensembles de données « ISPD 2005 »), leur stratégie découverte par l'IA a battu les meilleures méthodes actuelles (comme EGPlace et WireMask-EA).
L'amélioration : Ils ont réduit la longueur totale des fils (longueur de fil/wirelength) de 14 % à 34 % par rapport aux meilleures méthodes précédentes. Dans la conception de puces, même une amélioration de 1 % est énorme ; 34 % est un bond colossal.

5. La « Recette Secrète »

L'IA a découvert que les meilleures stratégies n'étaient pas statiques (fixes). Au contraire, elles étaient dynamiques.

Règle statique : « Toujours mettre le plus gros bloc en premier. »
Règle dynamique (découverte par l'IA) : « Au début, mettre les plus gros blocs. Mais à mesure que nous arrivons à la moitié du processus, passer aux blocs qui sont connectés à ceux que nous venons de placer. Si un groupe de blocs est presque entièrement connecté, terminez ce groupe immédiatement. »

L'IA a appris à adapter sa stratégie en fonction de la progression du « chargement », tout comme un chargeur qualifié qui change son approche à mesure que le camion se remplit.

Résumé

L'article affirme que l'ordre dans lequel on place les composants sur une puce est un levée cachée pour l'optimisation qui a été ignorée. En utilisant une IA pour inventer et faire évoluer automatiquement de nouvelles stratégies d'ordonnancement — en utilisant un « test rapide » pour filtrer les mauvaises idées — ils ont trouvé un moyen de charger les puces beaucoup plus efficacement que jamais, réduisant considérablement la longueur des fils nécessaires pour les connecter.

Ils n'ont pas prétendu que cela résout tous les problèmes de puce ou s'applique à d'autres domaines ; ils ont spécifiquement démontré que l'optimisation de la séquence de placement est une dimension puissante et inexploitée pour créer de meilleures puces informatiques.

Résumé Technique : OrderPlace

Énoncé du Problème

Le placement de macros est une étape critique dans la conception physique moderne des puces, dictant fondamentalement la qualité, la performance et la manufacturabilité du circuit intégré final. Formellement, il s'agit d'un problème d'optimisation combinatoire à grande échelle nécessitant la détermination des positions physiques des macros au sein d'un canevas fixe sans chevauchement. Bien que les récentes avancées en apprentissage automatique aient accéléré la détermination des coordonnées, la dimension temporelle du séquençage de placement (c'est-à-dire l'ordre dans lequel les macros sont placées) reste largement régie par des heuristiques statiques ou des permutations aléatoires.

L'article soutient que le séquencement de placement n'est pas simplement une étape de prétraitement, mais un facteur décisif de l'optimisation. Dans les processus de placement séquentiels, les premières décisions définissent les conditions limites de faisabilité pour toutes les macros suivantes. Une seule décision sous-optimale tôt dans la séquence peut déclencher un « effet domino » irréversible, contraignant l'espace de solution et menant à de mauvais optima locaux. Malgré cela, les méthodes existantes se concentrent principalement sur la question spatiale du « Où placer ? » tout en traitant la question temporelle du « Qui passe en premier ? » comme un a priori fixe. De plus, explorer l'impact du séquencement est notoirement difficile car le signal d'ordonnancement est souvent masqué par de puissantes méthodes de raffinement, et l'évaluation d'une séquence unique nécessite généralement d'exécuter un cycle complet de placement, ce qui est extrêmement coûteux en calcul.

Méthodologie : OrderPlace

Pour relever ces défis, les auteurs proposent OrderPlace, un cadre d'évolution guidé par un modèle de langage étendu (LLM) et par procuration (proxy), conçu pour découvrir automatiquement des stratégies d'ordre de placement de macros. Le cadre opère à travers trois composantes principales :

1. Stratégies de Placement Initiales

Le cadre initialise une population de stratégies pour fournir un espace de recherche diversifié. Celles-ci sont catégorisées en :

Stratégies Statiques : Calculent les priorités basées uniquement sur des caractéristiques géométriques et topologiques au niveau de la macro (ex: surface, degré, connectivité des nets).
Stratégies Dynamiques : Adaptent les priorités en fonction de l'évolution de l'état de placement, souvent inspirées par la dynamique physique (ex: potentiels de ressort, modèles de champ, réduction d'entropie).

2. Évolution des Stratégies pilotée par LLM

OrderPlace utilise des LLM (ex: GPT-4, DeepSeek-V3, Claude) pour faire évoluer des stratégies d'ordonnancement au niveau du code. Le processus implique :

Ingénierie de Prompt : Le LLM reçoit des prompts système définissant le rôle d'un expert en VLSI et des prompts utilisateurs contenant les résultats d'évaluation des meilleures stratégies précédentes (Top-K) de la génération précédente.
Génération de Code : Le LLM génère de nouvelles classes Python représentant des stratégies de placement, soit sous forme de trieurs statiques, soit sous forme de fonctions de priorité dynamiques.
Boucle Évolutive : Le cadre maintient une population de stratégies à travers les générations. Il sélectionne les stratégies Top-K basées sur des scores de fitness et les utilise comme contexte pour générer de nouvelles stratégies candidates, favorisant la découverte de nouvelles combinaisons et de mécanismes dynamiques.

3. Évaluation Guidée par Procuration (Proxy)

Pour atténuer le coût prohibitif d'une optimisation complète pour chaque candidat, OrderPlace introduit un mécanisme d'évaluation par procuration léger :

Procédure Gloutonne Guidée par Masque de Fils (Wire-Mask) : Au lieu d'une optimisation complète, les stratégies sont évaluées à l'aide d'un algorithme de placement glouton déterministe guidé par des masques de longueur de fils précalculés.
Monte Carlo Parallèle : Chaque stratégie est exécutée sur plusieurs graines initiales aléatoires en parallèle pour générer une distribution de résultats de longueur de périmètre de demi-périmètre (HPWL).
Score de Fitness : La fitness d'une stratégie est la moyenne de la HPWL sur les exécutions réussies. Un mécanisme de timeout et une validation de syntaxe garantissent l'efficacité et la robustesse.

Une fois que la recherche évolutive est terminée, les stratégies Top-K subissent un ajustement fin via la procédure gloutonne guidée par le masque de fils pour produire les résultats de placement finaux.

Contributions Clés

Changement de Perspective : L'article fournit des preuves théoriques et empiriques que la séquence de placement est une dimension critique, bien qu'historiquement négligée, de l'optimisation. Il démontre qu'un ordonnancement sous-optimal conduit à une dégradation asymptotique de la qualité de la solution (ex: dégradation de $\Omega(l)$ pour les topologies en chaîne et $\Theta(g)$ pour les topologies en étoile).
Innovation Méthodologique : OrderPlace est le premier cadre évolutif piloté par LLM spécifiquement conçu pour le séquençage de placement de macros. Il intègre avec succès l'évaluation par procuration pour résoudre le défi des boucles de rétroaction coûteuses dans l'optimisation du floorplanning.
Découverte de Nouvelles Stratégies : Le cadre découvre des algorithmes de tri généralisables allant des heuristiques statiques à des règles dynamiques complexes inspirées de la physique (ex: modèles gravitationnels, réduction d'entropie et priorisation de la fermeture de nets) qui surpassent les heuristiques conçues manuellement.

Résultats Expérimentaux

Les auteurs ont évalué OrderPlace sur la suite de benchmarks standard ISPD 2005 (huit conceptions de puces).

Performance : OrderPlace a obtenu les meilleures (plus basses) valeurs de HPWL sur 7 des 8 circuits.
Comparaisons :
- Comparé à WireMask-EA, OrderPlace a réduit la longueur de fil de 34,04 %.
- Comparé à la méthode de pointe EGPlace, OrderPlace a réduit la longueur de fil de 14,08 %.
- Dans une comparaison directe utilisant le test de rang de Wilcoxon, OrderPlace a performé de manière significative sur 7 circuits par rapport à EGPlace.
Convergence : OrderPlace a démontré une efficacité de calcul remarquable, convergeant nettement plus vite que EGPlace. La meilleure stratégie découverte atteignait systématiquement des points de convergence plus bas plus tôt dans la trajectoire d'optimisation.
Congestion et Taille Mixte : OrderPlace a également montré une routabilité supérieure (congestion) et a atteint des performances de premier plan dans les tâches de placement de tailles mixtes lorsqu'il est combiné avec un placeur global (DreamPlace).
Impact du LLM : Les études d'ablation ont confirmé que les stratégies générées par LLM surpassaient systématiquement toutes les stratégies initiales conçues à la main, indiquant que le gain de performance provient de la découverte de politiques d'ordonnancement non triviales au-delà des heuristiques existantes.

Signification et Revendications

L'article affirme qu'OrderPlace représente la première preuve systématique que le séquençage de placement, traditionnellement considéré comme une étape de prétraitement statique, sert de déterminant critique dans l'optimisation de placement. En automatisant la découverte de stratégies d'ordonnancement via les LLM et l'évaluation par procuration, la méthode atténue efficacement la sous-optimalité dans le placement basé sur la décision de séquence.

Les auteurs soulignent que leur approche se distingue des travaux précédents qui traitent le séquençage comme un a priori fixe ou s'appuient sur des agents de RL pour apprendre implicitement les séquences. Au contraire, OrderPlace optimise explicitement la séquence d'entrée comme un hyperparamètre. Le travail suggère que le potentiel d'optimisation du séquencement de placement est une dimension « dormante » qui, lorsqu'elle est débloquée, peut fondamentalement accélérer les solveurs gloutons et déverrouiller de meilleures solutions globales.

Limites : L'étude est actuellement limitée à l'évaluation de l'impact de l'ordre de placement sur les méthodes gloutonnes guidées par masque. L'interaction avec les méthodes stochastiques basées sur l'apprentissage reste inexplorée, et des travaux futurs sont proposés pour étudier comment l'ordonnancement de placement peut améliorer les méthodes de placement pilotées par apprentissage profond.