AlphaDev
| Tipus | model d'intel·ligència artificial  |
|---|---|
| Equip | |
| Desenvolupador(s) | Google DeepMind |
AlphaDev és un sistema d'intel·ligència artificial desenvolupat per Google DeepMind per descobrir algorismes informàtics millorats mitjançant l'aprenentatge per reforç. AlphaDev es basa en AlphaZero, un sistema que dominava els jocs d'escacs, shogi i go mitjançant el joc individual. AlphaDev aplica el mateix enfocament per trobar algorismes més ràpids per a tasques fonamentals com ara l'ordenació i el hush.[1][2]
Desenvolupament
[modifica]El 7 de juny de 2023, Google DeepMind va publicar un article a Nature presentant AlphaDev, que va descobrir nous algorismes que superaven els mètodes més avançats per a algorismes de classificació petits.[3] Per exemple, AlphaDev va trobar una seqüència de llenguatge assemblador més ràpida per ordenar seqüències de 5 elements.[4] Després d'analitzar els algorismes en profunditat, AlphaDev va descobrir dues seqüències úniques d'instruccions d'assemblatge anomenades moviments d'intercanvi i còpia AlphaDev que eviten una sola instrucció d'assemblatge cada vegada que s'apliquen.[3][5] Per als algorismes d'ordenació variable, AlphaDev va descobrir estructures d'algorismes fonamentalment diferents. Per exemple, per a VarSort4 (ordenació de fins a 4 elements), AlphaDev va descobrir un algorisme 29 instruccions d'assemblador més curt que el benchmark humà.[3] AlphaDev també va millorar la velocitat dels algorismes de resum fins a un 30% en certs casos.
El gener de 2022, Google DeepMind va presentar els seus nous algorismes d'ordenació a l'organització que gestiona C++, un dels llenguatges de programació més populars del món, i després d'una revisió independent, els algorismes d'AlphaDev es van afegir a la biblioteca.[6] Aquest va ser el primer canvi als algorismes d'ordenació de la biblioteca estàndard de C++ en més d'una dècada i la primera actualització que va incloure un algorisme descobert mitjançant IA.[6] El gener de 2023, DeepMind també va afegir el seu algorisme de resum per a entrades de 9 a 16 bytes a la biblioteca de codi obert C++ Abseil.[7][6] Google estima que aquests dos algorismes s'utilitzen bilions de vegades cada dia.
Disseny
[modifica]AlphaDev està construït sobre AlphaZero, el model d'aprenentatge per reforç que DeepMind va entrenar per dominar jocs com el Go i els escacs.[8] L'avenç de l'empresa va ser tractar el problema de trobar un algorisme més ràpid com un joc i després entrenar la seva IA per guanyar-lo.[9] AlphaDev juga a un joc per a un sol jugador on l'objectiu és construir iterativament un algorisme en llenguatge assemblador que sigui ràpid i correcte.[10] AlphaDev utilitza una xarxa neuronal per guiar la seva cerca de moviments òptims i aprèn de la seva pròpia experiència i demostracions sintètiques.
AlphaDev mostra el potencial de la IA per fer avançar els fonaments de la informàtica i optimitzar el codi per a diferents criteris. Google DeepMind espera que AlphaDev inspiri més investigacions sobre l'ús de la IA per descobrir nous algorismes i millorar els existents.
Algorisme
[modifica]L'algorisme d'aprenentatge principal d'AlphaDev és una extensió d'AlphaZero.
Codificació de la programació en assemblador en un joc
[modifica]Per tal d'utilitzar AlphaZero en la programació en assemblador, els autors van crear una representació vectorial basada en Transformer dels programes en assemblador dissenyada per capturar la seva estructura subjacent.[11] Aquesta representació finita permet a una xarxa neuronal jugar a la programació en assemblador com un joc amb un nombre finit de moviments possibles (com ara Go),
La representació utilitza els components següents:
- Una xarxa Transformer, per codificar els codis d'operació d'assembly, es converteixen en codificacions d'un sol ús i es concatenen per formar la seqüència d'entrada en brut.
- Una xarxa de perceptrons multicapa, que codifica l'"estat de la CPU", és a dir, els estats de cada registre i ubicació de memòria per a un conjunt d'entrades determinat,
Jugant al joc
[modifica]L'estat del joc és el programa d'assemblador generat fins a un punt donat.
El moviment de joc és una instrucció addicional afegida al programa d'assemblador actual.
La recompensa del joc depèn de la correcció i la latència del programa d'assemblatge. Per reduir costos, AlphaDev només calcula la latència real mesurada en menys del 0,002% dels programes generats, ja que no avalua la latència durant el procés de cerca. En comptes d'això, utilitza dues funcions que estimen la correcció i la latència mitjançant l'entrenament mitjançant aprenentatge supervisat utilitzant els valors reals mesurats de correcció i latència.
Resultat
[modifica]Funció resumida
[modifica]AlphaDev va desenvolupar algorismes de resum per a entrades de 9 a 16 bytes a Abseil, una col·lecció de codi obert d'algorismes C++ preescrits.
Biblioteca d'ordenació estàndard LLVM
[modifica]AlphaDev va descobrir nous algorismes d'ordenació, que van comportar millores de fins al 70% a la biblioteca d'ordenació libc++ de LLVM per a seqüències més curtes i millores d'aproximadament l'1,7% per a seqüències que superen els 250.000 elements. Aquestes millores s'apliquen als tipus de dades uint32, uint64 i float per a les arquitectures de CPU ARMv8, Intel Skylake i AMD Zen 2. L'assemblatge condicional sense branques d'AlphaDev i el nou moviment d'intercanvi van contribuir a aquestes millores de rendiment. Els algorismes descoberts van ser sotmesos a enginyeria inversa des de l'assemblador de baix nivell fins a C++, i s'han inclòs oficialment a la biblioteca d'ordenació estàndard libc++.
Millora de la deserialització a protobuf
[modifica]AlphaDev va aprendre una funció de deserialització VarInt optimitzada a protobuf,[12] superant el punt de referència humà per a entrades de valor únic aproximadament tres vegades en termes de velocitat. AlphaDev també va descobrir un nou moviment d'assignació VarInt, que combina dues operacions en una sola instrucció per estalviar latència.
Comparació amb l'enfocament lògic d'IA
[modifica]El rendiment d'AlphaDev es va comparar amb la superoptimització estocàstica,[13] un enfocament lògic d'IA. Aquest últim es va executar amb almenys la mateixa quantitat de recursos i temps de rellotge de paret que AlphaDev. Els resultats van mostrar que AlphaDev-S requereix una quantitat prohibitiva de temps per optimitzar directament la latència, ja que la latència s'ha de calcular després de cada mutació. Com a tal, AlphaDev-S optimitza per a un proxy de latència, concretament la longitud de l'algorisme, i, al final de l'entrenament, es busquen tots els programes correctes generats per AlphaDev-S.
Referències
[modifica]- ↑ Mankowitz, Daniel J.; Michi, Andrea; Zhernov, Anton; Gelmi, Marco; Selvi, Marco Nature, 618, 7964, 2023, p. 257–263. Bibcode: 2023Natur.618..257M. DOI: 10.1038/s41586-023-06004-9. PMC: 10247365. PMID: 37286649.
- ↑ «AlphaDev discovers faster sorting algorithms» (en anglès). Blog. Google DeepMind, 07-06-2023. Arxivat de l'original el 2023-06-20. [Consulta: 20 juny 2023].
- 1 2 3 Mankowitz, Daniel J.; Michi, Andrea; Zhernov, Anton; Gelmi, Marco; Selvi, Marco Nature, 618, 7964, 2023, p. 257–263. Bibcode: 2023Natur.618..257M. DOI: 10.1038/s41586-023-06004-9. PMC: 10247365. PMID: 37286649.
- ↑ , <https://github.com/deepmind/alphadev>. Consulta: 21 juny 2023
- ↑ Tunney, Justine. «Understanding DeepMind's Sorting Algorithm» (en anglès). justine.lol, 20-06-2023. Arxivat de l'original el 2023-06-18. [Consulta: 20 juny 2023].
- 1 2 3 Heaven, Will Douglas. «Google DeepMind's game-playing AI just found another way to make code faster» (en anglès). MIT Technology Review, 07-06-2023. Arxivat de l'original el 2023-06-14. [Consulta: 20 juny 2023].
- ↑ «⚙ D118029 Introduce branchless sorting functions for sort3, sort4 and sort5.» (en anglès). reviews.llvm.org. [Consulta: 21 juny 2023].
- ↑ Heaven, Will Douglas. «Google DeepMind's game-playing AI just found another way to make code faster» (en anglès). MIT Technology Review, 07-06-2023. Arxivat de l'original el 2023-06-14. [Consulta: 20 juny 2023].
- ↑ «AlphaDev discovers faster sorting algorithms» (en anglès). Blog. Google DeepMind, 07-06-2023. Arxivat de l'original el 2023-06-20. [Consulta: 20 juny 2023].
- ↑ Mankowitz, Daniel J.; Michi, Andrea; Zhernov, Anton; Gelmi, Marco; Selvi, Marco Nature, 618, 7964, 2023, p. 257–263. Bibcode: 2023Natur.618..257M. DOI: 10.1038/s41586-023-06004-9. PMC: 10247365. PMID: 37286649.
- ↑ Mankowitz, Daniel J.; Michi, Andrea; Zhernov, Anton; Gelmi, Marco; Selvi, Marco Nature, 618, 7964, 2023, p. 257–263. Bibcode: 2023Natur.618..257M. DOI: 10.1038/s41586-023-06004-9. PMC: 10247365. PMID: 37286649.
- ↑ «VarInt protocol buffer serialization and deserialization» (en anglès). protobuf.dev. [Consulta: 24 juny 2023].
- ↑ Schkufza, Eric; Sharma, Rahul; Aiken, Alex ACM SIGARCH Computer Architecture News, 41, 1, 16-03-2013, p. 305–316. arXiv: 1211.0557. DOI: 10.1145/2490301.2451150. ISSN: 0163-5964 [Consulta: free].