JeffDean又用深度學習搞事情：這次要顛覆整個計算機系統結構設計

本文由 「AI前線」原創，原文鏈接：JeffDean又用深度學習搞事情：這次要顛覆整個計算機系統結構設計

策劃編輯 | Natalie

作者 | Milad Hashemi 等

編譯 | Rays

編輯 | Emily

AI 前線導讀：上個月，Jeff Dean、Michael I.Jordan、李飛飛、LeCun 等大牛發起的系統機器學習會議 SysML 2018 在斯坦福閉幕。這是一個專門針對系統和機器學習交叉研究領域的會議，目的是彌補當前關於 AI/ML 的討論大多偏向演算法和應用而關於底層的基礎設施卻少有討論造成的缺口。

在會議主題演講中，Jeff Dean提到了去年穀歌發布的研究論文《用 ML 模型替代資料庫索引結構》（The Case for Learned Index Structures，去年在技術圈引起轟動，詳見 AI 前線首發報道），其關鍵點就是用計算換內存。未來基於摩爾定律的 CPU 在本質上將不復存在，利用神經網路取代分支重索引結構，資料庫就可以從硬體發展趨勢中受益。Jeff Dean 認為，這代表了一個非常有前景且十分有趣的方向：傳統系統開發中，使用 ML 的視角，就能發現很多新的應用。除了資料庫，ML 還能使用在系統的哪些方面？Jeff Dean 表示，一個很大的機會是啟發式方法，計算機系統里大量應用啟發式方法，因此，ML 在用到啟發式方法的地方都有機會帶來改變。

今天 AI 前線為大家帶來的是《用 ML 模型替代資料庫索引結構》研究的續篇，這一次谷歌研究人員嘗試用深度學習解決馮·諾依曼結構內存性能瓶頸，並取得了一定成果。Jeff Dean 在推特評論表示，未來在計算機系統的眾多領域，類似研究工作將不斷增多。

該論文是將神經網路應用於計算機結構設計中的一項開創性工作。如何將機器學習應用於計算機硬體結構領域，目前依然鮮有研究。這篇論文展示了深度學習在解決馮·諾依曼架構計算機內存性能瓶頸問題中的應用。論文關注的是學習內存訪問模式這一關鍵問題，意在構建一種準確高效的內存預期器。研究提出將預期策略視為 NLP 中的 n-gram 模型，並使用 RNN 模型完全替代基於表的傳統預取。在基準測試集上的實驗表明，基於神經網路的模型在預測內存訪問模式上可穩定地給出更優的準確率和召回率。

更多乾貨內容請關注微信公眾號「AI 前線」，（ID：ai-front）

以下內容為AI前線根據論文編譯整理而成：

在計算機結構的設計中，很多問題涉及使用預測和啟發式規則，內存預取就是其中的一個經典問題。內存預取將指令和數據在被微處理器實際使用前，預先置於存取速度更快的內存中。因為在馮·諾伊曼結構計算機中，微處理器的運算速度要比內存訪問速度高出數個數量級，因此內存預取是一個關鍵的瓶頸問題，也被稱為「內存牆」（Memory Wall）。有統計表明，計算機中 50% 的計算周期是在等待數據載入到內存中。為解決內存牆的問題，微處理器使用了層次結構的內存，即在結構上採用多級緩存設計，讓規模更小但是訪問速度更快的緩存更接近於處理器。為降低內存讀取的延遲，需要預測何時以及哪些數據應預取到緩存中。因此，提高性能的一個關鍵問題，是如何給出有效的內存訪問模式預測。

在現代處理器中，使用了一些預測方法。很多預測器是基於記錄表實現的。記錄表是一種內存數組結構，記錄了未來事件與以往歷史信息的關聯性。但是相比起傳統的單機工作負載，現代數據中心的工作負載規模呈現指數級的增長，這對內存訪問模式預測提出了嚴峻挑戰。預測的準確性會隨預測表規模的增大而顯著下降。簡單地擴展預測表的規模，需在硬體實現上付出很大的代價。

神經網路技術已在 NLP 和文本理解取得了很好的效果，它為解決序列預測問題提供了一種強大的技術。例如，在 SPARC T4 處理器中，已經部署了一種簡單的感知機，實現對分支處理指令的預測。但是，對於微處理器架構設計而言，如何有效地引入序列學習演算法依然是一個開放的問題。

