處理器訪存子系統(tǒng)關鍵隊列的性能建模 ①

李文青 吳 畏 章隆兵 肖俊華 王 劍

(*計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190) (**中國科學院大學 北京 100049) (***龍芯中科技術有限公司 北京 100190)

0 引 言

隨著片上晶體管數量的增加，處理器計算能力迅猛提升，出現“存儲墻”問題，訪存成為處理器性能的一個重要瓶頸[1，2]。工業(yè)界和學術界使用許多技術來解決和緩解“存儲墻”問題，如使用Cache、多發(fā)射亂序執(zhí)行、向量指令等，從提高訪存速度、挖掘指令間的并行性掩蓋訪存時間或減少訪存次數等方面解決“存儲墻”問題。

超標量處理器支持訪存的推測執(zhí)行，增加訪存指令執(zhí)行時間上的重疊，加快了程序的執(zhí)行。處理器推測訪存過程中，訪存流水線中的幾個關鍵隊列有著重要的作用，這些隊列保存指令狀態(tài)、實現多條指令同時訪存、確保存取的數據不因發(fā)出順序改變而帶來錯誤、并且維護訪存指令的提交順序。

中央處理器(central processing unit，CPU)計算能力的提高，加大了對訪存速度的需求，訪存子系統(tǒng)的設計越來越復雜，訪存流水線中隊列壓力變大，CPU訪存相關隊列也越做越大。隊列的增大對CPU直接的影響就是面積和功耗的增加，快速尋找隊列大小的最佳組合和性能的折中點十分重要。

隊列大小組合方面并沒有很多研究可以參考，其中大多數是按照經驗來做，同時也可以使用模擬、建模的方式找到一個性能較好的大小組合[3，4]。模擬處理器執(zhí)行情況可以使用硬件仿真或者軟件模擬。軟件模擬是處理器設計空間探索常用的方式，但軟件模擬硬件的執(zhí)行通常要比真實處理器慢很多，時間上的開銷使得巨大的設計空間無法得到足夠的探索。硬件仿真雖然較軟件模擬更快更準確，但靈活性差，資源需求大，也不適合做設計空間的探索。

本文采用了模擬器和回歸模型相結合的建模方法，從模擬到預測，逐步擴大設計空間探索的范圍，求解隊列大小組合和性能的最佳平衡點。本文設計并實現了周期精確的訪存子系統(tǒng)模擬器，對訪存子系統(tǒng)的功能和行為進行了詳細的模擬，并使用目標處理器的現場可編程門陣列(field programmable gate array，FPGA)原型驗證平臺進行了校準。通過實驗和分析，提出了一種面向訪存子系統(tǒng)關鍵隊列大小的回歸模型，該模型測試誤差較低且結果穩(wěn)定，模型可用于預測整個訪存子系統(tǒng)設計空間中隊列大小組合的性能。

本文剩余部分組織如下：第1節(jié)回顧了與本研究相關的前人的工作，第2節(jié)介紹模擬器和回歸模型的設計，第3節(jié)描述了模擬器的實現，模型的構建以及誤差分析，第4節(jié)使用模型預測不同條件下隊列大小的最佳組合，第5節(jié)是整個文章的總結。

1 相關工作

在訪存子系統(tǒng)的設計發(fā)展中，有很多工作對其中的隊列進行了研究。文獻[5-8]介紹了通過改變load/store隊列的組織方式、相互關聯性、數據依賴的解決方法等方面減少功耗、面積和延遲，提高處理器性能。本文側重于在確定的隊列組織方式和策略下，探索適合本架構的隊列大小平衡，從而在特定架構下使硬件資源達到最高的利用率。

