6月8日,，DeepMind 在著名學(xué)術(shù)刊物 Nature 上，發(fā)表了其最新研究成果：一個(gè)名為 AlphaDev 的 AI 系統(tǒng),。AlphaDev不僅可以將排序算法提速70％,，甚至在有的算法上,，能比人類(lèi)快3倍之多。十多年來(lái),，C++排序庫(kù)首次更改,。AI優(yōu)化世界代碼，又達(dá)新里程碑,。
從名字上便可以看出,，AlphaDev 與 AlphaGo、AlphaFold 一樣,，同屬 DeepMind 旗下的 Alpha 系列,，而 AlphaDev 的發(fā)布也同樣在業(yè)界引起了廣泛關(guān)注。
具體來(lái)說(shuō),，AlphaDev 是一種通過(guò)強(qiáng)化學(xué)習(xí)來(lái)發(fā)現(xiàn)增強(qiáng)的計(jì)算機(jī)科學(xué)算法的 AI 系統(tǒng),，它發(fā)現(xiàn)了一種更快的排序算法，直接超越了科學(xué)家和工程師們幾十年來(lái)的研究,，將排序算法的速度提高了 70%,！
DeepMind 計(jì)算機(jī)科學(xué)家 Daniel Mankowitz 更是表示：“我們估計(jì)，AlphaDev 發(fā)現(xiàn)的排序算法和哈希算法每天都會(huì)被調(diào)用數(shù)萬(wàn)億次,。”
強(qiáng)化學(xué)習(xí),，打破計(jì)算瓶頸
既然 AlphaDev 發(fā)現(xiàn)的是一種全新的排序算法，那我們便先從“排序”說(shuō)起,。
不論是將 3 個(gè)字母按字母順序排列,、將 5 個(gè)數(shù)字從大到小排列，亦或是將一個(gè)有上百萬(wàn)條記錄的數(shù)據(jù)庫(kù)進(jìn)行排列,，這都是排序,，是一種幾乎所有關(guān)鍵軟件的基礎(chǔ)算法。在 20 世紀(jì) 50 年代之前,，排序工作多數(shù)都依賴(lài)人工,，直至后來(lái)商業(yè)計(jì)算機(jī)興起，最早用于排序的計(jì)算機(jī)科學(xué)算法才開(kāi)始出現(xiàn)并發(fā)展,。
如今,，開(kāi)發(fā)者們所用的排序技術(shù)和算法，都是過(guò)去幾十年計(jì)算機(jī)科學(xué)家和程序員們積累下來(lái)的研究成果,。相較于幾十年前的手動(dòng)排序,，現(xiàn)在的算法確實(shí)已經(jīng)很高效，但也正因如此,，想要將其進(jìn)一步改進(jìn)無(wú)疑是一項(xiàng)重大挑戰(zhàn),，難度不亞于“找到一種新的節(jié)電方式”或“發(fā)現(xiàn)一種更有效的數(shù)學(xué)方法”。當(dāng)前,，GPT-4,、Bard等大模型的參數(shù)指數(shù)級(jí)增長(zhǎng),，對(duì)算力等資源的需求不斷增長(zhǎng)。而過(guò)去50年里,，人類(lèi)不斷依靠芯片的改進(jìn)以跟上步伐,。但隨著微芯片接近物理極限，改進(jìn)代碼讓計(jì)算更強(qiáng)大,、更持續(xù)變得至關(guān)重要,。尤其是，對(duì)每天運(yùn)行數(shù)萬(wàn)億次代碼的算法愈重要,。
因此,，DeepMind 在論文中提到：“人類(lèi)的直覺(jué)和專(zhuān)業(yè)知識(shí)對(duì)于改進(jìn)算法至關(guān)重要。然而,，許多算法已經(jīng)到了人類(lèi)專(zhuān)家無(wú)法進(jìn)一步優(yōu)化它們的階段,，導(dǎo)致計(jì)算瓶頸不斷擴(kuò)大。”
AlphaDev發(fā)現(xiàn)了一種更快的排序算法,，數(shù)十億人每天都在不知不覺(jué)中使用這些算法。它們是一切的基礎(chǔ),，從在線搜索結(jié)果,，社交帖子，到計(jì)算機(jī)和手機(jī)數(shù)據(jù)處理方式,。這些算法每天都要執(zhí)行數(shù)萬(wàn)億次,。利用AI生成更好的算法，將改變我們對(duì)計(jì)算機(jī)編程的方式,，并影響我們數(shù)字化社會(huì)的方方面面,。根據(jù)Nature論文中的數(shù)據(jù)，AlphaZero所創(chuàng)造的算法能比人類(lèi)的數(shù)據(jù)排序速度快三倍,。
今天,，Google DeepMind還開(kāi)源了在主C++庫(kù)中的最新排序算法，所有人皆可用,。
開(kāi)源地址：https://reviews.llvm.org/D118029
打破傳統(tǒng),，從匯編指令入手
為了幫助打破這一計(jì)算瓶頸，DeepMind 引入了 AlphaDev,， AlphaDev的創(chuàng)新意義在于,，它并不是通過(guò)改進(jìn)現(xiàn)有算法，而是完全從頭開(kāi)始發(fā)現(xiàn)了更快的算法,。而且,，它竟然著手于大多數(shù)人類(lèi)并沒(méi)有想到的地方——計(jì)算機(jī)匯編指令。匯編指令用于創(chuàng)建二進(jìn)制代碼,。雖然開(kāi)發(fā)者寫(xiě)代碼時(shí)用的是C++等高級(jí)語(yǔ)言,，但為了讓計(jì)算機(jī)理解,，這些高級(jí)語(yǔ)言必須翻譯成「低級(jí)」的匯編指令。
以此作為靈感,，DeepMind 認(rèn)為相較于在高層次的編碼語(yǔ)言中,，在匯編指令這個(gè)較低的層次上，應(yīng)該還存在許多改進(jìn)空間,，而這些改進(jìn)在更高級(jí)的編程語(yǔ)言中可能很難發(fā)現(xiàn),。因?yàn)橛?jì)算機(jī)的存儲(chǔ)和操作會(huì)更靈活，如果再多做一些潛在的改進(jìn),，對(duì)速度和能源使用也將產(chǎn)生更大影響,。
通過(guò)玩“游戲”來(lái)發(fā)現(xiàn)新算法
眾所周知，DeepMind的強(qiáng)化學(xué)習(xí)模型,，在圍棋,、國(guó)際象棋和將棋等游戲中，屢次擊敗世界冠軍,。而我們這次的主角——AlphaDev,，基于的正是AlphaZero。AlphaDev的工作方式與之前的AlphaZero相似,，后者結(jié)合了計(jì)算機(jī)推理和直覺(jué),，在棋盤(pán)游戲中選擇每一步的走法。只不過(guò),，AlphaDev并不會(huì)選擇下一步怎么走棋,，而是選擇添加哪些指令。
為了訓(xùn)練AlphaDev來(lái)發(fā)現(xiàn)新的算法,，DeepMind 讓 AlphaDev 開(kāi)始了一個(gè)單人“匯編游戲（Assembly Game）”,。
根據(jù)論文介紹，在這個(gè)游戲中,，玩家需要選擇一系列低級(jí)匯編指令,，以此產(chǎn)生一種新的高效排序算法：“這個(gè)游戲很有挑戰(zhàn)性，因?yàn)橥婕倚枰紤]匯編指令的組合空間,，以產(chǎn)生一種既可證明正確又快速的算法,。難度不僅來(lái)自搜索空間的大小，可能的組合數(shù)量類(lèi)似于國(guó)際象棋和圍棋,，而且其中一條不正確的指令都可能會(huì)使整個(gè)算法無(wú)效,。”
在游戲過(guò)程中，AlphaDev 每玩一次 AssemblyGame,，都會(huì)從頭開(kāi)始構(gòu)建一個(gè)匯編程序,，從一組初始無(wú)序的指令開(kāi)始構(gòu)建，從而定義一種新的高效算法,。
隨著游戲的進(jìn)行,，算法不斷建立,，而 AlphaDev 會(huì)通過(guò)比較算法的輸出和預(yù)期的結(jié)果來(lái)檢查它是否正確。對(duì)于排序算法,，AlphaDev 的檢驗(yàn)方式是：輸入無(wú)序的數(shù)字后,，可否輸出正確排序的數(shù)字。
DeepMind 將游戲的輸贏作為 AlphaDev 的激勵(lì)方式,，而該游戲的輸贏也很好判定：
? 使用匯編指令,，生成正確的低延遲算法，AlphaDev 即贏得游戲,。
? 生成不正確的算法或正確但低效的算法,，AlphaDev 即輸?shù)粲螒颉?/p>
新排序算法，速度提升 70%,！
于是,，在這樣的“游戲”過(guò)程中，AlphaDev 發(fā)現(xiàn)了更快的排序算法,，主要是圍繞 3-5 個(gè)元素的較短序列的排序算法,。
DeepMind 解釋道：“因?yàn)檫@些算法是使用最廣泛的算法之一，它們經(jīng)常作為較大排序函數(shù)的一部分被多次調(diào)用,，改進(jìn)這些算法可以加快對(duì)任意數(shù)量項(xiàng)目進(jìn)行排序的整體速度,。”
因而，AlphaDev 發(fā)現(xiàn)的這個(gè)新排序算法,，對(duì)于較短的序列來(lái)說(shuō)，速度可提升 70%,，對(duì)于超過(guò) 25 萬(wàn)個(gè)元素的序列來(lái)說(shuō),，速度也能提高約 1.7%。
為了讓更多人用到這個(gè)新排序算法,，DeepMind 對(duì)算法進(jìn)行了逆向工程,，并以此改進(jìn)了 LLVM libc++ 標(biāo)準(zhǔn)排序庫(kù)，可供全球數(shù)百萬(wàn)開(kāi)發(fā)者和公司使用,。DeepMind 計(jì)算機(jī)科學(xué)家 Daniel Mankowitz 激動(dòng)表示：“這些算法目前位于 C++ 標(biāo)準(zhǔn)排序庫(kù)中,，這是十多年來(lái)對(duì)這些子例程的首次更改！”
新哈希函數(shù),，速度提升 30%,！
除了新排序算法，通過(guò)研究 AlphaDev 的發(fā)現(xiàn)過(guò)程,，它實(shí)際上還創(chuàng)造了一種新方法：其排序算法包含新的指令序列,，每次應(yīng)用時(shí)都會(huì)跳過(guò)一條指令——對(duì)于每天都會(huì)被使用上萬(wàn)億次的排序算法來(lái)說(shuō)，這無(wú)疑將產(chǎn)生巨大影響,。
DeepMind 研究人員將此稱(chēng)作 “AlphaDev 交換和復(fù)制動(dòng)作（AlphaDev swap and copy moves）：通過(guò)交換和復(fù)制移動(dòng),，AlphaDev 跳過(guò)了一個(gè)步驟,，以一種看似錯(cuò)誤實(shí)際上很快捷的方式連接項(xiàng)目。“這顯示了 AlphaDev 發(fā)現(xiàn)原始解決方案的能力,，并挑戰(zhàn)了人類(lèi)改進(jìn)計(jì)算機(jī)科學(xué)算法的思考方式,。”
如下圖示例原始sort3實(shí)現(xiàn)，有min(A, B, C),，使用AlphaDev Swap Move,，AlphaDev發(fā)現(xiàn)，你只需要min(A, B),。
再比如,，原始實(shí)現(xiàn)用max(B, min(A ,C, D))中較大的排序算法對(duì)8個(gè)元素進(jìn)行排序。AlphaDev發(fā)現(xiàn)使用其「swap and copy moves」時(shí)只需要max(B, min(A, C)),。
不僅如此,，在發(fā)現(xiàn)了新排序算法后，DeepMind 還測(cè)試了 AlphaDev 是否可以改進(jìn)數(shù)據(jù)結(jié)構(gòu)中常用的哈希算法,，結(jié)果 AlphaDev 不負(fù)眾望,，確實(shí)也發(fā)現(xiàn)了一種新的哈希算法，將其應(yīng)用于 9-16 字節(jié)范圍內(nèi)的哈希函數(shù)時(shí),，速度可提高 30%,。而這個(gè)新哈希算法，也會(huì)在今年被發(fā)布到開(kāi)源的 Abseil 庫(kù)中,，供全球數(shù)百萬(wàn)開(kāi)發(fā)者使用,。
用 AI 來(lái)優(yōu)化代碼的未來(lái)
通過(guò)以上新發(fā)現(xiàn)的排序算法和哈希算法，AlphaDev 已展示出了其概括和發(fā)現(xiàn)新算法的能力,，即用 AI 來(lái)優(yōu)化世界上的代碼,，并朝著開(kāi)發(fā)通用 AI 工具邁出了重要一步。Google DeepMind認(rèn)為,，AlphaDev是朝著開(kāi)發(fā)AGI工具邁出的一步,，這些工具有助于優(yōu)化整個(gè)計(jì)算生態(tài)系統(tǒng)，還能解決其他有益于社會(huì)的問(wèn)題,。
不過(guò),，研究人員也承認(rèn)，目前AlphaDev在低級(jí)匯編指令優(yōu)化能力非常強(qiáng),，但是隨著算法的發(fā)展也存在局限性,。為了讓開(kāi)發(fā)者更可用，AlphaDev用高級(jí)語(yǔ)言（如C++）優(yōu)化算法的能力正在探索中,。AlphaDev的新發(fā)現(xiàn),，如「AlphaDev swap move」和「AlphaDev copy move」，不僅表明它可以改進(jìn)算法，還可以找到新的解決方案,。研究人員希望,，這些發(fā)現(xiàn)能激勵(lì)研究人員和開(kāi)發(fā)人員創(chuàng)造技術(shù)和方法，進(jìn)一步優(yōu)化基礎(chǔ)算法,，以創(chuàng)建一個(gè)更強(qiáng)大,、更可持續(xù)的計(jì)算生態(tài)系統(tǒng)。
參考鏈接：
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
2519
2023-06-13 10:00:36
