Il sistema AI crea i primi miglioramenti all’ordinamento del codice in oltre un decennio – Ars Technica

Senza dubbio chiunque abbia studiato informatica di base ha passato del tempo a ideare un algoritmo di ordinamento, un codice che prende un elenco non ordinato di elementi e li mette in ordine crescente o decrescente. È una sfida interessante perché ci sono così tanti modi per farlo e perché le persone hanno passato molto tempo a capire come eseguire questo ordinamento nel modo più efficiente possibile.

L’ordinamento è così semplice che gli algoritmi sono incorporati nella maggior parte delle librerie standard dei linguaggi di programmazione. E nel caso della libreria C++ utilizzata con il compilatore LLVM, il codice non è stato toccato da oltre un decennio.

Ma il gruppo DeepMind AI di Google ha ora sviluppato uno strumento di apprendimento per rinforzo in grado di sviluppare algoritmi altamente ottimizzati senza prima essere addestrati su esempi di codice umano. Il trucco era prepararlo a trattare la programmazione come un gioco.

È tutto un gioco

DeepMind, tra le altre cose, è noto per lo sviluppo di software che insegna da solo a giocare. Questo approccio si è dimostrato molto efficace, conquistando giochi diversi come gli scacchi, Lui vaE Astronave. Mentre i dettagli variano a seconda del gioco con cui ha a che fare, il programma impara giocando da solo e scopre le opzioni che gli consentono di massimizzare il punteggio.

Poiché non è stato addestrato sui giochi giocati dagli umani, il sistema DeepMind può capire modi per giocare a giochi a cui gli umani non hanno pensato. Naturalmente, poiché gioca sempre contro se stesso, ci sono casi in cui ha sviluppato punti ciechi che gli umani possono sfruttare.

Questo approccio è molto rilevante per la programmazione. Grandi paradigmi linguistici scrivono codice efficiente perché hanno visto molti esempi umani. Ma a causa di ciò, è molto improbabile che sviluppino qualcosa che gli umani non hanno mai fatto prima. Se stiamo cercando di migliorare algoritmi ben compresi, come le funzioni di ordinamento, basando qualcosa sul codice umano esistente, nella migliore delle ipotesi, otterrai prestazioni equivalenti. Ma come si fa a convincere un’intelligenza artificiale a selezionare davvero un nuovo approccio?

I ragazzi di DeepMind hanno adottato lo stesso approccio che hanno adottato con gli scacchi e Lui va: Hanno trasformato l’ottimizzazione del codice in un gioco. Il sistema AlphaDev ha sviluppato algoritmi di compilazione x86 che trattavano la latenza del codice come un hit e cercavano di minimizzare quell’hit assicurando al tempo stesso che il codice venisse completato senza errori. Attraverso l’apprendimento per rinforzo, AlphaDev sviluppa gradualmente la capacità di scrivere codice altamente efficiente e robusto.

All’interno di AlphaDev

Dire che il sistema migliora la latenza è tutt’altra cosa che spiegare come funziona. Come la maggior parte degli altri sistemi di intelligenza artificiale complessi, AlphaDev è costituito da diversi componenti distinti. Una è la funzione di rappresentazione, che tiene traccia delle prestazioni complessive del codice mentre viene sviluppato. Ciò include la struttura complessiva dell’algoritmo, nonché l’uso di registri e memoria x86.

Il sistema aggiunge singolarmente le istruzioni di montaggio, selezionate da a Trova l’albero di Monte Carlo– ancora una volta, un approccio mutuato dai sistemi di gioco. L’aspetto “albero” di questo approccio consente al sistema di restringersi rapidamente a un’area limitata da un’ampia gamma di possibili istruzioni, mentre Monte Carlo aggiunge un grado di casualità alle istruzioni esatte che vengono scelte da quel ramo. (Si noti che “help” in questo contesto include cose come i record specifici scelti per creare un assieme valido e completo.)

Il sistema quindi valuta lo stato del codice assembly per latenza e validità e gli assegna un punteggio e lo confronta con il punteggio del punteggio precedente. E attraverso l’apprendimento per rinforzo, mette in relazione le informazioni su come funzionano i diversi rami dell’albero, dato lo stato del programma. Nel tempo, “impara” come ottenere una condizione di gioco vincente – ordinamento completato – con il punteggio massimo, il che significa latenza minima.

Il vantaggio principale di questo sistema è che l’addestramento non deve includere alcun esempio di codice. Al contrario, il sistema genera i propri esempi di codice e quindi li valuta. Nel processo, viene bloccato sulle informazioni su quali set di istruzioni sono efficaci nell’ordinamento.

Codice utile

L’ordinamento in programmi complessi può gestire gruppi di elementi ampi e arbitrari. Ma a livello di librerie standard, sono costituite da un ampio insieme di funzioni molto specifiche che gestiscono solo una situazione o pochi casi. Ad esempio, esistono algoritmi separati per ordinare tre elementi, quattro elementi e cinque elementi. E c’è un altro insieme di funzioni in grado di gestire un numero arbitrario di elementi fino a un massimo, il che significa che puoi chiamarne uno che ordina fino a quattro elementi, ma non di più.

DeepMind ha impostato AlphaDev su ciascuna di queste funzioni, ma funzionano in modo molto diverso. Per le funzioni che gestiscono un numero specificato di elementi, è possibile scrivere codice senza rami in cui esegue codice diverso in base allo stato della variabile. Di conseguenza, le prestazioni di questo codice sono generalmente proporzionali al numero di istruzioni richieste. AlphaDev è stato in grado di eliminare tutte le istruzioni Sort-3, Sort-5 e Sort-8, e ancor più di Sort-6 e Sort-7. Ce n’era solo uno (grado 4) in cui non riusciva a trovare un modo per migliorare il codice umano. L’esecuzione ripetuta del codice su sistemi reali ha mostrato che meno istruzioni si traducevano in prestazioni migliori.

L’ordinamento di un numero variabile di voci comporta la ramificazione nel codice e diversi processori hanno diverse quantità di hardware dedicato alla gestione di questi rami. Pertanto, il codice è stato valutato in base alle sue prestazioni su 100 dispositivi diversi. Anche in questo caso, AlphaDev ha trovato il modo di ottenere prestazioni extra e daremo un’occhiata a come farlo in una situazione: una funzione che ordina fino a quattro elementi.

Nell’attuale implementazione nella libreria C++, il codice esegue una serie di test per vedere quanti elementi deve ordinare e chiama la funzione di ordinamento personalizzata per quel numero di elementi. Il codice rivisto fa qualcosa di ancora più strano. Verifica se sono presenti due elementi e chiama una funzione separata per ordinarli se necessario. Se il conteggio è maggiore di due, il codice chiama per ordinare i primi tre. Se sono presenti tre elementi, verranno restituiti i risultati di questo tipo.

Tuttavia, se ci sono quattro elementi da ordinare, esegue un codice specializzato che è molto efficiente nell’inserire un quarto elemento nella posizione appropriata all’interno di un array di tre elementi ordinati. Sembra un approccio strano, ma ha costantemente superato il mio codice esistente.

in produzione

Poiché AlphaDev ha prodotto un codice più efficiente, il team ha voluto reintegrarlo nella libreria C++ standard di LLVM. Il problema qui è che il codice era in assembly anziché in C++. Quindi, hanno dovuto lavorare all’indietro e capire quale codice C++ avrebbe prodotto lo stesso assembly. Una volta fatto ciò, il codice è stato unito alla toolchain LLVM, la prima volta che una parte del codice è stata modificata in oltre un decennio.

Di conseguenza, i ricercatori hanno stimato che il codice AlphaDev viene ora eseguito migliaia di miliardi di volte al giorno.

Natura, 2023. DOI: 10.1038/s41586-023-06004-9 (sui DOI).