楊大為，王　爽，王　丹

（中國(guó)電子科技集團(tuán)公司第四十七研究所，沈陽(yáng)110032）

基于32位微處理器系統(tǒng)架構(gòu)的Cache設(shè)計(jì)

楊大為，王爽，王丹

（中國(guó)電子科技集團(tuán)公司第四十七研究所，沈陽(yáng)110032）

近年來(lái)隨著芯片技術(shù)的發(fā)展，嵌入式微處理器迎來(lái)了新的機(jī)遇，廣泛應(yīng)用于通信、多媒體、網(wǎng)絡(luò)以及娛樂(lè)等方面。處理器的處理速度發(fā)展迅速，近乎于指數(shù)增長(zhǎng)，然而內(nèi)存的處理速度增長(zhǎng)緩慢，因此內(nèi)存的存儲(chǔ)速度成為了影響嵌入式微處理器系統(tǒng)性能的主要瓶頸，為了均衡成本、性能和功耗，高速緩存Cache廣泛應(yīng)用于嵌入式系統(tǒng)中。首先介紹Cache的工作原理，其次對(duì)直接映射、全關(guān)聯(lián)映射、組相聯(lián)映射三種策略進(jìn)行比較分析，然后分析行大小與命中率的關(guān)系，最后設(shè)計(jì)一款基于32位微處理器系統(tǒng)架構(gòu)的高速緩存Cache。

高速緩存；組相聯(lián)；行填充；命中率；寫(xiě)通；寫(xiě)回

1　引　言

近年來(lái)，嵌入式微處理器發(fā)展迅速，在移動(dòng)終端、多媒體、網(wǎng)絡(luò)通信等方面應(yīng)用尤其廣泛，對(duì)處理器性能的要求也越來(lái)越高。為了彌補(bǔ)內(nèi)存速度較低的問(wèn)題，Cache作為連接內(nèi)核和內(nèi)存的橋梁，對(duì)于提高處理器訪問(wèn)程序和數(shù)據(jù)的速度［1］，起到了至關(guān)重要的作用。

2　Cache工作原理

Cache位于主存與內(nèi)核之間，用于提高存儲(chǔ)系統(tǒng)的性能，提高處理器訪問(wèn)主存的效率。Cache的功能完全用硬件來(lái)實(shí)現(xiàn)，對(duì)于軟件人員是完全透明的。如果處理器內(nèi)核可以在Cache中找到需要的數(shù)據(jù)，叫做hit（命中）；如果沒(méi)有找到，叫做miss（未命中）。

當(dāng)Cache命中時(shí)，可以很快將所需數(shù)據(jù)返回給內(nèi)核；當(dāng)Cache未命中時(shí)，需對(duì)Cache進(jìn)行更新，從主存中重新把需要的數(shù)據(jù)搬移進(jìn)Cache，再返回給處理器內(nèi)核。Cache存儲(chǔ)體由塊即Cache行（line）構(gòu)成，塊是Cache與主存之間進(jìn)行數(shù)據(jù)交換的基本單位。

由于程序具有局部性特點(diǎn)，所以Cache 具有時(shí)間局部性和空間局部性［2］的特點(diǎn)。時(shí)間局部性即如果某個(gè)數(shù)據(jù)被訪問(wèn)，那么在不久的將來(lái)它很可能再次被訪問(wèn)?？臻g局部性即如果某個(gè)數(shù)據(jù)被訪問(wèn)，那么與它相鄰的數(shù)據(jù)很可能很快被訪問(wèn)。每次miss都把被訪問(wèn)地址相鄰塊大小的數(shù)據(jù)調(diào)入到Cache中，能夠提高Cache的命中率。圖1為cache工作原理圖。

圖1　Cache工作原理

3　Cache設(shè)計(jì)

3.1地址映像方式

由于內(nèi)存的空間遠(yuǎn)遠(yuǎn)大于Cache，因此內(nèi)存中的數(shù)據(jù)與Cache為多對(duì)一的映射關(guān)系。設(shè)計(jì)時(shí)采用組相聯(lián)映像方式［3］。組相聯(lián)是一種較為通用的映射策略，結(jié)合了直接映射訪問(wèn)速度快、實(shí)現(xiàn)簡(jiǎn)單的優(yōu)點(diǎn)和全相聯(lián)映射命中率高的優(yōu)點(diǎn)。首先，將高速緩存分成若干大小相等的塊，每一塊稱作一個(gè)way（路）；接著用類似于直接映射方式中的分頁(yè)方法將主存按照一個(gè)way的大小進(jìn)行分頁(yè)；然后將高速緩存中的每一個(gè)way都分成大小相同的line，包含每一個(gè)way中相同位置的line的集合稱作一個(gè)set（組）。在進(jìn)行數(shù)據(jù)填充時(shí)，主存的每一個(gè)數(shù)據(jù)塊只能映射到高速緩存中固定的set上，即在set之間采用直接映射的方式；但是主存的每一個(gè)數(shù)據(jù)塊可以映射到組內(nèi)的任意一個(gè)way上，即在set內(nèi)部采用全相聯(lián)映射方式。

3.2Cache種類

本設(shè)計(jì)采用獨(dú)立［4］cache結(jié)構(gòu)，即指令Cache與數(shù)據(jù)Cache分開(kāi)。數(shù)據(jù)寫(xiě)入Cache時(shí)采用可配置策略，即寫(xiě)通（Write－Through）還是寫(xiě)回（Write－Back）由CP15協(xié)處理器寄存器的設(shè)置決定。并且采用讀分配策略［5］，也就是說(shuō)只有在讀操作下有命中時(shí)才會(huì)產(chǎn)生行填充（linefill）。

3.3替換算法

如果在讀取數(shù)據(jù)或指令的過(guò)程中發(fā)生Cache miss，則需要從主存中調(diào)入包含被訪問(wèn)數(shù)據(jù)的新塊到Cache中。而這個(gè)新塊可以裝入到任一路Cache中的對(duì)應(yīng)塊中。當(dāng)可以裝入這個(gè)新塊的幾路Cache塊都已經(jīng)裝滿時(shí)，就啟動(dòng)Cache替換算法［6］，從那些塊中找出一個(gè)不常用的塊，把它調(diào)回到主存中，騰出一個(gè)塊存放從主存中調(diào)來(lái)的新塊。本設(shè)計(jì)中的替換算法有兩種：隨機(jī)替換算法和輪轉(zhuǎn)法［7］。

隨機(jī)替換算法通過(guò)一個(gè)偽隨機(jī)數(shù)發(fā)生器產(chǎn)生一個(gè)偽隨機(jī)數(shù)，用新塊將編號(hào)為該偽隨機(jī)數(shù)的Cache塊替換掉。這種算法很簡(jiǎn)單，易于實(shí)現(xiàn)。但是它沒(méi)有考慮程序的局部性特點(diǎn)，因而效果較差。

輪轉(zhuǎn)法設(shè)計(jì)一個(gè)計(jì)數(shù)器，利用該計(jì)數(shù)器依次選擇將要被替換出去的Cache塊。這種算法容易預(yù)測(cè)最壞情況下Cache的性能。但它有一個(gè)明顯的缺點(diǎn)，在程序發(fā)生很小的變化時(shí)，可能造成Cache平均性能的急劇變化。

3.4Cache大小

Cache大小設(shè)計(jì)為4KB－64KB之間可配置。每塊Cache的標(biāo)簽（TAG）和每Cache行的索引（Index）由內(nèi)核地址組成，其形成方法如表1所示。

表1　Cache對(duì)內(nèi)核地址的處理

3.5Cache結(jié)構(gòu)

本設(shè)計(jì)采用的Cache結(jié)構(gòu)［8］為4路組相聯(lián)結(jié)構(gòu)，以8KB大小為例，每路cache有2KB大小，每塊Cache有8個(gè)字大小，所以每路Cache的塊數(shù)為64。圖2為8KB 4路組相聯(lián)Cache結(jié)構(gòu)示意圖。

在cache實(shí)現(xiàn)中，Icache分為DataRam、TagRam、ValidRam，Dcache分為DataRam、TagRam、ValidRam和DirtyRam。它們分別由不同的Ram實(shí)現(xiàn)。下面以8KB大小為例說(shuō)明cache的Ram實(shí)現(xiàn)。

DataRam：每路的大小為2KB，由于設(shè)計(jì)中數(shù)據(jù)寬度是32位的，所以Cache的Ram要用32位數(shù)據(jù)寬度的Ram實(shí)現(xiàn)。這樣每個(gè)DataRam的大小為512W?？紤]到Cache的高速要求，在實(shí)現(xiàn)中不會(huì)將一個(gè)DataRam對(duì)應(yīng)一路Cache來(lái)實(shí)現(xiàn)，而是將一路Cache分散在四個(gè)DataRam中，這樣一次linefill的數(shù)據(jù)可以在最短的時(shí)鐘周期內(nèi)全部寫(xiě)入到DataRam中，保證了Cache讀取數(shù)據(jù)及替換的高速要求。分配原則如表2所示。

圖2　8KB 4路組相聯(lián)Cache結(jié)構(gòu)

表2　DataRam結(jié)構(gòu)

TagRam：每塊cache八個(gè)字?jǐn)?shù)據(jù)的Tag是相同的，所以每塊cache只有一個(gè)Tag，這樣一片cache對(duì)應(yīng)的TagRam寬度為22位，深度為64（同cache每片的塊數(shù)）。四片cache對(duì)應(yīng)四個(gè)Tag Ram。

ValidRam：Icache和Dcache分別有一個(gè)ValidRam與之對(duì)應(yīng)，深度為一路cache塊數(shù)的四分之一，寬度為24位，0－15位存放Valid數(shù)據(jù)，16－23位存放RRCount數(shù)據(jù)。RRCount用在輪轉(zhuǎn)替換策略中，指示cache塊在上次替換中的路數(shù)。ValidRam的格式如表3所示。

表3　ValidRam結(jié)構(gòu)

BitsFunction［15］Index x＋3，Valid bit Way 3［17：16］Index x，RRCount［1：0］［19：18］Index x＋1，RRCount［1：0］［21：20］Index x＋2，RRCount［1：0］［23：22］Index x＋3，RRCount［1：0］

DirtyRam：Dcache有一個(gè)DirtyRam與之對(duì)應(yīng)，深度為一路cache塊的大小，寬度為八位，每一位表示半行（四個(gè)W）cache是否有Dirty數(shù)據(jù)，格式如表4所示。

表4　DirtyRam結(jié)構(gòu)

3.6Cache控制器結(jié)構(gòu)

Cache控制器的設(shè)計(jì)包括了接口設(shè)計(jì)（與CP15及Sysctl接口、與Cache存儲(chǔ)器接口、與總線接口（BIU））、替換模塊設(shè)計(jì)、行填充緩沖器（FB）及寫(xiě)操作替換緩沖器（EWB）設(shè)計(jì)、Cache標(biāo)簽處理等模塊的設(shè)計(jì)，Cache控制器結(jié)構(gòu)如圖3所示。

圖3　cache控制器結(jié)構(gòu)框圖

Cache設(shè)計(jì)中的接口時(shí)序如圖4－6所示。

圖4　Cache與SysControl、CP15接口時(shí)序圖

圖5　CacheBIU接口時(shí)序圖

圖6　CacheRam接口時(shí)序圖

Cache控制器的功能實(shí)現(xiàn)依靠狀態(tài)機(jī)設(shè)計(jì)完成。本Cache設(shè)計(jì)主要有6個(gè)狀態(tài)機(jī)，一個(gè)主狀態(tài)機(jī)，伴隨5個(gè)次狀態(tài)機(jī)完成Cache控制器所有功能的實(shí)現(xiàn)。這6個(gè)狀態(tài)機(jī)的設(shè)計(jì)過(guò)程如下：

Cache狀態(tài)產(chǎn)生狀態(tài)機(jī)（見(jiàn)圖7）：產(chǎn)生Cache當(dāng)前狀態(tài)。有讀存儲(chǔ)器請(qǐng)求時(shí)，在Cache中沒(méi)有命中，并且沒(méi)有取消操作時(shí)進(jìn)入Cache的行填充狀態(tài)機(jī)進(jìn)行l(wèi)inefill操作。有讀存儲(chǔ)器請(qǐng)求時(shí)，在FB命中，但是命中無(wú)效，說(shuō)明linefill沒(méi)有完成，需要的數(shù)據(jù)還沒(méi)有進(jìn)入BIU，并且沒(méi)有取消操作時(shí)進(jìn)入FB狀態(tài)機(jī)進(jìn)行等待。否則數(shù)據(jù)就在FB中保持準(zhǔn)備好狀態(tài)。根據(jù)上面三種情況和一些控制信號(hào)來(lái)判斷當(dāng)前的Cache是否是準(zhǔn)備好狀態(tài)。

圖7　Cache狀態(tài)產(chǎn)生狀態(tài)機(jī)

行填充狀態(tài)機(jī)（見(jiàn)圖8）：請(qǐng)求BIU傳遞8個(gè)linefill數(shù)據(jù)。在LF1狀態(tài)下判斷BIU是否正在line-fill一組數(shù)據(jù)或者是否有EWB數(shù)據(jù)還沒(méi)有通過(guò)BIU寫(xiě)到外部存儲(chǔ)器中，如果有就停留在LF1狀態(tài)，如果沒(méi)有或操作完成就進(jìn)入PEND狀態(tài)。在PEND狀態(tài)中，查詢總線的反饋信號(hào)，總線反饋后表示可以進(jìn)行l(wèi)inefill操作，進(jìn)入FB2狀態(tài)開(kāi)始linefill，并無(wú)條件進(jìn)入IDLE狀態(tài)，并且在IDLE狀態(tài)下可以繼續(xù)剩下的linefill操作。

FB狀態(tài)機(jī)（見(jiàn)圖9）：在IDLE狀態(tài)下判斷是否有l(wèi)inefill請(qǐng)求或者如果有CP15的FB排空命令就進(jìn)入LF1狀態(tài)。在LF1狀態(tài)下，判斷BIU是否正在linefill一組數(shù)據(jù)或者是否有EWB數(shù)據(jù)還沒(méi)有通過(guò)BIU寫(xiě)到外部存儲(chǔ)器中，如果有就停留在LF1的狀態(tài)，否則進(jìn)入FB1狀態(tài)。在FB1狀態(tài)下，使能FB排空控制，將FB中的四個(gè)字寫(xiě)入Cache存儲(chǔ)器中，然后進(jìn)入FB2狀態(tài)。在FB2狀態(tài)下，將FB中的另外四個(gè)字寫(xiě)入Cache存儲(chǔ)器中并無(wú)條件進(jìn)入IDLE狀態(tài)，完成linefill填充FB的過(guò)程。所以在整個(gè)過(guò)程中，F(xiàn)B中的內(nèi)容不被寫(xiě)到Cache中，直到新的linefill情況發(fā)生時(shí)FB中的內(nèi)容才被寫(xiě)入到Cache存儲(chǔ)器中以便FB存放新的linefill數(shù)據(jù)，并且八個(gè)數(shù)據(jù)的寫(xiě)操作在兩個(gè)周期內(nèi)完成。

圖8　行填充狀態(tài)機(jī)

圖9　FB狀態(tài)機(jī)

寫(xiě)替換狀態(tài)機(jī)（見(jiàn)圖10）：在IDLE狀態(tài)下，如果有l(wèi)inefill發(fā)生并且將被替換的行中有dirty數(shù)據(jù)，就會(huì)進(jìn)入下一個(gè)狀態(tài)。可能進(jìn)入的下一個(gè)狀態(tài)是WAIT還是WB1則是根據(jù)當(dāng)前EWB是否是空來(lái)決定，如果當(dāng)前EWB不是空，則EWB處于busy狀態(tài)，這時(shí)的下一個(gè)狀態(tài)就應(yīng)該進(jìn)入WAIT狀態(tài)，否則發(fā)出讀取被替換行物理地址信息，讀取被替換行的低四個(gè)字，然后進(jìn)入WB1狀態(tài)。在WB1狀態(tài)下，讀取被替換行的高四個(gè)字，寫(xiě)EWB的低四個(gè)字，申請(qǐng)BIU傳輸EWB數(shù)據(jù)，進(jìn)入WB2狀態(tài)。在WB2狀態(tài)下，寫(xiě)EWB的高四個(gè)字，這時(shí)如果寫(xiě)數(shù)據(jù)緩沖器（PWB）中的一個(gè)數(shù)據(jù)是被替換行中的一個(gè)數(shù)據(jù)，則PWB中的這個(gè)數(shù)據(jù)寫(xiě)入到EWB中，進(jìn)入EWB2狀態(tài)。在EWB2狀態(tài)下，如果PWB中的另一個(gè)數(shù)據(jù)是被替換行中的一個(gè)數(shù)據(jù)，則此數(shù)據(jù)也寫(xiě)入到EWB中。

圖10　寫(xiě)替換狀態(tài)機(jī)

寫(xiě)替換總線狀態(tài)機(jī)（見(jiàn)圖11）：在IDLE狀態(tài)下，如果有替換請(qǐng)求，表示此時(shí)有新的數(shù)據(jù)填充到EWB中，需要總線將EWB中的數(shù)據(jù)寫(xiě)到外部存儲(chǔ)器中，這時(shí)就會(huì)進(jìn)入WB2狀態(tài)。在WB2狀態(tài)下，判斷總線當(dāng)前是否正在進(jìn)行l(wèi)inefill的數(shù)據(jù)傳輸，如果沒(méi)有，就進(jìn)入EWB2狀態(tài)，否則停留在WB2狀態(tài)等待。在EWB2狀態(tài)下，申請(qǐng)總線傳輸數(shù)據(jù)，并進(jìn)入PEND狀態(tài)。在PEND狀態(tài)下，表示當(dāng)前有一組EWB數(shù)據(jù)沒(méi)有存儲(chǔ)到外部存儲(chǔ)器中，當(dāng)總線完成傳輸后回到IDLE狀態(tài)。

圖11　寫(xiě)替換總線狀態(tài)機(jī)

CP15控制狀態(tài)機(jī)（見(jiàn)圖12）：在IDLE狀態(tài)下，有CP15對(duì)Cache的操作控制，但不是使整個(gè)Cache無(wú)效的操作，就會(huì)進(jìn)入下一個(gè)狀態(tài)PW。在PW狀態(tài)下，判斷是否有未處理的操作，有寫(xiě)替換操作則保持在PW狀態(tài)，linefill操作則進(jìn)入FB1狀態(tài)，否則進(jìn)入OP1狀態(tài)。FB1狀態(tài)下，無(wú)條件進(jìn)入FB2狀態(tài)。在FB2狀態(tài)下，判斷本次linefill是否結(jié)束，如果沒(méi)有結(jié)束，保持FB2狀態(tài)不變，否則進(jìn)入OP1狀態(tài)。在OP1狀態(tài)下，表示所有沒(méi)有處理的操作全部結(jié)束，并判斷CP15清除信號(hào)，如果信號(hào)有效，表示CP15沒(méi)有其他操作，狀態(tài)返回到IDLE狀態(tài)，否則進(jìn)入OP2狀態(tài)。在OP2狀態(tài)下，無(wú)條件進(jìn)入OP3狀態(tài)后進(jìn)入OP4狀態(tài)。在OP4狀態(tài)下，如果是清除Cache操作，并且有dirty數(shù)據(jù)時(shí)就會(huì)進(jìn)入OP5狀態(tài)，否則返回到IDLE狀態(tài)。在OP5狀態(tài)下，要將Cache中的dirty數(shù)據(jù)通過(guò)EWB寫(xiě)到外部存儲(chǔ)器中，完成后進(jìn)入IDLE狀態(tài)，否則停留在OP5狀態(tài)等待dirty數(shù)據(jù)寫(xiě)替換完成。

圖12　CP15控制狀態(tài)機(jī)

4　仿真驗(yàn)證

為了對(duì)設(shè)計(jì)的32位4路組相聯(lián)Cache進(jìn)行驗(yàn)證，需要搭建一個(gè)虛擬仿真驗(yàn)證平臺(tái)，該平臺(tái)的示意圖如圖13所示。

圖13　仿真平臺(tái)示意圖

該平臺(tái)包括以下幾個(gè)部分：

（1）內(nèi)核，實(shí)現(xiàn)32位微處理器的核心功能；

（2）Cache模塊，包括4路組相聯(lián)Cache控制器和存儲(chǔ)器，完成Cache功能，是被測(cè)試模塊；

（3）仿真環(huán)境測(cè)例，使用匯編語(yǔ)言或者C語(yǔ)言編寫(xiě)，然后轉(zhuǎn)為*.rcf文件的格式，存放在Memory中；

（4）仿真用的Memory模型，用于存放仿真程序的二進(jìn)制文件，存放仿真過(guò)程中產(chǎn)生的中間數(shù)據(jù)；另外該Memory模型也是該仿真平臺(tái)的主存，使能Cache功能后，可以通過(guò)Cache進(jìn)行緩存；

（5）仿真環(huán)境所需的復(fù)位信號(hào)（Rst）及時(shí)鐘信號(hào)（CLK）；

（6）在仿真過(guò)程中，可依據(jù)不同的仿真命令生成不同格式的仿真波形，waveform模型完成這部分功能。

5　結(jié)束語(yǔ)

介紹了Cache的基本原理，闡述了一款高速緩存Cache的設(shè)計(jì)，包括映射方式、種類、替換算法的設(shè)計(jì)以及Cache和Cache控制器的結(jié)構(gòu)設(shè)計(jì)?？梢杂糜?2位微處理器系統(tǒng)架構(gòu)中，解決慢速主存給處理器內(nèi)核造成的存儲(chǔ)器訪問(wèn)效率低下的瓶頸問(wèn)題。

［1］萬(wàn)木楊.大話處理器－處理器基礎(chǔ)知識(shí)讀本［M］.北京：清華大學(xué)出版社，2011.WAN Mu－yang.Topic Processor－Processor Basic Knowledge［M］.BeiJing：Tsinghua University Press，2011.

［2］Peter Grun.Nikil Dutt.Alexandru Nicolau.Memory Architecture Exploration for Programmable Embedded Systems［M］.New York：Kluwer Academic Publishers，2003.

［3］William Stallings.Computer Organization and Architechture［M］.New Jersey：Prentice Hall，2010.

［4］Vincent P.Heuring，Harry F.Jordan.Computer Organization and Design（The Hardware／Software Interface）Edition［M］.New York：Morgan Kaufmann，2008.

［5］Bruce Jacob，Spencer W.Ng，David T.Wang.Memory Systems（Cache，DRAM，Disk）［DB／OL］.Burlington：Morgan Kaufmann，2008.

［6］D.Sweetman.See MIPS Run Linux［M］.New York：Elsevier，2007.

［7］CoreLink Level 2 Cache Controller L2C－310 Technical Reference Manual［DB／OL］.ARM Ltd.2012.

［8］杜春雷.ARM體系架構(gòu)與編程［M］.北京：清華大學(xué)出版社，2003.Du Chun－lei.ARM Architecture and Programming［M］.BeiJing：Tsinghua University Press，2003.

Design of Cache Based on 32－Bit CPU System Architecture

Yang Da－wei，Wang Shuang，Wang Dan
（The 47th Research Institute of China Electronics Technology Group Corporation，Shenyang 110032，China）

With the development of the chip technology，the embedded processor catches the new opportunities，which is widely used in such fields as communication，multimedia，networking，entertainment，etc.The processing speed of the processor nearly increases in a certain index，while the slower processing speed of the memory becomes the major bottleneck of MCU system characteristics.Considering of balancing cost，performance and power，the cache widely is used in MCU system.In this paper，the principle of the cache is firstly described，the direct－mapping，full－associate cache and set－associate cache are compared as well.Then，the relationship between line size and hit rate is analyzed.Lastly，a cache，based on 32 bits processor architecture，is designed.

Cache；Set－associate；Linefill；Hit rate；Write－Through；Write－Back

10.3969／j.issn.1002－2279.2016.01.002

TN492

B

1002－2279（2016）01－0005－06

楊大為（1977－），男（回族），遼寧省沈陽(yáng)市人，高級(jí)工程師，主研方向：集成電路設(shè)計(jì)。

2015－10－29