AlphaDev发现更快的排序算法

发布日期：2023年6月7日
作者：Daniel J. Mankowitz 和 Andrea Michi

数字社会对计算和能源需求日益增长。过去五十年来，我们依靠硬件改进来满足需求。但随着微芯片接近物理极限，改进运行其上的代码变得至关重要，以使计算更强大和可持续。这对于每天运行数万亿次的算法尤为重要。

在今日发表于《自然》的论文中，介绍了AlphaDev——一个使用强化学习发现增强型计算机科学算法的人工智能系统，其性能超过了科学家和工程师数十年打磨的算法。

AlphaDev发现了更快的排序算法，即排序数据的方法。数十亿人每天都在使用这些算法而未察觉。它们支撑着从在线搜索结果排序、社交帖子排序到计算机和手机数据处理的一切。使用AI生成更好的算法将改变我们编程计算机的方式，并影响日益数字化的社会的各个方面。

通过将新排序算法开源到主流C++库中，全球数百万开发者和公司现在将其用于云计算、在线购物和供应链管理等行业的AI应用。这是该排序库十多年来首次变更，也是首次通过强化学习设计的算法被添加至此库。这被视为使用AI优化世界代码的重要一步。

什么是排序？

排序是以特定顺序组织若干项目的方法。例如按字母顺序排列三个字母、从大到小排列五个数字，或排序包含数百万条记录的数据库。

该方法在历史中不断演变。最早例子可追溯至二、三世纪，学者在亚历山大图书馆手动按字母顺序排列数千本书。工业革命后，出现了可辅助排序的机器——制表机将信息存储在打孔卡上，用于收集1890年美国人口普查结果。

随着1950年代商用计算机的兴起，最早的计算机科学排序算法得以发展。如今，全球代码库中使用许多不同的排序技术和算法来组织海量在线数据。

图示：未排序数字序列输入算法，输出排序后数字。

当代算法耗费计算机科学家和程序员数十年研究才开发出来。它们如此高效，以至于进一步改进成为重大挑战，类似于寻找节电新方法或更高效的数学方法。这些算法也是计算机科学的基石，在大学计算机科学入门课程中教授。

寻找新算法

AlphaDev通过从零开始而非改进现有算法来发现更快算法，并开始关注大多数人类未涉及的领域：计算机汇编指令。

汇编指令用于创建计算机执行的二进制代码。虽然开发者使用C++等高级语言编写代码，但必须将其翻译为“低级”汇编指令计算机才能理解。

相信在此低级层存在许多改进，这些改进在高级编程语言中难以发现。计算机存储和操作在此层更灵活，意味着存在更多潜在改进，可能对速度和能耗产生更大影响。

代码通常用C++等高级编程语言编写，然后使用编译器转换为称为汇编指令的低级CPU指令。汇编器再将汇编指令转换为计算机可执行机器代码。

图A：排序最多两个元素的C++算法示例。
图B：代码对应的汇编表示。

通过游戏寻找最佳算法

AlphaDev基于AlphaZero——我们的强化学习模型，曾在围棋、国际象棋和将棋中击败世界冠军。通过AlphaDev，展示了该模型如何从游戏迁移到科学挑战，从模拟迁移到实际应用。

为训练AlphaDev发现新算法，将排序转化为单人“汇编游戏”。每回合，AlphaDev观察生成的算法和中央处理器（CPU）中的信息，然后通过选择要添加到算法的指令来移动。

汇编游戏极其困难，因为AlphaDev必须高效搜索大量可能的指令组合，以找到可排序且比当前最佳算法更快的算法。可能的指令组合数量类似于宇宙中的粒子数或国际象棋（10^{120局）和围棋（10}700局）的可能移动组合数。单一错误移动可能使整个算法无效。

图A：汇编游戏。玩家AlphaDev接收系统状态st作为输入，并通过选择汇编指令添加到迄今生成的算法中来移动at。
图B：奖励计算。每次移动后，生成的算法被馈送测试输入序列——对于sort3，这对应于三个元素序列的所有组合。算法然后生成输出，与排序情况下预期输出的排序序列进行比较。代理根据算法的正确性和延迟获得奖励。

随着算法逐条指令构建，AlphaDev通过比较算法输出与预期结果来检查其正确性。对于排序算法，这意味着无序数字输入，正确排序数字输出。奖励AlphaDev正确排序数字以及排序的速度和效率。AlphaDev通过发现正确、更快的程序赢得游戏。

