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

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

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

?

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

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

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

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

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

0　引　言

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

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

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

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

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

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

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

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

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

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

2.1地址映射方式

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

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

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

2.2替換算法

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

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

表2　各算法面積對比

表3　各算法性能對比

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

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

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

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

2.3預填充策略

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

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

圖5　流水預填充時序

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

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

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

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

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

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

3　Flash控制器性能測試

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

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

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

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

表4　Flash控制器性能對比

4　結(jié)　語

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

[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.計算機體系結(jié)構(gòu):量化研究方法[M].3版.北京:機械工業(yè)出版社,2002.

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

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

[9] 薛燕.Cache預測技術(shù)的研究[D].西安:西北工業(yè)大學,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è)計，軟硬件協(xié)同設(shè)計，抗靜電保護電路設(shè)計。李凌浩，碩士生。黃雅東，教授。吳中海，教授。張興，教授。

TP3

A

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