AlphaDev scopre algoritmi di ordinamento più veloci | Intelligenza-Artificiale

Indice contenuti

Nuovi algoritmi trasformeranno le basi dell’informatica

La società digitale sta guidando una crescente domanda di calcolo e di utilizzo dell’energia. Negli ultimi cinquant’anni abbiamo fatto affidamento sui miglioramenti dell’hardware per tenere il passo. Ma man mano che i microchip si avvicinano ai loro limiti fisici, è fondamentale migliorare il codice che viene eseguito su di essi per rendere l’informatica più potente e sostenibile. Ciò è particolarmente importante per gli algoritmi che compongono il codice che viene eseguito trilioni di volte al giorno.

Nel nostro articolo pubblicato oggi in Naturapresentiamo AlphaDev, un sistema di intelligenza artificiale (AI) che utilizza l’apprendimento per rinforzo per scoprire algoritmi informatici avanzati, superando quelli perfezionati da scienziati e ingegneri nel corso di decenni.

AlphaDev ha scoperto un algoritmo più veloce per l’ordinamento, un metodo per ordinare i dati. Miliardi di persone utilizzano questi algoritmi ogni giorno senza rendersene conto. Sono alla base di tutto, dal posizionamento dei risultati di ricerca online e dei post sui social al modo in cui i dati vengono elaborati su computer e telefoni. La generazione di algoritmi migliori utilizzando l’intelligenza artificiale trasformerà il modo in cui programmiamo i computer e avrà un impatto su tutti gli aspetti della nostra società sempre più digitale.

Rendendo open source i nostri nuovi algoritmi di ordinamento in la libreria principale C++milioni di sviluppatori e aziende in tutto il mondo ora lo utilizzano su applicazioni IA in tutti i settori, dal cloud computing e lo shopping online alla gestione della catena di fornitura. Questa è la prima modifica a questa parte della libreria di ordinamento in oltre un decennio e la prima volta che un algoritmo progettato tramite l’apprendimento per rinforzo viene aggiunto a questa libreria. Consideriamo questo un importante trampolino di lancio verso l’utilizzo dell’intelligenza artificiale per ottimizzare il codice mondiale, un algoritmo alla volta.

Cos’è l’ordinamento?

L’ordinamento è un metodo per organizzare un numero di elementi in un ordine particolare. Gli esempi includono l’alfabetizzazione di tre lettere, la disposizione 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 II e III secolo, quando gli studiosi alfabetizzarono a mano migliaia di libri sugli scaffali della Grande Biblioteca di Alessandria. Dopo la rivoluzione industriale, arrivò l’invenzione di macchine che potevano aiutare con lo smistamento: le macchine per la tabulazione memorizzavano le informazioni su schede perforate che venivano utilizzate per raccogliere i risultati del censimento del 1890 negli Stati Uniti.

E con l’avvento dei computer commerciali negli anni ’50, abbiamo assistito allo sviluppo dei primi algoritmi informatici per l’ordinamento. Oggi esistono molte tecniche e algoritmi di ordinamento diversi utilizzati nelle basi di codice di tutto il mondo per organizzare enormi quantità di dati online.

Illustrazione di cosa fa un algoritmo di ordinamento. Nell’algoritmo viene inserita una serie di numeri non ordinati e vengono emessi numeri ordinati.

Per sviluppare gli algoritmi contemporanei ci sono voluti decenni di ricerca da parte di informatici e programmatori. Sono così efficienti che apportare ulteriori miglioramenti è una sfida importante, come cercare di trovare un nuovo modo per risparmiare elettricità o un approccio matematico più efficiente. Questi algoritmi sono anche una pietra angolare dell’informatica, insegnati nei corsi introduttivi di informatica nelle università.

Alla ricerca di nuovi algoritmi

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

Le istruzioni di assemblaggio vengono utilizzate per creare codice binario che i computer possano mettere in azione. Mentre gli sviluppatori scrivono in linguaggi di codifica come C++, noti come linguaggi di alto livello, questo deve essere tradotto in istruzioni di assemblaggio di “basso livello” affinché i computer possano comprenderle.

Riteniamo che esistano molti miglioramenti a questo livello inferiore che potrebbero essere difficili da scoprire in un linguaggio di codifica di livello superiore. L’archiviazione e le operazioni dei computer sono più flessibili a questo livello, il che significa che ci sono molti più potenziali miglioramenti che potrebbero avere un impatto maggiore sulla velocità e sul consumo di energia.

Il codice è in genere scritto in un linguaggio di programmazione di alto livello come C++. Questo viene poi tradotto in istruzioni CPU di basso livello, chiamate istruzioni di assembly, utilizzando un compilatore. Un assemblatore converte quindi le istruzioni di assemblaggio in codice macchina eseguibile che il computer può eseguire.

**Figura A:** Un esempio di algoritmo C++ che ordina fino a due elementi.
‍**Figura B:** La rappresentazione dell’assembly corrispondente del codice.

