Technische Samenvatting: OrderPlace

Probleemstelling

Macro-plaatsing is een cruciale stap in modern chip-physical design en bepaalt fundamenteel de kwaliteit, prestaties en produceerbaarheid van de uiteindelijke geïntegreerde schakeling. Formeel gezien is het een grootschalig combinatorisch optimalisatieprobleem waarbij de fysieke posities van macro's binnen een vast canvas zonder overlap bepaald moeten worden. Hoewel recente ontwikkelingen in machine learning de coördinatiebepaling hebben versneld, wordt de temporele dimensie van de plaatsingsvolgorde (d.w.z. de volgorde waarin macro's worden geplaatst) nog grotendeels beheerst door statische heuristieken of willekeurige permutaties.

Het artikel betoogt dat de plaatsingsvolgorde niet louter een voorverwerkingsstap is, maar een beslissende factor in de optimalisatie. In sequentiële plaatsingsprocessen definiëren vroege beslissingen de haalbare randvoorwaarden voor alle daaropvolgende macro's. Een enkele suboptimale plaatsing vroeg in de sequentie kan een onomkeerbaar "domino-effect" veroorzaken, waardoor de oplossingsruimte wordt beperkt en tot slechte lokale optima leidt. Ondanks dit focussen bestaande methoden zich voornamelijk op de ruimtelijke vraag "Waar te plaatsen?", terwijl de temporele vraag "Wie gaat eerst?" als een vaste prior wordt behandeld. Bovendien is het onderzoeken van de impact van sequencing berucht moeilijk, omdat het ordeningssignaal vaak wordt gemaskeerd door krachtige verfijningsmethoden, en het evalueren van een enkele sequentie doorgaans een volledige, computationeel prohibitieve plaatsingscyclus vereist.

Methodologie: OrderPlace

Om deze uitdagingen aan te pakken, stellen de auteurs OrderPlace voor, een proxy-gestuurd Large Language Model (LLM) evolutie-framework dat ontworpen is om strategieën voor macro-plaatsingsvolgorde automatisch te ontdekken. Het framework werkt via drie hoofdcomponenten:

1. Initiële Plaatsingsvolgorde-strategieën

Het framework initialiseert een populatie van strategieën om een diverse zoekruimte te bieden. Deze worden gecategoriseerd in:

• Statische Strategieën: Berekenen prioriteiten uitsluitend op basis van macro-niveau geometrische en topologische kenmerken (bijv. oppervlakte, graad, netwerkconnectiviteit).
• Dynamische Strategieën: Aanpassen prioriteiten op basis van de evoluerende plaatsingsstatus, vaak geïnspireerd door fysieke dynamica (bijv. veerpotentialen, veldmodellen, entropiereductie).

2. LLM-gestuurde Strategie-evolutie

OrderPlace maakt gebruik van LLM's (bijv. GPT-4, DeepSeek-V3, Claude) om code-niveau ordeningsstrategieën te evolueren. Het proces omvat:

• Prompt Engineering: De LLM krijgt systeemprompts die de rol van een VLSI-expert definiëren en gebruikersprompts die de evaluatieresultaten bevatten van de best presterende strategieën (Top-K) uit de vorige generatie.
• Code Generatie: De LLM genereert nieuwe Python-klassen die plaatsingsstrategieën vertegenwoordigen, als ofwel statische sorteerders of dynamische priorititeitsfuncties.
• Evolutionaire Loop: Het framework onderhoudt een populatie van strategieën over generaties heen. Het selecteert de top-K strategieën op basis van fitnessscores en gebruikt deze als context om nieuwe kandidaat-strategieën te genereren, wat de ontdekking van nieuwe combinaties en dynamische mechanismen bevordert.

3. Proxy-gestuurde Evaluatie

Om de prohibitieve kosten van volledige optimalisatie voor elke kandidaat te beperken, introduceert OrderPlace een lichtgewicht proxy-evaluatiemechanisme:

• Wire-Mask-Gestuurde Greedy Procedure: In plaats van volledige optimalisatie worden strategieën geëvalueerd met behulp van een deterministisch greedy plaatsingsalgoritme dat wordt gestuurd door vooraf berekende draadlengte-masks (wire-length masks).
• Parallel Monte Carlo: Elke strategie wordt in parallel uitgevoerd op meerdere willekeurige initiële seeds om een distributie van Half-Perimeter Wire Length (HPWL) resultaten te generen.
• Fitness Scoring: De fitness van een strategie is de gemiddelde HPWL over succesvolle runs. Een timeout-mechanisme en syntaxisvalidatie zorgen voor efficiëntie en robuustheid.

