System AI tworzy pierwsze od ponad dekady udoskonalenia sortowania kodu – Ars Technica

Bez wątpienia każdy, kto studiował podstawy informatyki, spędził czas na opracowywaniu algorytmu sortowania — kodu, który pobiera nieuporządkowaną listę elementów i ustawia je w porządku rosnącym lub malejącym. To interesujące wyzwanie, ponieważ istnieje tak wiele sposobów, aby to zrobić, a ludzie spędzili dużo czasu, zastanawiając się, jak zrobić to sortowanie tak wydajnie, jak to tylko możliwe.

Sortowanie jest tak proste, że algorytmy są wbudowane w większość standardowych bibliotek języków programowania. A w przypadku biblioteki C++ używanej z kompilatorem LLVM kod nie był zmieniany od ponad dekady.

Ale grupa Google DeepMind AI opracowała teraz narzędzie do uczenia się przez wzmacnianie, które może opracowywać wysoce zoptymalizowane algorytmy bez uprzedniego szkolenia na przykładach kodu ludzkiego. Sztuczka polegała na tym, aby przygotować go do traktowania programowania jako gry.

To wszystko jest grą

DeepMind znany jest między innymi z tworzenia oprogramowania, które uczy się grać w gry. To podejście okazało się bardzo skuteczne, podbijając gry tak różnorodne, jak szachy, On idzieI StarCraft. Chociaż szczegóły różnią się w zależności od gry, z którą ma do czynienia, program uczy się, grając sam i odkrywa opcje, które pozwalają mu zmaksymalizować wynik.

Ponieważ nie był szkolony w grach, w które grają ludzie, system DeepMind może wymyślić sposoby grania w gry, o których ludzie nie pomyśleli. Oczywiście, ponieważ zawsze gra przeciwko sobie, istnieją przypadki, w których rozwinął martwe punkty, które ludzie mogą wykorzystać.

To podejście jest bardzo istotne w programowaniu. Wielkie paradygmaty językowe piszą wydajny kod, ponieważ widziały wiele ludzkich przykładów. Ale z tego powodu jest bardzo mało prawdopodobne, aby rozwinęli coś, czego ludzie wcześniej nie robili. Jeśli chcemy ulepszyć dobrze rozumiane algorytmy, takie jak funkcje sortowania, oparcie czegoś na istniejącym kodzie ludzkim w najlepszym razie zapewni równoważną wydajność. Ale jak sprawić, by sztuczna inteligencja naprawdę wybrała nowe podejście?

Ludzie z DeepMind przyjęli to samo podejście, co w przypadku szachów i On idzie: Zmienili optymalizację kodu w grę. System AlphaDev opracował algorytmy kompilacji x86, które traktowały opóźnienie kodu jako trafienie i próbowały zminimalizować to trafienie, zapewniając jednocześnie, że kod działa do końca bez błędów. Dzięki uczeniu się przez wzmacnianie AlphaDev stopniowo rozwija umiejętność pisania wysoce wydajnego i solidnego kodu.

Wewnątrz AlphaDev

Powiedzieć, że system poprawia opóźnienia, to zupełnie inna sprawa niż wyjaśnienie, jak to działa. Podobnie jak większość innych złożonych systemów AI, AlphaDev składa się z kilku odrębnych komponentów. Jednym z nich jest funkcja reprezentacji, która śledzi ogólną wydajność kodu podczas jego opracowywania. Obejmuje to ogólną strukturę algorytmu, a także użycie rejestrów i pamięci x86.

System dodaje indywidualnie instrukcje montażu, wybrane przez a Znajdź drzewo Monte Carlo– znowu podejście zapożyczone z systemów do gier. Aspekt „drzewa” tego podejścia pozwala systemowi szybko zawęzić się do ograniczonego obszaru z dużego zakresu możliwych instrukcji, podczas gdy metoda Monte Carlo dodaje stopień przypadkowości do dokładnych instrukcji wybranych z tej gałęzi. (Zauważ, że „pomoc” w tym kontekście obejmuje takie rzeczy, jak określone rekordy wybrane do utworzenia poprawnego, kompletnego zestawu).

Następnie system ocenia stan kodu asemblera pod kątem opóźnienia i ważności oraz przypisuje mu ocenę i porównuje ją z oceną poprzedniej oceny. A poprzez uczenie się przez wzmacnianie przekazuje informacje o tym, jak działają różne gałęzie drzewa, biorąc pod uwagę stan programu. Z biegiem czasu „uczysz się”, jak osiągnąć zwycięski warunek gry – sortowanie zakończone – z maksymalnym wynikiem, co oznacza minimalne opóźnienie.

Główną zaletą tego systemu jest to, że jego szkolenie nie musi zawierać żadnych przykładów kodu. Zamiast tego system generuje własne przykłady kodu, a następnie je ocenia. W procesie zawiesza się informacja o tym, które zestawy instrukcji są skuteczne w sortowaniu.

Przydatny kod

Sortowanie w złożonych programach może obsługiwać duże, dowolne grupy elementów. Ale na poziomie standardowych bibliotek są one zbudowane z dużego zestawu bardzo specyficznych funkcji, które obsługują tylko jedną sytuację lub kilka przypadków. Na przykład istnieją osobne algorytmy do sortowania trzech elementów, czterech elementów i pięciu elementów. Jest jeszcze inny zestaw funkcji, który może obsłużyć dowolną liczbę elementów aż do maksimum – co oznacza, że ​​możesz wywołać taki, który sortuje do czterech elementów, ale nie więcej.

DeepMind ustawił AlphaDev na każdą z tych funkcji, ale działają one zupełnie inaczej. W przypadku funkcji obsługujących określoną liczbę elementów możliwe jest napisanie kodu bez żadnych rozgałęzień, w których wykonuje on inny kod w zależności od stanu zmiennej. W rezultacie wydajność tego kodu jest generalnie proporcjonalna do liczby wymaganych instrukcji. AlphaDev był w stanie ogolić wszystkie instrukcje Sort-3, Sort-5 i Sort-8, a nawet więcej instrukcji Sort-6 i Sort-7. Był tylko jeden (ranga 4), w którym nie mógł znaleźć sposobu na ulepszenie ludzkiego kodu. Wielokrotne uruchamianie kodu na rzeczywistych systemach pokazało, że mniej instrukcji skutkowało lepszą wydajnością.

Sortowanie zmiennej liczby wpisów wymaga rozgałęzień w kodzie, a różne procesory mają różne ilości sprzętu przeznaczonego do obsługi tych rozgałęzień. Dlatego kod został oceniony na podstawie jego działania na 100 różnych urządzeniach. Tutaj ponownie AlphaDev znalazł sposób na wyciśnięcie dodatkowej wydajności, a my przyjrzymy się, jak to zrobić w jednej sytuacji: funkcja, która sortuje do czterech elementów.

W bieżącej implementacji w bibliotece C++ kod uruchamia serię testów, aby zobaczyć, ile elementów potrzebuje do posortowania, i wywołuje niestandardową funkcję sortowania dla tej liczby elementów. Zmieniony kod robi coś jeszcze dziwniejszego. Testuje, czy istnieją dwa elementy i w razie potrzeby wywołuje oddzielną funkcję, aby je posortować. Jeśli liczba jest większa niż dwa, kod wywołuje sortowanie pierwszych trzech. Jeśli są trzy elementy, zostaną zwrócone wyniki tego sortowania.

Jeśli jednak są cztery elementy do posortowania, uruchamia wyspecjalizowany kod, który bardzo skutecznie wstawia czwarty element w odpowiednie miejsce w tablicy trzech posortowanych elementów. Wydaje się to dziwnym podejściem, ale konsekwentnie przewyższa mój istniejący kod.

w produkcji

Ponieważ AlphaDev stworzył bardziej wydajny kod, zespół chciał ponownie zintegrować go ze standardową biblioteką C++ LLVM. Problem polega na tym, że kod był w asemblerze, a nie w C++. Musieli więc pracować wstecz i dowiedzieć się, który kod C++ wytworzy ten sam zespół. Po wykonaniu tej czynności kod został włączony do łańcucha narzędzi LLVM — po raz pierwszy część kodu została zmodyfikowana od ponad dekady.

W rezultacie naukowcy oszacowali, że kod AlphaDev jest obecnie wykonywany biliony razy dziennie.

Przyroda, 2023. DOI: 10.1038 / s41586-023-06004-9 (o DOI).