處理器設計空間探索通?；谀M器展開，通過測試大量不同的處理器參數，得到對應響應，進而指導硬件設計。有許多模擬器在研究中得到廣泛的應用，如SimpleScalar、GEM5、SimICS、PTLsim、McSimA+等，它們可在功能模擬、時序模擬、全系統(tǒng)模擬或應用級模擬等不同抽象層次對處理器進行仿真模擬。軟件模擬硬件的速度較慢，這是影響對設計空間探索的一大因素。本實驗中的模擬器對多種訪存子系統(tǒng)中隊列的進出時機、解決數據沖突策略進行了周期精確的詳細模擬，忽略了其余部件不必要的細節(jié)，在提高模擬速度的同時，有針對性地模擬架構設計，得到了更準確的結果。

通過模擬器可以得到設定配置的對應響應(如性能、功耗、某事件發(fā)生次數等信息)，理論上可以通過遍歷整個設計空間找到全局最優(yōu)解，然而因為資源、時間的限制和可配置參數的巨大組合數，使用軟件模擬或者硬件仿真得到整個設計空間的結果是不可能的。對于搜索空間非常大的問題，一般采用啟發(fā)式搜索[9](如A*、模擬退火等)或預測模型[10-12](如線性回歸、支持向量機等統(tǒng)計學或機器學習方法)方法。文獻[13]通過少數模擬點得到26個處理器參數的模型，通過擬合出的模型系數得到對性能影響較大的處理器部件，指導處理器優(yōu)化方向。自文獻[13]之后，預測模型的方法被廣泛運用到處理器設計空間探索中。本文使用預測模型的方法，通過分析和實驗，得出訪存流水線關鍵隊列大小之間的回歸模型。得到模型后無需再使用模擬器，便可以對整個設計空間中隊列不同大小組合的性能進行預測評估，擴大了可行的設計空間探索范圍，減少了設計空間探索的時間。

2 軟件模擬器與回歸模型混合建模

2.1 訪存流水線中關鍵隊列

在超標量處理器中，將已經準備好的訪存指令發(fā)射、執(zhí)行，很大程度上加快了處理器的執(zhí)行速度，但是訪存指令的推測執(zhí)行同時也會帶來數據沖突的問題。訪存子系統(tǒng)中，亂序執(zhí)行需要依靠LDQ(load queue)、STQ(store queue)和MMQ(memory issue queue)這幾個關鍵的隊列來實現并維護正確的數據關系[5]。

LDQ和STQ是訪存指令的重定序隊列，LDQ/STQ按照程序順序存放load/store指令。這2個隊列在程序運行過程中記錄已經在訪存流水線中且尚未提交的訪存指令的狀態(tài)，并保證已經寫回的訪存指令按序提交。同時，2個隊列中一些進入退出機制(如回滾、例外、正常提交等情況)保證了寫回寄存器和內存的數據的正確性。

MMQ是訪存流水線的第1級，按照一定的規(guī)則將其中未發(fā)射的訪存指令發(fā)射到訪存流水線中。MMQ中指令的退出由LDQ和STQ中指令的狀態(tài)進行決定。

從以上描述可以看出，這3個隊列的大小影響著能同時在訪存流水線中的訪存指令的數量，不同的查找和退出機制也會產生不同程度的回滾和例外的發(fā)生。

同時在流水線中的訪存指令越多，指令之間的時間重疊就會增多，從而增加了整體的執(zhí)行速度。但是回滾和例外也會因為流水線中指令數量的增加而增加，從而在一定程度上回滾導致更多發(fā)射出的指令無效。重新發(fā)射訪存指令浪費了時間和資源，例外更是會打斷指令的執(zhí)行，造成更大的損失。

模擬器假定ROQ(reorder queue，重排序隊列)、MMQ、STQ都無限大，其余配置都和目標機器相同，圖1(a)展示了不同LDQ的大小對運行時鐘周期數的影響。假定模擬器ROQ、MMQ、STQ以及其余配置都和目標機器相同，圖1(b)展示了改變LDQ的大小對運行時鐘周期數的影響。

(b) ROQ、MMQ、STQ和目標機器相同

(a) ROQ、MMQ、STQ無限大

