AlphaDev — это система искусственного интеллекта , разработанная Google DeepMind для обнаружения усовершенствованных алгоритмов компьютерной науки с использованием обучения с подкреплением . AlphaDev основана на AlphaZero , системе, которая освоила шахматы , сёги и го самостоятельно . AlphaDev применяет тот же подход для поиска более быстрых алгоритмов для таких фундаментальных задач, как сортировка и хеширование . [1] [2] [3]
7 июня 2023 года Google DeepMind опубликовала в журнале Nature статью, посвященную AlphaDev, в которой были обнаружены новые алгоритмы, превзошедшие самые современные методы для алгоритмов небольшой сортировки. [1] Например, AlphaDev обнаружила более быструю последовательность языка ассемблера для сортировки последовательностей из 5 элементов. [4] После углубленного анализа алгоритмов AlphaDev обнаружила две уникальные последовательности инструкций ассемблера, называемые перемещениями обмена и копирования AlphaDev, которые избегают одной инструкции ассемблера при каждом применении. [1] [3] Для алгоритмов сортировки переменных AlphaDev обнаружила принципиально разные структуры алгоритмов. Например, для VarSort4 (сортировка до 4 элементов) AlphaDev обнаружила алгоритм на 29 инструкций ассемблера короче человеческого эталона. [1] AlphaDev также улучшила скорость алгоритмов хеширования до 30% в некоторых случаях. [2]
В январе 2022 года Google DeepMind представила свои новые алгоритмы сортировки в организацию, которая управляет C++ , одним из самых популярных языков программирования в мире, и после независимой проверки алгоритмы AlphaDev были добавлены в библиотеку. [5] Это было первое изменение алгоритмов сортировки стандартной библиотеки C++ за более чем десятилетие и первое обновление, включающее алгоритм, обнаруженный с помощью ИИ. [5] В январе 2023 года DeepMind также добавила свой алгоритм хеширования для входных данных от 9 до 16 байт в Abseil, коллекцию готовых алгоритмов C++ с открытым исходным кодом, которые может использовать любой, кто пишет код на C++. [6] [5] По оценкам Google, эти два алгоритма используются триллионы раз каждый день. [7]
AlphaDev построен на основе AlphaZero, модели обучения с подкреплением, которую DeepMind обучила, чтобы освоить такие игры, как го и шахматы. [5] Прорыв компании состоял в том, чтобы рассматривать проблему поиска более быстрого алгоритма как игру, а затем обучать свой ИИ, чтобы выиграть в ней. [2] AlphaDev играет в однопользовательскую игру, где цель состоит в итеративном построении алгоритма на языке ассемблера, который является и быстрым, и правильным. [1] AlphaDev использует нейронную сеть для руководства поиском оптимальных ходов и учится на собственном опыте и синтетических демонстрациях. [1]
AlphaDev демонстрирует потенциал ИИ для продвижения основ вычислений и оптимизации кода для различных критериев. Google DeepMind надеется, что AlphaDev вдохновит на дальнейшие исследования по использованию ИИ для открытия новых алгоритмов и улучшения существующих. [2]
Основной алгоритм обучения в AlphaDev является расширением AlphaZero .
Чтобы использовать AlphaZero в программировании ассемблера, авторы создали векторное представление программ ассемблера на основе Transformer , предназначенное для захвата их базовой структуры. [1] Это конечное представление позволяет нейронной сети играть в программирование ассемблера как в игру с конечным числом возможных ходов (например, в го),
Представление использует следующие компоненты:
Состояние игры — это ассемблерная программа, сгенерированная к заданному моменту.
Игровой ход — это дополнительная инструкция, добавляемая к текущей ассемблерной программе.
Награда игры является функцией правильности и задержки программы сборки. Чтобы снизить стоимость, AlphaDev вычисляет фактическую измеренную задержку только для менее чем 0,002% сгенерированных программ, поскольку не оценивает задержку в процессе поиска. Вместо этого он использует две функции, которые оценивают правильность и задержку, обучаясь посредством контролируемого обучения с использованием реальных измеренных значений правильности и задержки.
AlphaDev разработала алгоритмы хеширования для входных данных от 9 до 16 байт для Abseil, коллекции предварительно написанных алгоритмов C++ с открытым исходным кодом. [8]
AlphaDev обнаружил новые алгоритмы сортировки, которые привели к 70% улучшений в библиотеке сортировки LLVM libc++ для более коротких последовательностей и около 1,7% улучшений для последовательностей, превышающих 250 000 элементов. Эти улучшения применяются к типам данных uint32, uint64 и float для архитектур ЦП ARMv8, Intel Skylake и AMD Zen 2. Условная сборка AlphaDev без ветвей и новый ход обмена способствовали этим улучшениям производительности. Обнаруженные алгоритмы были реверсированы с низкоуровневой сборки на C++ и официально включены в стандартную библиотеку сортировки libc++. [6]
AlphaDev изучил оптимизированную функцию десериализации VarInt в protobuf [ 9], превосходящую человеческий бенчмарк для однозначных входов примерно в три раза по скорости. AlphaDev также обнаружил новый ход назначения VarInt, объединяющий две операции в одну инструкцию для экономии задержек.
Производительность AlphaDev сравнивалась со стохастической супероптимизацией, [10] логическим подходом ИИ. Последний был запущен с по крайней мере тем же количеством ресурсов и временем, что и AlphaDev. Результаты показали, что AlphaDev-S требует непомерно большого количества времени для прямой оптимизации по задержке, поскольку задержка должна вычисляться после каждой мутации. Таким образом, AlphaDev-S оптимизирует для прокси-сервера задержки, в частности, длины алгоритма, а затем, в конце обучения, все правильные программы, сгенерированные AlphaDev-S, просматриваются.