同時基于預知信息和預測機制的SDRAM動態頁策略＊

呂 暉，謝向輝

（數學工程與先進計算國家重點實驗室，江蘇 無錫214125）

1 引言

隨著集成電路技術的發展，片上計算資源的集成度越來越高，片上所能集成的計算核心數量已經從單核、多核一直發展到數百甚至數千核心［1，2］。但是，存儲技術的發展速度遠不能滿足計算能力的發展需求。特別受芯片信號引腳數量和數據傳輸率兩方面因素的限制，訪存帶寬已經成為系統性能的最主要瓶頸。如何充分發掘有限的訪存帶寬資源，成為系統設計者需要重點考慮的問題之一。

基于成本和性能等多方面因素的考量，SDRAM成為構建現代主存系統的基礎。從用于通用計算系統的DDR系列存儲技術（DDR、DDR2、DDR3、DDR4），到用于嵌入式／手持計算系統的LPDDR系列存儲技術（LPDDR2、LPDDR3、LPDDR4），以及用于顯存領域的GDDR系列存儲技術（GDDR3、GDDR5），甚至混合存儲立方體HMC（Hybrid Memory Cube）等新型存儲技術［3］，SDRAM都是其中最重要的組成部分。

SDRAM的結構特征和工作原理，決定了頁策略是提升實際訪存效率的重要因素之一。傳統上，頁策略分為頁打開策略和頁關閉策略。一般情況下，頁打開策略適用于頁命中率較高的訪存序列，而頁關閉策略適用于頁命中率相對較低的序列。這樣，無論固定采用頁打開策略，還是固定采用頁關閉策略，均存在性能相對較差的情況。因此，如何將兩種頁策略相結合，就成為研究者們的關注點［4～12］。

在上述研究工作中，絕大多數均基于預測機制［4～10］。調度器記錄訪存序列的歷史信息，對未知的訪存請求的行為特征進行預測，然后依此動態確定采用何種頁策略。這類基于預測機制的頁策略，其性能取決于頁策略切換時機是否能夠精確契合訪存序列的行為特征。受限于應用程序訪存行為的復雜程度以及硬件預測機制的實現代價，基于預測機制的動態頁策略對訪存性能的改善程度有限。

文獻［11，12］則采用了基于預知信息的頁策略。文獻［11］所使用的預知信息由處理器提供，當存儲控制器中的訪存請求緩沖為空時，方可進行頁策略轉換。該方法使用單獨的“預充電”命令關閉頁，而不是采用“帶預充電功能的讀／寫”命令，這就導致無法有效降低對命令總線帶寬的需求。

文獻［12］所使用的預知信息由存儲控制器內部的訪存請求緩沖提供。當請求隊列非空時，該方法能夠根據請求調度緩沖中的待處理請求的地址信息，直接計算出后續訪存請求的頁命中情況，存儲控制器可依此動態決定采用何種頁策略；當請求隊列為空時，該方法則固定采用頁打開策略。盡管文獻［12］是迄今為止相對最理想的動態頁策略之一，但卻并未對預知信息對不同頁策略的系統性能優化程度進行全面研究。此外，當訪存請求較為稀疏，導致請求隊列為空時，該方法不具備對后續訪存序列頁命中情況的有效預測能力。

基于以上分析，本文系統研究了使用預知信息對多種頁策略的性能優化效果，并提出了一種同時基于預知信息和預測機制的動態頁策略。該策略能夠更好地適用各類不同類型的訪存序列，有效提升實際訪存效率。該策略的關鍵思想是，若請求隊列非空，則最適宜當前請求的頁策略可以精確獲知；若請求隊列為空，則依據歷史信息對最適宜當前請求的頁策略進行預測。

為了系統研究基于預知信息的多種動態頁策略的性能優化效果，并證實本文所提出的動態頁策略的有效性，作者采用SPEC2006中的部分測試程序分別在1核、2核、4核、8核環境下進行了36項測試。每項測試完成六種頁策略實驗，其中，三種使用傳統頁策略，三種使用基于預知信息的動態頁策略。從實驗結果可以看出，基于預知信息的頁策略均優于不基于預知信息的頁策略，最好情況下，實際訪存帶寬可提升42%。此外，對于三種基于預知信息的頁策略而言，三者性能差異相對較小，而本文所提出的“同時基于預知信息和預測機制的動態頁模式調度策略”的多數情況下性能較優，能夠較好地適應各類不同的訪存序列。

