Da un modello di calcolo tradizionale una soluzione innovativa di problemi QUBO, Quadratic Unconstrained Binary Optimization
Massimo Bernaschi, dirigente tecnologo dell’Istituto per le applicazioni del calcolo del Cnr spiega cos’è SatOnGPU, una combinazione di algoritmi e tecnologia che ha permesso non solo di vincere una sfida computazionale, ma apre anche la strada alla soluzione di una classe di problemi molto complessi e di grande rilevanza pratica.
Molti problemi pratici rilevanti, in settori anche molto differenti tra loro quali, ad esempio, la logistica, lo sviluppo di nuovi materiali, l’intelligenza artificiale, la finanza o la gestione del traffico aereo, richiedono sforzi computazionali notevoli, per lo più formulabili come problemi di ottimizzazione combinatoria.
Da un punto di vista semplificato, si tratta di far trovare a un calcolatore la giusta combinazione di N bit, minimizzando le risorse di calcolo (cioè il tempo di computazione e la memoria utilizzata).
Una particolare classe di problemi è quella chiamata QUBO (Quadratic Unconstrained Binary Optimization), dove il numero di combinazioni da provare, per trovare una soluzione, è dell’ordine di 2N (ovvero, con N uguale a 64, si hanno circa 20 miliardi di miliardi di combinazioni).
Una collaborazione tra l’Università Sapienza, l’Università Complutense di Madrid, il colosso statunitense Nvidia e il Cnr ha proposto una soluzione a problemi QUBO basata su cluster di GPU (Graphics Processing Unit), schede originariamente pensate per velocizzare la grafica, (es. nei videogiochi), ma utilizzate negli ultimi anni per eseguire velocemente poderosi calcoli numerici. Tale piattaforma, denominata SatOnGPU, si è rivelata la più performante nel confronto svolto dalla University of Southern California (USC) con altre piattaforme hardware/software (incluso un computer quantistico), ognuna dotata di un proprio algoritmo ottimizzato per la ricerca della soluzione per un insieme di problemi QUBO.
Una piattaforma è più adatta a risolvere dei problemi computazionali tipo QUBO se la crescita del tempo per svolgere un calcolo complesso, all’aumentare di N, è più lenta (ovvero se, a parità di tempo, riesce a risolvere problemi più grandi).
Le GPU, negli ultimi anni, hanno avuto un ruolo chiave nello sviluppo del deep learning e dell’intelligenza artificiale, perché permettono di calcolare velocemente i prodotti tra tabelle di numeri (matrici) utilizzate per “addestrare” reti neurali profonde. La sfida lanciata dalla University of Southern California è stata vinta grazie a un’attenta analisi del problema e un’approfondita conoscenza della piattaforma hardware/software che ha permesso di sfruttare le possibilità di calcolo parallelo fornite dalle GPU.
SatOnGPU si basa su metodi calcolo che si possono definire tradizionali laddove, ultimamente, ingenti risorse si stanno concentrando, invece, sullo sviluppo del cosiddetto calcolo quantistico. Ciò a dimostrazione che nei modelli di calcolo tradizionale c’è ancora molto da esplorare, sia per sfruttarne a pieno le prestazioni, sia per ridurre il loro consumo energetico.
Vedi anche: