国产美女主播视频一区_国产精品蜜臀在线观看_亚洲成人动漫一区_亚洲视屏在线播放

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

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

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

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

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

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

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

三個函數分別定義如下：

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

延遲分數的計算可以是：

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

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

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

模型包含兩部分：

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

網絡模型整體的結構如下：

Transformer 編碼器模塊具體圖示

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

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

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

網絡參數超參設置

論文的補充資料中提供了網絡的參數和三個函數頭的具體配置。

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

訓練細節(jié)

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

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

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

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

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

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

啥是排序網絡算法？

排序網絡算法（Sorting Network Algorithm）是一種能夠對一組輸入數據進行排序的并行算法，其具有較好的并行性能適用于多處理器或多核心系統。

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

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

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

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

下圖是對一個構造好的排序網絡，輸入真實待排序序列的例子：

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

AlphaDev swap move

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

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

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

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

AlphaDev copy move

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

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

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

偽代碼如下:

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

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