2 研究背景與研究目的

2.1 SDRAM 頁策略

在現代SDRAM系統中，每個存儲顆粒由若干存儲體（Bank）組成，每個存儲體由存儲陣列、頁緩沖以及附加邏輯等組成。在訪問SDRAM時，需要先使用激活ACT（Active）操作將SDRAM的存儲陣列中的內容讀入頁緩沖，然后才能使用讀RD（Read）或者寫 WE（Write）命令對其進行訪問，訪問完畢后可以使用預充電命令PRE（Precharge）將頁緩沖的數據寫回SDRAM的存儲陣列。當預充電命令緊隨讀命令（或者寫命令）之后時，可以使用一條“帶預充電的讀命令（或者寫命令）”替代由“讀命令（或者寫命令）和預充電命令”組成的命令序列。其中，“帶預充電的讀命令”簡記為RDap，“帶預充電的寫命令”簡記為WEap。

如果在一次讀寫訪問之后，將數據繼續保持在頁緩沖中，而不是將其寫回至存儲陣列，那么這種頁策略就稱為“頁打開策略”；如果在一次訪問之后，將頁緩沖中的數據寫回SDRAM的存儲陣列，那么這種頁策略就稱為“頁關閉策略”［2］。訪存序列如圖1所示。

頁打開策略和頁關閉策略擁有各自的優缺點。對于頁打開策略，若后續訪問能夠命中頁緩沖中的數據，則能減少訪存延遲、減少訪存命令數量，有利于增加訪存帶寬；但是，若后續訪問不命中頁緩沖的數據，則增加訪存延遲、增加訪存命令數量，不利于提升訪存帶寬。對于頁關閉策略，其訪存延遲、所耗用的訪存命令數量均與是否命中頁緩沖無關，其好處是訪存延遲、訪存帶寬不受頁命中率高低的影響；其不足是當頁緩沖命中率較高時，無法使訪存延遲、訪存帶寬最優化。

圖1 SDRAM頁打開策略和頁關閉策略的訪存命令序列圖Figure 1 SDRAM command sequence for the page open／close policy

2.2 研究目的

無論固定采用頁打開策略，還是固定采用頁關閉策略，都無法使訪存性能在各類情況下均獲得最優。因此，根據訪存行為的特征，混合使用頁打開和頁關閉策略組成的動態頁策略，是提升系統訪存性能的有效手段之一。

根據策略選擇依據的不同，動態頁策略可分為兩類：一類是基于預測的頁策略，一類是基于預知信息的頁策略。在能夠獲知后續訪存請求的地址信息的條件下，基于預知信息的頁策略能夠更精確地對頁模式進行調度，對訪存性能的優化效果更為顯著。在無法獲知后續訪存請求的地址信息的條件下，若基于合適的預測機制對頁模式進行調度，則有可能獲得更好的優化效果。

總之，動態頁策略對于訪存延遲、訪存帶寬、主存系統功耗等都會產生顯著影響，有必要對其進行深入研究。

3 系統結構

為了能對基于預知信息的動態頁策略進行系統的分析，本文設計并實現了一個能以較低的硬件代價同時支持六種頁策略的SDRAM存儲控制器。

該存儲控制器由以下幾個主要功能模塊構成：訪存請求緩沖、請求解析狀態機、數據寫入緩沖、數據讀出緩沖等。其中，訪存請求緩沖用于存放用戶訪存請求；請求解析狀態機則負責將訪存請求緩沖的模塊依次取出，并將其翻譯成SDRAM命令序列；數據寫入緩沖，用于接收用戶數據，并在合適的時機將其送入SDRAM；數據讀出緩沖，用于接收來自SDRAM的數據，并將其以約定的格式送回用戶。總體結構如圖2所示。

Figure 2 Architecture of the memory controller圖2 存儲控制器總體結構

3.1 請求解析狀態機