本文的研究考慮在微處理架構中引入基於序列的神經網路模型，意在解決內存牆所提出挑戰，將序列學習應用到內存預取這一難題上。內存預取問題，在本質上可以看成是一種回歸問題。但是該問題的輸出空間很大，並且非常稀疏，使用標準的回歸模型難以給出好的效果。本文作者們考慮使用一些圖像和語言生成上的最新研究成果，例如 PixelRNN 和 Wavenet。這些研究成果對搜索空間做離散化，使得內存預取模型更近似於神經語言模型，並依此作為構建神經網路內存預取器的出發點。本文研究所提出的神經網路模型，可以成功地建模問題的輸出空間，實現一種神經網路內存預取，並給出了顯著優於現有傳統硬體預取器的性能。此外，論文中使用的 RNN 可以根據應用的內存訪問軌跡辨別應用的底層語義信息，給出的結果更具可解釋性。

背景知識

內存預取器（Prefetcher）

內存預取器是一種計算機硬體結構，它使用歷史內存訪問記錄預測將來的內存訪問模式。現有的內存預取器大體上可分為兩類。一類稱為「步長預取器」（stride prefetcher），另一類稱為「關聯預取器」（correlation prefetcher）。現代處理器中通常使用的是步長預取器，序列中固定採用穩定的、可重複的地址差值（即序列中相鄰兩個內存地址間的差值）。例如，給定一個內存訪問模式（0，4，8，12），每次訪問的地址差值為 4，那麼預取器可以由此預測此後的地址訪問模式為（16，20，24）。

關聯預取器可預測地址差值不固定的重複模式。它使用了一個大的記錄表，保持過往的內存訪問歷史信息。相比於步長預取器，關聯預取器可以更好地預測非規則變化的模式。典型的管理預取器包括 Markov 預取器、GHB 預取器，以及一些使用大規模內存中結構的最新研究預取器。關聯預取器需要具備一張大規模的記錄表，該表的實現代價大，因此通常並未實現在多核處理器中。

遞歸神經網路（RNN）

深度學習適用於很多的序列預測問題，例如語言識別和自然語言處理。其中，RNN 可對長距離依賴建模。LSTM 作為一種廣為使用的 RNN 變體，通過以加法方式而非乘法方式傳播內部狀態，解決了標準 RNN 的訓練問題。LSTM 由隱含狀態、元胞狀態、輸入門、輸出門和記憶門組成，分別表示了需要存儲的信息，以及在下一個時間步（timestep）中傳播的信息。給定時間步和輸入，LSTN 的狀態可以使用如下過程計算：

1. 計算輸入門、輸出門和記憶門
2. 更新胞元狀態
3. 計算 LSTM 隱含狀態（輸出）

其中，表示當前的輸入和前一個隱含狀態的級聯（concatenation），表示點乘操作（element-wise multiplication），是 Sigmoid 非線性函數。上面給出的過程表示了單個 LSTM 層的處理形式，是該層的權重，是偏差。LSTM 層可以進行堆疊，在時間步 N 的 LSTM 層的輸出，可以作為另一個 LSTM 層的輸入，這類似於前向回饋神經網路中的多層結構。這使得模型在使用相對較少額外參數的情況下，增大了靈活性。

問題定義

將預取作為預測問題

預取可以看成是對未來內存訪問模式的預測過程。如果數據並不在緩存中（即緩存未命中），預期器需要根據歷史訪問情況，到主存中去獲取數據。每條內存地址由內存操作指令（load/store）生成。內存操作指令是計算機指令集中的一個子集，實現對計算機系統中具有地址內存的操作。

很多硬體廠商建議在做出預期決策時使用兩個特徵。一個是截至目前緩存未命中的地址序列，另一個是指令地址序列，也稱為程序計數器（Program counter，PC），即關聯到生成每條緩存未命中地址的指令。

每條 PC 可以唯一標識一條指令，指令是對給定代碼文件中的特定函數編譯生成的。PC 序列可告知模型應用代碼的控制流模式，而緩存未命中地址序列可告知模型需要下一步預期的地址情況。在現代計算機系統中，上述特性均使用 64 位整數表示。

