6月8日，DeepMind 在著名學(xué)術(shù)刊物 Nature 上，發(fā)表了其最新研究成果：一個(gè)名為 AlphaDev 的 AI 系統(tǒng)。AlphaDev不僅可以將排序算法提速70％，甚至在有的算法上，能比人類快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)商業(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年里，人類不斷依靠芯片的改進(jìn)以跟上步伐。但隨著微芯片接近物理極限，改進(jìn)代碼讓計(jì)算更強(qiáng)大、更持續(xù)變得至關(guān)重要。尤其是，對(duì)每天運(yùn)行數(shù)萬(wàn)億次代碼的算法愈重要。
因此，DeepMind 在論文中提到：“人類的直覺(jué)和專業(yè)知識(shí)對(duì)于改進(jìn)算法至關(guān)重要。然而，許多算法已經(jīng)到了人類專家無(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)造的算法能比人類的數(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ù)人類并沒(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ù)量類似于國(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 研究人員將此稱作 “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)了人類改進(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
評(píng)論 0