发现更快的排序算法

AlphaDev发现了新的排序算法，使LLVM libc++排序库对较短序列的排序速度提高达70%，对超过25万个元素的序列速度提高约1.7%。

专注于改进三到五个元素的较短序列的排序算法。这些算法使用最广泛，因为它们常作为更大排序函数的一部分被多次调用。改进这些算法可加速排序任意数量项目。

为使新排序算法更易于使用，将算法反向工程并翻译为C++——开发者最流行的编程语言之一。这些算法现可在LLVM libc++标准排序库中使用，被全球数百万开发者和公司使用。

发现新方法

AlphaDev不仅找到了更快算法，还发现了新方法。其排序算法包含新的指令序列，每次应用时节省一条指令。这可能产生巨大影响，因为这些算法每天被使用数万亿次。

称之为“AlphaDev交换和复制移动”。此新方法让人想起AlphaGo的“第37步”——一反直觉的棋步，震惊旁观者并击败传奇围棋选手。通过交换和复制移动，AlphaDev跳过一步以连接项目，看似错误实为捷径。这展示了AlphaDev发现原创解决方案的能力，并挑战了我们改进计算机科学算法的方式。

左：原始实现使用min(A,B,C)。
右：AlphaDev交换移动——发现仅需要min(A,B)。

左：在排序八个元素的较大排序算法中使用max(B, min(A, C, D))的原始实现。
右：AlphaDev发现使用其复制移动时仅需要max(B, min(A, C))。

从排序到数据结构哈希

发现更快排序算法后，测试了AlphaDev是否能泛化并改进不同的计算机科学算法：哈希。

哈希是计算中用于检索、存储和压缩数据的基本算法。如同图书管理员使用分类系统定位特定书籍，哈希算法帮助用户知道寻找什么及确切位置。这些算法获取特定键（如用户名“Jane Doe”）的数据并进行哈希——将原始数据转换为唯一字符串（如1234ghfty）的过程。计算机使用此哈希快速检索与键相关的数据，而非搜索所有数据。

将AlphaDev应用于数据结构中最常用的哈希算法之一，尝试发现更快算法。当应用于哈希函数的9-16字节范围时，AlphaDev发现的算法速度提高30%。

今年，AlphaDev的新哈希算法发布到开源Abseil库中，供全球数百万开发者使用，估计现在每天被使用数万亿次。

一次优化一个算法，优化世界代码

通过优化和发布全球开发者使用的改进排序和哈希算法，AlphaDev展示了其泛化和发现具有实际影响新算法的能力。视AlphaDev为开发通用AI工具的一步，这些工具有助于优化整个计算生态系统并解决其他造福社会的问题。

虽然在低级汇编指令空间优化非常强大，但随着算法增长存在限制，目前正在探索AlphaDev直接优化C++等高级语言算法的能力，这对开发者更有用。

AlphaDev的发现，如交换和复制移动，不仅显示其能改进算法，还能找到新解决方案。希望这些发现激励研究人员和开发者创建技术和方法，进一步优化基本算法，以创建更强大和可持续的计算生态系统。

了解更多优化计算生态系统的信息：[链接]

致谢：感谢Juanita Bawagan、Arielle Bier、Gabriella Pearl、Duncan Smith、Katie McAtackney、Kathryn Seager、Max Barnett、Ross West、Dominic Barlow、Hollie Dobson、Domhnall Malone在文本和图表方面的帮助。此项工作由团队完成，贡献者包括Daniel J. Mankowitz、Andrea Michi、Anton Zhernov、Marco Gelmi、Marco Selvi、Cosmin Paduraru、Edouard Leurent、Shariq Iqbal、Jean-Baptiste Lespiau、Alex Ahern、Thomas Koppe、Kevin Millikin、Stephen Gaffney、Sophie Elster、Jackson Broshear、Chris Gamble、Kieran Milan、Robert Tung、Minjae Hwang、Taylan Cemgil、Mohammadamin Barekatain、Yujia Li、Amol Mandhane、Thomas Hubert、Julian Schrittwieser、Demis Hassabis、Pushmeet Kohli、Martin Riedmiller、Oriol Vinyals和David Silver。感谢Mikita Sazanovich和Danila Kutenin对哈希算法的贡献。
更多精彩内容 请关注我的个人公众号 公众号（办公AI智能小助手）或者 我的个人博客 https://blog.qife122.com/
公众号二维码