Sistemul AI creează primele îmbunătățiri ale sortării codurilor în peste un deceniu – Ars Technica

Fără îndoială, oricine a studiat informatica de bază și-a petrecut timp să creeze un algoritm de sortare – cod care preia o listă neordonată de articole și le pune în ordine crescătoare sau descrescătoare. Este o provocare interesantă, deoarece există atât de multe moduri de a face acest lucru și pentru că oamenii au petrecut mult timp să descopere cum să facă această sortare cât mai eficient posibil.

Sortarea este atât de simplă încât algoritmii sunt încorporați în majoritatea bibliotecilor standard de limbaje de programare. Și în cazul bibliotecii C++ utilizate cu compilatorul LLVM, codul nu a fost atins de peste un deceniu.

Dar grupul Google DeepMind AI a dezvoltat acum un instrument de învățare prin consolidare care poate dezvolta algoritmi extrem de optimizați fără a fi mai întâi instruit pe exemple de cod uman. Trucul a fost să-l pregătească să trateze programarea ca pe un joc.

Totul este un joc

DeepMind, printre altele, este cunoscut pentru dezvoltarea de software care învață singur cum să joace jocuri. Această abordare sa dovedit extrem de eficientă, cucerind jocuri la fel de diverse precum șahul, El mergeȘi StarCraft. În timp ce detaliile variază în funcție de jocul cu care se ocupă, programul învață jucându-se singur și descoperă opțiuni care îi permit să maximizeze scorul.

Deoarece nu a fost instruit cu privire la jocurile jucate de oameni, sistemul DeepMind poate găsi modalități de a juca jocuri la care oamenii nu s-au gândit. Desigur, din moment ce joacă întotdeauna împotriva lui însuși, există cazuri în care a dezvoltat puncte oarbe pe care oamenii le pot exploata.

Această abordare este strâns legată de programare. Paradigmele lingvistice grozave scriu cod eficient pentru că au văzut o mulțime de exemple umane. Dar din această cauză, este foarte puțin probabil să dezvolte ceva ce oamenii nu au făcut înainte. Dacă căutăm să îmbunătățim algoritmi bine înțeleși, cum ar fi funcțiile de sortare, bazarea ceva pe codul uman existent vă va obține, în cel mai bun caz, o performanță echivalentă. Dar cum obții un AI pentru a alege cu adevărat o nouă abordare?

Cei de la DeepMind au adoptat aceeași abordare pe care au făcut-o cu șahul și El merge: Au transformat optimizarea codului într-un joc. Sistemul AlphaDev a dezvoltat algoritmi de compilare x86 care au tratat latența codului ca pe o lovitură și au încercat să minimizeze acel hit, asigurându-se în același timp că codul a rulat până la finalizare fără erori. Prin învățare prin consolidare, AlphaDev dezvoltă treptat capacitatea de a scrie cod foarte eficient și robust.

În interiorul AlphaDev

A spune că sistemul îmbunătățește latența este cu totul altă chestiune decât a explica cum funcționează. La fel ca majoritatea altor sisteme AI complexe, AlphaDev este alcătuit din mai multe componente distincte. Una este funcția de reprezentare, care urmărește performanța generală a codului pe măsură ce este dezvoltat. Aceasta include structura generală a algoritmului, precum și utilizarea registrelor x86 și a memoriei.

Sistemul adaugă instrucțiuni de asamblare individual, selectate de a Găsiți arborele Monte Carlo– din nou, o abordare împrumutată de la sistemele de jocuri. Aspectul „arboresc” al acestei abordări permite sistemului să se restrângă rapid la o zonă limitată dintr-o gamă largă de instrucțiuni posibile, în timp ce Monte Carlo adaugă un grad de aleatorie instrucțiunilor exacte care sunt alese din acea ramură. (Rețineți că „ajutor” în acest context include lucruri precum înregistrările specifice alese pentru a crea un ansamblu valid și complet.)

