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

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

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

?

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

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

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

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

嵌入式FlashCache組相聯映射LRU流水預填充

0　引　言

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

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

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

1　Flash控制器架構

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

圖1　Flash控制器架構

2　內嵌Cache設計

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

圖2　內嵌Cache結構

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

2.1地址映射方式

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

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

表1　組相聯性能對比

2.2替換算法

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

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

表2　各算法面積對比

表3　各算法性能對比

圖3　優化的LRU替換算法

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

圖4　優化的LRU算法圖例

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

2.3預填充策略

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

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

圖5　流水預填充時序

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

T1時刻，c2m_rd拉高后4個系統時鐘(clk)，Flash輸出128 bit數據，將A0對應數據輸出(c2p_rdata)。

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

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

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

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

3　Flash控制器性能測試

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

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

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

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

表4　Flash控制器性能對比

4　結　語

本文實現了一種基于Cache機制的Flash控制器，與Cache和控制器分離的設計相比，本設計結構更加緊湊，利于綜合工具優化。內嵌Cache的設計從映射結構、替換算法、預填充三個方面進行。在映射方式上，通過需求分析及實驗對比，確定內嵌Cache采用4組4路組相聯映射。對比8組2路映射，該映射方式最大可降低8.8%的Cache缺失率。在替換算法上，本文提出“優化的LRU算法”，并對FIFO、偽隨機、LRU及“優化的LRU算法”進行RTL實現及性能測試。通過測試對比，新算法的面積及關鍵路徑比LRU減少10%，而性能與LRU相似，且優于其他替換算法。在預填充上，本文將“順序預取”“輔助緩存”與“流水控制”相結合，實現了處理器順序讀取下的不間斷取指，進一步提升Cache性能。最后，通過實驗對比，對內嵌Cache的整體性能進行測試。相較于未加入Cache機制的控制器，本設計可使處理器取指時間節省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.計算機體系結構:量化研究方法[M].3版.北京:機械工業出版社,2002.

[7] 何勇,肖斌,陳章,等.一種低功耗的動態可重構Cache設計[J].計算機應用與軟件,2009,26(8):247-250.

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

[9] 薛燕.Cache預測技術的研究[D].西安:西北工業大學,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。曹健，講師，主研領域：嵌入式系統設計，軟硬件協同設計，抗靜電保護電路設計。李凌浩，碩士生。黃雅東，教授。吳中海，教授。張興，教授。

TP3

A

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