AlphaDev scopre algoritmi di ordinamento più veloci

'AlphaDev discovers faster sorting algorithms'.

Nuovi algoritmi trasformeranno le fondamenta della computazione

La società digitale sta guidando una crescente domanda di calcolo e di consumo energetico. Negli ultimi cinque decenni, ci siamo affidati ai miglioramenti dell’hardware per stare al passo. Ma poiché i microchip si avvicinano ai loro limiti fisici, è fondamentale migliorare il codice che viene eseguito su di essi per rendere il calcolo più potente e sostenibile. Questo è particolarmente importante per gli algoritmi che compongono il codice eseguito trilioni di volte al giorno.

Nel nostro articolo pubblicato oggi su Nature, presentiamo AlphaDev, un sistema di intelligenza artificiale (IA) che utilizza l’apprendimento per rinforzo per scoprire algoritmi informatici migliorati – superando quelli perfezionati da scienziati e ingegneri nel corso di decenni.

AlphaDev ha scoperto un algoritmo più veloce per l’ordinamento, un metodo per l’organizzazione dei dati. Miliardi di persone utilizzano questi algoritmi ogni giorno senza rendersene conto. Essi sono alla base di tutto, dal ranking dei risultati di ricerca online e dei post sui social media, al modo in cui i dati vengono elaborati su computer e telefoni. Generare algoritmi migliori utilizzando l’IA trasformerà il modo in cui programmiamo i computer e avrà un impatto su tutti gli aspetti della nostra società digitale in continua crescita.

Condividendo in open source i nostri nuovi algoritmi di ordinamento nella principale libreria C++, milioni di sviluppatori e aziende di tutto il mondo ora li utilizzano nelle applicazioni di intelligenza artificiale in settori che vanno dal cloud computing e lo shopping online alla gestione della catena di approvvigionamento. Questo è il primo cambiamento apportato a questa parte della libreria di ordinamento in oltre un decennio e la prima volta che un algoritmo progettato tramite apprendimento per rinforzo viene aggiunto a questa libreria. Vediamo questo come una pietra miliare importante per utilizzare l’IA per ottimizzare il codice del mondo, un algoritmo alla volta.

Cos’è l’ordinamento?

L’ordinamento è un metodo per organizzare un certo numero di elementi in un ordine specifico. Esempi includono l’alfabetizzazione di tre lettere, l’ordinamento di cinque numeri dal più grande al più piccolo o l’ordinamento di un database di milioni di record.

Questo metodo si è evoluto nel corso della storia. Uno dei primi esempi risale al secondo e terzo secolo, quando gli studiosi hanno alfabetizzato migliaia di libri a mano sugli scaffali della Grande Biblioteca di Alessandria. Con la rivoluzione industriale, è stata inventata una macchina che poteva aiutare nell’ordinamento: le macchine per la tabulazione conservavano le informazioni su schede perforate, che furono utilizzate per raccogliere i risultati del censimento del 1890 negli Stati Uniti.

E con la diffusione dei computer commerciali negli anni ’50, sono stati sviluppati i primi algoritmi di informatica per l’ordinamento. Oggi, esistono molte tecniche di ordinamento e algoritmi diversi che vengono utilizzati nelle basi di codice in tutto il mondo per organizzare grandi quantità di dati online.

Illustrazione di ciò che fa un algoritmo di ordinamento. Una serie di numeri non ordinati viene inserita nell'algoritmo e vengono restituiti numeri ordinati.

Gli algoritmi contemporanei hanno richiesto decenni di ricerca da parte di scienziati informatici e programmatori per essere sviluppati. Sono così efficienti che apportare ulteriori miglioramenti rappresenta una sfida importante, simile a cercare un nuovo modo per risparmiare energia o un approccio matematico più efficiente. Questi algoritmi sono anche un pilastro dell’informatica, insegnati nei corsi introduttivi di informatica nelle università.

Ricerca di nuovi algoritmi

AlphaDev ha scoperto algoritmi più veloci partendo da zero anziché perfezionare algoritmi esistenti, e ha iniziato a cercare dove la maggior parte degli umani non guarda: le istruzioni di assembly del computer.

Le istruzioni di assembly vengono utilizzate per creare il codice binario che i computer devono mettere in atto. Mentre gli sviluppatori scrivono in linguaggi di programmazione come C++, noti come linguaggi di alto livello, ciò deve essere tradotto in istruzioni di assembly di “basso livello” affinché i computer possano capire.

