AI-systeem zorgt voor eerste verbeteringen in codesortering in meer dan tien jaar – Ars Technica

Ongetwijfeld heeft iedereen die basiscomputerwetenschap heeft gestudeerd tijd besteed aan het bedenken van een sorteeralgoritme – code die een ongeordende lijst met items neemt en ze in oplopende of aflopende volgorde plaatst. Het is een interessante uitdaging omdat er zoveel manieren zijn om dit te doen en omdat mensen veel tijd hebben besteed aan het uitzoeken hoe ze dit zo efficiënt mogelijk kunnen sorteren.

Sorteren is zo eenvoudig dat de algoritmen zijn ingebouwd in de meeste standaardbibliotheken met programmeertalen. En in het geval van de C++-bibliotheek die wordt gebruikt met de LLVM-compiler, is de code al meer dan tien jaar niet meer aangeraakt.

Maar de DeepMind AI-groep van Google heeft nu een leermiddel voor versterking ontwikkeld dat sterk geoptimaliseerde algoritmen kan ontwikkelen zonder eerst te worden getraind in voorbeelden van menselijke code. De truc was om hem voor te bereiden om programmeren als een spel te behandelen.

Het is allemaal een spel

DeepMind staat onder meer bekend om het ontwikkelen van software die zichzelf leert spellen te spelen. Deze aanpak is zeer effectief gebleken en verovert zo uiteenlopende spellen als schaken, Hij gaatEn StarCraft. Hoewel de details variëren afhankelijk van het spel waarmee het te maken heeft, leert het programma door zichzelf te spelen en ontdekt het opties waarmee het de score kan maximaliseren.

Omdat het niet is getraind op games die door mensen worden gespeeld, kan het DeepMind-systeem manieren bedenken om games te spelen waar mensen niet aan hebben gedacht. Omdat het altijd tegen zichzelf speelt, zijn er natuurlijk gevallen waarin het blinde vlekken heeft ontwikkeld die mensen kunnen uitbuiten.

Deze benadering hangt nauw samen met programmeren. Geweldige taalparadigma’s schrijven efficiënte code omdat ze veel menselijke voorbeelden hebben gezien. Maar daarom is het zeer onwaarschijnlijk dat ze iets ontwikkelen dat mensen nog niet eerder hebben gedaan. Als we goed begrepen algoritmen willen verbeteren, zoals sorteerfuncties, zal het baseren van iets op bestaande menselijke code in het beste geval gelijkwaardige prestaties opleveren. Maar hoe zorg je ervoor dat een AI echt een nieuwe aanpak kiest?

De mensen bij DeepMind hebben dezelfde aanpak gevolgd als bij schaken en Hij gaat: Ze hebben code-optimalisatie omgezet in een spel. Het AlphaDev-systeem ontwikkelde x86-compilatie-algoritmen die codelatentie als een hit behandelden en probeerden die hit te minimaliseren en er tegelijkertijd voor te zorgen dat de code foutloos werd voltooid. Door middel van versterkend leren ontwikkelt AlphaDev geleidelijk het vermogen om zeer efficiënte en robuuste code te schrijven.

Binnen AlphaDev

Zeggen dat het systeem de latentie verbetert, is iets heel anders dan uitleggen hoe het werkt. Net als de meeste andere complexe AI-systemen, bestaat AlphaDev uit verschillende afzonderlijke componenten. Een daarvan is de representatiefunctie, die de algehele prestaties van de code bijhoudt terwijl deze wordt ontwikkeld. Dit omvat de algehele structuur van het algoritme, evenals het gebruik van x86-registers en geheugen.

Het systeem voegt montage-instructies individueel toe, geselecteerd door a Zoek de Monte Carlo-boom– nogmaals, een benadering die is ontleend aan spelsystemen. Door het “boom” -aspect van deze benadering kan het systeem zich snel beperken tot een beperkt gebied uit een groot aantal mogelijke instructies, terwijl Monte Carlo een zekere mate van willekeur toevoegt aan de exacte instructies die uit die tak worden gekozen. (Merk op dat “help” in deze context zaken omvat zoals de specifieke records die zijn gekozen om een ​​geldige, volledige assembly te maken.)

Het systeem evalueert vervolgens de status van de assemblagecode op latentie en validiteit en kent er een score aan toe, en vergelijkt deze met de score van de vorige score. En door bekrachtigend leren geeft het informatie over hoe de verschillende takken van de boom werken, gezien de status van het programma. Na verloop van tijd “leer” je hoe je een winnende spelconditie kunt bereiken – min of meer voltooid – met maximale score, wat neerkomt op minimale latentie.

Het belangrijkste voordeel van dit systeem is dat het trainen ervan geen codevoorbeelden hoeft te bevatten. In plaats daarvan genereert het systeem zijn eigen codevoorbeelden en evalueert deze vervolgens. Daarbij hangt het af van informatie over welke instructiesets effectief zijn bij het sorteren.

Handige code

Sorteren in complexe programma’s kan grote, willekeurige groepen items aan. Maar op het niveau van standaardbibliotheken zijn ze opgebouwd uit een groot aantal zeer specifieke functies die slechts één situatie of enkele gevallen aankunnen. Er zijn bijvoorbeeld afzonderlijke algoritmen voor het sorteren van drie items, vier items en vijf items. En er is nog een reeks functies die een willekeurig aantal items tot een maximum aankan – wat betekent dat u er een kunt noemen die maximaal vier items sorteert, maar niet meer.

DeepMind heeft AlphaDev op elk van deze functies ingesteld, maar ze werken heel anders. Voor functies die een bepaald aantal elementen afhandelen, is het mogelijk om code te schrijven zonder enige vertakkingen waar het verschillende code uitvoert op basis van de status van de variabele. Als gevolg hiervan is de prestatie van deze code over het algemeen evenredig met het aantal vereiste instructies. AlphaDev was in staat om alle Sort-3-, Sort-5- en Sort-8-instructies en zelfs meer Sort-6- en Sort-7-instructies te scheren. Er was er maar één (rang 4) waar hij geen manier kon vinden om de menselijke code te verbeteren. Herhaaldelijk uitvoeren van de code op daadwerkelijke systemen toonde aan dat minder instructies resulteerden in betere prestaties.

Het sorteren van een variabel aantal items omvat vertakkingen in de code, en verschillende processors hebben verschillende hoeveelheden hardware die zijn bedoeld voor het afhandelen van deze vertakkingen. Daarom werd de code geëvalueerd op basis van de prestaties op 100 verschillende apparaten. Ook hier heeft AlphaDev manieren gevonden om extra prestaties te leveren, en we zullen bekijken hoe dit in één situatie moet: een functie die maximaal vier items sorteert.

In de huidige implementatie in de C++-bibliotheek voert de code een reeks tests uit om te zien hoeveel elementen er moeten worden gesorteerd en roept de aangepaste sorteerfunctie voor dat aantal elementen aan. De herziene code doet nog iets vreemds. Test of er twee elementen zijn en roept indien nodig een afzonderlijke functie aan om ze te sorteren. Als het aantal groter is dan twee, roept de code aan om de eerste drie te sorteren. Als er drie items zijn, worden de resultaten van deze sortering geretourneerd.

Als er echter vier items moeten worden gesorteerd, voert het gespecialiseerde code uit die zeer efficiënt is in het invoegen van een vierde item op de juiste plaats in een reeks van drie gesorteerde items. Dit lijkt een vreemde benadering, maar het presteerde consequent beter dan mijn bestaande code.

in de maak

Omdat AlphaDev efficiëntere code produceerde, wilde het team deze opnieuw integreren in de LLVM-standaard C++-bibliotheek. Het probleem hier is dat de code in assembler was in plaats van in C++. Dus moesten ze achteruit werken en uitzoeken welke C++-code dezelfde assembly zou produceren. Nadat dit was gebeurd, werd de code samengevoegd met de LLVM-toolchain – de eerste keer in meer dan tien jaar dat een deel van de code was gewijzigd.

Als gevolg hiervan schatten onderzoekers dat AlphaDev-code nu biljoenen keren per dag wordt uitgevoerd.

Natuur, 2023. DOI: 10.1038 / s41586-023-06004-9 (over DOI’s).