接觸過基礎計(ji)算機科學(xue)課(ke)程的(de)(de)朋(peng)友們，肯定都曾親自(zi)動手設計(ji)排序(xu)算法——也(ye)就是(shi)借助代碼(ma)將無序(xu)列表中的(de)(de)各個條目按升序(xu)或降序(xu)方式重新排列。這是(shi)個有趣的(de)(de)挑戰，可行(xing)的(de)(de)操(cao)作方法也(ye)多(duo)種多(duo)樣。人(ren)們曾投入大量時間探索(suo)如何更高效(xiao)地完成排序(xu)任務(wu)。
作為(wei)一項基(ji)礎操作，大多數編程語言的(de)標(biao)準庫(ku)中都內置有(you)排序(xu)算法。世界各地的(de)代(dai)(dai)碼(ma)庫(ku)中使(shi)用了(le)許(xu)多不同的(de)排序(xu)技術(shu)和(he)算法來(lai)在線組織大量數據，但至少就與 LLVM 編譯器(qi)配套(tao)使(shi)用的(de) C++庫(ku)而言，排序(xu)代(dai)(dai)碼(ma)已經有(you)十多年沒有(you)任(ren)何(he)變化了(le)。
近日，谷(gu)歌(ge) DeepMind AI 小(xiao)組如(ru)今開(kai)發(fa)出(chu)(chu)一種強化(hua)學(xue)(xue)習(xi)工具 AlphaDev，能(neng)夠在無需通(tong)過(guo)人(ren)類代碼示例做(zuo)預訓練的情況下(xia)，開(kai)發(fa)出(chu)(chu)極限優化(hua)的算(suan)法(fa)。如(ru)今，這些算(suan)法(fa)已經集成到 LLVM 標準 C++ 排(pai)序庫中，這是(shi)十多年來排(pai)序庫部分第一次發(fa)生變化(hua)，也是(shi)第一次將通(tong)過(guo)強化(hua)學(xue)(xue)習(xi)設計的算(suan)法(fa)添加到該庫中。
把編程過程視為“游戲”
由于不必(bi)預先接觸(chu)任何人(ren)類游(you)戲策(ce)略，DeepMind 系統往(wang)往(wang)能(neng)發現人(ren)類從未(wei)設想過的攻關思路。當然，由于完全依(yi)靠自我對抗來(lai)學(xue)習經驗，DeepMind 在(zai)某些情況(kuang)下也會(hui)形成可被人(ren)類利用(yong)的盲點。
這種(zhong)方(fang)法跟編(bian)程(cheng)其實(shi)非常相似。大(da)語言模(mo)型之所以能夠編(bian)寫出(chu)有效代(dai)碼(ma)(ma)，就是因為(wei)它們(men)看到過大(da)量人類(lei)(lei)代(dai)碼(ma)(ma)示例(li)。但也正(zheng)因為(wei)如此，語言模(mo)型很難產出(chu)人類(lei)(lei)之前(qian)沒做過的東西。如果我(wo)們(men)希望(wang)對普遍存在的現有算法(例(li)如排序函(han)數(shu))做進一步優化，那么繼續依賴現有人類(lei)(lei)代(dai)碼(ma)(ma)將(jiang)很難突(tu)破固有思路的束縛(fu)。那么，如何才能讓 AI 找到真(zhen)正(zheng)的新(xin)方(fang)向?
DeepMind 的研究人員采用了(le)與國(guo)際象棋和圍棋相(xiang)同(tong)的方法(fa)：把代(dai)碼(ma)優化(hua)任務(wu)轉化(hua)成單(dan)人“組裝游戲”。AlphaDev 系統開(kai)發(fa)出一種 x86 匯編算(suan)法(fa)，會將(jiang)代(dai)碼(ma)的運行延遲視(shi)為(wei)一個分數(shu)，在努(nu)力將(jiang)該分數(shu)最小化(hua)的同(tong)時確(que)保代(dai)碼(ma)能(neng)夠(gou)順暢跑通(tong)。通(tong)過強化(hua)學(xue)習，AlphaDev 逐漸具(ju)備了(le)編寫緊(jin)湊、高效代(dai)碼(ma)的能(neng)力。
AlphaDev 基于AlphaZero。DeepMind 向來以(yi)開發(fa)能(neng)自(zi)學(xue)游(you)戲規則的 AI 軟(ruan)件(jian)(jian)而聞(wen)名(ming)。這種思路(lu)被證明(ming)效果拔群，也(ye)先后攻克(ke)了國際(ji)象(xiang)棋(qi)、圍棋(qi)和《星際(ji)爭霸》等(deng)諸多游(you)戲難(nan)題。雖然具(ju)體細節因所玩(wan)(wan)游(you)戲而異，但 DeepMind 軟(ruan)件(jian)(jian)確實能(neng)在重復游(you)玩(wan)(wan)中不斷學(xue)習，持續探索能(neng)令得分最大化(hua)的辦法(fa)。
AlphaDev 的兩個核(he)心組件是學習(xi)算法和表示函數。
AlphaDev 學習(xi)算(suan)(suan)法(fa)可(ke)以結合 DRL 和隨機搜索(suo)優化(hua)算(suan)(suan)法(fa)來(lai)玩組(zu)裝游(you)戲。AlphaDev 中的主要學習(xi)算(suan)(suan)法(fa)是 AlphaZero 33的擴展，AlphaZero 33 是一種著名的 DRL 算(suan)(suan)法(fa)，其中訓練(lian)神經(jing)網絡以指導搜索(suo)完成游(you)戲。
表(biao)示(shi)函數(shu)，負(fu)責跟蹤代碼(ma)開發時的(de)(de)(de)(de)整體性能，其中(zhong)包(bao)括算法(fa)的(de)(de)(de)(de)常(chang)規(gui)結(jie)構以及對 x86 寄(ji)存(cun)器和內存(cun)的(de)(de)(de)(de)使(shi)用。該(gai)系統會單獨添加匯編(bian)指令(ling)(ling)，通過蒙特(te)卡洛樹搜(sou)索(同樣是(shi)一(yi)種從游戲系統中(zhong)借用的(de)(de)(de)(de)方(fang)法(fa))進行(xing)選(xuan)擇。樹狀結(jie)構允許(xu)系統快速(su)將搜(sou)索范圍縮小(xiao)至(zhi)包(bao)含大量潛在指令(ling)(ling)的(de)(de)(de)(de)有(you)限區(qu)域，而蒙特(te)卡洛方(fang)法(fa)則以一(yi)定(ding)程(cheng)度的(de)(de)(de)(de)隨機性從這個分支區(qu)域內選(xuan)擇具(ju)體指令(ling)(ling)。(請(qing)注意(yi)，這里所說的(de)(de)(de)(de)“指令(ling)(ling)”是(shi)為創建有(you)效、完整程(cheng)序集(ji)而選(xuan)擇特(te)定(ding)寄(ji)存(cun)器等操作。)
之后，系統會(hui)評估匯編代碼(ma)的(de)(de)延遲(chi)和有效性(xing)狀(zhuang)態(tai)，為其打分(fen)(fen)并與前一(yi)次得分(fen)(fen)進行(xing)比(bi)較。而通過強(qiang)化(hua)學習，系統會(hui)在給定的(de)(de)程序狀(zhuang)態(tai)之下(xia)保留樹結(jie)構(gou)中不同分(fen)(fen)支的(de)(de)工作(zuo)信息。隨著時間推移，系統將逐漸(jian)“學會(hui)”如何以(yi)最高得分(fen)(fen)(代表最低延遲(chi))獲得游戲勝利(li)(成(cheng)功完成(cheng)排序)。 AlphaDev 的(de)(de)主要表示(shi)函數基(ji)于(yu) Transformer。
為了訓練 AlphaDev 發現(xian)新算法(fa)(fa)，AlphaDev 在每(mei)輪(lun)中(zhong)都會觀(guan)察它(ta)生(sheng)成的(de)算法(fa)(fa)和中(zhong)央處理器 (CPU) 中(zhong)包含的(de)信息，然后通過選擇要(yao)添加(jia)到(dao)算法(fa)(fa)中(zhong)的(de)指令(ling)完(wan)成游戲(xi)。AlphaDev 必(bi)須有效地(di)搜索大(da)量可(ke)(ke)能的(de)指令(ling)組合，以(yi)找到(dao)可(ke)(ke)以(yi)排序的(de)算法(fa)(fa)，并且(qie)還(huan)要(yao)比(bi)當前最好的(de)算法(fa)(fa)更快(kuai)，同時代理模型可(ke)(ke)以(yi)根據算法(fa)(fa)的(de)正(zheng)確性和延遲(chi)獲得獎勵。
圖 A：組裝游戲，圖 B：獎勵計算
最(zui)終，AlphaDev 發(fa)現了新的(de)排序(xu)算法，這些算法可以讓 LLVM libc++ 排序(xu)庫得(de)到改進：對于(yu)較短的(de)序(xu)列，排序(xu)庫的(de)速(su)度提(ti)高了 70%;對于(yu)超過 250,000 個元素的(de)序(xu)列，速(su)度提(ti)高了約 1.7%。
具體而言，該(gai)算法的創(chuang)新主要在于兩種指(zhi)令序(xu)列：AlphaDev Swap Move(交(jiao)換(huan)移動)和 AlphaDev Copy Move(復制(zhi)移動)，通過(guo)(guo)這兩個指(zhi)令，AlphaDev 跳(tiao)過(guo)(guo)了一個步驟，以(yi)一種看似錯誤(wu)但(dan)實際上是(shi)捷徑(jing)的方式連接(jie)項(xiang)目(mu)。
左(zuo)圖：帶有 min(A,B,C) 的(de)原始 sort3 實現。
?右圖： AlphaDev Swap Move - AlphaDev 發現你(ni)只需要 min(A,B)。
左：max (B, min (A, C))的(de)原(yuan)始實現(xian)用于對八個(ge)元素進行排(pai)序的(de)更大排(pai)序算法。
?右： AlphaDev 發現在使(shi)用其復制(zhi)移動時只需(xu)要 max (B, min (A, C))。
這套(tao)系(xi)統的主(zhu)要優勢在(zai)于(yu)，其訓練過程不借助任何代(dai)碼(ma)示例。相(xiang)反，系(xi)統會自主(zhu)生成代(dai)碼(ma)示例，然后對其做出評(ping)估(gu)。過程當中，它(ta)也就逐漸掌握了關于(yu)有效排序(xu)的指令組(zu)合信息。
從排序到散列
在發現更快(kuai)的(de)排序算(suan)法(fa)后，DeepMind 測試了 AlphaDev 是否可以概括和(he)改進不同的(de)計(ji)算(suan)機科學算(suan)法(fa)：散列。
哈希(xi)是(shi)(shi)計(ji)算(suan)(suan)中用(yong)于檢(jian)索(suo)、存儲和壓縮數據的基本算(suan)(suan)法。就像使用(yong)分類系(xi)統來(lai)定位某本書(shu)(shu)的圖書(shu)(shu)管理員一(yi)(yi)樣(yang)，散(san)列算(suan)(suan)法可以(yi)(yi)幫助用(yong)戶知(zhi)道他(ta)們正在尋找什么以(yi)(yi)及在哪(na)里(li)可以(yi)(yi)找到它。這(zhe)些算(suan)(suan)法獲取特定密鑰的數據(例(li)如用(yong)戶名(ming)“Jane Doe”)并對(dui)其(qi)進行哈希(xi)處理——這(zhe)是(shi)(shi)一(yi)(yi)個將原(yuan)始(shi)數據轉換(huan)為唯一(yi)(yi)字符串(例(li)如 1234ghfty)的過程。計(ji)算(suan)(suan)機使用(yong)此散(san)列來(lai)快速檢(jian)索(suo)與密鑰相(xiang)關的數據，而不是(shi)(shi)搜索(suo)所(suo)有數據。
DeepMind 將 AlphaDev 應(ying)用于數據結構中最常用的(de)散列算法(fa)之(zhi)一，以嘗試發(fa)現(xian)更快的(de)算法(fa)。當(dang)將其應(ying)用于散列函數的(de) 9-16 字節范(fan)圍時，AlphaDev 發(fa)現(xian)的(de)算法(fa)速(su)度提(ti)高了 30%。
今(jin)年，AlphaDev 的新哈希算法被發布到(dao)開源Abseil 庫中，可(ke)供(gong)全(quan)球數百(bai)萬開發人員(yuan)使用，該(gai)庫現在每(mei)天被數萬億次使用。
實際可用的代碼
復雜程(cheng)序(xu)中的(de)排(pai)(pai)序(xu)機制能夠(gou)處(chu)理大量任(ren)意條目(mu)的(de)集合。但在標準庫層面來看，這種能力源自一系(xi)列高度限定的(de)具(ju)體函數。這些函數各自只能處(chu)理一種或(huo)(huo)幾(ji)種情況。例如，某些單獨算法只能對(dui) 3、4 或(huo)(huo) 5 個條目(mu)做排(pai)(pai)序(xu)。我(wo)們(men)也可以同(tong)時(shi)使用(yong)一組函數對(dui)任(ren)意數量的(de)條目(mu)作排(pai)(pai)序(xu)，但原則上每一次函數調(diao)用(yong)最(zui)多只能對(dui) 4 個條目(mu)做排(pai)(pai)序(xu)。
DeepMind 在每(mei)個函數(shu)上都設置了 AlphaDev，其實際運行方式(shi)有著很(hen)大區別。對于負責處理特定(ding)數(shu)量(liang)(liang)條目的函數(shu)，可以編寫出不含任何分支的代(dai)碼(ma)，即(ji)根據變量(liang)(liang)狀態執行不同的代(dai)碼(ma)。因此代(dai)碼(ma)性能往往與(yu)所涉及的指令數(shu)量(liang)(liang)成反比。
AlphaDev 已經成功將 sort-3、sort-5 和 sort-8 的(de)指令數量(liang)各減一，在 sort-6 和 sort-7 中的(de)指令削減量(liang)甚至更多(duo)。只有(you) sort-4 上沒能(neng)找到改進現有(you)代碼的(de)方(fang)法。而在實際系統(tong)上的(de)重(zhong)復運行測試證(zheng)明，更少的(de)指令確實帶(dai)來(lai)了更好的(de)性能(neng)。
至于對可變數量(liang)條目進行排序(xu)，則(ze)要求代碼中包含分(fen)支，而不(bu)同處(chu)(chu)理器專(zhuan)用于處(chu)(chu)理這些(xie)分(fen)支的元件(jian)數量(liang)也有區別。
對于這類(lei)情況，研究人員(yuan)在(zai) 100 臺不同(tong)的(de)計算設備(bei)上對代碼性能(neng)做出了(le)評估。AlphaDev 在(zai)這類(lei)場景下(xia)同(tong)樣找到(dao)了(le)進(jin)一(yi)步(bu)榨取性能(neng)的(de)方法(fa)，下(xia)面我們以一(yi)次最多(duo)排(pai)序 4 個條目(mu)的(de)函數為(wei)例，看(kan)(kan)看(kan)(kan)它到(dao)底是怎么(me)操作的(de)。
在(zai) C++庫的現(xian)有實現(xian)中，代碼需要(yao)進行一(yi)系列(lie)測試來確認具體(ti)需要(yao)對多(duo)少(shao)個條目做排序，再根據(ju)條目數量調用相應的排序函數。
而(er) AlphaDev 修改后的代(dai)(dai)碼(ma)則(ze)采取(qu)更(geng)加“神奇(qi)”的思路：它先(xian)測試是不是 2 個(ge)(ge)(ge)條(tiao)目(mu)，如果(guo)(guo)是則(ze)調用相(xiang)應函數(shu)(shu)立即做排序(xu)。如果(guo)(guo)數(shu)(shu)量大于(yu) 2 個(ge)(ge)(ge)，則(ze)代(dai)(dai)碼(ma)會(hui)先(xian)對前(qian) 3 個(ge)(ge)(ge)條(tiao)目(mu)做排序(xu)。這樣如果(guo)(guo)確(que)實只有(you) 3 個(ge)(ge)(ge)條(tiao)目(mu)，則(ze)返(fan)回排序(xu)結(jie)果(guo)(guo)。 由于(yu)實際是有(you) 4 個(ge)(ge)(ge)條(tiao)目(mu)要做排序(xu)，所(suo)以 AlphaDev 會(hui)運行專門代(dai)(dai)碼(ma)，以非(fei)常高效的方(fang)式(shi)將(jiang)第 4 個(ge)(ge)(ge)條(tiao)目(mu)插入(ru)到前(qian) 3 個(ge)(ge)(ge)已經排序(xu)完(wan)成(cheng)的條(tiao)目(mu)中的適(shi)當位置。
這種辦法(fa)聽(ting)起來有(you)點怪(guai)異，但事實(shi)證明其性(xing)能確實(shi)始(shi)終優于現有(you)代(dai)碼。
由于 AlphaDev 確(que)實生成了更高效的代碼(ma)，所(suo)以(yi)研(yan)究團隊打算把(ba)這些成果重(zhong)新合并(bing)到 LLVM 標(biao)準 C++庫中。但問(wen)題是(shi)這些代碼(ma)為匯(hui)編(bian)格式，而(er)非 C++。所(suo)以(yi)他們必須通過逆向計算找到能夠生成相(xiang)同程序集的 C++代碼(ma)。
現如(ru)今，代碼(ma)成果已經被(bei)(bei)合并至 LLVM 工(gong)具(ju)鏈(lian)內，成為十多(duo)年來這部分代碼(ma)的(de)首次(ci)更新。 研究人(ren)員(yuan)估計，AlphaDev 生(sheng)成的(de)新代碼(ma)正(zheng)每天被(bei)(bei)執(zhi)行數萬(wan)億(yi)次(ci)。
結束語
“太棒了!將(jiang)我們(men)程序員很早就學會的這種基本排序任務的速(su)度提高了 70%。看到 AI 在我們(men)都依賴的算法和庫中提供(gong)重大(da)加(jia)速(su)，真是令人興奮。”有開(kai)發(fa)者對谷歌 DeepMind 的成果(guo)表示(shi)振奮。
但(dan)也(ye)有開發者(zhe)并(bing)不買賬：“相當(dang)令人(ren)失(shi)望……1.7% 的(de)改善?5 個元(yuan)素的(de)序列 70%?可能是(shi)最(zui)不受歡迎(ying)、最(zui)不切(qie)實際的(de)應用研(yan)究(jiu)……”也(ye)有開發者(zhe)表(biao)示：“說發現了新算法(fa)是(shi)不是(shi)有點誤(wu)導人(ren)?似乎更(geng)像是(shi)算法(fa)優化。無論(lun)如何(he)這仍然(ran)很酷(ku)。”
參考鏈接(jie)：
//arstechnica.com/science/2023/06/googles-deepmind-develops-a-system-that-writes-efficient-algorithms/
//www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
本文轉載來源：
//www.infoq.cn/news/IF32PWjiACV0aPxQGD70