Crediamo che a questo livello più basso esistano molti miglioramenti difficili da scoprire in un linguaggio di programmazione di livello superiore. La memoria e le operazioni dei computer sono più flessibili a questo livello, il che significa che ci sono significativamente più miglioramenti potenziali che potrebbero avere un impatto maggiore sulla velocità e sull’utilizzo dell’energia.

Il codice di solito viene scritto in un linguaggio di programmazione di alto livello come C++. Questo viene poi tradotto in istruzioni di CPU a basso livello, chiamate istruzioni di assembly, utilizzando un compilatore. Un assembler converte quindi le istruzioni di assembly in codice eseguibile che il computer può eseguire.
Figura A: Un esempio di algoritmo C++ che ordina fino a due elementi. ‍ Figura B: La corrispondente rappresentazione in assembly del codice.

Trovare i migliori algoritmi con un gioco

AlphaDev si basa su AlphaZero , il nostro modello di apprendimento per rinforzo che ha sconfitto i campioni del mondo in giochi come Go, scacchi e shogi. Con AlphaDev, mostriamo come questo modello possa passare dai giochi alle sfide scientifiche, e dalle simulazioni alle applicazioni reali.

Per addestrare AlphaDev a scoprire nuovi algoritmi, abbiamo trasformato l’ordinamento in un “gioco di assemblaggio” per un solo giocatore. Ad ogni turno, AlphaDev osserva l’algoritmo che ha generato e le informazioni contenute nell’unità di elaborazione centrale (CPU). Poi gioca una mossa scegliendo un’istruzione da aggiungere all’algoritmo..

Il gioco di assemblaggio è incredibilmente difficile perché AlphaDev deve cercare efficientemente attraverso un enorme numero di possibili combinazioni di istruzioni per trovare un algoritmo che possa ordinare e che sia più veloce di quello attuale. Il numero di possibili combinazioni di istruzioni è simile al numero di particelle nell’universo o al numero di possibili combinazioni di mosse nei giochi degli scacchi (10 120 giochi) e del Go (10 700 giochi). E una singola mossa sbagliata può invalidare l’intero algoritmo.

<img alt="Figura A: Il gioco di assemblaggio. Il giocatore, AlphaDev, riceve lo stato del sistema st come input e gioca una mossa at selezionando un'istruzione di assemblaggio da aggiungere all'algoritmo che è stato generato finora. ‍ Figura B: Il calcolo della ricompensa. Dopo ogni mossa, l'algoritmo generato viene alimentato con sequenze di input di test – per sort3, ciò corrisponde a tutte le combinazioni di sequenze di tre elementi. L'algoritmo genera quindi un output, che viene confrontato con l'output atteso delle sequenze ordinate per il caso dell'ordinamento. L'agente viene ricompensato in base alla correttezza e alla latenza dell'algoritmo.

Man mano che l’algoritmo viene costruito, istruzione dopo istruzione, AlphaDev verifica che sia corretto confrontando l’output dell’algoritmo con i risultati attesi. Per gli algoritmi di ordinamento, ciò significa che i numeri non ordinati entrano e i numeri ordinati correttamente escono. Ricompensiamo AlphaDev sia per l’ordinamento corretto dei numeri sia per la velocità ed efficienza con cui lo fa. AlphaDev vince il gioco scoprendo un programma corretto e più veloce.

Scoprire algoritmi di ordinamento più veloci

AlphaDev ha scoperto nuovi algoritmi di ordinamento che hanno portato a miglioramenti nella libreria di ordinamento LLVM libc++ fino al 70% più veloci per sequenze più brevi e circa l’1,7% più veloci per sequenze superiori a 250.000 elementi.

Ci siamo concentrati sul miglioramento degli algoritmi di ordinamento per sequenze più brevi di tre a cinque elementi. Questi algoritmi sono tra i più utilizzati perché vengono spesso chiamati molte volte come parte di funzioni di ordinamento più ampie. Migliorare questi algoritmi può portare a un aumento generale della velocità per l’ordinamento di qualsiasi numero di elementi.

Per rendere il nuovo algoritmo di ordinamento più utilizzabile per le persone, abbiamo decodificato gli algoritmi e li abbiamo tradotti in C++, uno dei linguaggi di programmazione più popolari utilizzati dagli sviluppatori. Questi algoritmi sono ora disponibili nella libreria di ordinamento standard LLVM libc++, utilizzata da milioni di sviluppatori e aziende in tutto il mondo.

