一種基于Cache機(jī)制的嵌入式Flash控制器設(shè)計(jì)

曹　健　李凌浩　黃雅東　吳中海　張　興,2

1(北京大學(xué)軟件與微電子學(xué)院　北京 100871)2(北京大學(xué)信息科學(xué)技術(shù)學(xué)院　北京 100871)

?

一種基于Cache機(jī)制的嵌入式Flash控制器設(shè)計(jì)

曹健1,2*李凌浩1黃雅東1吳中海1張興1,2

1(北京大學(xué)軟件與微電子學(xué)院北京 100871)2(北京大學(xué)信息科學(xué)技術(shù)學(xué)院北京 100871)

嵌入式Flash(eFlash)在SoC中的運(yùn)用日益廣泛，而Flash較慢的讀取速度與處理器高頻取指之間的矛盾愈發(fā)突出。針對(duì)該問(wèn)題，在Flash控制器中引入Cache機(jī)制，并運(yùn)用組相聯(lián)映射、優(yōu)化的“最近最少使用”LRU(Least Recently Used)替換算法、流水預(yù)填充結(jié)構(gòu)對(duì)Cache進(jìn)行多方面優(yōu)化。與未加入Cache機(jī)制的Flash控制器相比，加入Cache機(jī)制的Flash控制器可使處理器取指時(shí)間節(jié)省38%。

嵌入式FlashCache組相聯(lián)映射LRU流水預(yù)填充

0　引　言

嵌入式Flash(eFlash)是一種和傳統(tǒng)CMOS工藝相兼容，內(nèi)嵌于芯片內(nèi)部的非易失性存儲(chǔ)器。eFlash以低成本、高安全性等特點(diǎn)，在SoC領(lǐng)域應(yīng)用廣泛，常作為系統(tǒng)的程序存儲(chǔ)器。然而，eFlash較慢的讀取速度，易成為系統(tǒng)瓶頸。特別是隨著工藝特征尺寸的縮小，eFlash與處理器頻率差距逐漸增大。本文針對(duì)這一問(wèn)題，在Flash控制器中引入Cache機(jī)制，縮小了兩者的速度差距。同時(shí)Cache復(fù)用了控制器內(nèi)部邏輯，節(jié)約資源的同時(shí)便于工具綜合優(yōu)化。

Cache由Wilkes于1965年提出[1]，其原理是根據(jù)程序局部性原則，通過(guò)小容量速度快的存儲(chǔ)器緩存部分指令或數(shù)據(jù)，以減少處理器對(duì)慢速大容量存儲(chǔ)器的訪問(wèn)次數(shù)。Smith于1982年提出了Cache設(shè)計(jì)的三個(gè)基本參數(shù)——容量、關(guān)聯(lián)度、行長(zhǎng)，分析了容量與程序循環(huán)體，關(guān)聯(lián)度、行長(zhǎng)與Cache命中率之間的關(guān)系，以及它們對(duì)整體性能的影響[2]，為以后的Cache設(shè)計(jì)提供了基本思路。Puzak從Cache替換算法的角度進(jìn)行分析，提出了經(jīng)典的LRU替換算法[3]。Chan等從預(yù)填充的角度，提出了輔助緩存結(jié)構(gòu)[5]，解決了“Cache 污染”的問(wèn)題，提供了另一種提升Cache性能的思路。2008年，Baker等提出了4至6路組相聯(lián)動(dòng)態(tài)分配的映射方法[10]，可有效降低1%的Cache塊沖突。Ricardo等對(duì)Cache可重構(gòu)技術(shù)進(jìn)行研究[11]，通過(guò)改變Cache容量、關(guān)聯(lián)度、替換算法等結(jié)構(gòu)參數(shù)，實(shí)現(xiàn)Cache對(duì)不同應(yīng)用場(chǎng)景下的動(dòng)態(tài)或靜態(tài)重構(gòu)。Shan等于2011年提出了EBA-LRU-SEQ算法[12]，該算法在LRU算法基礎(chǔ)上加入分支預(yù)取表，可降低54%的Cache功耗。

