Un annealer Ising digitale compatto compute-in-memory con bit SRAM probabilistico in 28 nm per il problema del commesso viaggiatore

Perché percorsi e chip più intelligenti contano

Ogni giorno camion di consegna, aeroplani e pacchetti di dati devono decidere quale percorso seguire affinché tutto arrivi puntuale con il minor costo possibile. Questo tipo di rompicapo, noto come Problema del Commesso Viaggiatore, diventa rapidamente insormontabile anche per potenti computer man mano che aumentano le tappe da visitare. L’articolo alla base di questo riassunto presenta un nuovo tipo di chip specializzato che affronta questi problemi di pianificazione dei percorsi in modo molto più efficiente, sfruttando idee derivate dai materiali magnetici e integrandole direttamente nella memoria standard del calcolatore.

Un classico rompicapo: visitare ogni tappa una sola volta

Il Problema del Commesso Viaggiatore pone una domanda semplice: data una lista di città e le distanze tra di esse, qual è il tour più breve che visita ogni città esattamente una volta e ritorna al punto di partenza? Il problema è che il numero di tour possibili esplode con l’aumentare delle città, quindi valutare ogni opzione è impossibile nella pratica. Piuttosto, gli approcci moderni cercano percorsi molto buoni, se non ottimi. Una strategia promettente imita il modo in cui una rete di piccoli magneti, chiamata modello di Ising, può stabilizzarsi in uno stato a bassa energia che rappresenta una buona soluzione. Permettendo con cura a questa rete di “agitarsi” attraverso cambiamenti casuali che progressivamente si attenuano, il sistema sfugge a scelte locali svantaggiose e trova percorsi migliori.

Trasformare un chip di memoria in un risolutore di problemi

Invece di eseguire questo processo su processori ordinari, gli autori lo integrano direttamente nell’hardware di memoria, una strategia chiamata compute-in-memory. Progettano un chip compatto in tecnologia 28 nanometri in cui ogni piccola cella di memoria memorizza sia informazioni sulle distanze sia partecipa direttamente ai calcoli. Ingenuamente, il chip sfrutta le imperfezioni naturali di fabbricazione delle sue celle di memoria come sorgente incorporata di casualità, eliminando la necessità di ingombranti generatori di numeri casuali. Disturbando brevemente i valori memorizzati con una “spinta” di tensione controllata, alcuni bit si capovolgono in modo probabilistico, fornendo la gentile casualità necessaria per il processo di annealing senza circuiteria aggiuntiva.

Spezzare grandi mappe in piccoli quartieri

Uno dei principali ostacoli all’uso di solver in stile Ising su grandi compiti di pianificazione dei percorsi è la quantità enorme di dati richiesta: una rappresentazione completa di un tour da 96 città richiederebbe normalmente una vasta rete di connessioni e memoria. Per evitarlo, i ricercatori raggruppano le città vicine in piccoli cluster e poi dispongono quei cluster su più livelli di gerarchia. Al livello più alto, il chip risolve l’ordine dei cluster; al livello successivo, affina l’ordine delle città all’interno di ciascun cluster; e così via. Questo approccio graduale riduce drasticamente la quantità di memoria e di connessioni necessarie, abbassando la complessità hardware da una crescita proporzionale alla quarta potenza del numero di città a una che cresce soltanto con il quadrato, comprimendo poi ulteriormente le distanze memorizzate impacchettando soltanto quelle effettivamente necessarie.

Come il chip aggiorna molte scelte contemporaneamente

All’interno del chip, gruppi di tre città formano blocchi elementari gestiti in parallelo. L’array di memoria è organizzato in modo che all’interno di ciascun cluster il circuito possa calcolare rapidamente la variazione della lunghezza totale del tour se si scambiano sezioni del percorso. Poiché alcuni cluster non interferiscono direttamente, il sistema può aggiornare tutti i cluster “dispari” in un passaggio e tutti quelli “pari” nel successivo, accelerando la ricerca pur comportandosi come se le modifiche fossero effettuate una alla volta. Durante ogni ciclo, il chip usa le sue celle di memoria rumorose per decidere se accettare una mossa peggiore con una certa probabilità—alta all’inizio per esplorare e più bassa in seguito per stabilizzarsi—imitando il raffreddamento di un metallo e orientando il percorso verso distanze sempre più brevi.

Dal chip di laboratorio a percorsi su larga scala

Il prototipo contiene una modesta memoria speciale di 6 kilobit ma è già in grado di risolvere istanze del Problema del Commesso Viaggiatore a 96 città in circa 620 microsecondi consumando meno di un microjoule di energia. Rispetto a hardware precedenti progettati per lo stesso compito, ottiene miglioramenti fino a centinaia di volte in termini di memoria richiesta per unità di dimensione del problema. Le simulazioni mostrano inoltre che affiancando molti di questi blocchi di memoria lo stesso progetto potrebbe scalare a problemi con migliaia di città mantenendo una crescita hardware quasi lineare. Per un lettore non specialista, il messaggio chiave è che rimodellando un chip di memoria familiare in un risolutore attivo—e trasformando i difetti di fabbricazione inevitabili in una caratteristica utile—questo lavoro indica la strada verso hardware piccoli, rapidi ed energeticamente efficienti in grado di aiutare a pianificare percorsi e orari complessi in tempo reale.

Citazione: Kong, Y., Lu, A., Liu, H. et al. A compact digital compute-in-memory Ising annealer with probabilistic SRAM bit in 28 nm for travelling salesman problem. npj Unconv. Comput. 3, 15 (2026). https://doi.org/10.1038/s44335-026-00060-w

Parole chiave: problema del commesso viaggiatore, annealer Ising, compute-in-memory, hardware SRAM, ottimizzazione combinatoria