AI система създава първите подобрения в сортирането на кодове от повече от десетилетие – Ars Technica

Без съмнение всеки, който е изучавал основни компютърни науки, е прекарал време в разработването на алгоритъм за сортиране – код, който взема неподреден списък от елементи и ги поставя във възходящ или низходящ ред. Това е интересно предизвикателство, защото има толкова много начини да направите това и защото хората са прекарали много време в измисляне как да направят това сортиране възможно най-ефективно.

Сортирането е толкова основно, че алгоритмите са вградени в повечето стандартни библиотеки на езици за програмиране. А в случая на библиотеката C++, използвана с компилатора LLVM, кодът не е пипан повече от десетилетие.

Но групата DeepMind AI на Google вече е разработила инструмент за обучение за подсилване, който може да разработи силно оптимизирани алгоритми, без първо да бъде обучен на примери на човешки код. Номерът беше да го подготви да се отнася към програмирането като към игра.

Всичко е игра

DeepMind, наред с други неща, е известен с разработването на софтуер, който се учи как да играе игри. Този подход се оказа много ефективен, завладявайки различни игри като шах, Той отиваИ StarCraft. Въпреки че подробностите варират в зависимост от играта, с която работи, програмата се учи, като играе сама и открива опции, които й позволяват да увеличи максимално резултата.

Тъй като не е обучена за игри, играни от хора, системата DeepMind може да намери начини да играе игри, за които хората не са се сетили. Разбира се, тъй като винаги играе срещу себе си, има случаи, в които е развил слепи зони, които хората могат да използват.

Този подход е много подходящ за програмирането. Страхотните езикови парадигми пишат ефективен код, защото са виждали много човешки примери. Но поради това е много малко вероятно те да развият нещо, което хората не са правили преди. Ако търсим да подобрим добре разбрани алгоритми, като например функции за сортиране, базирайки се на съществуващ човешки код, в най-добрия случай ще ви осигури еквивалентна производителност. Но как да накараш AI наистина да избере нов подход?

Хората от DeepMind са възприели същия подход, както при шаха и Той отива: Те превърнаха оптимизацията на кода в игра. Системата AlphaDev разработи x86 алгоритми за компилиране, които третираха забавянето на кода като попадение и се опитаха да минимизират това попадение, като същевременно гарантират, че кодът работи до завършване без грешки. Чрез подсилващо обучение, AlphaDev постепенно развива способността да пише високоефективен и стабилен код.

Вътре в AlphaDev

Да се ​​каже, че системата подобрява латентността е съвсем друг въпрос, отколкото да се обясни как работи. Подобно на повечето други сложни AI системи, AlphaDev се състои от няколко различни компонента. Едната е функцията за представяне, която проследява цялостната производителност на кода, докато се разработва. Това включва цялостната структура на алгоритъма, както и използването на x86 регистри и памет.

Системата добавя индивидуални инструкции за сглобяване, избрани от a Намерете дървото Монте Карло– отново подход, заимстван от системите за игри. „Дървовидният“ аспект на този подход позволява на системата бързо да стесни до ограничена област от голям набор от възможни инструкции, докато Монте Карло добавя степен на произволност към точните инструкции, които са избрани от този клон. (Имайте предвид, че „помощ“ в този контекст включва неща като конкретните записи, избрани за създаване на валиден, пълен комплект.)

След това системата оценява състоянието на асемблиращия код за латентност и валидност и му присвоява резултат и го сравнява с резултата от предишния резултат. И чрез обучение с подсилване, той свързва информация за това как работят различните клонове на дървото, като се има предвид състоянието на програмата. С течение на времето вие „научавате“ как да постигнете условие за печеливша игра – сортиране завършено – с максимален резултат, което означава минимално забавяне.

Основното предимство на тази система е, че обучението й не трябва да включва примери за код. Вместо това системата генерира собствени примери за код и след това ги оценява. В този процес той се закача на информация за това кои набори от инструкции са ефективни при сортиране.

Полезен код

Сортирането в сложни програми може да обработва големи, произволни групи от елементи. Но на нивото на стандартните библиотеки те са изградени от голям набор от много специфични функции, които обработват само една ситуация или няколко случая. Например, има отделни алгоритми за сортиране на три елемента, четири елемента и пет елемента. И има друг набор от функции, които могат да обработват произволен брой елементи до максимум – което означава, че можете да извикате такава, която сортира до четири елемента, но не повече.

DeepMind е настроил AlphaDev на всяка от тези функции, но те работят много различно. За функции, които обработват определен брой елементи, е възможно да се напише код без разклонения, където той изпълнява различен код въз основа на състоянието на променливата. В резултат на това производителността на този код обикновено е пропорционална на броя на необходимите инструкции. AlphaDev успя да обръсне всички инструкции на Sort-3, Sort-5 и Sort-8 и дори повече от Sort-6 и Sort-7. Имаше само един (ранг 4), където не можеше да намери начин да подобри човешкия код. Многократното изпълнение на кода на реални системи показа, че по-малко инструкции водят до по-добра производителност.

Сортирането на променлив брой записи включва разклоняване на кода и различните процесори имат различно количество хардуер, предназначен за обработка на тези разклонения. Следователно кодът беше оценен въз основа на неговата производителност на 100 различни устройства. Тук отново AlphaDev намери начини да постигне допълнителна производителност и ние ще разгледаме как да го направим в една ситуация: функция, която сортира до четири елемента.

В текущата реализация в библиотеката C++ кодът изпълнява поредица от тестове, за да види колко елемента трябва да сортира и извиква функцията за персонализирано сортиране за този брой елементи. Ревизираният код прави нещо още по-странно. Тества дали има два елемента и извиква отделна функция, за да ги сортира, ако е необходимо. Ако броят е по-голям от две, кодът извиква сортиране на първите три. Ако има три елемента, резултатите от този сорт ще бъдат върнати.

Въпреки това, ако има четири елемента за сортиране, той изпълнява специализиран код, който е много ефективен при вмъкване на четвърти елемент на подходящото място в рамките на масив от три сортирани елемента. Това изглежда като странен подход, но постоянно превъзхожда съществуващия ми код.

в производството

Тъй като AlphaDev създаде по-ефективен код, екипът искаше да го интегрира отново в стандартната C++ библиотека на LLVM. Проблемът тук е, че кодът беше в асемблиране, а не в C++. И така, те трябваше да работят в обратна посока и да разберат кой C++ код ще произведе същото сглобяване. След като това беше направено, кодът беше обединен в инструменталната верига LLVM – първият път, когато част от кода беше модифициран от повече от десетилетие.

В резултат на това изследователите са изчислили, че кодът на AlphaDev сега се изпълнява трилиони пъти на ден.

Природа, 2023. DOI: 10.1038 / s41586-023-06004-9 (относно DOI).