Влияние
Новые алгоритмы изменят основы вычислений
Цифровое общество стимулирует растущий спрос на вычисления и использование энергии. В течение последних пяти десятилетий мы полагались на усовершенствования аппаратного обеспечения, чтобы идти в ногу со временем. Но по мере того, как микрочипы приближаются к своим физическим пределам, крайне важно улучшить код, который на них работает, чтобы сделать вычисления более мощными и устойчивыми. Это особенно важно для алгоритмов, составляющих код, выполняющийся триллионы раз в день.
В нашем документ, опубликованный сегодня в Природамы представляем AlphaDev, систему искусственного интеллекта (ИИ), которая использует обучение с подкреплением для открытия усовершенствованных алгоритмов информатики, превосходящих те, которые оттачивались учеными и инженерами на протяжении десятилетий.
AlphaDev обнаружила более быстрый алгоритм сортировки — метод упорядочивания данных. Миллиарды людей используют эти алгоритмы каждый день, даже не осознавая этого. Они лежат в основе всего: от ранжирования результатов онлайн-поиска и публикаций в социальных сетях до обработки данных на компьютерах и телефонах. Создание более совершенных алгоритмов с использованием ИИ изменит то, как мы программируем компьютеры, и повлияет на все аспекты нашего все более цифрового общества.
Открыв исходный код наших новых алгоритмов сортировки в основная библиотека C++, миллионы разработчиков и компаний по всему миру теперь используют его в приложениях искусственного интеллекта в различных отраслях: от облачных вычислений и онлайн-покупок до управления цепочками поставок. Это первое изменение в этой части библиотеки сортировки за более чем десятилетие, и впервые в эту библиотеку был добавлен алгоритм, разработанный с помощью обучения с подкреплением. Мы рассматриваем это как важный шаг к использованию ИИ для оптимизации мирового кода, по одному алгоритму за раз.
Что такое сортировка?
Сортировка – это метод организации ряда элементов в определенном порядке. Примеры включают размещение трех букв в алфавитном порядке, расположение пяти чисел от самого большого к меньшему или упорядочивание базы данных, содержащей миллионы записей.
Этот метод развивался на протяжении всей истории. Один из самых ранних примеров относится ко второму и третьему веку, когда ученые вручную расставили по алфавиту тысячи книг на полках Великой Александрийской библиотеки. После промышленной революции были изобретены машины, которые могли помочь в сортировке: машины для составления таблиц хранили информацию на перфокартах, которые использовались для сбора результатов переписи 1890 года в Соединенных Штатах.
А с появлением коммерческих компьютеров в 1950-х годах мы стали свидетелями разработки первых компьютерных алгоритмов сортировки. Сегодня существует множество различных методов и алгоритмов сортировки, которые используются в кодовых базах по всему миру для организации огромных объемов данных в Интернете.
Иллюстрация того, что делает алгоритм сортировки. В алгоритм вводится ряд несортированных чисел, а на выходе выводятся отсортированные числа.
На разработку современных алгоритмов ученым-компьютерщикам и программистам потребовались десятилетия исследований. Они настолько эффективны, что дальнейшие улучшения являются серьезной проблемой, сродни попытке найти новый способ экономии электроэнергии или более эффективный математический подход. Эти алгоритмы также являются краеугольным камнем информатики, и их преподают на вводных курсах информатики в университетах.
В поисках новых алгоритмов
AlphaDev открыла более быстрые алгоритмы, начав с нуля, а не совершенствуя существующие алгоритмы, и начала искать то, чего не делает большинство людей: инструкции по сборке компьютера.
Инструкции по ассемблеру используются для создания двоичного кода, который компьютеры могут ввести в действие. Хотя разработчики пишут на языках кодирования, таких как C++, известных как языки высокого уровня, их необходимо перевести в «низкоуровневые» ассемблерные инструкции, чтобы их могли понять компьютеры.
Мы считаем, что на этом нижнем уровне существует множество улучшений, которые может быть трудно обнаружить на языке кодирования более высокого уровня. Компьютерное хранилище и операции на этом уровне более гибкие, а это означает, что существует значительно больше потенциальных улучшений, которые могут оказать большее влияние на скорость и энергопотребление.
Код обычно пишется на языке программирования высокого уровня, таком как C++. Затем они с помощью компилятора преобразуются в инструкции ЦП низкого уровня, называемые инструкциями ассемблера. Затем ассемблер преобразует инструкции ассемблера в исполняемый машинный код, который может запускать компьютер.
Рисунок А: Пример алгоритма C++, который сортирует до двух элементов.
Рисунок Б: Соответствующее ассемблерное представление кода.
Находим лучшие алгоритмы с помощью игры
AlphaDev основан на AlphaZero, нашей модели обучения с подкреплением, которая победила чемпионов мира в таких играх, как го, шахматы и сёги. С помощью AlphaDev мы показываем, как эту модель можно перенести из игр в научные задачи, а также из моделирования в реальные приложения.
Чтобы научить AlphaDev находить новые алгоритмы, мы превратили сортировку в однопользовательскую «игру-сборку». На каждом этапе AlphaDev наблюдает за сгенерированным алгоритмом и информацией, содержащейся в центральном процессоре (ЦП). Затем он выполняет ход, выбирая инструкцию, которую нужно добавить в алгоритм.
Игра со сборкой невероятно сложна, потому что AlphaDev приходится эффективно перебирать огромное количество возможных комбинаций инструкций, чтобы найти алгоритм, способный сортировать, и который работает быстрее, чем лучший на данный момент. Число возможных комбинаций инструкций аналогично числу частиц во Вселенной или количеству возможных комбинаций ходов в играх в шахматы (10120 игр) и го (10700 игр). И одно неверное движение может свести на нет весь алгоритм.
Рисунок А: Игра «Сборка». Игрок AlphaDev получает на входе состояние системы и выполняет ход, выбирая ассемблерную инструкцию, которую нужно добавить к уже сгенерированному алгоритму.
Рисунок Б: Расчет вознаграждения. После каждого хода сгенерированному алгоритму подаются тестовые входные последовательности — для sort3 это соответствует всем комбинациям последовательностей из трёх элементов. Затем алгоритм генерирует выходные данные, которые сравниваются с ожидаемыми выходными данными отсортированных последовательностей в случае сортировки. Агент вознаграждается в зависимости от правильности алгоритма и задержки.
По мере построения алгоритма, по одной инструкции за раз, AlphaDev проверяет его правильность, сравнивая выходные данные алгоритма с ожидаемыми результатами. Для алгоритмов сортировки это означает, что входят неупорядоченные числа, а выходят правильно отсортированные числа. Мы вознаграждаем AlphaDev как за правильную сортировку чисел, так и за то, насколько быстро и эффективно она это делает. AlphaDev выигрывает, обнаружив правильную и более быструю программу.
Открытие более быстрых алгоритмов сортировки
AlphaDev обнаружила новые алгоритмы сортировки, которые привели к улучшениям в библиотеке сортировки LLVM libc++, которая стала на 70 % быстрее для более коротких последовательностей и примерно на 1,7 % быстрее для последовательностей, превышающих 250 000 элементов.
Мы сосредоточились на улучшении алгоритмов сортировки более коротких последовательностей из трех-пяти элементов. Эти алгоритмы являются одними из наиболее широко используемых, поскольку их часто вызывают много раз как часть более крупных функций сортировки. Улучшение этих алгоритмов может привести к общему ускорению сортировки любого количества элементов.
Чтобы сделать новый алгоритм сортировки более удобным для людей, мы провели реверс-инжиниринг алгоритмов и перевели их на C++, один из самых популярных языков программирования, используемых разработчиками. Эти алгоритмы теперь доступны в Стандартная библиотека сортировки LLVM libc++используемый миллионами разработчиков и компаний по всему миру.
Поиск новых подходов
AlphaDev не только нашла более быстрые алгоритмы, но и открыла новые подходы. Его алгоритмы сортировки содержат новые последовательности инструкций, которые сохраняют одну инструкцию каждый раз, когда они применяются. Это может иметь огромное значение, поскольку эти алгоритмы используются триллионы раз в день.
Мы называем это «перемещением и копированием AlphaDev». Этот новый подход напоминает «ход 37» AlphaGo – противоречивую игру, которая ошеломила зрителей и привела к поражению легендарного игрока в го. При перемещении замены и копирования AlphaDev пропускает шаг для соединения элементов таким образом, который выглядит как ошибка, но на самом деле является ярлыком. Это показывает способность AlphaDev находить оригинальные решения и бросает вызов нашему мышлению о том, как улучшить алгоритмы информатики.
Левый: Исходная реализация с min(A,B,C).
Верно: AlphaDev Swap Move — AlphaDev обнаруживает, что вам нужно только min(A,B).
Левый: Исходная реализация с max(B,min(A,C,D)) используется в более крупном алгоритме сортировки для сортировки восьми элементов.
Верно: AlphaDev обнаружила, что при использовании перемещения копирования требуется только max (B, min (A, C))
От сортировки к хешированию в структурах данных
Обнаружив более быстрые алгоритмы сортировки, мы проверили, сможет ли AlphaDev обобщить и улучшить другой алгоритм информатики: хеширование.
Хеширование — это фундаментальный алгоритм вычислений, используемый для извлечения, хранения и сжатия данных. Подобно библиотекарю, который использует систему классификации для поиска определенной книги, алгоритмы хеширования помогают пользователям узнать, что они ищут и где именно это найти. Эти алгоритмы берут данные для определенного ключа (например, имени пользователя «Джейн Доу») и хэшируют их – процесс, в котором необработанные данные преобразуются в уникальную строку символов (например, 1234ghfty). Этот хэш используется компьютером для быстрого получения данных, связанных с ключом, вместо поиска всех данных.
Мы применили AlphaDev к одному из наиболее часто используемых алгоритмов хеширования структур данных, чтобы попытаться найти более быстрый алгоритм. А когда мы применили его к диапазону хеш-функции 9–16 байт, алгоритм, обнаруженный AlphaDev, оказался на 30 % быстрее.
В этом году новый алгоритм хеширования AlphaDev был выпущен в открытый доступ. Библиотека Абселядоступный миллионам разработчиков по всему миру, и, по нашим оценкам, сейчас он используется триллионы раз в день.
Оптимизация мирового кода, по одному алгоритму за раз
Оптимизируя и запуская улучшенные алгоритмы сортировки и хеширования, используемые разработчиками по всему миру, AlphaDev продемонстрировала свою способность обобщать и открывать новые алгоритмы с практическим эффектом. Мы рассматриваем AlphaDev как шаг к разработке универсальных инструментов искусственного интеллекта, которые могут помочь оптимизировать всю вычислительную экосистему и решить другие проблемы, которые принесут пользу обществу.
Хотя оптимизация в области низкоуровневых ассемблерных инструкций очень эффективна, по мере роста алгоритма возникают ограничения, и в настоящее время мы изучаем возможность AlphaDev оптимизировать алгоритмы непосредственно на языках высокого уровня, таких как C++, что было бы более полезно для разработчиков.
Открытия AlphaDev, такие как перемещения подкачки и копирования, не только показывают, что они могут улучшить алгоритмы, но и найти новые решения. Мы надеемся, что эти открытия вдохновят исследователей и разработчиков на создание методов и подходов, которые смогут дополнительно оптимизировать фундаментальные алгоритмы для создания более мощной и устойчивой вычислительной экосистемы.