初始模型可以在每個時間步使用兩個輸入特徵，即在步生成的緩存未命中地址，以及由 PC 預測的 N+1 步緩存未命中情況。但是其中存在一個問題，應用的地址空間是非常稀疏的。對於此問題的訓練數據而言，緩存未命中的空間複雜度為量級，其中只有的緩存未命中地址出現在的物理地址空間中。圖 1 顯示了使用標準 SPEC CPU2006 基準測試集 omnetpp 時的緩存情況，紅色點表示了緩存未命中地址。這一空間範圍寬泛，具有重度多模態本質，這對傳統的時序回歸模型提出了挑戰。例如，雖然神經網路非常適用於正則化輸入，但是對這樣的數據做正則化時，有限精度的浮點數表示將導致顯著的信息丟失。該問題影響了對輸入層和輸出層的建模。在本文中，作者對此給出了解決方法。

將預取作為分類問題

在本文作者提出的解決方法中，考慮將整個地址空間視為一個離散的大規模辭彙表，並對辭彙表執行分類操作。這類似於 NLP 中對隨後出現的字元或單詞的預測問題。但是，該空間是極度稀疏的，並且其中部分地址比其它地址更頻繁地訪問。對於 RNN 模型，是可以管理這樣規模的有效辭彙表的。此外，相比於單模態回歸技術，通過生成多模態輸出，模型處理可以變得更加靈活。在圖像處理和語音生成領域中，已有一些研究成功地將輸出輸出作為預測問題而非回歸問題。

但是，預期問題存在著種可能的 softmax 目標，因此需要給出一種量化（quantization）模式。更重要的是，預取必須完全準確才能發揮作用。對於通常的 64 個位元組情況應該如此，對於通常是 4096 個位元組的頁面也應如此。在頁面層級上的預測，將會給出中可能的目標。為避免對超過個值應用 softmax，一些研究提出應用非線性量化模式將空間降維到 256 類。但是這些解決方法這並不適用於本文中的問題。因為這些方法降低了地址的解析度，使得預取無法獲得所需的高精度。

由於動態邊界效應，例如地址空間布局隨機化（ASLR）問題，同一程序的多輪運行可能會訪問不同的原始地址。但是，同一程序對於一個給定的布局將給出一致的行為。由此，一種可行的策略是預測地址差值，而非直接預測地址本身。如表 1 所示，地址差值的可能出現情況，要比地址的可能出現情況呈空間指數級別降低。

表 1 程序追蹤數據集統計情況，「M」表示「百萬」

模型描述

論文給出了兩種基於 LSTM 的預取模型。第一種模型稱為「嵌入 LSTM」模型，它類似於標準的語言模型。第二種模型利用內存訪問空間的結構去降低辭彙表的規模，降低了模型佔用的內存量。

嵌入 LSTM 模型

該模型限制輸出辭彙表的規模，僅建模最頻繁出現的地址間隔。根據表 1，要獲得最優 50% 的準確性，所需的辭彙表規模僅為量級乃至更小。這樣規模的辭彙表完全處於標準語言模型可解決的能力範圍內。基於此，論文提出的第一種模型對輸出辭彙表規模做了限制，選用了其中 50000 個最頻繁出現的唯一地址差值。對於輸入辭彙表，模型考慮在辭彙表中出現了至少 10 次的所有地址差值。要進一步擴展辭彙表，無論在統計學還是計數上都是有挑戰的。這些挑戰可以採用層次 softmax 類方法解決，有待進一步研究。

嵌入 LSTM 的結構如圖 2 所示。模型將輸入和輸出地址差值以分類表示（即獨熱編碼）。在時間步，分別嵌入輸入和，並將嵌入辭彙級聯起來，構成兩層 LSTM 的輸入。進而，LSTM 對地址差值辭彙做分類，並且選取個最高概率地址差值，用於預取。分類方法可直接給出預測概率，這對傳統硬體是另一個優點。

實際實現中，預取器會返回多個預測值，因此需要從中做出權衡。雖然更多的預測值增加了緩存命中下一個時間步的可能性，但是有可能會從緩存中移除其它一些有用的項。論文選取在每個時間步預取 LSTM 的頭部 10 個預測值。這裡還有其它一些可能的做法，例如使用使用 beam-search 預測之後個時間步，或是通過直接學習先於 LSTM 的一次前向操作給出對到時間步的預測。

嵌入 LSTM 模型存在一些局限性。首先，大型的辭彙表增加了模型的計算複雜度和存儲量。其次，截取部分辭彙表無疑為模型準確性設置了一個上限。最後，不易處理一下罕見發生的地址差值，因為這些差值很少在訓練集中出現。該問題在 NLP 領域稱為「罕見辭彙問題」。

聚類與 LSTM 的組合模型

假定大多數地址間感興趣操作發生在本地地址空間中。例如，結構體和數組的數據結構通常使用持續的數據塊存儲，並會被指令重複訪問。論文在模型設計中引入了上述理念，對本地上下文做細緻建模。與之不同的是，在嵌入 LSTM 模型中不僅考慮了本地上下文，而且引入了全局上下文。

通過查看更窄區域的地址空間，可以發現其中的確存在著豐富的本地上下文。為此，論文從 omnetpp 中取出了部分地址集，並使用 K-Means 聚類為 6 個不同的區域。圖 3 中展示了其中的兩個聚類。

為達到對本地地址空間區域建模的相對準確性，論文對原始地址空間進行 K-Means 聚類，將數據分區為多個聚類，並對計算每個聚類內的地址差值。圖 4a 是對上例的可視化。該方法具有一個顯著的優點，就是聚類內的地址差值集要顯著地小於全局辭彙表中的差值，這緩解了嵌入 LSTM 模型中存在的一些問題。

為進一步降低模型的規模，論文使用了多任務 LSTM 對所有距離建模，即對每個聚類獨立使用一個 LSTM 建模。聚類 ID 也添加為模型的特性，這為每個 LSTM 提供了一組不同的偏差。

將地址空間分區為更小的區域，意味著每個聚類內地址組使用的幅度量級大體上相同。因此，所生成的地址差值可以有效地正則化為適用於 LSTM 的真實輸入值，不再需要維護一個大型的嵌入矩陣，進而進一步降低了模型的規模。更重要的是，下一個地址差值預測的問題可作為一個分類問題，而回歸模型在現實中通常不夠精確。

該模型解決了一些嵌入 LSTM 中存在的問題。預處理步驟（即對地址空間的聚類）是模型中需要權衡考慮的一個因素。此外，該模型只對本地上下文建模，也可以對程序訪問的不同地址空間區域進行動態建模。

實驗

一個有效的內存預取器，應該具備對緩存未命中情況的準確預測能力。因此，論文的實驗主要針對如何測定預取器的有效性。

實驗數據的收集

實驗中所使用的數據主要是程序的動態追蹤數據，其中包含程序計算的一個內存地址序列。追蹤數據使用動態工具 Pin 捕獲。該工具附著在進程上，並以文件形式給出被測量應用訪問內存的「PC，虛地址」元組。原始訪問追蹤數據主要包含了堆棧訪問等命中內存的方法。對於研究中關注的預測緩存未命中情況，實驗中使用了一個模擬 Intel Broadwell 微處理器的模擬器，獲取緩存未命中情況。

實驗程序使用的是對內存做密集訪問的 SPEC CPU2006 應用。該基準測試集用於算機系統的性能做完全評估。但是，與現代數據中心工作負載相比，SPEC CPU2006 依然是一個小規模的工作集。因此在論文的實驗中，還添加了 Google 的 Web 搜索工作負載。

實驗中將內存訪問數據集分為訓練集和測試集，其中 70% 用於訓練，30% 用於測試。在每個數據集上獨立訓練每個 LSTM。嵌入 LSTM 使用 ADAM 訓練，聚類 LSTM 使用 Adagrad 訓練。使用的超參數參見原文附錄。

實驗測試的度量包括準確率和召回率。在實驗中，對每個模型做出 10 次預測。如果在頭部 10 次預測中給出了完全正確的地址差值，就認為生成了一次準確預測。

模型對比情況

