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

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

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

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

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

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

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

Этот метод развивался на протяжении всей истории. Один из самых ранних примеров относится ко второму и третьему векам, когда ученые вручную расставили в алфавитном порядке тысячи книг на полках Великой Александрийской библиотеки. После промышленной революции были изобретены машины, которые могли помочь в сортировке: табулирующие машины сохраняли информацию на перфокартах, которые использовались для сбора результатов переписи 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 был выпущен в открытый доступ. Спусковая библиотекадоступный миллионам разработчиков по всему миру, и, по нашим оценкам, сейчас он используется триллионы раз в день.

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

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

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

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

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