Systém AI vytváří první vylepšení třídění kódu za více než deset let – Ars Technica

Není pochyb o tom, že každý, kdo studoval základní informatiku, strávil čas vymýšlením třídícího algoritmu – kódu, který vezme neuspořádaný seznam položek a seřadí je vzestupně nebo sestupně. Je to zajímavá výzva, protože existuje tolik způsobů, jak to udělat, a protože lidé strávili spoustu času zjišťováním, jak toto třídění provést co nejefektivněji.

Třídění je tak základní, že algoritmy jsou zabudovány do většiny standardních knihoven programovacích jazyků. A v případě knihovny C++ používané s kompilátorem LLVM nebyl kód za více než deset let zpracován.

Ale skupina DeepMind AI společnosti Google nyní vyvinula nástroj pro výuku posílení, který dokáže vyvinout vysoce optimalizované algoritmy, aniž by byl nejprve vyškolen na příkladech lidského kódu. Trik byl připravit ho na to, aby s programováním zacházel jako s hrou.

Všechno je to hra

DeepMind je mimo jiné známá vývojem softwaru, který se sám učí hrát hry. Tento přístup se ukázal jako vysoce účinný, dobývá hry tak rozmanité, jako jsou šachy, On jdeA StarCraft. Zatímco detaily se liší v závislosti na hře, kterou se zabývá, program se učí hraním sám a objevuje možnosti, které mu umožňují maximalizovat skóre.

Protože nebyl trénován na hrách, které hrají lidé, dokáže systém DeepMind přijít na způsoby, jak hrát hry, o kterých lidé ani neuvažovali. Samozřejmě, protože vždy hraje sám proti sobě, existují případy, kdy si vytvořil slepá místa, která mohou lidé využít.

Tento přístup úzce souvisí s programováním. Skvělá jazyková paradigmata píší efektivní kód, protože viděli spoustu lidských příkladů. Ale kvůli tomu je velmi nepravděpodobné, že by vyvinuli něco, co lidé dosud nedokázali. Pokud se snažíme vylepšit dobře srozumitelné algoritmy, jako jsou funkce řazení, založit něco na existujícím lidském kódu vám v nejlepším případě poskytne ekvivalentní výkon. Jak ale přimět AI, aby skutečně zvolila nový přístup?

Lidé z DeepMind zvolili stejný přístup jako k šachům a On jde: Z optimalizace kódu udělali hru. Systém AlphaDev vyvinul x86 kompilační algoritmy, které zacházely s latencí kódu jako s hitem a snažily se tento zásah minimalizovat a zároveň zajistit, aby kód běžel do dokončení bez chyb. Prostřednictvím posilovacího učení AlphaDev postupně rozvíjí schopnost psát vysoce efektivní a robustní kód.

Uvnitř AlphaDev

Tvrzení, že systém zlepšuje latenci, je docela jiná věc než vysvětlovat, jak to funguje. Stejně jako většina ostatních komplexních systémů AI se AlphaDev skládá z několika odlišných komponent. Jednou je funkce reprezentace, která sleduje celkový výkon kódu při jeho vývoji. To zahrnuje celkovou strukturu algoritmu, stejně jako použití x86 registrů a paměti.

Systém přidává návod k sestavení jednotlivě, vybraný a Najděte strom Monte Carlo– opět přístup vypůjčený z herních systémů. Aspekt „stromu“ tohoto přístupu umožňuje systému rychle se zúžit na omezenou oblast z velkého rozsahu možných instrukcí, zatímco Monte Carlo přidává určitý stupeň náhodnosti k přesným instrukcím, které jsou vybrány z dané větve. (Všimněte si, že „nápověda“ v tomto kontextu zahrnuje věci, jako jsou konkrétní záznamy vybrané k vytvoření platného úplného sestavení.)

Systém poté vyhodnotí stav sestavení kódu z hlediska latence a platnosti a přiřadí mu skóre a porovná jej se skóre předchozího skóre. A prostřednictvím posilovacího učení poskytuje informace o tom, jak různé větve stromu fungují, vzhledem ke stavu programu. Postupem času se „naučíte“, jak dosáhnout vítězné herní podmínky – seřazení dokončeno – s maximálním skóre, což znamená minimální latenci.

Hlavní výhodou tohoto systému je, že jeho školení nemusí obsahovat žádné příklady kódu. Místo toho systém vygeneruje vlastní příklady kódu a poté je vyhodnotí. Přitom se zavěsí na informace o tom, které instrukční sady jsou efektivní při řazení.

Užitečný kód

Třídění ve složitých programech zvládne velké, libovolné skupiny položek. Ale na úrovni standardních knihoven jsou sestaveny z velké sady velmi specifických funkcí, které řeší pouze jednu situaci nebo několik případů. Například existují samostatné algoritmy pro řazení tří položek, čtyř položek a pěti položek. A je tu další sada funkcí, která dokáže zpracovat libovolný počet položek až do maxima – to znamená, že můžete zavolat takovou, která seřadí až čtyři položky, ale ne více.

DeepMind nastavil AlphaDev na každou z těchto funkcí, ale fungují velmi odlišně. Pro funkce, které zpracovávají zadaný počet prvků, je možné psát kód bez větví, kde spouští odlišný kód na základě stavu proměnné. Výsledkem je, že výkon tohoto kódu je obecně úměrný počtu požadovaných instrukcí. AlphaDev dokázal oholit všechny instrukce Sort-3, Sort-5 a Sort-8, a to ještě více než Sort-6 a Sort-7. Byl pouze jeden (hodnost 4), kde nemohl najít způsob, jak vylepšit lidský kód. Opakované spouštění kódu na skutečných systémech ukázalo, že méně instrukcí vedlo k lepšímu výkonu.

Třídění proměnlivého počtu záznamů zahrnuje větvení v kódu a různé procesory mají různé množství hardwaru vyhrazeného pro zpracování těchto větví. Proto byl kód vyhodnocen na základě jeho výkonu na 100 různých zařízeních. AlphaDev zde opět našel způsoby, jak vyždímat extra výkon, a my se podíváme na to, jak to udělat v jedné situaci: funkci, která třídí až čtyři položky.

V aktuální implementaci v knihovně C++ kód spouští řadu testů, aby zjistil, kolik prvků potřebuje seřadit, a pro tento počet prvků volá vlastní třídicí funkci. Revidovaný kód dělá něco ještě podivnějšího. Testuje, zda existují dva prvky, a v případě potřeby zavolá samostatnou funkci, která je seřadí. Pokud je počet větší než dva, kód zavolá seřadit první tři. Pokud existují tři prvky, vrátí se výsledky tohoto druhu.

Pokud však existují čtyři položky k řazení, spustí se specializovaný kód, který je velmi účinný při vkládání čtvrté položky na příslušné místo v poli tří seřazených položek. Zdá se to jako zvláštní přístup, ale neustále překonává můj stávající kód.

ve výrobě

Protože AlphaDev produkoval efektivnější kód, chtěl jej tým znovu začlenit do standardní knihovny C++ LLVM. Problém je v tom, že kód byl v assembleru spíše než C++. Museli tedy pracovat pozpátku a zjistit, který kód C++ vytvoří stejné sestavení. Jakmile to bylo hotovo, kód byl začleněn do LLVM toolchain – což bylo poprvé, kdy byly některé kódy upraveny za více než deset let.

V důsledku toho vědci odhadli, že kód AlphaDev je nyní spouštěn bilionykrát denně.

Příroda, 2023. DOI: 10.1038 / s41586-023-06004-9 (o DOI).