Trovare i migliori algoritmi con un gioco

AlphaDev è basato su AlphaZeroil 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 può trasferirsi dai giochi alle sfide scientifiche e dalle simulazioni alle applicazioni nel mondo reale.

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

Il gioco dell’assemblaggio è incredibilmente difficile perché AlphaDev deve cercare in modo efficiente un numero enorme di possibili combinazioni di istruzioni per trovare un algoritmo in grado di ordinare ed è più veloce di quello attualmente migliore. Il numero di possibili combinazioni di istruzioni è simile al numero di particelle nell’universo o al numero di possibili combinazioni di mosse nel gioco degli scacchi (10¹²⁰ giochi) e Go (10⁷⁰⁰ Giochi). E una singola mossa sbagliata può invalidare l’intero algoritmo.

**Figura A:** Il gioco dell’assemblaggio. Il giocatore, AlphaDev, riceve lo stato del sistema st come input e gioca una mossa selezionando un’istruzione di assembly 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 prova: 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 previsto delle sequenze ordinate nel caso dell’ordinamento. L’agente viene premiato in base alla correttezza e alla latenza dell’algoritmo.

Man mano che l’algoritmo viene creato, un’istruzione alla volta, AlphaDev ne verifica la correttezza confrontando l’output dell’algoritmo con i risultati attesi. Per gli algoritmi di ordinamento, ciò significa che i numeri non ordinati entrano e escono i numeri ordinati correttamente. Premiamo AlphaDev sia per aver ordinato correttamente i numeri sia per la rapidità ed efficienza con cui lo fa. AlphaDev vince la partita scoprendo un programma corretto e più veloce.

Alla scoperta di algoritmi di ordinamento più veloci

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

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

Per rendere il nuovo algoritmo di ordinamento più utilizzabile dalle persone, abbiamo decodificato gli algoritmi e li abbiamo tradotti in C++, uno dei linguaggi di codifica più popolari utilizzati dagli sviluppatori. Questi algoritmi sono ora disponibili nel file Libreria di ordinamento standard LLVM libc++utilizzato da milioni di sviluppatori e aziende in tutto il mondo.

Trovare nuovi approcci

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

Chiamiamo queste “mosse di scambio e copia AlphaDev”. Questo approccio innovativo ricorda la “mossa 37” di AlphaGo, una giocata controintuitiva che ha sbalordito gli spettatori e ha portato alla sconfitta di un leggendario giocatore di Go. Con lo spostamento di scambio e copia, AlphaDev salta un passaggio per connettere gli elementi in un modo che sembra un errore ma in realtà è una scorciatoia. Ciò dimostra la capacità di AlphaDev di scoprire soluzioni originali e sfidare il modo in cui pensiamo a come migliorare gli algoritmi informatici.

**Sinistra:** L’implementazione originale con min(A,B,C).
‍**Giusto:** AlphaDev Swap Move – AlphaDev scopre che hai solo bisogno di 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.
‍**Giusto:** AlphaDev ha scoperto che è necessario solo max (B, min (A, C)) quando si utilizza la 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 informatico: l’hashing.

L’hashing è un algoritmo fondamentale nell’informatica utilizzato per recuperare, archiviare e comprimere i dati. Come un bibliotecario che utilizza un sistema di classificazione per individuare un determinato libro, gli algoritmi di hashing aiutano gli utenti a sapere cosa stanno cercando ed esattamente dove trovarlo. Questi algoritmi prendono i dati per una chiave specifica (ad esempio il nome utente “Jane Doe”) e li sottopongono a hash: un processo in cui i dati grezzi vengono trasformati in una stringa di caratteri univoca (ad esempio 1234ghfty). Questo hash viene utilizzato dal computer per recuperare rapidamente i dati relativi alla chiave anziché cercare tutti i dati.

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

Quest’anno, il nuovo algoritmo di hashing di AlphaDev è stato rilasciato in open source Biblioteca di discesa in corda doppiadisponibile per milioni di sviluppatori in tutto il mondo e stimiamo che venga utilizzato trilioni di volte al giorno.

Ottimizzare il codice mondiale, un algoritmo alla volta

Ottimizzando e lanciando algoritmi di ordinamento e hashing migliorati utilizzati dagli sviluppatori di tutto il mondo, AlphaDev ha dimostrato la sua capacità di generalizzare e scoprire nuovi algoritmi con un impatto nel mondo reale. Consideriamo AlphaDev un passo avanti verso lo sviluppo di strumenti di intelligenza artificiale generici che potrebbero aiutare a ottimizzare l’intero ecosistema informatico e a risolvere altri problemi a beneficio della società.

Sebbene l’ottimizzazione nello spazio delle istruzioni di assemblaggio di basso livello sia molto potente, ci sono delle 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 sarebbero più utili per gli sviluppatori.

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

Ulteriori informazioni sull’ottimizzazione dell’ecosistema informatico: