AlphaDev обнаруживает более быстрые алгоритмы сортировки

Новые алгоритмы изменят основы вычислений

Цифровое общество приводит к росту спроса на вычисления и энергопотребления. В течение последних пяти десятилетий мы полагались на усовершенствование аппаратного обеспечения, чтобы идти в ногу со временем. Но поскольку микрочипы приближаются к своим физическим пределам, крайне важно улучшить код, который на них работает, чтобы сделать вычисления более мощными и устойчивыми. Это особенно важно для алгоритмов, которые составляют код, выполняющийся триллионы раз в день.

В нашей статье, опубликованной сегодня в Nature, мы представляем AlphaDev, систему искусственного интеллекта (ИИ), которая использует обучение с подкреплением для обнаружения улучшенных алгоритмов компьютерных наук, превосходящих те, которые оттачивались учеными и инженерами на протяжении десятилетий.

AlphaDev обнаружила более быстрый алгоритм сортировки – метода упорядочивания данных. Миллиарды людей используют эти алгоритмы каждый день, не осознавая этого. Они лежат в основе всего – от ранжирования результатов онлайн-поиска и социальных постов до обработки данных на компьютерах и телефонах. Создание более совершенных алгоритмов с помощью ИИ изменит способы программирования компьютеров и повлияет на все аспекты нашего все более цифрового общества.

Благодаря открытости наших новых алгоритмов сортировки в основной библиотеке C++ миллионы разработчиков и компаний по всему миру теперь используют их в приложениях ИИ в различных отраслях – от облачных вычислений и интернет-магазинов до управления цепочками поставок. Это первое изменение в этой части библиотеки сортировки за более чем десять лет, и впервые в эту библиотеку был добавлен алгоритм, разработанный на основе обучения с подкреплением. Мы рассматриваем это как важный шаг в использовании ИИ для оптимизации мирового кода, по одному алгоритму за раз.

Что такое сортировка?

Сортировка – это метод упорядочивания ряда предметов в определенном порядке. В качестве примера можно привести сортировку трех букв по алфавиту, упорядочивание пяти чисел от наибольшего к наименьшему или упорядочивание базы данных с миллионами записей.

Этот метод развивался на протяжении всей истории. Один из самых ранних примеров относится ко второму и третьему веку, когда ученые вручную расставляли тысячи книг по алфавиту на полках Великой Александрийской библиотеки. После промышленной революции были изобретены машины, которые могли помочь в сортировке – табуляционные машины хранили информацию на перфокартах, которые использовались для сбора результатов переписи населения 1890 года в США.

А с появлением коммерческих компьютеров в 1950-х годах мы увидели разработку самых первых алгоритмов сортировки в компьютерной науке. Сегодня существует множество различных методов и алгоритмов сортировки, которые используются в кодовых базах по всему миру для упорядочивания огромных объемов данных в Интернете.

Для разработки современных алгоритмов компьютерным ученым и программистам потребовались десятилетия исследований. Они настолько эффективны, что их дальнейшее совершенствование является серьезной задачей, сродни попытке найти новый способ экономии электроэнергии или более эффективный математический подход. Эти алгоритмы также являются краеугольным камнем компьютерной науки, их преподают на вводных курсах информатики в университетах.

Поиск новых алгоритмов

AlphaDev обнаружила более быстрые алгоритмы, начав с нуля, а не совершенствуя существующие алгоритмы, и начала искать там, где большинство людей не ищет: в инструкциях по сборке компьютера.

Инструкции ассемблера используются для создания двоичного кода для компьютеров. В то время как разработчики пишут на языках кодирования, таких как C++, известных как языки высокого уровня, они должны перевести их в “низкоуровневые” инструкции ассемблера, чтобы компьютеры могли их понять.

Мы считаем, что на этом низком уровне существует множество улучшений, которые трудно обнаружить в языке кодирования более высокого уровня. На этом уровне компьютерное хранилище и операции более гибкие, что означает, что существует гораздо больше потенциальных улучшений, которые могут оказать большее влияние на скорость и энергопотребление.

Поиск лучших алгоритмов с помощью игры

AlphaDev основана на AlphaZero, нашей модели обучения с подкреплением, которая победила чемпионов мира в таких играх, как го, шахматы и сёги. С помощью AlphaDev мы показываем, как эта модель может переходить от игр к научным задачам и от симуляций к реальным приложениям.

Чтобы научить AlphaDev находить новые алгоритмы, мы превратили сортировку в “сборочную игру” для одного игрока. На каждом ходу AlphaDev наблюдает за алгоритмом, который он создал, и за информацией, содержащейся в центральном процессоре (ЦП). Затем он делает ход, выбирая инструкцию для добавления в алгоритм.

Игра на ассемблере невероятно трудна, потому что AlphaDev должен эффективно перебирать огромное количество возможных комбинаций инструкций, чтобы найти алгоритм, который может сортировать, и быстрее, чем текущий лучший. Количество возможных комбинаций инструкций аналогично количеству частиц во Вселенной или количеству возможных комбинаций ходов в шахматной игре (10¹²⁰ игры) и Го (10⁷⁰⁰ игры). И один неверный ход может свести на нет весь алгоритм.

По мере построения алгоритма, по одной инструкции за раз, AlphaDev проверяет его правильность, сравнивая выходные данные алгоритма с ожидаемыми результатами. Для алгоритмов сортировки это означает, что на вход поступают неупорядоченные числа, а на выходе получаются правильно отсортированные. Мы награждаем AlphaDev как за правильную сортировку чисел, так и за то, как быстро и эффективно он это делает. AlphaDev побеждает в игре, обнаружив правильную и более быструю программу.

Открытие более быстрых алгоритмов сортировки

AlphaDev обнаружил новые алгоритмы сортировки, которые привели к улучшению библиотеки сортировки LLVM libc++, которая стала на 70% быстрее для более коротких последовательностей и примерно на 1.7% быстрее для последовательностей, превышающих 250,000 элементов.

Мы сосредоточились на улучшении алгоритмов сортировки для более коротких последовательностей из трех-пяти элементов. Эти алгоритмы являются одними из наиболее широко используемых, поскольку они часто вызываются много раз как часть более крупных функций сортировки. Улучшение этих алгоритмов может привести к общему ускорению сортировки любого количества элементов.

Чтобы сделать новый алгоритм сортировки более удобным для людей, мы провели реверс-инжиниринг алгоритмов и перевели их на C++, один из самых популярных языков кодирования, используемых разработчиками. Теперь эти алгоритмы доступны в стандартной библиотеке сортировки LLVM libc++, которую используют миллионы разработчиков и компаний по всему миру.

Поиск новых подходов

AlphaDev не только нашла более быстрые алгоритмы, но и обнаружила новые подходы. Его алгоритмы сортировки содержат новые последовательности инструкций, которые экономят одну инструкцию при каждом применении. Это может иметь огромное значение, поскольку эти алгоритмы используются триллионы раз в день.

Мы называем это “перемещениями подкачки и копирования AlphaDev”. Этот новый подход напоминает “ход 37” AlphaGo – контринтуитивную игру, которая ошеломила зрителей и привела к поражению легендарного игрока в го. С помощью хода обмена и копирования AlphaDev пропускает шаг, чтобы соединить элементы таким образом, который выглядит как ошибка, но на самом деле является коротким путем. Это демонстрирует способность AlphaDev находить оригинальные решения и бросает вызов тому, как мы думаем о том, как улучшить алгоритмы информатики.

От сортировки к хешированию в структурах данных

После открытия более быстрых алгоритмов сортировки мы проверили, может ли AlphaDev обобщить и улучшить другой алгоритм информатики: хэширование.

Хеширование – это фундаментальный алгоритм в вычислительной технике, используемый для получения, хранения и сжатия данных. Подобно библиотекарю, который использует систему классификации, чтобы найти определенную книгу, алгоритмы хэширования помогают пользователям знать, что они ищут и где именно это найти. Эти алгоритмы берут данные для определенного ключа (например, имя пользователя “Jane Doe”) и хэшируют их – процесс, при котором исходные данные превращаются в уникальную строку символов (например, 1234ghfty). Этот хэш используется компьютером для быстрого извлечения данных, относящихся к ключу, вместо того чтобы искать их во всех данных.

Мы применили AlphaDev к одному из наиболее часто используемых алгоритмов хэширования в структурах данных, чтобы попытаться найти более быстрый алгоритм. И когда мы применили его к диапазону 9-16 байт функции хэширования, алгоритм, который обнаружил AlphaDev, оказался на 30% быстрее.

В этом году новый алгоритм хэширования AlphaDev был выпущен в библиотеку Abseil с открытым исходным кодом, доступную миллионам разработчиков по всему миру, и, по нашим оценкам, сейчас он используется триллионы раз в день.

Оптимизация мирового кода, по одному алгоритму за раз

Оптимизировав и запустив улучшенные алгоритмы сортировки и хеширования, используемые разработчиками по всему миру, AlphaDev продемонстрировала свою способность обобщать и открывать новые алгоритмы с реальным эффектом. Мы рассматриваем AlphaDev как шаг к разработке инструментов ИИ общего назначения, которые могут помочь оптимизировать всю вычислительную экосистему и решить другие проблемы, которые принесут пользу обществу.

Хотя оптимизация в пространстве низкоуровневых инструкций ассемблера является очень мощной, существуют ограничения по мере роста алгоритма, и в настоящее время мы изучаем возможность AlphaDev оптимизировать алгоритмы непосредственно на языках высокого уровня, таких как C++, что было бы более полезно для разработчиков.

Открытия AlphaDev, такие как перемещения swap и copy, не только показывают, что он может улучшать алгоритмы, но и находить новые решения. Мы надеемся, что эти открытия вдохновят исследователей и разработчиков на создание методов и подходов, которые позволят еще больше оптимизировать фундаментальные алгоритмы для создания более мощной и устойчивой вычислительной экосистемы.

Узнайте больше об оптимизации вычислительной экосистемы: