久久久精品2019中文字幕神马_欧美亚洲一区三区_欧美大人香蕉在线_精品88久久久久88久久久_中文字幕一区二区三区在线播放 _精品国产一区二区三区久久影院_欧洲av在线精品_粉嫩av一区二区三区_亚洲欧美一区二区三区极速播放_国产亚洲精品久久

AlphaDev 將 CPU 匯編指令層面的算法優(yōu)化過程轉(zhuǎn)化為一個單玩家的游戲。

游戲每一步的狀態(tài)定義為 : St = 。

其中， Pt表示游戲到至今為止所生成的算法，Zt則表示在給定輸入的前提下執(zhí)行完 Pt里的指令之后，內(nèi)存和寄存器的狀態(tài)。

如上圖所示，在時間步 t，AlphaDev 接受到當前狀態(tài) St和 所要執(zhí)行的動作 at（比如 mov），也就是往當前生成的算法 Pt中添加的合法匯編指令。

在添加完指令之后，就是計算獎勵分數(shù) rt（包括評估算法的正確性和延遲）。

正確性評估就是將 N組測試序列輸入到算法 Pt中，得到N組輸出，和正確的排序結(jié)果最比較來計算獎勵分數(shù)。

論文中給出了3種正確性評估函數(shù)，首先定義 P為輸入序列長度， PCt為在時間步 t序列中，位置正確的值的個數(shù)，這里我理解應該是和正確的排序結(jié)果逐個位置對比，統(tǒng)計相等的個數(shù)。

三個函數(shù)分別定義如下：

論文中提到采用第三個函數(shù)效果最好。

延遲分數(shù)的計算可以是：

整個強化學習的游戲在執(zhí)行有限步驟之后就會被終止。只有生成正確而又低延遲的匯編代碼才算贏得游戲。而不管是生成了錯誤的代碼還是正確但低效的實現(xiàn)都視為游戲輸了。

AlphaDev 采用的強化學習算法是對 AlphqaZero 算法的擴展，也是采用深度神經(jīng)網(wǎng)絡來引導蒙特卡洛樹搜索（MCTS）的規(guī)劃過程。網(wǎng)絡模型的輸入是 St，輸出是對動作策略和獎勵的預測。

整個游戲過程簡單來說就是，用一個固定參數(shù)的網(wǎng)絡模型，通過給定的當前狀態(tài)執(zhí)行一個蒙特卡洛樹搜索過程，然后采取下一步動作。然后可以用生成的游戲過程（包含每一步的狀態(tài)和獎勵）去訓練和更新網(wǎng)絡的參數(shù)。

模型包含兩部分：

兩個網(wǎng)絡的輸出 embedding 會合并在一起來表示當前的狀態(tài)。

網(wǎng)絡模型整體的結(jié)構(gòu)如下：

Transformer 編碼器模塊具體圖示

如上圖所示，把當前生成的匯編代碼序列的每一條指令的操作碼和操作數(shù)都轉(zhuǎn)換為 one-hot 編碼序列，然后輸入到網(wǎng)絡中。

但是具體的 one-hot 編碼規(guī)則、詞表怎么設置、還有對于 CPU 狀態(tài)編碼網(wǎng)絡寄存器和內(nèi)存的狀態(tài)是怎么表示為網(wǎng)絡的輸入的等等，這些細節(jié)我在論文里沒找到。

然后兩個網(wǎng)絡的輸出 embedding 會合并到一起接著輸入到幾個函數(shù)頭里計算，分別是預測下一步策略的函數(shù)頭，預測算法正確性的函數(shù)頭和預測算法真實延遲的函數(shù)頭。

網(wǎng)絡參數(shù)超參設置

論文的補充資料中提供了網(wǎng)絡的參數(shù)和三個函數(shù)頭的具體配置。

而對于策略的預測，論文中提到為了簡化問題和提高收斂性，而對動作空間做了一些限制，規(guī)則如下：

訓練細節(jié)

AlphaDev 的訓練采用了 TPU v3，每個 TPU 核的 batch size 是 1024 ，總共用了 16 個 TPU 核，總共訓練了 100 萬次迭代。而在對于玩游戲積累訓練數(shù)據(jù)來說，則是在 TPU v4 上進行，總共用了 512 個 TPU 核。

實驗結(jié)果表明，最多只需2天模型就能訓收斂。

從實驗結(jié)果表格可以看到，對于短序列排序算法 AlphaDev 生成的代碼長度更短，而且平均耗時也更低。

對生成算法延遲的評估方式，比如對于 sort3則是在 100 臺機器上做評估，每臺機器隨機生成 1000 條 3個數(shù)的序列，然后每條序列輸入到算法中，對這 1000 次評估取第5百分位數(shù)作為最終的評估結(jié)果（排除 cache miss 和 任務搶占 等因素）。

耗時采用的是 CPU_CLK_UNHALTED.CORE這個計數(shù)器結(jié)果， 其計數(shù)值表示在一個特定時間段內(nèi)，處理器內(nèi)核的時鐘周期數(shù)。這個值越高，意味著處理器內(nèi)核在該時間段內(nèi)執(zhí)行了更多的指令。

對于定長序列排序，當應用到排序網(wǎng)絡算法[6]（sorting network algorithm）的時候 AlphaDev 生成的代碼中包含了一些有趣指令序列，相對于原始指令序列可以減少一條匯編指令，論文中稱之為：

啥是排序網(wǎng)絡算法？

排序網(wǎng)絡算法（Sorting Network Algorithm）是一種能夠?qū)σ唤M輸入數(shù)據(jù)進行排序的并行算法，其具有較好的并行性能適用于多處理器或多核心系統(tǒng)。

該算法的特點是，它將所有的比較和交換操作預先規(guī)劃好形成一個固定的結(jié)構(gòu)，然后將輸入數(shù)據(jù)按照這個結(jié)構(gòu)進行排序。

排序網(wǎng)絡由比較器（comparator）和線（wire）組成，如下圖所示：

水平線表示 wire，每條水平線持有一個待排序的值。兩條 wire 之間的垂直線段就表示一個比較器，比較器對比兩條水平線的值，如果比較器下方的值小于上方的值則交換兩條橫線的值，否則則不交換。

一個優(yōu)化過的排序網(wǎng)絡可以以最少的比較器，并將這些比較器放置在特定位置上，來實現(xiàn)對任意序列進行排序。

下圖是對一個構(gòu)造好的排序網(wǎng)絡，輸入真實待排序序列的例子：

可見初始輸入是 [2, 3, 1, 4]，這些隨機數(shù)從左到右按順序經(jīng)過這些比較器之后，就得到了排序好的序列 [1, 2, 3, 4]。

AlphaDev swap move

先來看這個排序網(wǎng)絡，只看紅圈部分的功能就是對給定的輸入 [A, B, C]將其轉(zhuǎn)換為 [min(A,B,C), max(min(A,C),B), max(A,C)]。

然后經(jīng)過 AlphaDev 優(yōu)化之后，可以將第一個輸出的 min(A,B,C)改為只計算 min(A,B)，原因是因為前面的 B和 C橫線之間經(jīng)過比較器之后已經(jīng)有了前置條件 B <= C。

而通過這個優(yōu)化就能省去一條匯編指令，下圖是紅圈部分的偽代碼實現(xiàn)：

左邊是原始偽代碼實現(xiàn)，右邊是經(jīng)過 AlphaDev 優(yōu)化之后的實現(xiàn)，可以看到少了一條匯編指令 mov S P。

AlphaDev copy move

接下來看對4個元素進行排序的排序網(wǎng)絡，是在對 sort8這個算法優(yōu)化過程中發(fā)現(xiàn)的。該排序網(wǎng)絡對于輸入序列 [A, B, C, D]轉(zhuǎn)換為 [min(A, B, C, D), max(B, min(A, C, D), max(C, min(A, D)), max(A, D) ]。

該排序網(wǎng)絡是 sort8的一個子排序網(wǎng)絡，而根據(jù)比較器的放置位置來看，A和 D比較之后后續(xù)就不再和其他元素比較了，所以D出來的結(jié)果就是四個元素中最大的，所以隱含了一個條件就是 D >= min(A, C)。

因此對第二個輸出元素的計算可以從 max(B, min(A, C, D))改為 max(B, min(A, C))，就可以節(jié)省一條匯編指令。

偽代碼如下:

左邊是原始偽代碼實現(xiàn)，右邊是經(jīng)過 AlphaDev 優(yōu)化之后的實現(xiàn)，可以看到少了一條匯編指令 mov P T。

這篇文章只是對 AlphaDev 論文中的主要內(nèi)容作解讀，對于更多的內(nèi)容和細節(jié)感興趣的讀者可以查閱原論文和論文的補充資料 [2,3]，DeepMind 也也開源了一份偽代碼實現(xiàn) [7]。