這篇文章如題所示，使用深度學(xué)習(xí)模型來學(xué)習(xí)程序的內(nèi)存存取模式，從而準(zhǔn)確有效的進行memory prefetching。
背景
先來看一下為什么需要memory prefetching。現(xiàn)代計算機馮諾依曼架構(gòu)中存在的memory wall這個問題，即計算比訪問內(nèi)存快幾個數(shù)量級，因此內(nèi)存訪問就會成為程序的瓶頸。為了解決這個問題，現(xiàn)代計算機多采用一種金字塔型的存儲結(jié)構(gòu)，即越上層存取速度越快，但也越小，越下層越大但也越慢。這時候把頻繁訪問的數(shù)據(jù)放在越上層有利于提高程序性能。但有可能數(shù)據(jù)訪問上層的cache時，數(shù)據(jù)并不在cache中，這時會產(chǎn)生cache miss，此時就需要訪問下一層的內(nèi)存，而memory prefetching就是提前把程序需要的數(shù)據(jù)提前預(yù)取到cache中，從而避免程序訪問時產(chǎn)生cache miss造成的性能損耗。
過去，硬件中大多數(shù)預(yù)測器都是基于表實現(xiàn)。也就是未來的事件應(yīng)該與在表(實現(xiàn)為內(nèi)存數(shù)組)中跟蹤的程序內(nèi)存訪問歷史相關(guān)聯(lián)?？煞譃閮深?stride prefetchers 和correlation prefetchers 。stride prefetcher在現(xiàn)代多核處理器中比較普遍，一般用來預(yù)測訪問連續(xù)數(shù)組時，步長訪問具有規(guī)律性，根據(jù)步長的規(guī)律性進行預(yù)取，如前面按照步長 (0, 4, 8, 12)訪問，那么可以預(yù)測后面可能要訪問(16, 20, 24) 。correlation prefetchers將內(nèi)存訪問的過去歷史存儲在表中，如Markov prefetchers (Joseph & Grunwald, 1997), GHB prefetchers (Nesbit & Smith, 2004), 可以比跨步預(yù)取器更擅長預(yù)測更多的不規(guī)則模式。因為存儲歷史數(shù)據(jù)需要較大的表存儲開銷，因此未在現(xiàn)代多核處理器中實現(xiàn)。
prefetching可以看作一個根據(jù)歷史內(nèi)存訪問信息來預(yù)測未來內(nèi)存訪問的問題，因此論文中使用LSTM建立模型，有兩個輸入特征：
- 目前觀察到的cache miss的地址
- 指令地址序列，也就是PCs（ program counters）。
PC可以唯一代表一個指令的，因此PC序列反映了程序控制流的模式，產(chǎn)生miss的地址序列則代表了下一個要預(yù)取的地址。
這里還存在一個問題，程序的地址空間達(dá)到了,非常稀疏，當(dāng)成回歸問題來不太適合。為了解決將地址空間視為一個大的、離散的詞匯表，并執(zhí)行分類。另一方面，相同程序不同運行地址會變，因此使用第N次和N+1次訪問地址的變化量delta來預(yù)測更好。
模型
模型很簡單，
第一個模型，Embedding LSTM：
模型限制詞表為50000個訪問最頻繁的不同的地址變化量， 在第N步， 輸入為和地址變化量?N ，二者的的詞嵌入合并在一起作為LSTM的輸入，模型的輸出為10個最有可能的?N 。
這個模型的限制在于較大的詞表增加了模型訓(xùn)練的難度，并且詞表的大小的限制也限制了模型的精度。
第二個模型，Clustering + LSTM：
首先使用kmeans劃分區(qū)域，然后在每個區(qū)域內(nèi)計算地址變化量，每個區(qū)域內(nèi)的地址變化量的值數(shù)量級差不多，有利于更好的規(guī)范化。圖中，每個區(qū)域的PC和?N分別喂給一個LSTM，并且這多個LSTM共享參數(shù)。
衡量指標(biāo)：
Precision：如果真正的delta在前10個預(yù)測所給出的delta集合內(nèi)，則模型預(yù)測被認(rèn)為是正確的。
Recall：測試時所有預(yù)測值對測試時看到的所有實際值的比值。
在只使用PC作為特征和只使用delta作為特征和使用兩者作為特征的對比實驗中，發(fā)現(xiàn)delta有利于Precision，而PC序列有助于提高召回。
此外，本文使用的是一個a train-offline test-online 模型，在使用過程中可能預(yù)取器的使用會改變改變了cache miss的分布，從而降低在之前沒有使用預(yù)取器的數(shù)據(jù)上訓(xùn)練的模型的有效性，雖然可以考慮online training緩解這個問題，但online的計算和內(nèi)存使用成本較大。
啟示
本質(zhì)上memory trace也是一種 程序的行為，所以我們可以使用神經(jīng)網(wǎng)絡(luò)建模程序行為，使用數(shù)據(jù)的分布來學(xué)習(xí)特定的模型，而不是部署通用的數(shù)據(jù)結(jié)構(gòu)或者使用啟發(fā)式算法。神經(jīng)網(wǎng)絡(luò)壓縮了學(xué)習(xí)到的分布的表示，將問題轉(zhuǎn)換為一個計算問題，考慮到最近ML加速器的發(fā)展，將其用硬件實現(xiàn)很有希望。
可以使用NN代替啟發(fā)式算法的一些地方：
- 預(yù)取
- 分支預(yù)測
- cache替換算法