從圖1可以看出，隨著LDQ的增大，總的時鐘周期數呈下降趨勢，在LDQ較大時，下降趨勢逐漸變緩直至幾乎不變。曲線所趨近的水平線是LDQ不出現滿阻塞情況下的時鐘周期數，也就是CPU不受訪存流水線隊列滿阻塞情況下的性能。這時候，程序執(zhí)行的周期數受到MissQ(miss queue)大小、Cache、程序本身數據相關的影響，以及定浮點隊列大小、流水線深度、流水線條數等CPU其他參數的影響。

在STQ、MMQ上做同樣的實驗，測得的結果和圖1類似，其原因也大致相同。

總的來說，隊列的增大在達到拐點之前對CPU性能有著正向的影響，且有著決定性的作用。

回滾和例外等因為亂序造成的因素雖然會帶來負影響，但影響程度不如增大隊列獲得的收益大。對于一些程序，可以從圖中看到，曲線下降趨勢中會有一些波動。通過模擬器統(tǒng)計的數據也能看出，在那些點受例外回滾的影響較大。

對比觀察圖1中(a)和(b)可發(fā)現，將其余3個隊列由無限大變?yōu)楹湍繕藱C器相同，曲線的拐點都向左移動。這說明，訪存流水線中隊列不阻塞的點受到其他隊列大小的影響。

表1、表2和表3分別是使用SPEC CPU 2000[14]中mcf程序load-store流，模擬器中的ROQ設為無限大，每次MMQ、LDQ、STQ中1個無限大、剩余2個隊列不斷改變大小得到這2個隊列大小的各種組合。按照其中一個隊列大小固定分類畫圖，觀察在一個隊列逐漸變化時，性能變?yōu)榉€(wěn)定的另一個隊列大小的變化。如表1所示，ROQ和MMQ無限大，當STQ為4時測得的LDQ大小變化對應的時鐘周期逐漸穩(wěn)定時LDQ大小是36。

表3 ROQ、LDQ無限大，MMQ大小不同時，對應的性能穩(wěn)定時STQ最小大小

表2 ROQ、STQ無限大，MMQ大小不同時，對應的性能穩(wěn)定時LDQ最小大小

表1 ROQ、MMQ無限大，STQ大小不同時，對應的性能穩(wěn)定時LDQ最小大小

任何一個隊列滿阻塞都會造成指令發(fā)射的停止，從而減少訪存流水線中的指令數。所以，隊列最佳大小會受到其他隊列大小的影響。通過單純改變一個隊列大小找到的該隊列最佳大小這一搜索方法是不妥當的。為了找到性能最佳折中點，需要將所有隊列的大小變化一起考慮。

2.2 軟件模擬器設計

不同的處理器會有不同的處理數據相關的策略。在訪存流水線關鍵隊列中，隊列之間相互訪問的方式、流水線中的指令回退的條件、檢測到數據錯誤后的處理方式、指令退出各個隊列的時機等策略都會有所不同[15，16]。這使得不同處理器即使隊列大小相同，隊列大小組合對性能的影響也是不一樣的。也就是說，策略不同的處理器的最佳隊列大小組合是不一樣的。亂序訪存的不同實現策略使得對每款處理器隊列大小有不同的要求，使用模擬器有針對性地探索隊列大小組合是一個很好的方法。

本文模擬器基于新一代的國產主流通用CPU訪存子系統(tǒng)設計[17，18]，是一款基于trace的周期精確的模擬器，其結構如圖2所示。

圖2 模擬器整體設計

模擬器的輸入是程序訪存流trace。訪存流是一個程序完整執(zhí)行過程中訪存指令的動態(tài)執(zhí)行信息，包括PC值、訪存地址、訪存指令類型和數據位寬。模擬器在RegMap部件進行trace的讀取并依據PC的差值進行其他指令的插入，進而模擬出完整的程序執(zhí)行流，發(fā)送往其余部件。程序可以根據要設計的處理器面向的領域和需求由設計人員自行選取，得到該程序的訪存流trace即可使用。