請求解析狀態機是存儲控制器的核心模塊。該狀態機根據SDRAM頁緩沖中的數據是否有效、訪存請求地址是否命中頁緩沖等信息，決定是否在SDRAM讀寫命令之前發送激活命令、預充電命令；然后，根據頁策略控制信息，決定是發送帶預充電功能的SDRAM讀寫命令，還是發送不帶預充電功能的SDRAM讀寫命令。請求解析狀態機的算法狀態圖如圖3所示。

3.2 頁策略控制信息的生成

為了實現基于預知信息的SDRAM動態頁策略，需要由訪存請求緩沖模塊向請求解析狀態機提供頁策略控制信息。該信息為位寬為1的控制位，當其取值為1時，表示需要采用頁打開策略；當其取值為0時，表示需要采用頁關閉策略。該控制位的取值可由所采用的頁策略、后續請求的頁命中情況動態確定。其生成邏輯的實現結構如圖4所示。

Figure 3 Algorithm state diagram of the request decomposing state machine圖3 請求解析狀態機的算法狀態圖

Figure 4 Generation of the page controlling policy圖4 頁策略控制信息的生成

在上述結構中，“非預知／預知”開關用于選擇是否采用“基于預知信息的頁策略”，“預測／非預測”開關用于選擇是否采用“基于預測機制的頁策略”，“頁打開／關閉策略”開關用于選擇是采用頁打開策略或是采用頁關閉策略。

當“非預知／預知”開關取值為1時，所控制的2選1邏輯輸出為0，該輸出將作為下一級選擇邏輯的控制開關值，因此，由地址對比邏輯所生成的“實測保持頁打開”信息將被忽略，此時，將采用“非預知”類型的頁策略。

當“非預知／預知”開關取值為0時，所控制的2選1邏輯輸出為“請求FIFO非空”值，該輸出將作為下一級選擇邏輯的控制開關值。當請求FIFO非空時，由地址對比邏輯所生成的“實測保持頁打開”信息將被選中，此時可精確預知后續請求的頁策略需求；當請求FIFO為空時，將采用頁打開、頁關閉或者基于預測的動態頁策略。

各個頁策略的配置編碼表如表1所示。

Table 1 Configuration codes for page policies表1 頁策略的配置編碼表

其中，模式預測狀態機的算法狀態圖如圖5所示。

Figure 5 Algorithm state diagram of the mode－prediction state machine圖5 模式預測狀態機的算法狀態圖

3.3 硬件實現代價分析

請求FIFO是已有結構，2個地址對比邏輯、4個2選1選擇器、1個模式預測狀態機和用于存放“當前正在處理的請求”和“最近一個已處理請求”的兩個寄存器是新增結構。其中，各新增結構的硬件實現代價分析如下：

（2）2選1選擇器。其邏輯表達式可記為：a［i］＝a［i］·（～s）＋b［i］·s。其中，c為邏輯的輸出，a、b為邏輯的輸入，～為“邏輯非”操作，·為“邏輯與”操作，＋為“邏輯或”操作。對于位寬為1的“2選1選擇器”而言，使用2個與門、1個非門、1個或門即可完成邏輯的搭建。

（3）模式預測狀態機。模式預測狀態機由一個位寬為2的當前狀態寄存器及其對應的次態生成邏輯構成。該狀態寄存器記為c，其次態生成邏輯的輸出記為n，頁命中標記記為p，根據模式預測狀態機的工作原理圖，可以得到次態生成邏輯的表達式如下：

其次態生成邏輯使用16個與門、6個或門、12個非門即可搭建完成。

由以上分析可知，所需要的新增硬件結構實現代價很小。

4 實驗

4.1 實驗方法

為了深入分析基于預知信息的SDRAM動態頁策略優化效果，作者使用Gem5模擬器搭建了1核心、2核心、4核心、8核心等四個不同核心數量的實驗系統。各個核心通過總線相連，共享同一個訪存通路。各系統中每個核心的主要硬件參數如表2所示。

本文采用SPEC cpu2006測試套件作為測試激勵。本文隨機選取了9個測試程序，運行在四個不同核心數量的實驗系統上。每個系統均對頁關閉策略、頁打開策略、基于預測的動態頁策略、基于預知信息的頁關閉策略、基于預知信息的頁打開策略、同時基于預知信息和預測機制的頁策略等六種策略進行測試。

Table 2 Hardware parameters of the experimental system表2 實驗系統的硬件參數