本文將Cache引入Flash控制器，通過(guò)映射結(jié)構(gòu)、替換算法和預(yù)填充三方面的優(yōu)化，對(duì)Cache性能進(jìn)行提升。在映射結(jié)構(gòu)上，以“容量”、“關(guān)聯(lián)度”、“行長(zhǎng)”為研究起點(diǎn)，通過(guò)實(shí)驗(yàn)對(duì)比，選擇性能、面積最優(yōu)的4組4路組相聯(lián)映射。在替換算法上，本文對(duì)LRU算法進(jìn)行改進(jìn)，新的算法以更小的硬件消耗取得與LRU相似的性能。在預(yù)填充方面，將文獻(xiàn)[5]的輔助緩存與流水線相結(jié)合，實(shí)現(xiàn)了處理器的順序無(wú)間斷取指。實(shí)驗(yàn)數(shù)據(jù)表明，與未加入Cache機(jī)制的Flash控制器對(duì)比，Cache機(jī)制的引用可節(jié)省38%的取指時(shí)間。

1　Flash控制器架構(gòu)

Flash控制器的整體架構(gòu)如圖1所示，采用哈佛結(jié)構(gòu)的處理器通過(guò)指令總線從Cache取指，通過(guò)外設(shè)總線配置專用寄存器(sbus_sfr)傳遞Flash操作命令。主狀態(tài)機(jī)(main_fsm)根據(jù)SFR配置，對(duì)“編程擦除控制器”(pe_ctrl)及Cache進(jìn)行調(diào)度。“編程擦除控制器”(pe_ctrl)在取得Flash總線控制權(quán)后，進(jìn)行相應(yīng)的Flash操作。由于主狀態(tài)機(jī)的統(tǒng)一調(diào)度及Flash讀邏輯的復(fù)用(fl_rd)，相較于Cache和Flash控制器分離的設(shè)計(jì)，內(nèi)嵌Cache節(jié)約了資源，減少了模塊間的信號(hào)交互，利于綜合工具的優(yōu)化。

圖1　Flash控制器架構(gòu)

2　內(nèi)嵌Cache設(shè)計(jì)

內(nèi)嵌Cache結(jié)構(gòu)如圖2所示，其主緩存容量為256 Byte，映射結(jié)構(gòu)為4組(Set)4路(Way)組相聯(lián)，每路大小為128 bit。其替換算法采用基于LRU的改進(jìn)算法。另外，其內(nèi)置128 bit的輔助流水緩存(Victim Way)，用于實(shí)現(xiàn)順序無(wú)間斷取指。

圖2　內(nèi)嵌Cache結(jié)構(gòu)

Cache工作流程為Code Bus發(fā)起讀操作，根據(jù)Code Bus地址Index段選中四組中的某一組，然后將該組所有路的TAG與Code Bus的TAG段進(jìn)行匹配，確定Cache命中或缺失。當(dāng)命中某路，用地址Offset段選通128 bit數(shù)據(jù)中的某個(gè)32 bit數(shù)據(jù)輸出。如果4路均未命中，而命中輔助緩存，則緩存數(shù)據(jù)輸出，并按替換算法將該數(shù)據(jù)寫(xiě)入某組某路，同時(shí)開(kāi)始新的預(yù)取指。如果均未命中，則掛起總線，進(jìn)行Flash讀操作，讀取的數(shù)據(jù)按替換算法寫(xiě)入某組某路輸出，并判斷是否進(jìn)行預(yù)取指操作。

2.1地址映射方式

文獻(xiàn)[2]提出Cache的映射方式需由容量、關(guān)聯(lián)度、行(路)長(zhǎng)度三個(gè)參數(shù)來(lái)確定。根據(jù)程序局部性原則，當(dāng)其他參數(shù)不變，Cache容量可裝載程序最大循環(huán)體時(shí)，其性能最優(yōu)[1]。通過(guò)對(duì)項(xiàng)目嵌入式應(yīng)用程序的統(tǒng)計(jì)，其循環(huán)體大多介于20 byte至192 byte之間，考慮到存儲(chǔ)的冗余量，確定Cache容量為256 byte。從文獻(xiàn)[6]的實(shí)驗(yàn)對(duì)比可知：當(dāng)緩存容量小于16K byte時(shí)，組相聯(lián)映射配合替換算法的性能遠(yuǎn)優(yōu)于直接映射，故緩存組織形式確定為組相聯(lián)映射。另外，由于所選Flash最慢讀取速率為30 M，而處理器工作頻率為120 M，且每次取指32 bit，為實(shí)現(xiàn)輔助緩存的流水結(jié)構(gòu)，確定每一“路”(Way)的寬度128 bit。上述變量確定后，關(guān)聯(lián)度則是通過(guò)各組合代碼實(shí)現(xiàn)后的實(shí)驗(yàn)對(duì)比來(lái)確定。

