AI重写排序算法能改写摩尔定律放缓的命运吗？

“重现当年AlphaGo神来之笔”,“没想到这么古老又基础的算法还能被进一步改进”……以上是网友对DeepMind公司AI系统AlphaDev发现的新排序算法的评价。这个名叫AlphaDev的人工智能是基于AlphaZero(2017年击败世界冠军的棋类AI)打造的,它正在重新“构想”排序算法,创新计算机领域核心算法。
    DeepMind在科学杂志《自然》上发表的一篇论文中提到,与C﹢﹢库中的算法相比,AlphaDev的新算法在对短序列元素进行排序时效率提高了70%,对超过25万个元素的序列排序效率提高了约1.7%。目前,新算法已经开源并纳入常用的Libc ﹢﹢库中。DeepMind表示,这是十多年来C﹢﹢排序算法库部分的首次更新。
    排序算法是计算机领域极为基础的“主力”算法之一,用于将一串数据按照特定的顺序进行排列。常见的歌单列表、图像处理等都离不开排序算法,其应用场景还包括直播间“买买买”、云计算集群任务处理等,不夸张地说,排序算法每天会被调用上亿次。
    近些年来,诸如冒泡排序、插入排序、堆排序等许多不同的排序算法得到了高度优化,因而排序算法的创新空间十分有限。“我们真的没想到能取得如此好的成绩:这个程序非常简短,这类程序已经被研究了数十年”,DeepMind公司的丹尼尔·曼科维茨(Daniel Mankowitz)说。
    AlphaDev不是对现有算法进行微调,而是从零开始“创造”,从汇编指令开始“摸索”。它使用汇编语言,这是一种介于程序代码与用0和1编码的二进制指令序列之间的基础语言,具有直接和简洁的特点,可以有效访问、控制计算机的各种硬件设备,占用内存少,执行速度快。DeepMind表示,使用汇编代码让AlphaDev有更多空间来创建更高效的算法。
    AlphaDev“摸索”算法的过程类似“打怪升级”。该人工智能系统被要求每次构建一条指令,并将输出与已知的正解方案进行对比,从而确保正在创建一个有效的方法。此外,随着难度增加,还会限制执行的步数以及待排序列的长度。DeepMind表示,随着问题规模扩大,这项任务会变得越发困难,因为指令的可能组合数可能逼近宇宙中的粒子总数。
    曼科维茨表示,元件尺寸正在触及物理极限,工艺研发难度与日俱增,摩尔定律(即单芯片计算能力每隔一段时间就会翻倍)即将走到尽头,但AlphaDev带来的计算效率提升或是应对之道。“这些算法正在被数以万亿次地调用(在软件中运行),我们估计每天都有数以百万计的开发人员和公司在世界各地使用它们。”曼科维茨说,“优化每天被调用数以万亿次的基础代码有望突破摩尔定律放缓的瓶颈。”
    英国伯明翰大学的马克·李认为,AlphaDev非常有趣,即使只能带来1.7%的速度提升也是有用的。但他表示,即使在其他基础算法中也能做到类似的效率提升,他仍对这种方法能弥补摩尔定律的失效持怀疑态度,因为其在上层软件应用中的效果还有待验证。“相关优化会从排序算法拓展到其他常用算法上,但暂时还无法进一步应用到更复杂的代码上。”他认为,硬件层面的进步和革新仍是主流趋势。

(来源:《新科学家》作者:Matthew Sparkes 翻译:吴双)

(编辑:户静凝)