對于實驗結果，本文重點關注未施加／已施加預知信息的頁策略之間的訪存帶寬差異。例如，“頁關閉策略”和“基于預知信息的頁關閉策略”之間的性能差異、“頁打開策略”和“基于預知信息的頁打開策略”之間的性能差異、“基于預測的動態頁策略”和“同時基于預知信息和預測機制的頁策略”之間的性能差異。

此外，為了衡量未施加／已施加預知信息的兩組頁策略各自的性能數據的離散程度，本文引入“相對極差”這一統計學當中的常用統計指標。該指標主要用于比較不同組別數據的離散程度，其取值越大，表示該組數據的離散程度越大；其取值越小，表示該組數據的離散程度越小。計算方法為：

其中，RR表示相對極差，xmax和xmin分別表示測量數據中的最大值和最小值，μ表示測量數據的平均數。

4.2 實驗結果

實驗結果如圖6所示。圖6的縱坐標為不同頁策略所獲得的訪存帶寬，橫坐標為不同核心數量下的測試激勵。其中，每一項測試激勵都使用六種頁策略進行測試，其測試結果從左至右分別對應著頁關閉策略、基于預知信息的頁關閉策略、頁打開策略、基于預知信息的頁打開策略、基于預測的動態頁策略、同時基于預知信息和預測機制的動態頁策略。

Figure 6 Experimental results圖6 實驗結果

Figure 7 Relative range of memory bandwidth of the two page policies圖7 兩組頁策略訪存帶寬的相對極差

從上述實驗數據中可以看出，當在基礎頁策略上施加預知信息進行優化后，訪存帶寬均獲改善，最好情況下，實際訪存帶寬可提升42%強。此外，對于未施加預知信息的頁關閉、頁打開、基于預測的動態頁策略，三者之間的訪存性能差異較大，其相對極差最大可達37%；而對于基于預知信息的頁關閉、基于預知信息的頁關閉頁打開、同時基于預知信息和預測機制的動態頁策略，三者之間的性能差異普遍顯著降低，均不超過19%。特別地，對于8核心系統，后三者的相對極差最大僅為6%，如圖7所示。這說明三種基于預知信息的頁策略之間的性能差異不大，均可獲得較理想的實際訪存帶寬。

對于每一項測試激勵而言，基于預知信息的三種頁策略（頁打開、頁關閉、基于預測的動態頁策略）的性能相對優劣如表3所示。

Table 3 Performance comparison of the three page policies based on advance information表3 三種基于預知信息的頁策略性能比較

從表3中可以看出，對于大多數測試激勵，同時基于預知信息和預測機制的動態頁模式調度策略最優，基于預知信息的頁打開策略性能略差，基于預知信息的頁關閉策略性能最差。

綜上所述，基于預知信息的三類頁策略均能有效提升系統訪存性能。三者之中相對而言，“同時基于預知信息和預測機制的動態頁模式調度策略”性能最優，帶寬最高的測試項數最多，即適應范圍最廣。

5 相關工作

對于SDRAM頁策略，已經有若干相關研究工作。除了最基本的頁打開、頁關閉兩種固定頁策略［2］以外，還出現了若干混合使用頁打開／頁關閉兩種頁策略的動態頁策略。

這些動態頁策略可分為三類。基于預測的動態頁策略、基于定時器的動態頁策略、基于預知信息的動態頁策略。

文獻［4～10］都是基于預測的動態頁策略。基于預測的動態頁策略可分為兩種，第一種基于歷史訪存序列進行預測，第二種是基于定時器機制進行預測。基于歷史訪存序列的動態頁策略，其基本原理是利用訪存序列的歷史信息，對后續訪存請求的頁命中情況進行預測，以選擇合適的頁策略。其中，文獻［4］使用有限狀態自動機記錄歷史信息，最多記錄4個歷史訪存請求的頁命中情況；文獻［5］則是僅記錄歷史訪存序列中的頁不命中次數，所記錄的歷史頁不命中最大次數動態可調整；文獻［6，7］可記錄連續16個以上的歷史訪存請求的頁命中情況；文獻［8］則是利用周期采樣技術對歷史訪存請求的頁命中情況進行分析。

文獻［9，10］都是基于定時器的動態頁策略，該策略的基本原理是每次訪存之后，保持頁打開一定時間（該時間長度由定時器決定），如無新的請求到來，則頁關閉。其中，文獻［9］中的定時器取值固定不變，文獻［10］中的定時器的取值隨著訪存序列特征的變動而動態變化。

文獻［11，12］則采用了基于預知信息的動態頁策略。該策略不再利用訪存序列的歷史信息對后續訪存請求的頁命中情況進行預測，而是直接觀察后續訪存請求的頁命中情況，以選擇合適的頁策略。其中，文獻［11］由處理器核心向存儲控制器提供后續訪存請求的頁命中情況，文獻［12］則由存儲控制器內部的訪存請求緩沖自行計算后續訪存請求的頁命中情況。

上述混合使用頁打開／頁關閉兩種頁策略的動態頁策略的效果，和對訪存序列行為特征的契合程度密切相關。總體來說，基于預知信息的動態頁策略的適應面相對較廣，但是仍對相當數量的訪存序列適應性較差，因此本文進行了進一步的深入研究。

6 結束語

本文對三類主要的基于預知信息的動態頁策略進行了系統研究，并提出了一種同時基于預知信息和預測機制的SDRAM動態頁策略。該策略可充分利用緩存在FIFO中的待處理訪存請求的地址信息，對后續頁命中情況進行精確判斷，并以之對頁策略進行管理；而當沒有待處理訪存請求可預知時，則利用所記錄的歷史信息對后續頁命中情況進行預測，為后續請求選擇合適的頁策略。

經實驗證實，總體而言，三類基于預知信息的動態頁策略之間的性能差異較小，均能獲得較理想的訪存帶寬。其中，同時基于預知信息和預測機制的動態頁策略的性能在三者之中最優，適應面最廣泛。

［1］ Sodani A.Intel Xeon Phi processor“knights landing”architectural overview［EB／OL］.［2015－11－17］.http：∥ www.nersc. gov／assets／uploads／KNL－ISC－2015－Workshop－Keynote.pdf.

［2］ Johnson D R，Johnson M R，Kelm J H，et al.Rigel：A 1，024－core single－chip accelerator architecture［J］.IEEE Micro，2011，31（4）：30－41.

［3］ Ahn J，Yoo S，Choi K.Dynamic power management of offchip links for hybrid memory cubes［C］∥Proc of the 51st ACM Annual Design Automation Conference，2014：1－6.

［4］ Park S，Park I.History－based memory mode prediction for improving memory performance［C］∥Proc of the 2003IEEE International Symposium on Circuits and Systems，2003：185－188.

［5］ Miura S，Ayukawa K，Watanabe T.A dynamic－SDRAM－mode－control scheme for low－power systems with a 32－bit RISC CPU［C］∥Proc of the ACM 2001International Symposium on Low Power Electronics and Design，2001：358－363.

［6］ Xu Y，Agarwal A S，Davis B T.Prediction in dynamic SDRAM controller policies［C］∥Proc of the 9th International Workshop on Embedded Computer Systems：Architectures，Modeling，and Simulation，2009：128－138.

［7］ Awasthi M，Nellans D W，Balasubramonian R，et al.Prediction based DRAM row－buffer management in the many－core era［C］∥Proc of the 11th IEEE International Conference on Parallel Architectures and Compilation Techniques，2011：183－184.

［8］ Xie M，Tong D，Feng Y，et al.Page policy control with memory partitioning for DRAM performance and power efficiency［C］∥Proc of the 2013IEEE International Symposium on Low Power Electronics and Design，2013：298－303.

［9］ Kahn O D，Wilcox J R.Method for dynamically adjusting a memory page closing policy：U.S.Patent 6799241［P］.2004－9－28.

［10］ Sander B T，Madrid P E，Smaus G W.Dynamic idle counter threshold value for use in memory paging policy：U.S.Patent 6976122［P］.2005－12－13.

［11］ Huan D，Li Z，Hu W，et al.Processor directed dynamic page policy［C］∥Proc of the 11th Asia－Pacific Computer Systems Architecture Conference，2006：109－122.

［12］ Binkert N，Beckmann B，Black G，et al.The gem5simulator［J］.ACM SIGARCH Computer Architecture News，2011，39（2）：1－7.