Trovare approcci nuovi

AlphaDev non solo ha trovato algoritmi più veloci, ma ha anche scoperto approcci innovativi. I suoi algoritmi di ordinamento contengono nuove sequenze di istruzioni che risparmiano una singola istruzione ogni volta che vengono applicate. Ciò può avere un enorme impatto poiché questi algoritmi vengono utilizzati miliardi di volte al giorno.

Chiamiamo queste mosse di ‘swap e copia di AlphaDev’. Questo approccio innovativo ricorda la ‘mossa 37’ di AlphaGo – una mossa controintuitiva che ha sorpreso gli spettatori e ha portato alla sconfitta di un leggendario giocatore di Go. Con la mossa di swap e copia, AlphaDev salta un passaggio per collegare gli elementi in modo che sembri un errore ma in realtà è una scorciatoia. Questo dimostra la capacità di AlphaDev di scoprire soluzioni originali e mette in discussione il modo in cui pensiamo di migliorare gli algoritmi delle scienze informatiche.

Sinistra: L'implementazione originale con min(A,B,C). ‍ Destra: Mossa di scambio di AlphaDev - AlphaDev scopre che è sufficiente min(A,B).
Sinistra: L'implementazione originale con max (B, min (A, C, D)) utilizzata in un algoritmo di ordinamento più ampio per ordinare otto elementi. ‍ Destra: AlphaDev ha scoperto che è sufficiente max (B, min (A, C)) quando si utilizza la sua mossa di copia.

Dall’ordinamento all’hashing nelle strutture dati

Dopo aver scoperto algoritmi di ordinamento più veloci, abbiamo testato se AlphaDev potesse generalizzare e migliorare un diverso algoritmo delle scienze informatiche: l’hashing.

L’hashing è un algoritmo fondamentale nell’informatica utilizzato per recuperare, memorizzare e comprimere dati. Come un bibliotecario che utilizza un sistema di classificazione per trovare un certo libro, gli algoritmi di hashing aiutano gli utenti a sapere cosa stanno cercando e esattamente dove trovarlo. Questi algoritmi prendono i dati per una chiave specifica (ad esempio il nome utente “Jane Doe”) e li trasformano in un hash – un processo in cui i dati grezzi vengono convertiti in una stringa unica di caratteri (ad esempio 1234ghfty). Questo hash viene utilizzato dal computer per recuperare i dati correlati alla chiave in modo rapido anziché cercare tutti i dati.

Abbiamo applicato AlphaDev a uno degli algoritmi di hashing più comunemente utilizzati nelle strutture dati per cercare di scoprire un algoritmo più veloce. E quando lo abbiamo applicato all’intervallo di 9-16 byte della funzione di hashing, l’algoritmo scoperto da AlphaDev era il 30% più veloce.

Quest’anno, il nuovo algoritmo di hashing di AlphaDev è stato rilasciato nella libreria open-source Abseil, disponibile a milioni di sviluppatori in tutto il mondo, e stimiamo che venga utilizzato miliardi di volte al giorno.

Ottimizzare il codice del mondo, un algoritmo alla volta

Ottimizzando e lanciando algoritmi di ordinamento e hashing migliorati utilizzati da sviluppatori di tutto il mondo, AlphaDev ha dimostrato la sua capacità di generalizzare e scoprire nuovi algoritmi con un impatto concreto nel mondo reale. Vediamo AlphaDev come un passo verso lo sviluppo di strumenti di intelligenza artificiale ad uso generale che potrebbero aiutare a ottimizzare l’intero ecosistema informatico e risolvere altri problemi che saranno vantaggiosi per la società.

Anche se l’ottimizzazione nello spazio delle istruzioni di assembly di basso livello è molto potente, ci sono limitazioni man mano che l’algoritmo cresce, e attualmente stiamo esplorando la capacità di AlphaDev di ottimizzare gli algoritmi direttamente in linguaggi di alto livello come C++, che sarebbe più utile per gli sviluppatori.

Le scoperte di AlphaDev, come le mosse di swap e copia, non solo dimostrano che può migliorare gli algoritmi ma anche trovare nuove soluzioni. Speriamo che queste scoperte ispirino sia i ricercatori che gli sviluppatori a creare tecniche e approcci che possano ottimizzare ulteriormente gli algoritmi fondamentali per creare un ecosistema informatico più potente e sostenibile.

Per saperne di più sull’ottimizzazione dell’ecosistema informatico:

Leggi il nostro caso di studio: https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools