處理器中非阻塞cache技術(shù)的研究

孟銳

（西安工業(yè)大學(xué) 北方信息工程學(xué)院，陜西 西安 710025）

自從第一個(gè)微處理器問世以來，微處理器技術(shù)已經(jīng)成為現(xiàn)代信息化社會(huì)中信息技術(shù)的核心，其研究已經(jīng)成為各國在競(jìng)爭(zhēng)中的一個(gè)熱點(diǎn)，現(xiàn)在的微處理器在功能、規(guī)模、工藝以及工作頻率等性能上越來越優(yōu)良。由于我國致力于處理器的研究比較晚，盡管其發(fā)展速度很快，在市場(chǎng)上仍然沒有辦法與外國芯片競(jìng)爭(zhēng)，因此研制具有自主知識(shí)產(chǎn)權(quán)的處理器具有極其重要的意義。

1 非阻塞cache技術(shù)的引用

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

當(dāng)訪問數(shù)據(jù)cache的請(qǐng)求在未命中時(shí)，數(shù)據(jù)cache就會(huì)由于等待從低一級(jí)存儲(chǔ)器中取回失效的數(shù)據(jù)而阻塞發(fā)射下一條訪問存儲(chǔ)器的請(qǐng)求，因此導(dǎo)致整個(gè)處理器的工作被阻塞。以上兩種情況的存在，嚴(yán)重降低處理器的性能，最終導(dǎo)致blocking data cache成為高性能處理器的性能瓶頸。

非阻塞cache技術(shù)是一種通過減少缺失代價(jià)，挖掘處理器其他執(zhí)行部件的操作和訪問存儲(chǔ)器的操作之間并行性的一種技術(shù)，對(duì)數(shù)據(jù)cache以及整個(gè)處理器系統(tǒng)的性能都有很大影響。因此研究高性能流水結(jié)構(gòu)非阻塞數(shù)據(jù)cache對(duì)于提高處理器性能具有重要的意義。

2 非阻塞cache技術(shù)的研究

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

在該技術(shù)中常用的方法有：

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

當(dāng)所有的MSHR寄存器被使用完，cache就會(huì)阻塞處理器。隨著MSHR寄存器的入口數(shù)目的增加，cache的設(shè)計(jì)復(fù)雜度急速增加。研究結(jié)果表明，使cache取得最大性能的MSHR的最佳數(shù)目是4個(gè)[3]。

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

圖1 一個(gè)4級(jí)流水結(jié)構(gòu)的非阻塞cache結(jié)構(gòu)Fig.1 Non-blocking cache structure of the four level pipeline structure

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

圖2 非阻塞cache結(jié)構(gòu)圖Fig.2 Non-blocking cache structure

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

3 非阻塞數(shù)據(jù)cache的流水線沖突解決策略

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

4 基于“龍騰”R2的非阻塞數(shù)據(jù)cache的設(shè)計(jì)

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

表1 數(shù)據(jù)cache相關(guān)指令Tab.1 data cache instruction

5 保持cache一致性策略

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

表2 MEI狀態(tài)定義Tab.2 MEI state defintion

在“龍騰”R2中實(shí)現(xiàn)了對(duì)內(nèi)存一致性協(xié)議的檢測(cè)。MEI的狀態(tài)轉(zhuǎn)移與當(dāng)前的MEI狀態(tài)以及內(nèi)存存儲(chǔ)標(biāo)志W(wǎng)IM都有關(guān)系。在非阻塞數(shù)據(jù)cache中不支持寫操作缺失下的寫分配（write-allocated）[4]， 數(shù)據(jù) cache為寫回 cache， 所以在新的cache一致性協(xié)議中就沒有無效態(tài)到修改態(tài)之間的狀態(tài)變遷，這樣新的數(shù)據(jù)cache的就是寫回且不支持寫分配的數(shù)據(jù)cache。

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

圖3 cache一致性狀態(tài)轉(zhuǎn)換圖Fig.3 Cache coherency policy state transition diagrams

6 cache的替換策略

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

7 數(shù)據(jù)cache驗(yàn)證結(jié)果

對(duì)cache功能的驗(yàn)證采用了Synopsys公司的VCS仿真平臺(tái)和Vera驗(yàn)證平臺(tái)表3列出了數(shù)據(jù)cache的驗(yàn)證結(jié)果。

表3 數(shù)據(jù)cache功能驗(yàn)證覆蓋率Tab.3 data cache functional verification coverage

8 結(jié)論

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

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

[2]胡孔陽，陳鵬，桑紅石.多線程非阻塞cache設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(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技術(shù)的VTS雷達(dá)PPI顯示優(yōu)化設(shè)計(jì)[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.