查看原文
其他

谷歌 Alpha 家族再添“猛将”:AlphaDev 重磅亮相,打破多年计算瓶颈,新排序算法提速 70%!

整理 | 郑丽媛
出品 | CSDN(ID:CSDNnews)

上周四,DeepMind 在著名学术刊物 Nature 上,发表了其最新研究成果:一个名为 AlphaDev 的 AI 系统。

从名字上便可以看出,AlphaDev 与 AlphaGo、AlphaFold 一样,同属 DeepMind 旗下的 Alpha 系列,而 AlphaDev 的发布也同样在业界引起了广泛关注。

具体来说,AlphaDev 是一种通过强化学习来发现增强的计算机科学算法的 AI 系统,它发现了一种更快的排序算法,直接超越了科学家和工程师们几十年来的研究,将排序算法的速度提高了 70%!

DeepMind 计算机科学家 Daniel Mankowitz 更是表示:“我们估计,AlphaDev 发现的排序算法和哈希算法每天都会被调用数万亿次。”


不断扩大的计算瓶颈


既然 AlphaDev 发现的是一种全新的排序算法,那我们便先从“排序”说起。

不论是将 3 个字母按字母顺序排列、将 5 个数字从大到小排列,亦或是将一个有上百万条记录的数据库进行排列,这都是排序,是一种几乎所有关键软件的基础算法。在 20 世纪 50 年代之前,排序工作多数都依赖人工,直至后来商业计算机兴起,最早用于排序的计算机科学算法才开始出现并发展。

如今,开发者们所用的排序技术和算法,都是过去几十年计算机科学家和程序员们积累下来的研究成果。相较于几十年前的手动排序,现在的算法确实已经很高效,但也正因如此,想要将其进一步改进无疑是一项重大挑战,难度不亚于“找到一种新的节电方式”或“发现一种更有效的数学方法”。

因此,DeepMind 在论文中提到:“人类的直觉和专业知识对于改进算法至关重要。然而,许多算法已经到了人类专家无法进一步优化它们的阶段,导致计算瓶颈不断扩大。”


打破传统,从汇编指令入手


为了帮助打破这一计算瓶颈,DeepMind 引入了 AlphaDev :“AlphaDev 不是改进现有算法,而是从头开始发现更快的算法,并从大多数人没想到的地方切入:计算机的汇编指令。”

现在,虽然开发者多用 C++ 等高级编程语言写代码,但为了让计算机理解,还是必须用编译器将其转换为“低级”汇编指令,再由汇编程序将汇编指令转换为计算机可以运行的可执行机器代码。

以此作为灵感,DeepMind 认为相较于在高层次的编码语言中,在汇编指令这个较低的层次上,应该还存在许多改进空间,因为计算机的存储和操作会更灵活,对速度和能源使用也将产生更大影响。


通过玩“游戏”来发现新算法


有了以上基本构思后,DeepMind 让 AlphaDev 开始了一个单人“汇编游戏(Assembly Game)”。

根据论文介绍,在这个游戏中,玩家需要选择一系列低级汇编指令,以此产生一种新的高效排序算法:“这个游戏很有挑战性,因为玩家需要考虑汇编指令的组合空间,以产生一种既可证明正确又快速的算法。难度不仅来自搜索空间的大小,可能的组合数量类似于国际象棋和围棋,而且其中一条不正确的指令都可能会使整个算法无效。”

由于这个特性,AlphaDev 基于 AlphaZero 研发——其强化学习模型在围棋、国际象棋和象棋等游戏中都曾打败世界冠军。

在游戏过程中,AlphaDev 每玩一次 AssemblyGame,都会从头开始构建一个汇编程序,从一组初始无序的指令开始构建,从而定义一种新的高效算法。

随着游戏的进行,算法不断建立,而 AlphaDev 会通过比较算法的输出和预期的结果来检查它是否正确。对于排序算法,AlphaDev 的检验方式是:输入无序的数字后,可否输出正确排序的数字。

DeepMind 将游戏的输赢作为 AlphaDev 的激励方式,而该游戏的输赢也很好判定:

▶ 使用汇编指令,生成正确的低延迟算法,AlphaDev 即赢得游戏。

▶ 生成不正确的算法或正确但低效的算法,AlphaDev 即输掉游戏。


新排序算法,速度提升 70%!


于是,在这样的“游戏”过程中,AlphaDev 发现了更快的排序算法,主要是围绕 3-5 个元素的较短序列的排序算法。

DeepMind 解释道:“因为这些算法是使用最广泛的算法之一,它们经常作为较大排序函数的一部分被多次调用,改进这些算法可以加快对任意数量项目进行排序的整体速度。”

因而,AlphaDev 发现的这个新排序算法,对于较短的序列来说,速度可提升 70%,对于超过 25 万个元素的序列来说,速度也能提高约 1.7%。

为了让更多人用到这个新排序算法,DeepMind 对算法进行了逆向工程,并以此改进了 LLVM libc++ 标准排序库,可供全球数百万开发者和公司使用。DeepMind 计算机科学家 Daniel Mankowitz 激动表示:“这些算法目前位于 C++ 标准排序库中,这是十多年来对这些子例程的首次更改!”


新哈希函数,速度提升 30%!


除了新排序算法,通过研究 AlphaDev 的发现过程,它实际上还创造了一种新方法:其排序算法包含新的指令序列,每次应用时都会跳过一条指令——对于每天都会被使用上万亿次的排序算法来说,这无疑将产生巨大影响。

DeepMind 研究人员将此称作 “AlphaDev 交换和复制动作(AlphaDev swap and copy moves):通过交换和复制移动,AlphaDev 跳过了一个步骤,以一种看似错误实际上很快捷的方式连接项目。“这显示了 AlphaDev 发现原始解决方案的能力,并挑战了人类改进计算机科学算法的思考方式。”

不仅如此,在发现了新排序算法后,DeepMind 还测试了 AlphaDev 是否可以改进数据结构中常用的哈希算法,结果 AlphaDev 不负众望,确实也发现了一种新的哈希算法,将其应用于 9-16 字节范围内的哈希函数时,速度可提高 30%。而这个新哈希算法,也会在今年被发布到开源的 Abseil 库中,供全球数百万开发者使用。


用 AI 来优化代码的未来


通过以上新发现的排序算法和哈希算法,AlphaDev 已展示出了其概括和发现新算法的能力,即用 AI 来优化世界上的代码,并朝着开发通用 AI 工具迈出了重要一步。

因此对于 AlphaDev 的影响,DeepMind 表达了其最终展望:“我们希望这些发现,能激励研究人员和开发人员创造技术和方法,进一步优化基本算法,以创建一个更强大和可持续的计算生态系统。”

参考链接:

https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

https://www.nature.com/articles/s41586-023-06004-9

推荐阅读:

高考志愿填什么,才不会被 AI 抢饭碗

算网共生 云智无界 | 算网的新征程等你加入

苹果欲让 Mac 变成「游戏机」,发布移植工具,几秒就能玩上 Windows 游戏!

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存