Zodra de evolutionaire zoektocht is voltooid, ondergaan de top-K strategieën verfijning via de wire-mask-gestuurde greedy procedure om de uiteindelijke plaatsingsresultaten te produceren.

Belangrijkste Bijdragen

1. Perspectiefverschuiving: Het artikel levert theoretisch en empirisch bewijs dat de plaatsingsvolgorde een kritieke, maar historisch over het hoofd geziene dimensie van optimalisatie is. Het toont aan dat suboptimale ordening leidt tot asymptotische degradatie van de oplossingskwaliteit (bijv. $\Omega(l)$ degradatie voor keten-topologieën en $\Theta(g)$ voor ster-topologieën).
2. Methodologische Innovatie: OrderPlace is het eerste LLM-gestuurde evolutionaire framework dat specifiek is ontworpen voor macro-plaatsingsvolgordes. Het integreert succesvol proxy-evaluatie om de uitdaging van dure feedbackloops in floorplanning-optimalisatie op te lossen.
3. Ontdekking van Nieuwe Strategieën: Het framework ontdekt generaliseerbare sorteeralgoritmen die variëren van statische heuristieken tot complexe, door fysica geïnspireerde dynamische regels (bijv. gravitationele modellen, entropiereductie en net-sluitingsprioritering) die handmatig vervaardigde heuristieken overtreffen.

Experimentele Resultaten

De auteurs hebben OrderPlace geëvalueerd op de standaard ISPD 2005 benchmark suite (acht chip-ontwerpen).

• Prestaties: OrderPlace behaalde de beste (laagste) HPWL-waarden op 7 van de 8 circuits.
• Vergelijkingen:
  • Vergeleken met WireMask-EA, reduceerde OrderPlace de draadlengte met 34,04%.
  • Vergeleken met de state-of-the-art methode EGPlace, reduceerde OrderPlace de draadlengte met 14,08%.
  • In een directe vergelijking met behulp van de Wilcoxon rank-sum test, presteerde OrderPlace significant beter op 7 circuits vergeleken met EGPlace.
• Convergentie: OrderPlace vertoonde een opmerkelijke computationele efficiëntie en convergeerde aanzienlijk sneller dan EGPlace. De best ontdekte strategie bereikte consistent eerder lagere convergentiepunten in het optimalisatietraject.
• Congestie en Mixed-Size: OrderPlace toonde ook superieure routabiliteit (congestie) en behaalde leidende prestaties in mixed-size plaatsingstaken wanneer het werd gecombineerd met een globale placer (DreamPlace).
• LLM Impact: Ablatie-studies bevestigden dat door LLM gegenereerde strategieën consequent beter presteerden dan alle handmatig vervaardigde initiële strategieën, wat aangeeft dat de prestatiewinst voortkomt uit de ontdekking van niet-triviale ordeningsbeleid buiten bestaande heuristieken.

Betekenis en Claims

Het artikel claimt dat OrderPlace het eerste systematische bewijs is dat plaatsingsvolgorde, traditioneel beschouwd als een statische voorverwerkingsstap, dient als een kritieke determinant in plaatsingsoptimalisatie. Door de ontdekking van ordeningsstrategieën via LLM's en proxy-evaluatie te automatiseren, mitigeert de methode effectief suboptimaliteit in sequentie-beslissingsgebaseerde plaatsing.

De auteurs benadrukken dat hun aanpak verschilt van eerdere werken die sequencing behandelen als een vaste prior of vertrouwen op RL-agents om sequenties impliciet te leren. In plaats daarvan optimaliseert OrderPlace de invoersequentie expliciet als een hyperparameter. Het werk suggereert dat het optimalisatiepotentieel van plaatsingsvolgorde een "slapende" dimensie is die, wanneer ontsloten, de greedy solvers fundamenteel kan versnellen en betere globale oplossingen kan ontsluiten.

Beperkingen: De studie is momenteel beperkt tot het evalueren van de impact van plaatsingsvolgorde op mask-gestuurde greedy methoden. De interactie met stochastische, op leren gebaseerde methoden blijft onverkend, en toekomstig werk wordt voorgesteld om te onderzoeken hoe plaatsingsvolgorde deep learning-gestuurde plaatsingsmethoden kan verbeteren.