Addressing Large Action Spaces in 3D Floorplanning via Spatial Generalization

1. Il Problema: Spazi di Azione Discreti e Scalabilità

Il floorplanning (pianificazione del layout) è una fase critica nella progettazione di circuiti integrati (IC) che determina le prestazioni, il consumo energetico e l'area del chip. È un problema NP-hard con uno spazio di ricerca combinatorio enorme.

Le recenti soluzioni basate sull'Apprendimento per Rinforzo (RL), come CircuitTraining e Chipformer, affrontano il problema trattando il posizionamento dei moduli come un'azione su una griglia discreta.

• Limitazione principale: In questi approcci, lo spazio delle azioni è definito dalla risoluzione della griglia (es. 100x100 posizioni). Per un layout 3D, lo spazio delle azioni cresce esponenzialmente (es. $2 \times 100 \times 100 = 20.000$ azioni possibili).
• Conseguenze:
  1. Scalabilità: Il modello deve produrre una distribuzione di probabilità su tutte le possibili coordinate, rendendo l'inferenza computazionalmente proibitiva per risoluzioni elevate.
  2. Generalizzazione scarsa: In un approccio discreto, il segnale di gradiente (reward) viene ricevuto solo per la cella selezionata. Non c'è feedback per le celle vicine, impedendo al modello di apprendere che spostamenti minimi producono risultati simili.
  3. Dipendenza da dati esperti: Molti metodi richiedono traiettorie di addestramento generate da esperti umani o strumenti ottimali, che sono costosi o difficili da ottenere.

2. Metodologia: SGF (Spatial Generalization for Floorplanning)

Gli autori propongono SGF, un metodo che sposta la rappresentazione delle azioni da uno spazio discreto a uno spazio continuo, sfruttando la struttura intrinseca del problema.

Concetti Chiave

• SLDAS (Structured Large Discrete Action Spaces): Il paper formalizza il floorplanning come uno spazio di azioni discrete strutturato e di grandi dimensioni.
• L-Action Similarity (Similitudine L-azione): L'ipotesi fondamentale è che la funzione valore $Q(s, a)$ sia L-Lipschitziana. In termini pratici, questo significa che il "ritorno" (reward) di un'azione è simile a quello di azioni vicine nello spazio fisico. Spostare un modulo di una piccola quantità non cambia drasticamente le prestazioni del layout.
• Generalizzazione Spaziale: Sfruttando questa similitudine, il modello può generalizzare l'apprendimento: un gradiente ricevuto per un'azione influenza anche le azioni vicine, riducendo la sparsità del segnale di apprendimento.

Architettura del Modello

SGF combina i Decision Transformers (DT) con l'architettura Wolpertinger:

1. Attore (Actor): Un Decision Transformer che, dato lo stato corrente (storia delle azioni, reward-to-go, stato della griglia), predice una posizione continua $\hat{\alpha}_t \in [0, 1]^3$ (coordinate normalizzate x, y, z).
2. Modulo k-NN: La posizione continua viene mappata alle $k$ azioni discrete legali più vicine (vicini nel senso della distanza euclidea sulla griglia).
3. Critic: Un secondo Decision Transformer valuta le $k$ azioni candidate discrete, prevedendo il "return-to-go" (reward futuro atteso) per ciascuna.
4. Selezione: L'azione finale $\tilde{a}_t$ è quella tra le $k$ candidate che minimizza l'errore rispetto al reward target desiderato.

Addestramento su Dati Casuali

Un aspetto rivoluzionario è che SGF viene addestrato esclusivamente su traiettorie casuali (azioni scelte a caso nell'ambiente), senza dati di esperti.

• Il modello impara a riconoscere i pattern spaziali grazie alla struttura induttiva (L-action similarity).
• L'attore viene addestrato per imitare la distribuzione continua delle azioni (usando una perdita L1 su coordinate continue).
• Il critic viene addestrato per prevedere i reward futuri (Return-to-Go) basandosi su dati sub-ottimali, sfruttando il concetto di Hindsight Experience Replay (HER).

3. Contributi Chiave

1. Formalizzazione SLDAS: È il primo lavoro a introdurre formalmente il floorplanning come un caso di Structured Large Discrete Action Space, definendo matematicamente la similitudine delle azioni vicine.
2. Decoupling Output-Resolution: La dimensione dell'output del modello (3 coordinate continue) è indipendente dalla risoluzione della griglia del canvas. Questo risolve il collo di bottiglia della scalabilità nei layout 3D ad alta risoluzione.
3. Apprendimento senza Esperti: Dimostra che è possibile apprendere politiche di posizionamento efficaci partendo solo da dati casuali, sfruttando l'induzione spaziale, eliminando la necessità di costose traiettorie di esperti per l'addestramento offline.
4. Generalizzazione Spaziale: Mostra che la rappresentazione continua permette al modello di apprendere più efficientemente dai dati, poiché il segnale di gradiente si propaga a un'intera regione dello spazio delle azioni, non solo a un singolo punto.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su benchmark standard (MCNC, IBM, GSRC) come ami33, ami49, n50, n100 e ibm6.

• Confronto con Chipformer: SGF è stato confrontato con Chipformer (un metodo basato su griglia discreta e Decision Transformer).
  • Risultati: SGF ha ottenuto risultati significativamente migliori in termini di lunghezza dei fili (wirelength) su tutti i benchmark, nonostante fosse stato addestrato solo offline su dati casuali, mentre Chipformer richiedeva addestramento online e fine-tuning su dati esperti.
  • Stabilità: Chipformer ha mostrato fluttuazioni nelle prestazioni anche con estesi fine-tuning online, suggerendo difficoltà a generalizzare. SGF ha mantenuto prestazioni superiori e più stabili.
• Metriche: SGF ha ridotto la lunghezza dei fili (es. su ami49: 32.304 vs 37.530 di Chipformer; su n50: 8.747 vs 13.447).
• Capacità del Critic: Il modello critic di SGF è riuscito a prevedere accuratamente i reward finali man mano che il layout veniva completato, confermando che il modello ha appreso le relazioni spaziali sottostanti.

5. Significato e Implicazioni

Questo lavoro rappresenta un cambio di paradigma nell'automazione del design elettronico (EDA) basato su ML:

• Superamento della Scalabilità: Dimostra che l'uso di spazi di azione continui è essenziale per gestire la complessità dei layout 3D moderni, evitando l'esplosione combinatoria delle dimensioni del modello.
• Efficienza dei Dati: Apre la strada all'uso di dati di addestramento "grezzi" o casuali, rendendo lo sviluppo di agenti RL per il floorplanning più accessibile e meno dipendente da dati di esperti costosi.
• Induzione Biologica: Il metodo imita l'intuizione umana secondo cui piccoli spostamenti fisici producono risultati simili, incorporando questo bias induttivo direttamente nell'architettura del modello.

In sintesi, SGF dimostra che la generalizzazione spaziale attraverso rappresentazioni continue è la chiave per risolvere i problemi di scalabilità e generalizzazione nel floorplanning 3D, offrendo una soluzione più robusta ed efficiente rispetto agli approcci basati su griglie discrete.