實(shí)驗(yàn)的測(cè)試向量由循環(huán)嵌套程序組成，Cache缺失率是通過(guò) Synopsys公司的VCS對(duì)電路cache_miss信號(hào)的高脈沖個(gè)數(shù)統(tǒng)計(jì)獲得(該信號(hào)高脈沖表明Cache缺失)。如表1所示，“2組8路組相聯(lián)”性能最優(yōu)，但由于實(shí)現(xiàn)“2組8路組相聯(lián)”需復(fù)雜的TAG比較器，導(dǎo)致資源開(kāi)銷(xiāo)大，且時(shí)序不能滿足實(shí)際需求，故折中選擇“4組4路”組相聯(lián)方式，其結(jié)構(gòu)如圖2所示。在該結(jié)構(gòu)中，將指令地址劃分為三段，Index用于選擇“組”號(hào)；TAG為“路標(biāo)”，用于確定某路命中或Cache缺失；當(dāng)某路被命中后，用Offset選通128 bit數(shù)據(jù)中的某個(gè)32 bit數(shù)據(jù)。

表1　組相聯(lián)性能對(duì)比

2.2替換算法

文獻(xiàn)[3]對(duì)Cache的各種替換算法進(jìn)行對(duì)比，并提出了LRU替換算法，即根據(jù)最近最少使用原則進(jìn)行替換。其原理是N路組相聯(lián)需在每一路之前添加一個(gè)N位計(jì)數(shù)器記錄每一路的使用情況，采用循環(huán)計(jì)數(shù)，增量為1。當(dāng)需要替換時(shí)，將計(jì)數(shù)值最小的路替換。相較偽隨機(jī)或FIFO算法，LRU體現(xiàn)了程序局部性的特點(diǎn)，故性能更優(yōu)，但其復(fù)雜度相對(duì)較高，硬件資源消耗大且關(guān)鍵路徑長(zhǎng)。

本設(shè)計(jì)對(duì)傳統(tǒng)的LRU算法進(jìn)行優(yōu)化，如表2、表3所示。優(yōu)化后的算法面積及關(guān)鍵路徑比LRU減少10%，而性能與LRU相似。該算法與LRU的主要區(qū)別是記錄每行最近最多使用的情況，從而使計(jì)數(shù)器的位寬減半。算法整體思路是在每“路”之前增加“l(fā)og2N”(N為“路”的數(shù)量)位的計(jì)數(shù)器，用于記錄各“路”的使用頻率。當(dāng)某“路”被命中時(shí)，其計(jì)數(shù)器變?yōu)樽畲笾担词褂妙l率最高，其他各路按一定原則計(jì)數(shù)值遞減；當(dāng)Cache缺失時(shí)，將計(jì)數(shù)值為0的“路”進(jìn)行替換。使用頻率的計(jì)數(shù)原則如圖3所示，首先將所有計(jì)數(shù)器的值由大到小進(jìn)行初始化；之后如果命中計(jì)數(shù)值最大的一路，則所有計(jì)數(shù)器的值保持不變；如果命中非最大值的任意一路，比該路計(jì)數(shù)值大的其它各路均減1，同時(shí)該路的計(jì)數(shù)值更新為最大值；如果所有路均為命中，則將計(jì)數(shù)為0的路更新為最大值，其他各路均減1。

表2　各算法面積對(duì)比

表3　各算法性能對(duì)比

圖3　優(yōu)化的LRU替換算法

以4路組相聯(lián)為例，如圖4的“Step 0”所示，每路之前有2 bit計(jì)數(shù)器，各計(jì)數(shù)器初始值從2’b11至2’b00依次遞減，2’b11表示該路使用頻率最多，2’b00表示該路使用頻率最低；在“Step1”中，當(dāng)命中“Way2”后，其計(jì)數(shù)值變?yōu)?’b11，其他各路計(jì)數(shù)器進(jìn)行遞減；當(dāng)Cache缺失發(fā)生，如“Step 2”所示，“Way 3”將被替換，其計(jì)數(shù)值變?yōu)?’b11，其他各路計(jì)數(shù)器進(jìn)行遞減。

圖4　優(yōu)化的LRU算法圖例

表2中的各項(xiàng)數(shù)據(jù)是通過(guò)對(duì)不同算法進(jìn)行代碼實(shí)現(xiàn)，并使用TSMC 90 nm標(biāo)準(zhǔn)單元庫(kù)進(jìn)行物理綜合得到，其綜合工具為Synopsys的Design Complier。表3中各算法Cache缺失率的獲得與表1所對(duì)應(yīng)的實(shí)驗(yàn)相同。

2.3預(yù)填充策略

預(yù)填充是一種提前從慢速存儲(chǔ)器中讀取數(shù)據(jù)寫(xiě)入Cache，以降低Cache缺失率的操作。其主要分為順序預(yù)填充和非順序預(yù)填充。順序預(yù)填充僅按地址順序進(jìn)行預(yù)取，不需對(duì)處理器取指進(jìn)行預(yù)測(cè)，硬件實(shí)現(xiàn)簡(jiǎn)單，適合嵌入式系統(tǒng)[9]。預(yù)填充可提高取指效率，但也會(huì)引入“Cache污染”的問(wèn)題，即預(yù)取數(shù)據(jù)未被處理器所用，而被替換的數(shù)據(jù)卻是真正所需的指令。為解決該問(wèn)題，出現(xiàn)了輔助緩存[5]及犧牲緩存[4]等輔助結(jié)構(gòu)。輔助緩存的思路是將預(yù)取數(shù)據(jù)先寫(xiě)入輔助緩存，當(dāng)Cache命中該數(shù)據(jù)后，再按替換算法寫(xiě)入主緩存區(qū)。犧牲緩存則是將預(yù)取的數(shù)據(jù)寫(xiě)入主緩存區(qū)，將被替換的數(shù)據(jù)寫(xiě)入犧牲緩存。兩種方法均可有效地解決“Cache污染”的問(wèn)題。

本文將“順序預(yù)取”、“輔助緩存”與“流水控制”相結(jié)合，實(shí)現(xiàn)了處理器順序讀取下的不間斷取指。其原理是根據(jù)Flash與處理器工作頻率相差4倍的關(guān)系，選定Flash讀數(shù)據(jù)寬度、輔助緩存寬度為指令長(zhǎng)度的4倍即128 bit，使一次消耗4個(gè)系統(tǒng)時(shí)鐘的Flash讀取可輸出4條指令。當(dāng)處理器取走第一條指令時(shí)，控制邏輯將輔助緩存的數(shù)據(jù)轉(zhuǎn)移至主緩存，并開(kāi)始新一輪的輔助緩存填充，從而實(shí)現(xiàn)流水預(yù)取指操作。具體時(shí)序如圖5所示。

圖5　流水預(yù)填充時(shí)序

T0時(shí)刻，Code Bus(AHB總線)讀使能(p2c_rd)有效，對(duì)A0地址進(jìn)行讀操作。假定此次操作為Cahce缺失，Cache拉低c2p_ready信號(hào)掛起處理器。同時(shí)，對(duì)Flash發(fā)起讀操作(c2m_rd拉高)，進(jìn)行第一次填充。

T1時(shí)刻，c2m_rd拉高后4個(gè)系統(tǒng)時(shí)鐘(clk)，F(xiàn)lash輸出128 bit數(shù)據(jù)，將A0對(duì)應(yīng)數(shù)據(jù)輸出(c2p_rdata)。

T2時(shí)刻，因A0數(shù)據(jù)已輸出，可視為一次Cache命中，故128 bit Flash數(shù)據(jù)直接寫(xiě)入主緩存的某一路(way_x)。因此時(shí)處理器還在順序取指，故Cache繼續(xù)進(jìn)行Flash流水預(yù)取(c2m_flash一直有效)，T3時(shí)刻將Flash數(shù)據(jù)輸出。

T4時(shí)刻，假定處理器進(jìn)行跳轉(zhuǎn)取指(p2c_addr返回A0)，Cache從主緩存輸出A0數(shù)據(jù)的。下一時(shí)鐘，預(yù)取的Flash數(shù)據(jù)被寫(xiě)入輔助緩存(way_v)。

T5時(shí)刻，處理器返回原有順序取指(p2c_addr返回A8)，輔助緩存數(shù)據(jù)被輸出。下一時(shí)鐘，輔助緩存數(shù)據(jù)被寫(xiě)入主緩存。當(dāng)Cache發(fā)生缺失或處理器進(jìn)行非邊界跳轉(zhuǎn)讀取(跳轉(zhuǎn)地址非Flash輸出128 bit數(shù)據(jù)的首地址)，Cache會(huì)掛起處理器，進(jìn)行新的流水線填充。

上述流水控制有效地結(jié)合了輔助緩存和順序取指，以4個(gè)時(shí)鐘填充流水線的極低代價(jià)，使處理器能夠順序無(wú)間斷取指，提升了程序的運(yùn)行效率。

3　Flash控制器性能測(cè)試

Cache設(shè)計(jì)需滿足程序局部性原則，而程序局部性主要表現(xiàn)形式為“循環(huán)體”，故Cache的測(cè)試程序由循環(huán)體相互嵌套組成，通過(guò)改變循環(huán)中順序執(zhí)行的指令長(zhǎng)度來(lái)測(cè)試被測(cè)對(duì)象的性能。

測(cè)試的參照對(duì)象為“Flash控制器第一版”和飛思卡爾的K21芯片。第一版Flash控制器未加入Cache機(jī)制，其只有簡(jiǎn)單的256 bit緩存結(jié)構(gòu)。當(dāng)處理器順序讀取時(shí)，該控制器可實(shí)現(xiàn)流水取指，如出現(xiàn)跳轉(zhuǎn)取指，則需要掛起處理器重新填充緩存。飛思卡爾的K21芯片是一款目前應(yīng)用于支付終端的主流MCU，其包含同樣大小的Cache，且處理內(nèi)核與本設(shè)計(jì)相同，可作為參照對(duì)象。

測(cè)試方法是在測(cè)試程序的開(kāi)始和末尾加入GPIO翻轉(zhuǎn)指令，通過(guò)使用精密示波器采集兩次GPIO翻轉(zhuǎn)的時(shí)間間隔，來(lái)確定程序執(zhí)行時(shí)長(zhǎng)。

從表4的實(shí)驗(yàn)數(shù)據(jù)可知，相對(duì)于未加入Cache機(jī)制的控制器，引入Cache機(jī)制的控制器可使處理器取指時(shí)間節(jié)省38%，與主流Flash控制器飛思卡爾的K21芯片性能相當(dāng)。

表4　Flash控制器性能對(duì)比

4　結(jié)　語(yǔ)

本文實(shí)現(xiàn)了一種基于Cache機(jī)制的Flash控制器，與Cache和控制器分離的設(shè)計(jì)相比，本設(shè)計(jì)結(jié)構(gòu)更加緊湊，利于綜合工具優(yōu)化。內(nèi)嵌Cache的設(shè)計(jì)從映射結(jié)構(gòu)、替換算法、預(yù)填充三個(gè)方面進(jìn)行。在映射方式上，通過(guò)需求分析及實(shí)驗(yàn)對(duì)比，確定內(nèi)嵌Cache采用4組4路組相聯(lián)映射。對(duì)比8組2路映射，該映射方式最大可降低8.8%的Cache缺失率。在替換算法上，本文提出“優(yōu)化的LRU算法”，并對(duì)FIFO、偽隨機(jī)、LRU及“優(yōu)化的LRU算法”進(jìn)行RTL實(shí)現(xiàn)及性能測(cè)試。通過(guò)測(cè)試對(duì)比，新算法的面積及關(guān)鍵路徑比LRU減少10%，而性能與LRU相似，且優(yōu)于其他替換算法。在預(yù)填充上，本文將“順序預(yù)取”“輔助緩存”與“流水控制”相結(jié)合，實(shí)現(xiàn)了處理器順序讀取下的不間斷取指，進(jìn)一步提升Cache性能。最后，通過(guò)實(shí)驗(yàn)對(duì)比，對(duì)內(nèi)嵌Cache的整體性能進(jìn)行測(cè)試。相較于未加入Cache機(jī)制的控制器，本設(shè)計(jì)可使處理器取指時(shí)間節(jié)省38%，與當(dāng)前主流Flash控制器飛思卡爾的K21芯片性能相當(dāng)。

[1] Wilkes.Slave memories and dynamic storage allocation[J].Electronic Computers,IEEE Transaetionson,1965(2):281-293.

[2] Smith A J.Cache memories[J].ACM Computing Surveys,1982,14(3):473-530.

[3] Puzak T R.Analysis of cache replacement-algorithms[D].PhD thesis.University of Massachusetts Amherst,1985.

[4] Jouppi N P.Improving direct-mapped cache performance by the addition of a small fully-associative cache and pre-fetch buffers[C]// ISCA’90:Proceedings of the 17thannual international symposium on Computer Architecture. New York. NY, USA ACM. 1990:364-373.

[5] Chan K K,Hay C C,Keller J R,et al.Design of the HP PA 7200 CPU[J].Hewlett-Packard Journal:technical information from the laboratiories of Hewlett-Packard Company,1996,47(1):25-33.

[6] Hennessy J L,Patterson D A.計(jì)算機(jī)體系結(jié)構(gòu):量化研究方法[M].3版.北京:機(jī)械工業(yè)出版社,2002.

[7] 何勇,肖斌,陳章,等.一種低功耗的動(dòng)態(tài)可重構(gòu)Cache設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用與軟件,2009,26(8):247-250.

[8] 張輪凱,宋風(fēng)龍,王達(dá).一種針對(duì)片上眾核結(jié)構(gòu)共享末級(jí)緩存的改進(jìn)的LFU替換算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(1):1-6,10.

[9] 薛燕.Cache預(yù)測(cè)技術(shù)的研究[D].西安:西北工業(yè)大學(xué),2005.

[10] Baker Mohammand,Ken Lin,Paul Bassett,et al.A 65nm Level-1 Cache For Mobile Applications[C]//International Conference on Microelectronics,2008:5-10.

[11] Ricardo Quislant,Ezequil Herruzo.Teaching the Cache Memory System Using A Reconfigurable Approach[J].IEEE Transactions on Education,2008,51(3):336-341.

[12] Shan Yueer,Yu Zongguang.EBA-LRU-SEQ Data Cache Policy in DSP to Optimize the Power Consumption[J].Tsinghua Science and Technology,2011,16(2):164-169.

DESIGN OF AN EMBEDDED FLASH CONTROLLER BASED ON CACHE MECHANISM

Cao Jian1,2*Li Linghao1Huang Yadong1Wu Zhonghai1Zhang Xing1,2

1(SchoolofSoftwareandMicroelectronics,PekingUniversity,Beijing100871,China)2(SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871,China)

Embedded Flash (eFlash) is widely used in SoC, but the contradiction became more prominent between the flash slow reading speed and the processor high-frequency fetch. To solve the problem, we introduce the cache mechanism in the flash controller, and use set-associative mapping, optimized LRU (Least Recently Used) replacement algorithm and pre-fetching structure to optimize the cache. Compared with the flash controller without cache, the flash controller with cache can enable the processor to take the time to save 38%.

Embedded flashCacheSet-associative mappingLRUPre-fetching

2015-10-28。曹健，講師，主研領(lǐng)域：嵌入式系統(tǒng)設(shè)計(jì)，軟硬件協(xié)同設(shè)計(jì)，抗靜電保護(hù)電路設(shè)計(jì)。李凌浩，碩士生。黃雅東，教授。吳中海，教授。張興，教授。

TP3

A

10.3969/j.issn.1000-386x.2016.08.053