處理器中非阻塞cache技術的研究

孟銳

（西安工業大學 北方信息工程學院，陜西 西安 710025）

自從第一個微處理器問世以來，微處理器技術已經成為現代信息化社會中信息技術的核心，其研究已經成為各國在競爭中的一個熱點，現在的微處理器在功能、規模、工藝以及工作頻率等性能上越來越優良。由于我國致力于處理器的研究比較晚，盡管其發展速度很快，在市場上仍然沒有辦法與外國芯片競爭，因此研制具有自主知識產權的處理器具有極其重要的意義。

1 非阻塞cache技術的引用

提高處理器性能可以從兩方面進行：一方面提高指令并行性，同時執行多條不相關的指令。二通過提高主頻，加快指令執行速度[1]。超標量處理器的研究就是從第一方面來提高處理器性能，采用流水線結構，通過增加取值、發射帶寬以及復制執行部件實現多條指令的并行執行，而在引入的這些技術中對數據的使用要求比較高，因此需要高性能的cache來滿足。

當訪問數據cache的請求在未命中時，數據cache就會由于等待從低一級存儲器中取回失效的數據而阻塞發射下一條訪問存儲器的請求，因此導致整個處理器的工作被阻塞。以上兩種情況的存在，嚴重降低處理器的性能，最終導致blocking data cache成為高性能處理器的性能瓶頸。

非阻塞cache技術是一種通過減少缺失代價，挖掘處理器其他執行部件的操作和訪問存儲器的操作之間并行性的一種技術，對數據cache以及整個處理器系統的性能都有很大影響。因此研究高性能流水結構非阻塞數據cache對于提高處理器性能具有重要的意義。

2 非阻塞cache技術的研究

該技術的核心思想是指在訪問cache缺失的情況下允許后續訪問存儲器的操作繼續進行。當訪問cache未命中時，一方面可以像其他級的cache發出請求，另外不阻止后續對cache的訪問，對于命中和未命中都按照命中的方式進行處理，從而可以節省平均訪問存儲器的時間，提高處理器的性能[2]。非阻塞cache技術在哈佛結構的數據cache和指令cache都能夠使用，本文主要針對數據cache進行介紹。

在該技術中常用的方法有：

1)采用缺失狀態保持存儲器（MSHR)，該寄存器的作用可以用來跟蹤和記錄缺失的cache塊的信息，一般包括：①缺失的cache塊在內存的物理地址；②缺失塊按特定的替換算法應該被存放到cache的什么地方；③所有訪問這個cache塊缺失的指令碼。同時使用該寄存器可以查看是否發生了二次缺失的情況，即當前正在處理的缺失塊是否有指令需要再次訪問該cache塊，如果發生則認為該cache塊發生了二次缺失。因此在指令訪問cache發生缺失，首先采用全相聯的方式查找所有的MSHR入口，如果發現有匹配的MSHR入口，則說明發生了二次缺失，就不會給這個缺失的請求分配新的MSHR入口，而是僅僅給它在load miss queue和storemiss queue中分配一個入口。這樣就達到了將多個缺失合并為一個缺失的目的，而且這種做法對于提高cache的命中率和減少總線接口單元的帶寬壓力也有好處。

當所有的MSHR寄存器被使用完，cache就會阻塞處理器。隨著MSHR寄存器的入口數目的增加，cache的設計復雜度急速增加。研究結果表明，使cache取得最大性能的MSHR的最佳數目是4個[3]。

2)數據cache流水線劃分。對cache的組織采用流水線結構可以提高數據cache的吞吐率，也是實現非阻塞cache技術的關鍵。圖1的數據cache支持非阻塞機制，這是一個4路兩端口的數據cache。數據cache具備4個TAG RAM，以及4個DATA RAM，整個數據cache的大小32KB，具有兩端口的4級流水線，每個周期可以執行2個load/store操作，這個非阻塞cache支持4個cache掛起的缺失操作，保持流水線不阻塞[4]。其中，當store操作的數據是cache hit的情形，數據就會被寫到cache的RAM中，即使兩個store操作具備相同的地址，也不會也導致數據cache的流水線阻塞。當store操作的數據是cache-miss的情形，數據將會被寫合并store data buffer，目的是為了減少總線的事務。合理的cache流水線劃分對于cache指令的執行以及cache的控制復雜度有比較大的影響。

圖1 一個4級流水結構的非阻塞cache結構Fig.1 Non-blocking cache structure of the four level pipeline structure

3)多體交叉編址存儲器。圖2-6是“龍芯”處理器中的非阻塞Cache結構示意圖[5]。這是2路組相聯的cache，每個cache的塊是8個字。為了支持數據cache流水方式的讀寫訪問流水操作，消除流水線中的結構沖突，將cache的每一路的TAG RAM和DATA RAM分成4個bank。但是對多體RAM會增加cache的功耗，嵌入式處理器中對功耗的要求比較高，所以這項技術的使用受到一些限制。

圖2 非阻塞cache結構圖Fig.2 Non-blocking cache structure

4)缺失情況下，讀優先于寫操作。對于支持寫回的cache，若要進行換入，換出，就遵循先換入，再換出的原則，即等到取回的數據從內存回來后，再把寫回緩沖器中的被cache淘汰的cache數據寫回到內存。

3 非阻塞數據cache的流水線沖突解決策略

對cache采用合理的流水線劃分是實現非阻塞cache技術的關鍵，因此對流水線技術中出現的數據相關的沖突解決策略是關鍵。為了充分發揮流水線性能，就需要有效地解決微處理器中流水線的沖突問題。相關是指引起指令流中的一條指令在指定的時鐘周期內停滯（stall）執行的事件。相關的發生將會引起流水線的斷流或延遲，降低微處理器的性能。在流水線中相關主要包括了數據相關、資源相關、控制相關3種沖突問題。其中數據相關是指后續指令的執行需要前面指令的數據，從而導致了后續指令在執行過程當中需要等待前面指令提供數據的停滯。資源相關是指多條指令在執行過程當中對相同資源的同時訪問而造成的競爭造成指令周期的停滯。控制相關是由于轉移指令的執行而產生的斷流情況。針對這3種相關問題可以采用不同的方法解決，在流水線的設計中，一方面減少相關的發生，增長微處理器處理的連續指令長度，來充分發揮流水線的性能；另一方面合理安排流水線中各級的操作，降低指令斷流引起的延遲，減少由于指令相關所帶來的性能損失。

4 基于“龍騰”R2的非阻塞數據cache的設計

“龍騰”R2是由西北工業大學航空微電子中心在“十五”期間研制成功兩款面向航空領域的嵌入式處理器。該處理器中的指令cache采用了三級流水線技術，增強了取指令的能力。IEU部件通過LSU部件把訪問cache的存取指令發射給數據cache。LSU部件對數據cache共有16種類型的訪問請求，如表1所示，把cache中將這些操作都歸為讀操作、寫操作和cache控制指令3類。讀操作每次讀取1個字，存操作可以以單字節、雙字節、三字節和字4種數據大小進行。當數據cache需要替換時，把整個cache行（32個字）寫回內存。

表1 數據cache相關指令Tab.1 data cache instruction

5 保持cache一致性策略

保持cache數據的一致性是cache設計中的一個關鍵問題。常見的解決cache一致性問題的方法有：監聽協議、目錄表法。高性能處理器目前最常用的方法是MESI監聽協議，其性能在眾多一致性協議中是最高的。MESI協議是一種采用寫——無效方式的監聽協議。它為每個cache塊提供兩個狀態，用于當前該處所處的狀態：修改態、專有態、共享態或者無效態當中的一個狀態。在龍騰R2中采用了MESI[6]協議的一個子集，忽略了共享態S（shared）狀態，即MEI一致性協議。表2描述了MEI的狀態。

表2 MEI狀態定義Tab.2 MEI state defintion

在“龍騰”R2中實現了對內存一致性協議的檢測。MEI的狀態轉移與當前的MEI狀態以及內存存儲標志WIM都有關系。在非阻塞數據cache中不支持寫操作缺失下的寫分配（write-allocated）[4]， 數據 cache為寫回 cache， 所以在新的cache一致性協議中就沒有無效態到修改態之間的狀態變遷，這樣新的數據cache的就是寫回且不支持寫分配的數據cache。

圖3是在非阻塞cache中采用的新的一致性協議，是在原來的MEI的基礎上增加了一個已分配的狀態，這個狀態用來表明在缺失的情況下需要使用替換算法為這個cache行分配一個空位，用來防止后面的指令繼續訪問該缺失的cache行。使用“已分配”這個狀態來表明這一路的cache塊是處于從內存加載的路上，以防發生錯誤。

圖3 cache一致性狀態轉換圖Fig.3 Cache coherency policy state transition diagrams

6 cache的替換策略

在cache設計中，采用效率較高的替換算法對于提高cache的性能非常重要，多種替換算法一直被深入的研究，但是常用的也僅有LRU和PLRU等少數幾種。LRU（leastrecently used）算法依據程序訪問的時間局部性原理，每次替換最近最少被使用的cache塊。隨著cache相聯度的增大，PLRU是LRU算法的一種近似實現,它使用一個二叉樹結構保存cache塊的歷史訪問順序。Hassan Ghasemzadeh等人發現PLRU算法在一些情況下會做出錯誤決定，并認為PLRU算法的最大缺點是二叉樹結構的頂層節點不能包含底部葉子節點的足夠信息[7]，并提出了MPLRU算法。在“龍騰”R2中采用了提出一種新的替換算法，即PLRU-0替換算法。Pseudo-LRU(PLRU)的原理：使用一個二叉樹結構保存cache塊的歷史訪問順序信息。它相對于LRU的優點是存儲信息只需要3位，節省了存儲空間，而堆棧實現的LRU則需要8位。

7 數據cache驗證結果

對cache功能的驗證采用了Synopsys公司的VCS仿真平臺和Vera驗證平臺表3列出了數據cache的驗證結果。

表3 數據cache功能驗證覆蓋率Tab.3 data cache functional verification coverage

8 結論

文中研究了非阻塞cache技術缺失下如何命中的原理，討論了在流水線結構中采用非阻塞cache技術提高cache的命中率，減少缺失代價從而提高處理器的性能，通過在“龍騰”R2中采用該技術的功能驗證說明了該技術的可行性。

[1]黃海林，徐彤，范東睿.嵌入式處理器中降低Cache缺失代價設計方法研究[J].小型微型計算機系統，2006(11):2077-2081.HUANG Hai-lin，XU Tong，FAN Dong-rui.Research on reducing cachemiss penalty of embedded processor[J].Small Microcomputer System，2006（11）:2077-2081.

[2]胡孔陽，陳鵬，桑紅石.多線程非阻塞cache設計[J].微電子學與計算機，2012（5）:144-147.HU Kong-yang，CHEN Peng，SANG Hong-shi.Design of Amultithreading non-blocking cache[J].Microelectronics and Computer，2012（5）:144-147.

[3]Kroft D.Lockup-free instruction fetch/prefetch Cache organization[J].In Proc of the 8th Annual Int.Symp.On Computer Architecture,1981:81-87.

[4]Hayakawa F，okano H，Suga A.A8-WAY VLIW Embedded Multimedia Processor with Advanced Cache Mechanism[C]//IEEE,2002:213-216.

[5]PowerPC Microprocessor Family:The Programming Environ ments For 32-BitMicroprocessors[S].Rev.2,Motorola Inc，Dec.2001.

[6]Jouppi N P.CacheWrite Policies and Performance[C]//08-S4-7495/93 1993 IEEE.

[7]Ghasemzadeh H，Mazrouee S，Kakoee M R.Modified Pseudo LRU Replacement Algorithm:Proceedings of the 13th Annual IEEE International Symposium and Workshop on Engineering of Computer Based Systems[C].IEEE [S.l.]:[s.n.].2006:371-376.

[8]劉鐸，黃曉燕.基于Direct3D技術的VTS雷達PPI顯示優化設計[J].電子科技，2014（5）:5-7，11.LIU Duo，HUANG Xiao-yan.Optimization design of VTS radar PPI display based on Direct3D Technology[J].Electronic Science and Technology，2014（5）:5-7，11.