模擬器對訪存子系統(tǒng)相關部件等進行了詳細的描述，優(yōu)化掉處理器其他部分的無關細節(jié)避免影響模擬器速度。訪存子系統(tǒng)主要由訪存流水線和存儲器層次訪問部分組成。訪存發(fā)射隊列MMQ、訪存數據存取堆MemRegfile、訪存地址生成MemAddr、數據快表DTLB、數據Cache DCache和LDQ/STQ構成了訪存流水線各流水級。模擬器詳細模擬了這些部件的內部構成和它們之間的傳遞訪問關系，并實現了多種可選擇的處理沖突策略。模擬器中還實現了STLB和3級Cache層次以及預取、storefill等存儲器層次訪問過程中的相關機制。重排序隊列對訪存子系統(tǒng)影響較大，所以也對此進行了詳細的模擬。圖2中實線部分的方框均為模擬器重點模擬部件，箭頭連線表示數據或控制傳輸，虛線框為簡單模擬的處理器其他部件。

軟件模擬器除了實現便捷、靈活配置外，還可以在各個階段加入計數變量，在程序模擬過程中統(tǒng)計到多種需要觀察的值，從而掌握程序行為和處理器結構更全面的信息。

2.3 回歸模型設計

回歸模型是在定義域范圍內自變量和因變量之間關系的數學表示。線性回歸模型被廣泛用于參數重要性估計和定義域范圍內任意點的對應輸出變量預測[13]。

多元線性模型基本形式可以表示如下：

(1)

其中，y是因變量，β0是常數項，該公式有n個自變量Xi，每個自變量對應有系數βi，是誤差項。

對于復雜的情況，線性的關系往往是不夠的，對于每個Xi可以構建其非線性的映射，將變量先做Xi的非線性函數，然后進行線性的回歸擬合。

從前面關于訪存隊列大小對整體性能的影響分析來看，隊列本身的大小在一定范圍內對整體性能有著決定性的作用。這個范圍的大小除了取決于處理器其他部件的參數外，還取決于訪存子系統(tǒng)中其他隊列的大小。

為了體現出這種關系，首先構造Xi關于隊列大小的函數，再使用線性回歸方程構建成為處理器性能關于隊列大小的方程式。因為ROQ雖然不屬于訪存子系統(tǒng)中獨有，但該隊列對訪存過程和訪存隊列的提交有著很大的影響，所以模型中考慮將其作為特征變量。

考慮到相互之間的大小影響，Xi關于隊列大小的子函數采用比值的形式更合適。第1類函數使用2個隊列的比值體現隊列間直接的影響；第2類函數使用2個隊列的乘積與一個隊列的比體現這2個隊列和另一個隊列的相互影響；第3類函數使用3個隊列的乘積與一個隊列的比體現這4個隊列之間的關系。模型如式(2)所示。

(2)

在使用軟件模擬器的基礎上，回歸模型將進一步節(jié)省模擬時間，擴大設計空間探索范圍，以找到符合條件較優(yōu)的解。[19]

3 模擬器實現與模型構建

3.1 訪存子系統(tǒng)模擬器實現

模擬器使用C++語言實現，所有隊列共有特性繼承自父類，每個隊列不同的退出機制實現在隊列子類的退出函數中，相互訪問、例外、回滾等也實現在各自的函數中，具有良好的模塊性?？赡艽嬖诘囊恍┙鉀Q數據沖突問題的策略使用宏定義在對應函數中實現，方便配置不同硬件參數。

模擬器中的RegMap對應于硬件指令分配，開啟一個線程讀取訪存指令trace并產生虛擬非訪存指令，另一個線程按照處理器前端指令供應速率向ROQ、MMQ、LDQ和STQ分配指令。這部分可能會發(fā)生例外，導致流水線清空，所以使用2個指針記錄已分配出去的位置和尚未提交的位置。

如圖2所示，訪存流水線的第1級訪存發(fā)射隊列MMQ將源寄存器已就緒的指令按照一定順序發(fā)射到訪存流水線中。指令經過MemRegfile、MemAddr、TLB和Cache，最后進入LDQ或STQ中，如果有數據沖突，則觸發(fā)沖突的解決方法；否則，指令等待訪存或者提交。模擬器實現時，將訪問DTLB作為一級，下一級訪問DCache，模擬器時序和結果上等同于硬件中同時訪問DTLB和DCache，下一個時鐘周期進行Tag比較。

模擬器實現了可擴展、多層次的Cache結構，其大小、延遲、替換策略等均可配置。DCache失效請求由missq進行訪問管理和Cache重填。同時，還實現了數據預取和store fill機制。

串行執(zhí)行程序的軟件模擬器為了模擬硬件的并行運行情況，每個部件的輸入部分都必須是上一個時鐘周期的值，模擬的同一個時鐘周期內的結果不能被使用。軟件對于流水級的逆序描述滿足上述要求。模擬器整體功能部件運行偽代碼如表4所示。

表4 模擬器整體功能部件運行偽代碼

3.2 訪存子系統(tǒng)模擬器性能數據

模擬器所模擬目標處理器為本課題組所設計的新一代國產處理器，模擬器校準使用該處理器RTL設計代碼的FPGA原型驗證平臺產生的數據，該平臺與目標處理器有著極高的相似度。

實驗中使用程序測試集為SPEC CPU 2000，是由標準性能評價機構(standard performance ealuation corporation，SPEC)開發(fā)的用于評測CPU性能的基準程序測試組，是常用的通用處理器平臺測試集。

FPGA平臺運行的處理器雖然主頻與真實機器有著很大的差異，總體絕對時間上會不同，但是處理器的時鐘周期在FPGA上運行和ASIC芯片上是一樣的，所以校準和預測的數據統(tǒng)計都使用硬件計數器的時鐘周期數來表示處理器性能。在訪存周期方面，將模擬器訪存周期數設置成和FPGA訪存周期相同，圖3是這種情況下SPEC CPU 2000訪存流在模擬器和在FPGA平臺上運行硬件性能計數器得出的DCache失效率對比。圖4是二者的MMQ和STQ阻塞率對比，LDQ阻塞在FPGA和模擬器中都幾乎為0。由于亂序執(zhí)行的原因，模擬器運行的程序流和SPEC CPU 2000程序流不完全一樣，且模擬器僅有訪存子系統(tǒng)的詳細模擬，添加的指令的執(zhí)行時間情況也不相同，因此圖4中數據有些差異，但是差異并不算很大且趨勢相同。

圖4 SPEC CPU 2000 load-store流在模擬器和FPGA原型驗證平臺上的隊列滿阻塞率

圖3 SPEC CPU 2000 load-store流在模擬器和FPGA原型驗證平臺上的DCache失效率

3.3 模型擬合及誤差分析

實驗中模擬器分別改變MMQ、ROQ、LDQ、STQ大小組成不同的大小組合運行程序，得到相應的總時鐘周期。隊列大小的選取應在設計空間大小范圍內，并且分布較為均勻且組合隨機，以便對整個設計空間不同組合附近都有模擬，從而得到更符合模擬情況的模型參數。

將得到的數據順序隨機，然后分成5份，使用其中的4份數據依據2.3節(jié)提出的模型式(2)進行線性回歸擬合，得到各個參數，此時便得到了該處理器設計在測試程序下的性能模型，通過輸入隊列大小可以預測處理器在該程序集下的運行時鐘周期數。然后將未參與擬合的一份數據的隊列大小和擬合出來的參數帶入式(2)，計算得到預測時鐘周期數，與對應模擬器得到數據進行對比，得到測試集結果。將4份參與擬合的訓練數據的隊列大小輸入公式，得到的時鐘周期數和模擬器得到的周期數進行對比，得到訓練集結果。實驗使用交叉驗證，將這5份數據都作為一次測試數據，分別進行5次上述實驗，得到5組實驗結果。

表5為fma3d程序load-store流的數據5次交叉驗證的線性回歸擬合參數、平均誤差和標準差。表6是mcf、applu、twolf、gap和swim程序load-store流的數據5次交叉驗證平均誤差和標準差，限于篇幅沒有列出5次擬合的參數，每個程序5次的擬合參數結果相似。

表5 fma3d程序load-store流的數據5次交叉驗證結果

表5續(xù)

表6 mcf，applu，twolf，gap和swim程序load-store流的數據5次交叉驗證結果

實驗中，測試數據沒有參與訓練，其結果可以反映模型的準確程度。將訓練數據使用模型計算得到的結果和測試數據得到的結果相比較，保證參數的訓練沒有過擬合。使用交叉驗證，檢查結果是否穩(wěn)定，排除數據的偶然性。對SPECCPU測試集中不同類型的應用程序進行測試，模型結果表現都穩(wěn)定且誤差較小，表明該模型對于不同類型應用程序都有效。表5和表6實驗結果證明式(2)在這些程序所測得數據集上表現良好，誤差在10%以內，無過擬合現象，結果穩(wěn)定。

4 通過模型預測隊列大小

對于面向不同領域的處理器將會有著不同的設計需求，處理器在性能要求方面有著不同的評價標準。在使用本文所采用的方法時，可以根據設計修改模擬器的構成，使用面向該領域通用的程序測試集(如SPECCPU、EEMBC、COREMARK、LINPACK等)或者設計者根據需求構建的程序集，得到隊列大小配置相應的性能數據。采用本文提出的回歸模型，得到目標類應用相應的模型系數，即可使用該模型預測隊列大小和性能的關系，從而根據設計的需求得到合理的隊列大小組合。

已經擬合好的回歸模型可以預測整個設計空間范圍內不同隊列大小搭配的性能結果，使得對這部分的設計空間探索更準確和容易。

本實驗中，為了可視化數據，圖5展示了在ROQ128、MMQ32情況下LDQ和STQ不同大小的性能情況，ROQ128、LDQ64情況下MMQ和STQ不同大小的性能情況以及在ROQ128、STQ48情況下MMQ和LDQ不同大小的性能情況。

圖5 不同程序MMQ,ROQ,LDQ,STQ固定其中2個隊列大小，另外2個隊列大小對性能的影響

對于回歸模型，可以使用梯度下降等求最優(yōu)解的方法找到合適的隊列大小組合，從而達到資源面積利用和性能折中的最佳點。本實驗的設計空間中隊列大小參數都是整數，設計空間雖然大，但是有限個數的點以及回歸模型O(1)的計算復雜度，使得即使遍歷整個設計空間也十分快。快速得到整個設計空間中不同隊列大小的性能預測結果后，便可以很快找到符合面積功耗和性能要求的隊列大小配置。例如，設置條件為隊列大小每增10、 總時間減少1%以上則選擇改變隊列大小，根據這個條件找到最佳隊列大小組合如表7所示。表7中，有給定3個隊列，預測某程序達到滿足閾值條件的最小隊列值，或者給定1個、2個固定隊列大小，預測某程序達到滿足閾值條件的最佳隊列組合值。閾值的設定和隊列大小固定的數目可以根據實際需求改變，通過得到的模型快速評估性能，進而得到不同條件下最佳隊列大小的組合方案。

表7 使用線性回歸模型得到滿足閾值條件的最佳隊列大小組合

5 結 論

處理器訪存在程序運行時占有很大的時間消耗，超標量處理器設計過程中，為了實現訪存的推測執(zhí)行，通常使用一些隊列來保存各個訪存行為的信息。本文討論了訪存流水線中各隊列大小對性能的影響原因和方式，采用了軟件模擬器和分析模型結合的建模方法，對隊列大小組合進行探索，找到隊列大小組合平衡點使得硬件資源利用率達到最優(yōu)。本文提出了一種面向訪存子系統(tǒng)的回歸模型，并設計了相應的軟件模擬器，經實驗驗證，軟件模擬器能較準確地模擬訪存行為，回歸模型適合于訪存子系統(tǒng)的建模使用，對數據的擬合誤差較小且結果穩(wěn)定，可用于下一代處理器訪存子系統(tǒng)設計空間探索和對性能的預測。