Molti problemi di grande rilevanza teorica e pratica possono essere formulati come problemi di ottimizzazione combinatoria.
Di particolare interesse sono i problemi detti QUBO (Quadratic Unconstrained Binary Optimization) che vengono fuori frequentemente in diversi campi tra cui il machine learning, il disegno di nuovi materiali, la verifica del software, il controllo del traffico aereo, la logistica o la gestione di portafogli di investimento (e la lista non finirebbe qui).
In pratica si tratta di trovare un’opportuna configurazione di N bit che combinati in una forma apparentemente semplice (una somma pesata di prodotti di due bit) minimizzano una funzione costo.
Con 3 bit (b1, b2, b3,), la funzione costo è Q11 b1 b1+ Q21 b2 b1+ Q22 b2 b2+ Q31 b3 b1+ Q32 b3 b2+ Q33 b3 b3.
La quantistica rivoluzionerà la sicurezza, la privacy: ecco progressi della ricerca e sfide aperte
Problemi QUBO e possibili soluzioni
I pesi Qij definiscono lo specifico problema QUBO. Con 3 bit il problema è facile da risolvere (ci sono solo 8 combinazioni di bit da provare) ma in generale un problema QUBO appartiene alla classe dei problemi NP hard (NP sta per Nondetermistic Polynomial-time). Senza entrare nella giungla delle definizioni più o meno formali, è sufficiente osservare che il numero di combinazioni da provare per risolvere a forza bruta il problema è 2N e quindi con N uguale a 64 diventa, circa, 20000000000000000000.’
L’importanza dei problemi QUBO ha spinto, sia la ricerca accademica sia quella industriale, ad investire nello sviluppo di soluzioni in grado di ridurre lo sforzo computazionale richiesto. Ad esempio, con hardware specializzato basato su FPGA (Field-Programmable Gate Array), oppure Quantum Annealers basati su qubit superconduttori ed altre soluzioni più o meno esotiche.
Recentemente, un gruppo della University of Southern California (USC) ha proposto un benchmark per determinare come cresce il tempo (scaling analysis) richiesto per risolvere un problema QUBO all’aumentare di N utilizzando varie piattaforme.
Una piattaforma è più adatta se la crescita è più lenta e, naturalmente, se riesce a risolvere problemi più grandi. Nella competizione, informale ma agguerrita, sono state confrontate sei piattaforme hardware/software ognuna con un proprio algoritmo ottimizzato per la ricerca della soluzione per un insieme di problemi specificati dal gruppo dell’USC. Sono comprese una piattaforma completamente tradizionale (CPU commerciale), ASIC (Application Specific Integraded Circuits) come quello proposto dalla Fujitsu nella loro Digital Annealer Unit, la Toshiba Simulated Bifurcation Machine (SBM) che usa 8 Nvidia V100 Tensor Core GPU disponibili tramite l’AWS Marketplace, la D-Wave Advantage (DWA) che implementa un algoritmo di annealing quantistico in un hardware programmabile.
Nel caso specifico utilizzando delle giunzioni Josephson superconduttrici per emulare la variante classica del problema. È stata confrontata anche la MemComputing che propone una piattaforma SasS per il calcolo inspirata dal funzionamento del cervello umano. Infine ha partecipato un gruppo di fisici ed informatici che includeva i professori Enzo Marinari, Giorgio Parisi (presidente dell’Accademia dei Lincei e recente vincitore del premio Wolf) e Federico Ricci-Tersenghi dell’Università Sapienza, il professor Victor Martin-Mayor dell’Università Complutense di Madrid, Mauro Bisson e Massimiliano Fatica, italiani che lavorano negli Stati Uniti per la Nvidia e chi scrive, dirigente tecnologo del Consiglio Nazionale delle Ricerche. Per rispondere alla sfida, il nostro gruppo ha utilizzato una soluzione innovativa ma basata su un modello di calcolo tradizionale implementata per un cluster di GPU.
…Come cercare una buca in un campo da golf da un’altezza di pochi centimetri
Per cercare di dare un’idea intuitiva della difficoltà di trovare un algoritmo adatto e della necessità che l’algoritmo fosse implementato in modo estremamente efficiente, è utile ricorrere ad un’analogia. Cercare la soluzione ad un problema di questo tipo è come cercare una buca in un campo da golf perfettamente rasato senza avere la possibilità di guardare il campo, se non da un’altezza di pochi centimetri. Solo se si è già veramente molto vicini alla buca si riesce a vederla ed il campo da golf è ovviamente enorme confrontato alle dimensioni della singola buca. Da notare come ci sono problemi simili, ma in cui è relativamente facile capire in che direzione muoversi mentre in questo caso non ci sono direzioni privilegiate. Una soluzione intuitiva può essere quella di partire da un qualunque punto e provare ad andare avanti sistematicamente, fino a quando non si arriva alla buca, evitando almeno di ripassare più di una volta nella stessa zona. Se ci si muove molto velocemente, può anche essere un’alternativa valida, in assenza di idee migliori, ma è chiaro che il tempo che si impiega (per quanto ci si possa muovere velocemente) dipende da quanto vicino (o lontano) si parte nella ricerca rispetto all’effettiva posizione della buca.
Campo da golf, vista da basso. Dove è la buca?
Se si è fortunati nella scelta del punto di partenza, il tempo può essere molto breve, ma partire da un punto vicino è un evento raro date le dimensioni del campo da golf. L’alternativa a cui abbiamo pensato, e che è alla base della soluzione che abbiamo proposto, è quella di partire da più punti (come se nella ricerca fossero coinvolte più persone) e andare avanti nella ricerca per un tempo fissato. Se nessuno dei punti di partenza si rileva fortunato, semplicemente si ricomincia da altri punti di partenza. In linea di principio, non si possono escludere casi in cui potrebbe essere meglio continuare la ricerca invece di ricominciare e bisogna individuare quale è il tempo massimo per cui cercare, prima di rinunciare e ricominciare da capo.
SatOnGPU, una soluzione innovativa, con le Graphics Processing Unit
Per gestire entrambi gli aspetti sono stati usati strumenti matematici e tecniche tipiche della meccanica statistica che non serve descrivere qui in dettaglio. È di più immediata comprensione il fatto che, dato un tempo massimo di ricerca, è importante massimizzare la velocità, in modo che a parità di tempo si esplori una parte maggiore delle possibili alternative. Qui entra in gioco la parte implementativa (si passa dalla teoria alla pratica) che deve riuscire a sfruttare al meglio la tecnologia a disposizione, nel nostro caso le GPU.
Le Graphics Processing Unit, come suggerisce il nome, sono “schede grafiche”, originariamente pensate per velocizzare la grafica, in particolare per i videogiochi ma da qualche anno sono diventate un acceleratore per molte applicazioni di calcolo numerico in cui è possibile eseguire contemporaneamente le stesse operazioni su dati diversi.
Ricordiamo che una delle ragioni del grande sviluppo che ha avuto il deep learning è proprio la possibilità che offrono le GPU di calcolare velocemente i prodotti tra tabelle di numeri (matrici) richiesti dall’addestramento ed esecuzione dei modelli basati su reti neurali “profonde”. Non sempre è semplice sfruttare bene il parallelismo nel calcolo reso possibile dalle GPU. Molti algoritmi sono stati originariamente pensati avendo in mente un modello di esecuzione sequenziale (un’operazione per volta) ed alcuni, addirittura, sembrano inevitabilmente sequenziali.
Per fortuna, in realtà, nella maggior parte dei casi, con un’attenta analisi del problema ed una buona conoscenza della piattaforma hardware/software, si può trovare un modo alternativo di esecuzione in cui sfruttare il parallelismo. Questo è esattamente quello che siamo riusciti a fare per fornire la risposta che ci è sembrata la migliore possibile alla sfida posta dal gruppo dell’USC.
Il problema è stato riformulato in modo da sfruttare il massimo grado di parallelismo, non solo partendo contemporaneamente da più punti (possibilità che viene in mente in maniera abbastanza intuitiva) ma anche muovendosi “in parallelo” dallo stesso punto. Se si torna alla formulazione originale del problema (trovare una particolare combinazione di N bit), significa partire contemporaneamente da diverse combinazioni e cambiare contemporaneamente più bit (invece di uno per volta). Se questo approccio viene ripetuto su più di una GPU, arriviamo ad un parallelismo a tre livelli. I risultati ottenuti sulle istanze del problema rese disponibili per il benchmark sono stati estremamente soddisfacenti come si può vedere nella figura che riassume le prestazioni di tutti.
La nostra soluzione è quella indicata da SatOnGPU; DAU è la piattaforma della Fujitsu; SBM quella della Toshiba; DWA è la piattaforma quantistica della D-Wave; MEM quella della Memcomputing e PT è il Parallel Tempering su CPU tradizionale usato dall’USC come punto di riferimento. Sono due le metriche da considerare per il confronto tra le diverse piattaforme. La prima è la dimensione massima del problema che si riesce a risolvere (chi arriva più a destra, verso valori più alti del numero di bit) e la seconda è la pendenza della curva che unisce i risultati per ogni piattaforma, minore è la pendenza, migliore è la scalabilità. Per entrambe, i risultati del SatOnGPU sono di gran lunga in vantaggio.
Per evitare equivoci, diciamo esplicitamente che sarebbe un errore generalizzare questo caso affermando che il calcolo quantistico o comunque modelli alternativi di calcolo sono una stravagante perdita di tempo e di soldi se si vuole risolvere un problema di ottimizzazione. Anche se le affermazioni sull’ormai prossima adozione su larga scala del calcolo quantistico sono quasi sicuramente, ad essere generosi, premature, è comunque importante continuare a fare ricerca nel campo del calcolo ad alte prestazioni (quantistico, classico, o in qualunque “variante”) ma con un approccio realmente scientifico e non di marketing mascherato. Purtroppo anche un gigante come Google (che non ha certo bisogno di pubblicità) ricorre, in questo campo, ad annunci ad effetto sulla raggiunta quantum supremacy che poi vengono di molto ridimensionati da due ricercatori senza paraocchi, armati solo di buone idee.
Nel campo del calcolo tradizionale abbiamo ancora molto da imparare sia a livello teorico sia, soprattutto, a livello pratico visto che spesso solo una frazione modesta (molto inferiore al 50%) delle prestazioni teoricamente possibili a livello hardware sono raggiunte dai codici che utilizziamo. Sfruttare al meglio le piattaforme di calcolo significa anche ridurre il loro consumo energetico. Ed è piuttosto strano che ci sia così poca attenzione a questo aspetto mentre molti parlano di crescita “sostenibile”.
Per chi fosse interessato ai dettagli, una descrizione completa (ma piuttosto tecnica) della nostra soluzione SatOnGPU alla sfida dell’USC con un’analisi completa dei risultati.
