415
2023-06-13 10:00:36
6月8日，deepmind 在著名学术刊物 nature 上，发表了其最新研究成果：一个名为 alphadev 的 ai 系统。alphadev不仅可以将排序算法提速70％，甚至在有的算法上，能比人类快3倍之多。十多年来，c 排序库首次更改。ai优化世界代码，又达新里程碑。
从名字上便可以看出，alphadev 与 alphago、alphafold 一样，同属 deepmind 旗下的 alpha 系列，而 alphadev 的发布也同样在业界引起了广泛关注。
具体来说，alphadev 是一种通过强化学习来发现增强的计算机科学算法的 ai 系统，它发现了一种更快的排序算法，直接超越了科学家和工程师们几十年来的研究，将排序算法的速度提高了 70%！
deepmind 计算机科学家 daniel mankowitz 更是表示：“我们估计，alphadev 发现的排序算法和哈希算法每天都会被调用数万亿次。”
强化学习，打破计算瓶颈
既然 alphadev 发现的是一种全新的排序算法，那我们便先从“排序”说起。
不论是将 3 个字母按字母顺序排列、将 5 个数字从大到小排列，亦或是将一个有上百万条记录的数据库进行排列，这都是排序，是一种几乎所有关键软件的基础算法。在 20 世纪 50 年代之前，排序工作多数都依赖人工，直至后来商业计算机兴起，最早用于排序的计算机科学算法才开始出现并发展。
如今，开发者们所用的排序技术和算法，都是过去几十年计算机科学家和程序员们积累下来的研究成果。相较于几十年前的手动排序，现在的算法确实已经很高效，但也正因如此，想要将其进一步改进无疑是一项重大挑战，难度不亚于“找到一种新的节电方式”或“发现一种更有效的数学方法”。当前，gpt-4、bard等大模型的参数指数级增长，对算力等资源的需求不断增长。而过去50年里，人类不断依靠芯片的改进以跟上步伐。但随着微芯片接近物理极限，改进代码让计算更强大、更持续变得至关重要。尤其是，对每天运行数万亿次代码的算法愈重要。
因此，deepmind 在论文中提到：“人类的直觉和专业知识对于改进算法至关重要。然而，许多算法已经到了人类专家无法进一步优化它们的阶段，导致计算瓶颈不断扩大。”
alphadev发现了一种更快的排序算法，数十亿人每天都在不知不觉中使用这些算法。它们是一切的基础，从在线搜索结果，社交帖子，到计算机和手机数据处理方式。这些算法每天都要执行数万亿次。利用ai生成更好的算法，将改变我们对计算机编程的方式，并影响我们数字化社会的方方面面。根据nature论文中的数据，alphazero所创造的算法能比人类的数据排序速度快三倍。
今天，google deepmind还开源了在主c 库中的最新排序算法，所有人皆可用。
开源地址：
打破传统，从汇编指令入手
为了帮助打破这一计算瓶颈，deepmind 引入了 alphadev， alphadev的创新意义在于，它并不是通过改进现有算法，而是完全从头开始发现了更快的算法。而且，它竟然着手于大多数人类并没有想到的地方——计算机汇编指令。汇编指令用于创建二进制代码。虽然开发者写代码时用的是c 等高级语言，但为了让计算机理解，这些高级语言必须翻译成「低级」的汇编指令。
以此作为灵感，deepmind 认为相较于在高层次的编码语言中，在汇编指令这个较低的层次上，应该还存在许多改进空间，而这些改进在更高级的编程语言中可能很难发现。因为计算机的存储和操作会更灵活，如果再多做一些潜在的改进，对速度和能源使用也将产生更大影响。
通过玩“游戏”来发现新算法
众所周知，deepmind的强化学习模型，在围棋、国际象棋和将棋等游戏中，屡次击败世界冠军。而我们这次的主角——alphadev，基于的正是alphazero。alphadev的工作方式与之前的alphazero相似，后者结合了计算机推理和直觉，在棋盘游戏中选择每一步的走法。只不过，alphadev并不会选择下一步怎么走棋，而是选择添加哪些指令。
为了训练alphadev来发现新的算法，deepmind 让 alphadev 开始了一个单人“汇编游戏（assembly game）”。
根据论文介绍，在这个游戏中，玩家需要选择一系列低级汇编指令，以此产生一种新的高效排序算法：“这个游戏很有挑战性，因为玩家需要考虑汇编指令的组合空间，以产生一种既可证明正确又快速的算法。难度不仅来自搜索空间的大小，可能的组合数量类似于国际象棋和围棋，而且其中一条不正确的指令都可能会使整个算法无效。”
在游戏过程中，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 发现原始k8凯发旗舰的解决方案的能力，并挑战了人类改进计算机科学算法的思考方式。”
如下图示例原始sort3实现，有min(a, b, c)，使用alphadev swap move，alphadev发现，你只需要min(a, b)。
再比如，原始实现用max(b, min(a ,c, d))中较大的排序算法对8个元素进行排序。alphadev发现使用其「swap and copy moves」时只需要max(b, min(a, c))。
不仅如此，在发现了新排序算法后，deepmind 还测试了 alphadev 是否可以改进数据结构中常用的哈希算法，结果 alphadev 不负众望，确实也发现了一种新的哈希算法，将其应用于 9-16 字节范围内的哈希函数时，速度可提高 30%。而这个新哈希算法，也会在今年被发布到开源的 abseil 库中，供全球数百万开发者使用。
用 ai 来优化代码的未来
通过以上新发现的排序算法和哈希算法，alphadev 已展示出了其概括和发现新算法的能力，即用 ai 来优化世界上的代码，并朝着开发通用 ai 工具迈出了重要一步。google deepmind认为，alphadev是朝着开发agi工具迈出的一步，这些工具有助于优化整个计算生态系统，还能解决其他有益于社会的问题。
不过，研究人员也承认，目前alphadev在低级汇编指令优化能力非常强，但是随着算法的发展也存在局限性。为了让开发者更可用，alphadev用高级语言（如c ）优化算法的能力正在探索中。alphadev的新发现，如「alphadev swap move」和「alphadev copy move」，不仅表明它可以改进算法，还可以找到新的k8凯发旗舰的解决方案。研究人员希望，这些发现能激励研究人员和开发人员创造技术和方法，进一步优化基础算法，以创建一个更强大、更可持续的计算生态系统。
参考链接：