Apoi, sistemul evaluează starea codului de asamblare pentru latență și valabilitate și îi atribuie un scor și îl compară cu scorul scorului anterior. Și prin învățare prin întărire, raportează informații despre modul în care funcționează diferitele ramuri ale copacului, având în vedere starea programului. De-a lungul timpului, „învățați” cum să atingeți o condiție de joc câștigătoare – sortare finalizată – cu scor maxim, ceea ce înseamnă o latență minimă.

Principalul avantaj al acestui sistem este că antrenamentul nu trebuie să includă exemple de cod. În schimb, sistemul generează propriile exemple de cod și apoi le evaluează. În acest proces, se blochează informații despre care seturi de instrucțiuni sunt eficiente în sortare.

Cod util

Sortarea în programe complexe poate gestiona grupuri mari, arbitrare de articole. Dar la nivelul bibliotecilor standard, acestea sunt construite dintr-un set mare de funcții foarte specifice care se ocupă de o singură situație sau de câteva cazuri. De exemplu, există algoritmi separați pentru sortarea a trei elemente, patru articole și cinci articole. Și există un alt set de funcții care pot gestiona un număr arbitrar de articole până la un maxim – adică puteți apela una care sortează până la patru articole, dar nu mai mult.

DeepMind a setat AlphaDev pe fiecare dintre aceste funcții, dar acestea funcționează foarte diferit. Pentru funcțiile care se ocupă de un număr specificat de elemente, este posibil să scrieți cod fără ramuri unde execută cod diferit în funcție de starea variabilei. Ca urmare, performanța acestui cod este în general proporțională cu numărul de instrucțiuni necesare. AlphaDev a putut să tundă toate instrucțiunile Sort-3, Sort-5 și Sort-8, și chiar mai mult decât Sort-6 și Sort-7. A existat doar unul (rangul 4) în care nu a putut găsi o modalitate de a îmbunătăți codul uman. Rularea repetată a codului pe sisteme reale a arătat că mai puține instrucțiuni au dus la performanțe mai bune.

Sortarea unui număr variabil de intrări implică ramificarea în cod, iar diferitele procesoare au cantități diferite de hardware dedicate gestionării acestor ramuri. Prin urmare, codul a fost evaluat pe baza performanței sale pe 100 de dispozitive diferite. Din nou, AlphaDev a găsit modalități de a obține performanță suplimentară și vom arunca o privire la cum să o facem într-o singură situație: o funcție care sortează până la patru articole.

În implementarea actuală din biblioteca C++, codul rulează o serie de teste pentru a vedea de câte elemente are nevoie pentru a sorta și apelează funcția de sortare personalizată pentru acel număr de elemente. Codul revizuit face ceva și mai ciudat. Testează dacă există două elemente și apelează o funcție separată pentru a le sorta dacă este necesar. Dacă numărul este mai mare de doi, codul apelează pentru a sorta primele trei. Dacă există trei elemente, rezultatele de acest fel vor fi returnate.

Cu toate acestea, dacă există patru elemente de sortat, rulează un cod specializat care este foarte eficient la inserarea unui al patrulea articol în locul potrivit într-o matrice de trei elemente sortate. Aceasta pare o abordare ciudată, dar a depășit constant codul meu existent.

in productie

Deoarece AlphaDev a produs cod mai eficient, echipa a vrut să-l reintegreze în biblioteca standard C++ LLVM. Problema aici este că codul era mai degrabă în asamblare decât în ​​C++. Deci, au trebuit să lucreze înapoi și să-și dea seama ce cod C++ va produce același ansamblu. Odată făcut acest lucru, codul a fost îmbinat în lanțul de instrumente LLVM – prima dată când o parte din cod a fost modificată în peste un deceniu.

Drept urmare, cercetătorii au estimat că codul AlphaDev este acum executat de trilioane de ori pe zi.

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