AlphaDev: Jak bude vypadat budoucnost výpočetní techniky?

V digitální společnosti, kde je poptávka po výpočetních operacích a energii neustále rostoucí, jsme se v posledních pěti desetiletích spoléhali na pokroky převážně v hardwarové oblasti. Jelikož však hardwarové vylepšení již nestačí s našimi požadavky pro výkon držet krok, stává se stále nezbytnějším zaměřit se na samotný software neboli kód. Analogicky jinými slovy jsme ve fázi, kdy spíše než osazováním stále většího lánu pole, budeme nuceni se zamyslet nad způsobem, jak vypěstovat na lánu pole ještě více plodin než dosud, bez nutnosti rozšíření jeho velikosti.

V našem případě se musíme zaměřit na to, jak napsat kód, tak, aby byl ještě efektivnější a flexibilnější – to platí zejména pro algoritmy, jejichž denní využití dosahuje biliónových hodnot. Právě na tento problém se podívali vědci z dceřiné společnosti Googlu.

AlphaDev: AI, která překonává lidské inženýry

V článku publikovaném v Nature představujeme AlphaDev, umělou inteligenci (AI), která využívá posilovací učení k objevení vylepšených algoritmů používaných v informačních technologiích – tyto algoritmy mají potenciál překonat své dřívější protějšky vytvořené a pilované vědci a inženýry po celém světě. AlphaDev objevila rychlejší algoritmus pro řazení – metodu pro uspořádání dat. Tyto algoritmy jsou používány miliardami lidí každý den, aniž by si to uživatelé smai uvědomovali. Generování lepších algoritmů pomocí AI zcela promění způsob, jakým programujeme počítače, a ovlivní všechny aspekty naší rozrůstající se digitální společnosti.

Open source: Nové algoritmy pro všechny

Zpřístupněním našich nových algoritmů pro řazení v hlavní knihovně C++ pomůže miliónům vývojářů a společnostem po celém světě. Tyto změny budou znatelné zejména pro společnosti a uživatele využívající AI aplikace po celém světě, ať už se jedná o systémy pro cloud computing, online nákupování nebo řízení dodavatelských řetězců. Jedná se o první velkou změnu za posledních 10 let, kdy dojde k modifikaci a vylepšení této části knihovny pro řazení. Poprvé zde tak bude přidán algoritmus využívající učení posilováním (reinforcement learning), které mimo jiné využívají i systémy AI. Pomocí umělé inteligence tak budeme schopni zefektivnit stávají algoritmy, a tím významně navýšit rychlost jednotlivých procesů, které jsou těmito algoritmy poháněny, ale i snížit náklady na elektřinu a výpočetní dobu.

Co jsou to řadicí metody?

Řazení je metoda organizace několika položek v určitém pořadí. Příklady zahrnují abecední seřazení tří písmen, uspořádání pěti čísel od největšího po nejmenší, nebo seřazení milionů záznamů v databázi. Tato metoda se vyvíjela v průběhu historie. Jedním z nejstarších příkladů je druhé a třetí století, kdy učenci ručně abecedně seřadili tisíce knih na policích Velké knihovny v Alexandrii. Po průmyslové revoluci přišel vynález strojů, které řadící metody násobně zefektivnily – tabulační stroje ukládaly informace na děrované kartičky, které byli použity ke sčítání výsledků během období sčítání lidu v roce 1890 ve Spojených státech.

Hledání zbrusu nových algoritmů

AlphaDev objevila rychlejší algoritmy tím, že začala od nuly, místo vylepšování stávajících algoritmů se rozhodla hledat tam, kde většina lidí nehledá: v assemblerovém neboli nízkoúrovňovém kódu. Nízkoúrovňový kód se používá k vytvoření binárního kódu (kód sestávající z kombinací 0 a 1), který počítače převedou na akci. Zatímco vývojáři píšou v programovacích jazycích jako je C++, známých jako vyšší programovací jazyky, musí být tyto instrukce přeložené do ‚nízkoúrovňových‘ instrukcí, kterým počítače rozumí.

Například v jazyce python, syntaxe print(„Hello world“) počítači nic neříká – již dříve však bylo naprogramováno, že zaregistruje-li počítač tento druh syntaxe přeloží si to z vyššího programovacího jazyka do nižšího programovacího jazyka, které mu již rozumí. Zatímco Vy vidíte syntaxi: print(„Hello world“), počítač místo toho vidí kombinaci 0 a 1.

Překračování hranic her a vědy

AlphaDev, založený na modelu AlphaZero, který se proslavil porážkou světových šampionů ve hrách Go, šachy a šógi, nyní překračuje hranice her a vstupuje do světa vědeckých výzev a reálných aplikací. Tento přechod demonstruje, jak může být AI model, původně navržený pro hry, převeden na řešení komplexních problémů v informativním světě.

