賈 迅，胡向東，尹 飛

（上海高性能集成電路設(shè)計中心，上海201204）

1 引言

預(yù)取技術(shù)根據(jù)實(shí)現(xiàn)方式可分為軟件預(yù)取和硬件預(yù)取。軟件預(yù)取由程序員或編譯器在程序中插入預(yù)取指令實(shí)現(xiàn)預(yù)?。挥布A(yù)取則需要在處理器的微結(jié)構(gòu)中增加預(yù)取引擎，引擎根據(jù)程序執(zhí)行時的訪存行為，發(fā)出硬件預(yù)取請求實(shí)現(xiàn)預(yù)取功能。硬件預(yù)取對程序員透明，沒有兼容性問題，能利用程序的動態(tài)訪問特征。目前，國產(chǎn)處理器如申威、龍芯［3］等僅支持軟件預(yù)取。

硬件預(yù)取技術(shù)的實(shí)現(xiàn)面臨兩個方面的挑戰(zhàn)：一是實(shí)現(xiàn)復(fù)雜度與硬件開銷的降低；二是與處理器具體結(jié)構(gòu)特點(diǎn)的結(jié)合。申威處理器硬件數(shù)據(jù)預(yù)取技術(shù)的突破不僅可以直接提升申威處理器的性能，拓寬其在高性能計算、安全平臺以及服務(wù)器領(lǐng)域的應(yīng)用；同時也可以為硬件預(yù)取技術(shù)在其它國產(chǎn)處理器中的應(yīng)用提供參考。

2 硬件預(yù)取機(jī)制

程序訪存行為的特征是硬件預(yù)取的基礎(chǔ)，預(yù)取引擎利用訪存特征生成預(yù)取請求的方法稱為預(yù)取機(jī)制。學(xué)術(shù)界在研究過程中，針對規(guī)則的存儲訪問提出了多種硬件預(yù)取機(jī)制，包括順序預(yù)取、流預(yù)取［4］和跨步預(yù)?。?］，同時也研究了針對不規(guī)則存儲訪問的預(yù)取機(jī)制，例如關(guān)聯(lián)預(yù)取。

（1）順序預(yù)取是最簡單的預(yù)取機(jī)制，預(yù)取引擎總是預(yù)取當(dāng)前訪問Cache行的下一個Cache行，硬件實(shí)現(xiàn)開銷小，但對訪存帶寬的需求較高。

（2）跨步預(yù)取利用同一條訪存指令在不同循環(huán)迭代過程中，訪問地址中存在的固定步長進(jìn)行預(yù)取，因而適用于矩陣或數(shù)組結(jié)構(gòu)較為密集的高性能計算應(yīng)用。硬件實(shí)現(xiàn)需要使用訪問預(yù)測表。如圖1a所示，記錄訪問的地址、步長以及訪存指令的PC值。預(yù)取引擎檢測到固定步長的訪問時，發(fā)出預(yù)取請求，預(yù)取的地址為當(dāng)前訪問地址加步長。

（3）流預(yù)取對流訪問特征進(jìn)行預(yù)取，流訪問特征是指一段時間內(nèi)，程序訪問的Cache行地址呈現(xiàn)遞增或遞減的規(guī)律。這種訪問規(guī)律在科學(xué)計算和工程應(yīng)用中廣泛存在。硬件實(shí)現(xiàn)時，需要使用流識別緩沖（如圖1b所示）記錄一段時間內(nèi)訪存的Cache行地址。預(yù)取引擎識別到流訪問，則進(jìn)行預(yù)取。

（4）關(guān)聯(lián)預(yù)取利用訪存地址之間存在的關(guān)聯(lián)性進(jìn)行預(yù)取。Markov預(yù)取［6］機(jī)制屬于典型的關(guān)聯(lián)預(yù)取，它利用Markov模型對訪存缺失地址建模。硬件上使用關(guān)聯(lián)預(yù)測表（如圖1c所示）記錄與缺失地址相關(guān)聯(lián)的訪存地址。當(dāng)訪問缺失時，預(yù)取與缺失地址相關(guān)聯(lián)的所有地址。指針預(yù)取［7］也是關(guān)聯(lián)預(yù)取的一種，它利用load指令和將這條訪存指令的結(jié)果作為訪問地址的load指令之間存在的“生產(chǎn)－消費(fèi)”關(guān)系進(jìn)行預(yù)取，硬件上同樣采用關(guān)聯(lián)信息表保存這種依賴關(guān)系。

Figure 1 Structures of various prefetching mechanisms圖1 不同預(yù)取機(jī)制的硬件結(jié)構(gòu)

表1從“訪存模式”“設(shè)計復(fù)雜性”“典型應(yīng)用”三個方面對上述介紹的不同硬件預(yù)取機(jī)制進(jìn)行了總結(jié)?？梢钥闯觯瑸榱私档陀布?shí)現(xiàn)的復(fù)雜度和開銷，商用處理器大多采用了較為簡單的流預(yù)取和跨步預(yù)取。

首先將邊u11u12,um(2n-1)um(2n)染為k+2色,把邊u0(2n+2)u1(2n+1)染為k+1色,邊u(m-1)2um1染為色,其次把邊us(2n+1)us(2n+2)(s=1,3,…,m-2)染為色,把邊us1us2(s=3,5,…,m-2)染為色。

Table 1 Summary of various prefetching mechanisms表1 不同預(yù)取機(jī)制的總結(jié)

3 硬件預(yù)取的實(shí)現(xiàn)方法

3.1 申威處理器的訪存通路

新一代申威處理器核心采用超標(biāo)量架構(gòu)，支持亂序發(fā)射、推測執(zhí)行和雙訪存流水線技術(shù)。核心內(nèi)部一級指令Cache和數(shù)據(jù)Cache分離，兩者共享二級Cache，核外配置有大容量三級Cache。由于硬件數(shù)據(jù)預(yù)取技術(shù)主要與存儲訪問相關(guān)，因而申威處理器的訪存數(shù)據(jù)通路（如圖2所示）是預(yù)取技術(shù)實(shí)現(xiàn)的研究重點(diǎn)。

訪存指令由指令發(fā)射部件發(fā)往整數(shù)執(zhí)行部件執(zhí)行后，首先要進(jìn)入數(shù)據(jù)Cache控制部件中的仲裁單元。仲裁成功后的請求發(fā)往雙訪存流水線訪問數(shù)據(jù)Cache。若訪問命中，對于load類請求，數(shù)據(jù)從Cache裝入寄存器文件，供處理器計算使用；對于store類請求，數(shù)據(jù)從寄存器文件寫入Cache。若訪問缺失，則請求信息登記在缺失地址隊列MAF（Miss Address File）中，并發(fā)往二級Cache進(jìn)行后續(xù)處理。訪存請求在執(zhí)行過程中可能發(fā)生沖突，普通的訪存請求發(fā)生沖突時進(jìn)入重試緩沖，軟件預(yù)取請求發(fā)生沖突則進(jìn)入專門設(shè)置的預(yù)取緩沖。重試緩沖與預(yù)取緩沖中的請求會在流水線空閑時，以重試的方式仲裁上流水線執(zhí)行。

Figure 2 Memory access pipeline of Shenwei microprocessor圖2 申威處理器的訪存流水線

3.2 硬件預(yù)取的實(shí)現(xiàn)框架

硬件預(yù)取的實(shí)現(xiàn)需要在數(shù)據(jù)Cache控制部件中增加預(yù)取引擎。預(yù)取引擎通過記錄雙訪存流水線上請求執(zhí)行的信息，在對應(yīng)預(yù)取機(jī)制的指導(dǎo)下生成硬件預(yù)取請求。為了降低硬件預(yù)取實(shí)現(xiàn)的邏輯復(fù)雜度與硬件開銷，本文將引擎生成的硬件預(yù)取請求也放入預(yù)取緩沖，從而數(shù)據(jù)Cache控制部件對硬件預(yù)取請求的處理可以復(fù)用軟件預(yù)取請求仲裁上流水線，請求訪問一級數(shù)據(jù)Cache，二級、三級Cache對訪問缺失的請求進(jìn)行處理的整個數(shù)據(jù)通路，如圖3所示。

Figure 3 Implementation framework of hardware prefetching圖3 硬件預(yù)取的實(shí)現(xiàn)框架

為了復(fù)用流水線處理軟件預(yù)取的數(shù)據(jù)通路，硬件預(yù)取請求的格式與軟件預(yù)取請求必須完全兼容。數(shù)據(jù)Cache控制部件中，軟件預(yù)取請求的定義包括：請求的有效位、請求的類型以及請求訪問的Cache行地址，硬件預(yù)取請求的定義見表2。

Table 2 Definition of hardware prefetching requests表2 硬件預(yù)取請求的定義

由于申威處理器采用雙訪存流水線，預(yù)取引擎在一個時鐘周期內(nèi)需要同時處理兩條訪存指令的訪問信息。本文以流水線A為例介紹預(yù)取引擎（PFHEngine）與其它模塊，如請求處理流水線（PIPELINE）、預(yù)取緩沖（PREQUEUE）、指令重排序緩沖（ROB）、數(shù)據(jù)Cache標(biāo)記管理單元（DTAG）和頁表管理單元（DTBM）的接口信號，如圖4 所示。

Figure 4 Interface between a prefetching engine and other modules圖4 預(yù)取引擎與其它模塊的接口

預(yù)取引擎記錄的訪問信息包括：訪存指令的PC值、請求的類型、地址、請求訪問Cache是否命中等。具體實(shí)現(xiàn)時，引擎內(nèi)部可以靈活采用不同的硬件預(yù)取機(jī)制。下文以流預(yù)取例，驗證預(yù)取引擎實(shí)現(xiàn)框架的正確性。

3.3 流預(yù)取的實(shí)現(xiàn)

流預(yù)取機(jī)制的實(shí)現(xiàn)需要在硬件上設(shè)置流識別緩沖以檢測一段時間內(nèi)的流訪問。流識別緩沖條目記錄的信息包括訪問的Cache行地址、條目的狀態(tài)以及訪問缺失的次數(shù)。具體的信號及含義如表3所示。

Table 3 Information recorded in the stream detection buffer表3 流識別緩沖記錄的信息

流識別緩沖中所有條目初始化時均置為無效態(tài)INV，后續(xù)的狀態(tài)轉(zhuǎn)換見圖5。其中，“淘汰”是指一段時間內(nèi)，處理器未訪問條目對應(yīng)的流?！跋蚯?向后訪問缺失”是指訪問缺失的地址等于條目記錄的Cache行地址加1 或減1。當(dāng)訪問缺失的次數(shù)大于流識別閾值時，條目進(jìn)入預(yù)取狀態(tài)。此時，處理器訪問流中一個新的Cache行，會觸發(fā)對下一個Cache行的預(yù)取。

4 性能評測

本文的實(shí)驗環(huán)境由處理器模型、基準(zhǔn)測試程序和硬件仿真加速器三部分構(gòu)成。為了真實(shí)測試硬件數(shù)據(jù)預(yù)取技術(shù)對申威處理器訪存性能的提升，本文采用申威處理器某芯片完整的邏輯設(shè)計作為處理器模型，芯片中各存儲層次的容量和訪問延遲如表4所示。本文采用Verilog硬件描述語言實(shí)現(xiàn)了硬件預(yù)取功能，其中流識別緩沖條目數(shù)為8，流識別閾值為2。

Figure 5 State transitions in the stream detection buffer圖5 流識別緩沖條目的狀態(tài)轉(zhuǎn)換

Table 4 Memory hierarchy parameters表4 各存儲層次的參數(shù)

本文采用SPEC CPU2000基準(zhǔn)測試程序集，其廣泛應(yīng)用于桌面系統(tǒng)和單處理器服務(wù)器的性能測試。SPEC CPU2000 由12 道整數(shù)測試程序和14道浮點(diǎn)測試程序組成，這些程序都從真實(shí)的用戶程序演變而來，因而可以真實(shí)反映不同程序的訪存特征。

為了進(jìn)一步提高實(shí)驗結(jié)果的準(zhǔn)確性，本文以Cadence公司的Palladium XP GXL系列［8］硬件仿真加速器作為實(shí)驗平臺，其提供了微處理器模型的仿真環(huán)境，并可以準(zhǔn)確反映處理器仿真運(yùn)行過程中的相關(guān)性能參數(shù)。本文以SPEC CPU2000測試程序在硬件仿真加速器上運(yùn)行完成所需周期數(shù)作為預(yù)取機(jī)制性能評價的標(biāo)準(zhǔn)。本文測試了單獨(dú)使用軟件預(yù)取、硬件預(yù)取和軟硬件混合預(yù)取的性能，整數(shù)、浮點(diǎn)測試程序的結(jié)果分別如圖6和圖7所示。

Figure 6 Integer performance improved by stream prefetching in Shenwei microprocessor圖6 流預(yù)取對申威處理器整數(shù)性能的提升

Figure 7 Float performance improved by stream prefetching in Shenwei microprocessor圖7 流預(yù)取對申威處理器浮點(diǎn)性能的提升

可以看出，對于整數(shù)程序，單獨(dú)使用軟件預(yù)取、硬件預(yù)取對申威處理器的性能提升效果分別為2.99%和7.79%，混合預(yù)取的性能提升為8.16%。對于浮點(diǎn)程序，單獨(dú)使用軟件預(yù)取、硬件預(yù)取對性能的提升效果分別為8.52%和11.20%，混合預(yù)取的性能提升為14.91%。硬件預(yù)取技術(shù)的使用可以將目前申威處理器的整數(shù)性能平均提升5.17%，最高提升28.88%（181.mcf）；浮點(diǎn)性能平均提升6.39%，最高提升30.11%（173.applu）。另外，對于課題178.galgel、191.fma3d，硬件預(yù)取的使用可以有效解決編譯器插入軟件預(yù)取因預(yù)取時機(jī)不合適而導(dǎo)致性能下降的問題。

對于硬件開銷和時序的評估，本文采用Synopsys公司的Design Compiler工具在1.6GHz、40nm 工藝下對數(shù)據(jù)Cache控制部件進(jìn)行邏輯綜合，以綜合的面積作為評價預(yù)取機(jī)制硬件開銷的標(biāo)準(zhǔn)，同時對時序結(jié)果進(jìn)行檢查，綜合過程中的參數(shù)配置見表5。

Table 5 Parameters used for logic synthesis表5 邏輯綜合的參數(shù)設(shè)置

硬件開銷的評估結(jié)果如表6所示，實(shí)現(xiàn)流預(yù)取所需的硬件開銷僅為申威處理器核心面積的0.14%。另外，根據(jù)綜合的時序報告，本文硬件預(yù)取的設(shè)計完全滿足1.6GHz下的時序要求。

Table 6 Implementation cost of hardware prefetching表6 數(shù)據(jù)預(yù)取技術(shù)實(shí)現(xiàn)所需的硬件開銷

5 結(jié)束語

硬件數(shù)據(jù)預(yù)取技術(shù)是緩解“存儲墻”問題的有效手段之一，在商用處理器中廣泛應(yīng)用。本文結(jié)合申威處理器“雙訪存流水線”“支持軟件預(yù)取”“集成多級Cache”的結(jié)構(gòu)特點(diǎn)，以降低邏輯設(shè)計的復(fù)雜度和硬件開銷為目標(biāo)，提出了預(yù)取引擎實(shí)現(xiàn)的整體框架，并通過流預(yù)取機(jī)制的實(shí)現(xiàn)驗證了其可行性。本文對硬件數(shù)據(jù)預(yù)取技術(shù)在國產(chǎn)處理器中的實(shí)現(xiàn)方式和應(yīng)用價值進(jìn)行了有益探索。

［1］ Intel Corporation.Intel 64and IA－32architecture optimization reference manual［EB/OL］.［2014－12－05］.http：//www.intel.com/content//www /us/en/documents/manuals/64－ia－32－architectures－optimization－manual.pdf.

［2］ Tendler J M，Dodson J S，F(xiàn)ields J S，et al.POWER4system microarchitecture［J］.IBM Journal of Research and Development，2002，46（1）：5－25.

［3］ LOONGSON Technology Corporation Limited.User mannual for Loongson 3B1500microprocessor［EB/OL］.［2014－12－05］.https：//www.loongsin.cn.（in Chinese）

［4］ Jouppi N P.Improving direct－mapped Cache performance by the addition of small fully－associative cache and prefetching buffers［C］∥Proc of the 17th Annual International Symposium on Computer Architecture，1990：364－373.

［5］ Chen T F，Baer J L.Effective hardware－based data prefetching for high－performance processors［J］.IEEE Transactions on Computers，1995，44（5）：609－623.

［6］ Joseph D，Grunwald D.Prefetching using Markov predictors［J］.IEEE Transactions on Computer，1999，48（2）：121－133.

［7］ Roth A，Moshovos A，Sohi G S.Dependence based prefetching for linked data structures［C］∥Proc of the 8th International Conference on Architectural Support for Programming Language and Operating Systems，1998：115－126.

［8］ Cadence Design Systems，Inc.Cadence Palladium XP verification computing platform［EB/OL］.［2014－12－05］.www.cadence.com/rl/resource/technical＿briefs/palladium＿xp＿tb.pdf.

附中文參考文獻(xiàn)：

［3］ 龍芯中科.龍芯3B1500處理器用戶手冊［EB/OL］.［2014－12－05］.https：//www.loongson.cn.