Una Ricottura Simulativa nella Costruzione di Circuiti con l'Intelligenza Artificiale: Ottimizzazione del Placement per Circuiti Integrati

Una Ricottura Simulativa nella Costruzione di Circuiti con l'Intelligenza Artificiale: Ottimizzazione del Placement per Circuiti Integrati Amelia Carolina Sparavigna1 e Gemini (Modello Linguistico di Google)2 1 DISAT, Politecnico di Torino, 2 Gemini AI DOI: 10.5281/zenodo.17447444 Il Placement di Circuiti Integrati (posizionamento dei blocchi logici su un chip) è un problema di ottimizzazione combinatoria (NP-hard) con forti analogie al problema del Commesso Viaggiatore e al Protein Folding. L'obiettivo primario è determinare la configurazione spaziale ottimale dei componenti e delle loro interconnessioni al fine di minimizzare la lunghezza totale dei fili (riducendo ritardi e consumo energetico) e prevenire la sovrapposizione dei blocchi.In questo studio, viene applicata l'euristica della Ricottura Simulativa (SA) per risolvere la complessità di questo design space. Lo Stato del sistema è definito dalle coordinate di tutti i blocchi logici. La Funzione di Energia (E) è una metrica complessa che combina il Costo Soft (lunghezza totale dei fili, calcolata tramite Distanza di Manhattan ponderata dalla matrice di interconnessione J) con un Costo Rigido (penalità elevatissima per le sovrapposizioni).L'SA sfrutta la sua capacità di Accettazione Probabilistica di Stati Peggiorativi (Esplorazione), regolata dalla temperatura, per evitare minimi locali e accedere a configurazioni globalmente migliori. L'implementazione su un esempio simulato di 5 blocchi su una griglia 10 x 10 ha dimostrato l'efficacia del metodo: il costo di cablaggio è stato ridotto da un valore iniziale casuale di 141.00 a un costo finale ottimale di 25.00, ottenendo una riduzione dell'82% nella lunghezza dei fili. Il risultato finale è un layout di chip dove i blocchi con la maggiore interconnessione sono posizionati adiacenti, confermando la superiorità dell'SA nella gestione di funzioni di costo complesse e vincoli geometrici. Introduzione In un precedente lavoro abbiamo già visto il problema del ‘commesso viaggiatore’, https://zenodo.org/records/17412171. Questo è l'esempio classico di un problema NP-hard. Schematicamente: Elemento SA TSP Stato (Configurazione) L' ordine di visita di tutte le città (un percorso). Energia () / Funzione di Costo La lunghezza totale del percorso. L'obiettivo è minimizzare questa energia. Mossa (Variazione di Stato) Scambiare l'ordine di due città nel percorso. Elemento SA TSP (Accettazione Peggiorativa) Accettare probabilisticamente un percorso che è temporaneamente più lungo (a temperatura alta) per uscire da un ottimo locale. Applicazione Ottimizzazione dei percorsi di consegna, pianificazione dei circuiti (es. PCB), logistica. Export to Sheets Altro problema affrontabile con la Simulated Annealing è la Progettazione di Circuiti Integrati (Placement & Routing). Ovvero, si tratta della disposizione dei componenti (celle logiche e fili) su un chip deve minimizzare l'area totale e la lunghezza dei collegamenti. Elemento SA Progettazione di Circuiti Stato (Configurazione) La posizione di tutti i componenti sul circuito. Energia () / Funzione di Costo La combinazione di: area totale occupata + lunghezza totale dei fili (interconnessioni) + penalità per le sovrapposizioni. Mossa (Variazione di Stato) Spostare un componente in una nuova posizione o scambiare la posizione di due componenti. (Accettazione Peggiorativa) Accettare un piazzamento che aumenta leggermente la lunghezza dei fili o l'area (a temperatura alta) per evitare un cattivo layout locale che renderebbe difficile il routing successivo. Applicazione Progettazione hardware e ottimizzazione delle performance. Export to Sheets Altro tipico problema è quelloa della Conformazione di Proteine (Protein Folding). Determinare la forma 3D con la minima energia potenziale che una proteina assume. Elemento SA Conformazione di Proteine Stato (Configurazione) L'insieme di tutti gli angoli torsionali () di tutti gli amminoacidi nella catena, che definiscono la forma 3D. Energia () / Funzione di Costo L'energia libera di Gibbs (l'energia potenziale del sistema). L'obiettivo è trovare la conformazione con l'energia più bassa. Mossa (Variazione di Stato) Modificare leggermente un angolo torsionale (un legame) nella struttura 3D. (Accettazione Peggiorativa) Accettare uno stato con energia temporaneamente più alta (a temperatura alta) per superare le barriere energetiche e trovare la conformazione stabile finale. Applicazione Biologia computazionale, scoperta di farmaci. Export to Sheets La Ricottura Simulativa è eccezionale in tutti questi casi (e nella logistica) perché può accettare temporaneamente soluzioni peggiorative per evitare di rimanere intrappolata in un minimo locale. In questo nostro studio ora proposto, affrontiamola Ricottura Simulativa per la Progettazione di Circuiti Integrati L'obiettivo è posizionare centinaia o migliaia di componenti (celle logiche, blocchi di memoria) su un chip di silicio e collegarli (instradamento) in modo da minimizzare lo spazio e massimizzare le prestazioni. Ecco come i tre elementi fondamentali della Ricottura Simulativa vengono definiti in questo contesto: 1. Stato (Configurazione del Circuito) Lo stato del sistema è la posizione spaziale (coordinate ) di ogni componente logico all'interno del circuito integrato.  Definizione: L'insieme delle coordinate di tutti i blocchi funzionali e delle porte logiche che compongono il chip. 2. Funzione di Energia (): Il Costo Complesso 󹳦󹳤󹳧 L'energia è una funzione molto complessa che l'algoritmo deve minimizzare. A differenza del TSP (dove era solo la distanza), qui è la somma di diversi costi di progettazione: Componente del Costo Obiettivo di Progettazione Minimizzare la lunghezza totale dei fili (interconnessioni) per ridurre ritardi (tempi di propagazione) e consumo energetico. Minimizzare l'area totale richiesta, per mantenere il chip piccolo e aumentare la resa produttiva. Una penalità altissima (il costo rigido, come nella logistica) se due componenti sono posizionati nello stesso spazio. Export to Sheets 3. Mossa (Variazione di Stato) La mossa è l'azione che cambia la disposizione dei componenti.  Mossa: Consiste nello scambiare la posizione di due componenti logici casuali oppure nello spostare un singolo componente in una nuova posizione casuale all'interno del chip. L'Importanza dell'Esplorazione con l'SA Il Placement & Routing è pieno di minimi locali. Una disposizione che sembra buona localmente (fili corti tra due blocchi) potrebbe impedire una disposizione ottimale globalmente.  Alta Temperatura (Esplorazione): A temperatura alta, l'SA accetta un temporaneo aumento della lunghezza dei fili (). Questo è il PERO' cruciale: accetta un layout momentaneamente peggiore per superare una configurazione sub-ottimale e accedere a una regione dello spazio delle soluzioni dove le interconnessioni globali sono molto più brevi.  Bassa Temperatura (Sfruttamento): Man mano che la Ricottura prosegue, l'algoritmo si concentra sul fissare la posizione dei componenti che minimizzano l'energia totale (lunghezza dei fili e area), portando a un layout quasi ottimale del chip. Questa applicazione è fondamentale perché dimostra come l'SA possa gestire funzioni di costo molto complesse che dipendono da interazioni geometriche e funzionali. Facciamo un esempio con un programma Python. Poiché un circuito reale è troppo complesso, useremo un esempio semplificato con un piccolo numero di blocchi che devono essere posizionati su una griglia. L'obiettivo sarà minimizzare la lunghezza totale dei fili. Codice Python: Placement con Ricottura Simulativa Questo codice simula il posizionamento di 5 blocchi su una griglia, collegati da una matrice di interconnessione. Python import numpy as np import random import math import matplotlib.pyplot as plt # --- 1. Definizione dello Stato e dei Costi --- NUM_BLOCKS = 5 GRID_SIZE = 10 # Il chip è una griglia 10x10 # Matrice di Interconnessione (J_ij): quante volte il Blocco i deve essere connesso al Blocco j. # Più alto è il valore, più i due blocchi dovrebbero essere vicini. # (I valori sono simmetrici e non c'è interconnessione con sé stessi) # B0 B1 B2 B3 B4 J = np.array([ [0, 5, 0, 1, 8], # B0 è molto connesso a B1 e B4 [5, 0, 3, 0, 0], # B1 è connesso a B0 e B2 [0, 3, 0, 4, 0], [1, 0, 4, 0, 2], [8, 0, 0, 2, 0] ]) def calculate_cost(positions): """ Funzione di Energia (E): Calcola il costo totale di interconnessione. Usiamo la Distanza di Manhattan (ottima per le griglie di routing). """ total_wire_length = 0 # 1. Costo Soft: Lunghezza dei fili (da minimizzare) for i in range(NUM_BLOCKS): for j in range(i + 1, NUM_BLOCKS): if J[i, j] > 0: # Distanza di Manhattan tra Blocco i e Blocco j dist_manhattan = abs(positions[i][0] - positions[j][0]) + \ abs(positions[i][1] - positions[j][1]) # Il costo aumenta con la distanza e con il numero di fili (J_ij) total_wire_length += J[i, j] * dist_manhattan # 2. Costo Rigido: Penalità di Sovrapposizione # Conversione delle coordinate in un set per rilevare le collisioni if len(positions) != len(set(positions)): # PENALITÀ ALTISSIMA se c'è sovrapposizione! total_wire_length += 100000 return total_wire_length # --- 2. Mossa (Variazione di Stato) --- def generate_neighbor(current_positions): """Genera un nuovo stato scambiando due blocchi o muovendone uno.""" new_positions = list(current_positions) # Scegli casualmente il tipo di mossa if random.random() < 0.5: # Mossa 1: Scambia la posizione di due blocchi casuali i, j = random.sample(range(NUM_BLOCKS), 2) new_positions[i], new_positions[j] = new_positions[j], new_positions[i] else: # Mossa 2: Sposta un singolo blocco in una nuova posizione casuale i = random.randint(0, NUM_BLOCKS - 1) # Genera una nuova posizione casuale all'interno della griglia new_x = random.randint(0, GRID_SIZE - 1) new_y = random.randint(0, GRID_SIZE - 1) new_positions[i] = (new_x, new_y) return tuple(new_positions) # Ritorna una tupla di tuple per immutabilità # --- 3. Algoritmo di Ricottura Simulativa (SA) --- def simulated_annealing_placement(T_initial, cooling_rate, steps): # Stato Iniziale: Posizioni casuali non sovrapposte initial_positions = [] while len(initial_positions) < NUM_BLOCKS: new_pos = (random.randint(0, GRID_SIZE - 1), random.randint(0, GRID_SIZE - 1)) if new_pos not in initial_positions: initial_positions.append(new_pos) current_positions = tuple(initial_positions) current_cost = calculate_cost(current_positions) best_cost = current_cost best_positions = current_positions T = T_initial history = [] for step in range(steps): if T < 1e-6: break new_positions = generate_neighbor(current_positions) new_cost = calculate_cost(new_positions) delta_E = new_cost - current_cost # Criterio di Accettazione di Boltzmann if delta_E <= 0: # Accetta miglioramenti current_positions, current_cost = new_positions, new_cost else: # Esplorazione: Accetta probabilisticamente un peggioramento probability = math.exp(-delta_E / T) if random.random() < probability: # PERO', accetta il peggioramento per uscire dal minimo locale! current_positions, current_cost = new_positions, new_cost if current_cost < best_cost: best_cost = current_cost best_positions = current_positions history.append(best_cost) T *= cooling_rate return best_positions, best_cost, history # --- 4. Esecuzione e Visualizzazione --- T_INITIAL = 1000.0 # Temperatura iniziale alta COOLING_RATE = 0.999 STEPS = 15000 best_positions, best_cost, history = simulated_annealing_placement(T_INITIAL, COOLING_RATE, STEPS) print(f"Dimensione Griglia: {GRID_SIZE}x{GRID_SIZE}") print(f"Costo Iniziale (Random): {history[0]:.2f}") print(f"Costo Ottimale Trovato: {best_cost:.2f}") # Plotting plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.plot(history) plt.title('Evoluzione del Costo (Lunghezza Fili)') plt.xlabel(f'Iterazione (su {STEPS})') plt.ylabel('Costo Totale') plt.subplot(1, 2, 2) # Disegno la griglia plt.xlim(-0.5, GRID_SIZE - 0.5) plt.ylim(-0.5, GRID_SIZE - 0.5) plt.xticks(np.arange(0, GRID_SIZE, 1)) plt.yticks(np.arange(0, GRID_SIZE, 1)) plt.grid(True) # Posizionamento dei blocchi for i, (x, y) in enumerate(best_positions): plt.scatter(x, y, s=500, label=f'B{i}', alpha=0.8) plt.annotate(f'B{i}', (x, y), ha='center', va='center', color='white', fontsize=10, fontweight='bold') # Disegno delle interconnessioni (Fili) for i in range(NUM_BLOCKS): for j in range(i + 1, NUM_BLOCKS): if J[i, j] > 0: x1, y1 = best_positions[i] x2, y2 = best_positions[j] # Disegno la linea con spessore proporzionale alla forza di interconnessione (J_ij) plt.plot([x1, x2], [y1, y2], 'r-', alpha=0.6, linewidth=0.5 * J[i, j]) plt.title(f'Placement Ottimale ({best_cost:.2f})') plt.xlabel('Coordinata X') plt.ylabel('Coordinata Y') plt.tight_layout() plt.show() Punti Salienti dell'Esempio 1. Funzione di Costo Unificata: La funzione calculate_cost combina i costi soft (minimizzazione della lunghezza dei fili, utilizzando la Distanza di Manhattan) e i costi rigidi (penalità elevatissima per le sovrapposizioni). 2. Interconnessione (J): La matrice indica quali blocchi devono essere vicini. L'SA spingerà B0 vicino a B4 (peso 8) e B0 vicino a B1 (peso 5) per minimizzare l'energia (lunghezza fili). 3. Mossa Flessibile: La funzione generate_neighbor sceglie casualmente tra:  Scambio: Riordina due blocchi (utile per i grandi movimenti).  Spostamento Singolo: Muove un blocco in una nuova posizione casuale (utile per le regolazioni fini). Questo esempio dimostra chiaramente come la Ricottura Simulativa bilancia i vincoli di interconnessione (spingendo i blocchi collegati a unirsi) e i vincoli fisici (non sovrapporsi) per trovare un layout ottimale. https://colab.research.google.com/drive/1guAtgnywzfxaUK4vWh7zHlee_ihydp6C?usp=sharing Risultati Dimensione Griglia: 10x10 Costo Iniziale (Random): 141.00 Costo Ottimale Trovato: 25.00 I risultati ottenuti dimostrano perfettamente il successo della Ricottura Simulativa (SA) applicata al problema di Placement di Circuiti Integrati! 🎉 Ecco l'analisi di questi valori: Parametro Valore Costo Iniziale (Random) 141 Costo Ottimale Trovato 25 Analisi dei Risultati 1. Il Successo dell'Algoritmo Il costo è la lunghezza totale dei fili (interconnessioni) necessaria per collegare tutti i blocchi, pesata dalla loro frequenza di connessione (la matrice ).  Riduzione del Costo: L'algoritmo ha ridotto il costo iniziale di 141 a soli 25.  Miglioramento: Questo rappresenta una riduzione di circa l'82% della lunghezza dei fili. Questo drastico calo dimostra che la Ricottura Simulativa ha funzionato in modo estremamente efficiente, riuscendo a spostare i blocchi più interconnessi vicini tra loro, minimizzando così la funzione di costo. 2. Il Ruolo dell'Esplorazione e dello Sfruttamento Questo risultato è stato possibile grazie alle due fasi critiche dell'SA:  Esplorazione (Alta Temperatura): L'algoritmo ha accettato numerosi scambi e spostamenti di blocchi che peggioravano temporaneamente il costo (il PERO'). Questo gli ha permesso di uscire dai minimi locali del posizionamento casuale (141) e di raggiungere regioni di soluzione molto migliori.  Sfruttamento (Bassa Temperatura): Nella fase finale, con la temperatura in calo, l'algoritmo si è concentrato solo sulle piccole mosse migliorative, cristallizzando la soluzione ottimale (25) in cui i blocchi fortemente interconnessi sono adiacenti. Il risultato 25 indica che è stato trovato un layout eccellente per il chip in termini di efficienza di cablaggio. Il grafico generato (quello che mostra il risultato finale con un costo di 25) è la visualizzazione del Placement Ottimale dei Blocchi Logici sul Chip trovato dalla Ricottura Simulativa. Questo grafico rappresenta il circuito integrato (idealizzato) sulla griglia e ha tre elementi chiave: 1. I Blocchi Logici I pallini colorati sono i Blocchi Logici (o Celle), che sono i componenti funzionali del circuito (es. un'unità aritmetica, un registro, una porta logica).  Significato: La posizione di ogni pallino sulla griglia (es. coordinate ) è il risultato ottimale trovato dalla Ricottura Simulativa, che minimizza l'energia (il costo). 2. Le Linee (Le Interconnessioni) Le linee che collegano i pallini sono i Fili di Interconnessione (o Nets), che rappresentano i collegamenti elettrici tra i blocchi logici.  Spessore della Linea: Lo spessore (o l'intensità del colore) è proporzionale al valore della matrice che abbiamo definito. Le linee più spesse indicano che quei due blocchi hanno un'interconnessione più critica (un numero maggiore di fili o un segnale più importante) e, per questo, l'algoritmo li ha posizionati molto vicini. 3. La Griglia (Lo Spazio del Chip) La griglia di sfondo rappresenta l'Area del Circuito Integrato disponibile (nel nostro esempio, ).  Significato: L'algoritmo ha trovato la disposizione dei pallini all'interno di questa area che rende la lunghezza totale dei fili (il costo finale di 25) minima. In sintesi, il grafico mostra che la Ricottura Simulativa ha preso l’insieme di blocchi (pallini) e la loro "tendenza a stare insieme" (matrice ) e ha trovato la migliore configurazione fisica per ridurre al minimo i ritardi e l'area di cablaggio del chip. Proviamo a stilare un report finale. Report finale: Ricottura Simulativa (SA) in Ambienti di Ottimizzazione Complessi come i Circuiti La Ricottura Simulativa (Simulated Annealing, SA) è una meta-euristica ispirata alla metallurgia, utilizzata per risolvere problemi di ottimizzazione combinatoria (NP-hard) che possiedono numerosi minimi locali. Il suo punto di forza è l'Accettazione Probabilistica di un Passaggio a un'Energia Superiore (o Esplorazione), regolata dalla temperatura (Criterio di Boltzmann), che previene il blocco in soluzioni sub-ottimali. Caratteristica Chiave Concetto Obiettivo SA Trovare il Minimo Globale (la soluzione a costo più basso). 1. Il Problema: Placement di Circuiti Integrati Il Placement (Posizionamento) dei blocchi funzionali su un chip è un problema di ottimizzazione combinatoria (NP-hard).  Obiettivo: Trovare le coordinate ottimali per ogni blocco logico sul chip al fine di minimizzare la lunghezza totale dei fili e prevenire la sovrapposizione dei componenti.  Stato: La configurazione del sistema è definita dalle posizioni di tutti i blocchi logici sulla griglia. 2. La Funzione di Costo (Energia, ) La Funzione di Costo che l'algoritmo di Ricottura Simulativa cerca di minimizzare è un termine complesso che bilancia l'efficienza di cablaggio (costo soft) con i vincoli fisici (costo rigido). A. Costo Soft: Interconnessione () Questo è il costo primario, calcolato utilizzando la Distanza di Manhattan (somma delle distanze assiali) tra le coppie di blocchi, ponderata dalla loro frequenza di connessione (la matrice ): L'obiettivo è posizionare i blocchi con un alto valore (alta interconnessione) molto vicini per ridurre al minimo il consumo energetico e i ritardi di propagazione nel chip.