實驗將基於 LSTM 的預取器與兩種硬體預取器進行了對比。第一種是標準流預取器。為保持機器學習預取器與傳統預取器的一致性，實驗中模擬了支持多至 10 個並發流的硬體結構。第二種是 GHB PC/DC 預期器。這是一種關聯預取器，它使用了兩個表。一個表用於存儲 PC，並將所存儲的 PC 作為執行第二個表的指針。第二個表存儲了地址差值的歷史信息。在每次訪問時，GHB 預取器跳轉到第二個表，預取歷史記錄的地址差值。關聯預取器對於複雜內存訪問模式表現很好，具有比流預取器更低的召回率。

圖 5 給出了不同預取器在各種基準測試數據集上的對比情況。儘管流預取器由於其動態辭彙表特性可以獲得最高的召回率，但是 LSTM 模型整體表現更好，尤其是準確率。

通過對比嵌入 LSTM 模型和聚類與 LSTM 的組合模型，可以看到兩種模型間的準確率不相上下。後者趨向於給出更好的召回率。當然，組合更多的模型將會給出更好的結果，這有待未來的工作去探索。

對比 PC 的預測情況

該實驗從嵌入 LSTM 模型的輸入中分別移除或 PC。實驗設計意在確定在不同輸入模組中所包含的相對信息內容。

實驗結果如圖 6 所示。從圖中可以看出，PC 和地址差值中包含有大量預測信息。地址差值序列中的預測信息可以提高準確率，而 PC 序列有助於提高召回率。

解釋程序的語義

相比於基於查找表的預期器，模式學習模型的一個主要優點是可以通過審視模型獲取數據的內涵。圖 7 展示了級聯串在 mcf 上嵌入情況的 t-SNE 可視化。

圖中的一個聚類是由一組具有統一代碼的重複指令組成，這是由於編譯器對循環體展開所導致。還有一個聚類僅由指針解除引用（pointer dereference）組成，這是由於程序遍歷鏈接列表所導致的。在 omnetpp 中，對數據結構的插入和移除操作映射為同一個聚類，而數據比較操作則映射在不同聚類中。例子所使用的代碼參見原文附錄。

結論及進一步工作

對應用程序行為的學習和預測，可在解決計算機架構中的控制和數據並發問題中發揮重要作用。傳統方法是使用基於表的預測器，但是當擴展到數據密集不規則工作負載時，實現此類方法的代價過大。

本文介紹了兩者基於神經網路的預取模型，它們給出了比基於表的傳統方法顯著高的準確率和召回率。在實驗中，論文對模型做離線訓練並在線測試，使用準確率和召回率評估了模型。實驗表明，論文提出的預取器模型可以改進緩存未命中的分布。當然，還有其它一些在不增加預取器的計算和內存負擔條件下改進預期器的方法。在進一步的研究中，可以考慮基於內存命中和未命中數據訓練模型，但是這將顯著改變數據集的分布和規模。

時效性也是研究預期其中一個考慮的重要因素。對於 RNN 預取器而言，預期過早會導致處理器未使用緩存數據，預取過遲會則對性能影響甚微，因為延遲訪問內存的代價已經付出。一個簡單的啟發式規則是採用類似於流預期器的行為，預先對多個時間步做出預測，而非僅是下一個時間步。

最後一點，對應用性能的影響可以評估 RNN 預取器的有效性。在理想情況下，RNN 將會直接優化應用性能。一個考慮是，使用強化學習技術作為動態環境中 RNN 的訓練方法。

當然，內存預取並非計算機系統中唯一需要給出預測執行的領域。只要涉及分支行為，就需要做出預測。分支演算法用於重定向控制流的地址，高速緩存替換演算法在需要做出替換決定時預測從高速緩存的最佳替換處。如果採用機器學習系統代替傳統微體系結構中的啟發式規則，可以通過對此類系統審視，更好地理解系統的行為。論文中的 t-SNE 實驗僅給出了一些表面上的觀察，展示了內存訪問模式是程序行為的一種表示。這表明，利用最新研究的 RNN 系統，為計算機系統結構研究提供了大量的機會。

查看論文原文：

https://arxiv.org/pdf/1803.02329.pdf

更多乾貨內容，可關注AI前線，ID：ai-front，後台回復「AI」、「TF」、「大數據」可獲得《AI前線》系列PDF迷你書和技能圖譜。

推薦閱讀：