DeepMind 的人工智能系统 AlphaDev 发现的排序算法可能彻底改变计算基础

6月8日消息:谷歌的人工智能研究实验室 DeepMind 通过其最新的 AI 系统 AlphaDev，在计算机科学领域取得了一项重大成就。AlphaDev 是 AlphaZero 的一个专门版本，通过发现更快的排序和散列算法，为全球开发人员在数据排序、存储和检索方面提供了必不可少的处理过程，每天使用数万亿次。

DeepMind 在今天发表在科学杂志《自然》上的一篇论文中表示，与 C++库中的算法相比，AlphaDev 的新算法在对短序列元素进行排序时效率提高了 70%，对超过 250，000 个元素的序列提高了约 1.7%。因此，当用户提交搜索查询时，AlphaDev 的算法可以更快地对结果进行排序，从而在大规模应用时节省大量时间和能源。

此外，该系统还发现了一种更快的散列算法，在数据中心中将哈希函数应用于 9 到 16 字节范围内时，效率提高了 30%。

革新计算机科学

DeepMind 认为这一重大成就将彻底改变计算机科学，并带来效率和效果的提升。

DeepMind 的研究员表示：「AlphaDev 发现了改进的排序算法，包括 AlphaDev 复制和交换移动等新颖创新。」他还说：「类似于 AlphaGo 著名的『37 手』给围棋这个古老游戏带来了一套新的策略，AlphaDev 独特的算法发现希望能激发出优化基础计算机科学算法的新视角和策略，并使其更快。」

Mankowitz 说，这是强化学习的一个重要里程碑，因为它提供了更多证据证明其有能力做出新发现，尤其是在代码优化领域。

该公司还宣布打算通过 LLVM libc++标准排序库将新算法提供给数百万开发人员和各行各业的公司。值得注意的是，这次更新是排序库这一部分十年来的首次修订，也是通过强化学习开发的算法的首次纳入。

Mankowitz 表示：「我们估计，我们公开发布的排序算法每天在全球被调用数万亿次，可以提供 2% 到 70% 的速度提升，这些算法可以为调用这些函数的开发人员和公司提供资源节省。我们相信这些算法将激发研究人员和实践者开发出更多的新方法，从而发现新的和改进的算法。」

利用强化学习增强传统算法开发

DeepMind 表示，目前大多数计算算法已经达到人类专家无法进一步优化的阶段，导致了计算瓶颈的不断加剧。该公司强调，使用深度强化学习可以通过生成精确高效的算法来增强开发方法。在进行更有效的搜索和考虑准确和快速程序的空间的同时，它通过优化 CPU 指令级别的实际测量延迟来实现。

排序算法是系统地对项目按指定顺序进行排列的基础。它们是计算机科学教育的基石。同样，散列在数据存储和检索中有广泛应用，比如在客户数据库中。散列算法通常使用一个键（比如用户名称「Jane Doe」）生成与所需数据值（比如「订单号 164335-87」）相对应的唯一散列值，以便进行检索。类似于图书管理员利用分类系统迅速找到特定书籍，散列系统使计算机能够事先知道所需信息及其准确位置。

虽然开发人员主要使用 C++等用户友好的高级语言编写代码，但将这些语言转化为低级汇编指令对于计算机理解来说是必不可少的。DeepMind 的研究人员认为，在低级别存在许多改进的空间，而在高级编程语言中揭示这些改进可能面临挑战。汇编级别提供了计算机存储和操作的灵活性，为能够显著影响速度和能源效率的改进提供了巨大潜力。

为了在 C++中运行算法，首先将其编译成称为汇编指令的低级 CPU 指令，这些指令在 CPU 上的内存和寄存器之间操作数据。

Mankowitz 表示：「这提供了算法操作的更加细致的概述，因此更容易找到改进算法的优化方式。通过在汇编中进行优化，我们发现了 AlphaDev 复制和交换移动。这些是一系列汇编指令，当应用于一个汇编程序时，可以通过减少一个指令来减小程序的大小。」

DeepMind 发现更快算法的独特方法

DeepMind 的 AlphaDev 采用了一种非常规的方法，通过探索人类鲜有涉足的计算机汇编指令领域，发现更快的算法。为了训练 AlphaDev 发现新算法，研究团队将排序重新构想为「单人汇编游戏」。AlphaDev 利用强化学习观察和生成算法，并结合 CPU 的信息。

在每一步中，AI 系统主动选择一个指令并将其纳入算法中，这是一个复杂且具有挑战性的过程，因为潜在的指令组合数目庞大。

AlphaDev 逐步构建算法的同时，还通过将算法的输出与预期结果进行比较来验证每一步的正确性。这种方法的最终目标是发现一个正确且更快的程序，从而在游戏中取得胜利。

DeepMind 的 AI 系统发现了新颖的排序算法，使 LLVM libc++排序库取得了显著的改进。研究主要集中在提高短序列的排序算法，这些算法通常被应用于更大的排序函数中，提高它们的效率可以改善排序任意数量的项目时的整体速度。

为了提高可用性，DeepMind 对发现的算法进行了逆向工程，并将其转化为 C++代码。

超越排序算法的领域

这些改进主要针对对数字进行排序的 sort3. sort4 和 sort5 程序。Mankowitz 解释说：「每当开发人员或应用程序需要对这些数据类型进行排序时，都可以调用我们的排序算法。根据要排序的项目数量，速度提升范围在 2% 到 70% 之间。由于这些函数每天被调用数万亿次，开发人员和用户将能够在消耗更少资源的情况下运行其应用程序/使用各种服务。」

此外，AlphaDev 的能力超越了排序算法的领域。DeepMind 还探索了系统的潜力，将其方法泛化并改进其他重要的计算机科学算法，包括散列算法。将 AlphaDev 的方法应用于 9 到 16 字节范围内的散列算法，其速度提高了 30%。

DeepMind 表示，AlphaDev 是朝着创建能够优化整个计算生态系统并应对各种社会挑战的多功能 AI 工具的进展中的重要里程碑。尽管优化低级汇编指令已经显示出巨大的威力，但该公司表示，他们正在积极探索 AlphaDev 直接优化高级语言（如 C++）中的算法的潜力，这对开发人员来说将更加有价值。他们还在尝试优化在运行应用程序和服务时更有效地调度资源，例如优化 YouTube 的视频压缩流程以及优化系统和应用程序运行的底层硬件。

Mankowitz 表示：「我们希望这些算法能够为研究人员和实践者提供一种不同的视角，看待如何构建算法。」