Pro trénink AlphaDevu v odhalování nových algoritmů jsme převedli proces třídění na jednohráčovou montážní hru. V každém kole hry AlphaDev sleduje algoritmus, který sestavil, a informace obsažené v centrální procesorové jednotce (CPU). Následně provede tah, kterým vybere instrukci, jež je přidána do algoritmu. AlphaDev si tak postupně v průběhu hry vytváří algoritmus a zjišťuje jeho efektivitu.

Tato hra v assembleru je výzvou i pro nejsofistikovanější AI. AlphaDev musí efektivně prozkoumat astronomické množství možných kombinací instrukcí, aby našel algoritmus, který je rychlejší a schopnější než algoritmy předešlé. Počet možných kombinací instrukcí je poté srovnatelný s počtem částic ve vesmíru nebo počtem možných kombinací tahů v partiích šachu a Go. A co je ještě horší, jediný chybný tah může znehodnotit celý algoritmus. 

Možná si někteří z Vás vzpomenete na dřívější hry, kde nebyl na každém rohu spawnovací point, ale při úmrtí Vaší postavy, jste museli hrát celou hru od znova. Tato skutečnost je velmi podobná tomu, jak dnes AI modely hledají algoritmy.

Přetváření světa algoritmů

Tyto nové algoritmy vedly k výraznému zlepšení třídicí knihovny LLVM libc++, která je nyní až o 70 % rychlejší pro kratší sekvence a přibližně o 1,7 % rychlejší pro sekvence přesahující 250 000 prvků.

Naším hlavním cílem bylo vylepšit třídicí algoritmy pro kratší sekvence o třech až pěti prvcích. Tyto algoritmy jsou mezi nejpoužívanějšími z důvodu jejich častého opakovaného volání jakožto součástí větších třídicích funkcí. Jakékoli zlepšení těchto algoritmů může mít významný dopad na celkovou rychlost třídění jakéhokoli počtu prvků.

Abychom zajistili, že naše nové třídicí algoritmy budou co nejvíce přístupné, provedli jsme reverzní inženýrství algoritmů a přeložili je do jazyka C++, jednoho z nejpopulárnějších programovacích jazyků na světě. Tyto algoritmy jsou nyní k dispozici ve standardní třídicí knihovně LLVM libc++, kterou využívají miliony vývojářů a firem po celém světě. Tímto krokem jsme otevřeli dveře k větší efektivitě a rychlosti pro širokou škálu aplikací.

Nové přístupy k algoritmům

Algoritmy třídění zahrnují nové sekvence instrukcí, které při každém použití ušetří jednu instrukci. Vzhledem k tomu, že tyto algoritmy se používají bilionkrát denně, může tento pokrok mít obrovský dopad na celkovou efektivitu výpočetních operací.

Nové sekvence instrukcí jsme pojmenovali „swapovací a kopírovací pohyby AlphaDev“. Tento nový přístup připomíná „tah 37“ od AlphaGo – neintuitivní tah, který překvapil nejenom že překvapil diváky, ale nakonec i vedl k porážce legendárního hráče Go, Leeho Sedola. 

Při tomto speciálním tahu AlphaDev udělá krok, který na první pohled vypadá jako chyba, ale ve skutečnosti se jedná o zkratku. Tento přístup ukazuje schopnost AlphaDev odhalovat originální řešení a zpochybňovat tradiční způsoby, jakými přemýšlíme o vylepšování algoritmů v informatice.

Od řazení k hašování v datových strukturách

Po objevení rychlejších algoritmů pro řazení jsme testovali, zda by AlphaDev mohla zobecnit a vylepšit i jiný algoritmus informatiky než je třídění, konkrétně tedy hašování. Hašování je základní algoritmus v počítačové vědě používaný k vyhledávání, ukládání a komprimaci dat. Když jsme AlphaDev aplikovali na nejběžněji používaný algoritmus pro hašování v datových strukturách, nalezli jsme algoritmus, který byl až o 30 % rychlejší.

Optimalizace světového kódu, jeden algoritmus najednou

Optimalizací a spuštěním vylepšených algoritmů pro řazení a hašování používaných vývojáři po celém světě, AlphaDev prokázal svou schopnost zobecnit a objevit nové algoritmy s reálným dopadem na celosvětové systémy. AlphaDev vidíme jako krok k vývoji univerzálních nástrojů AI, které by mohli pomoci optimalizovat výpočetní systémy a řešit problémy ve společnosti, vědě, technice, nebo i vesmírném inženýrství.