修思文,李彥哲,黃 凱,馬 德,晏榮杰,嚴(yán)曉浪

（1.浙江大學(xué)超大規(guī)模集成電路研究所,浙江杭州310027；2.杭州電子科技大學(xué)微電子CAD所,浙江杭州310018；3.中國(guó)科學(xué)院軟件研究所,北京100080）

面向MPSoC性能評(píng)估的高速緩存建模技術(shù)

修思文1,李彥哲1,黃 凱1,馬 德2,晏榮杰3,嚴(yán)曉浪1

（1.浙江大學(xué)超大規(guī)模集成電路研究所,浙江杭州310027；2.杭州電子科技大學(xué)微電子CAD所,浙江杭州310018；3.中國(guó)科學(xué)院軟件研究所,北京100080）

分析現(xiàn)有的面向MPSoC性能評(píng)估的高速緩存建模技術(shù)的缺點(diǎn),提出用于本機(jī)模擬的靜態(tài)分析和動(dòng)態(tài)標(biāo)注相結(jié)合的緩存建模技術(shù).該技術(shù)采用GCC剖析,避免了命中判斷時(shí)標(biāo)簽比較,擴(kuò)展了緩存更新的粒度.建立準(zhǔn)確的指令和各類型變量在目標(biāo)平臺(tái)的地址映射表,提高了仿真速度和評(píng)估的準(zhǔn)確性.該技術(shù)支持對(duì)多級(jí)緩存的建模,擴(kuò)展了對(duì)多處理器平臺(tái)的支持.實(shí)驗(yàn)結(jié)果表明,該技術(shù)的評(píng)估速度和準(zhǔn)確性均優(yōu)于現(xiàn)有技術(shù).

MPSoC性能評(píng)估；高速緩存建模；本機(jī)模擬；GCC剖析；靜態(tài)分析；動(dòng)態(tài)標(biāo)注；多級(jí)緩存

隨著嵌入式領(lǐng)域應(yīng)用需求的不斷提高,多核系統(tǒng)芯片（MPSoC）的體系結(jié)構(gòu)和設(shè)計(jì)規(guī)模變得愈加龐大與復(fù)雜,迫切需要高效、準(zhǔn)確的性能評(píng)估技術(shù),以實(shí)現(xiàn)快速的軟硬件架構(gòu)探索［1-2］,縮短產(chǎn)品的上市時(shí)間.MPSoC性能評(píng)估技術(shù)已逐漸成為電子系統(tǒng)級(jí)設(shè)計(jì)領(lǐng)域的前沿和熱點(diǎn)［3］.為了使性能評(píng)估足夠精準(zhǔn),必須考慮各系統(tǒng)組件的影響.其中,高速緩存（cache,以下簡(jiǎn)稱為緩存）尤為重要,對(duì)整個(gè)系統(tǒng)性能的影響很大.構(gòu)建高效、準(zhǔn)確的緩存模型是MPSoC性能評(píng)估的核心環(huán)節(jié)之一,可為MPSoC軟硬件架構(gòu)系統(tǒng)級(jí)設(shè)計(jì)提供有效的方法學(xué)和技術(shù)基礎(chǔ).

近年來,學(xué)術(shù)界提出了眾多的緩存建模技術(shù),主要分為靜態(tài)分析和動(dòng)態(tài)仿真2類.靜態(tài)分析首先建立緩存數(shù)學(xué)模型,然后遍歷分析軟件代碼所有可能的控制路徑得到最壞的性能結(jié)果［4-6］.靜態(tài)分析的方法常用于實(shí)時(shí)系統(tǒng),利用計(jì)算代替模擬,具有快速、全面的優(yōu)點(diǎn)；但評(píng)估結(jié)果過于悲觀,易導(dǎo)致性能冗余,造成硬件資源浪費(fèi).與靜態(tài)分析相比,動(dòng)態(tài)仿真可以獲得更加準(zhǔn)確的評(píng)估結(jié)果,按模型層次和仿真方法來區(qū)分,主要分為指令集仿真器（instruction set simulator,ISS）和本機(jī)模擬（native simulation）.基于ISS的評(píng)估技術(shù)［7-9］以目標(biāo)處理器仿真模型為基礎(chǔ),對(duì)匯編指令逐條解析模擬程序?qū)嶋H執(zhí)行過程,采用細(xì)節(jié)的緩存模型,雖然可以反映系統(tǒng)精確的執(zhí)行過程和時(shí)間,但由于其極慢的速度難以勝任早期的性能評(píng)估.

為了達(dá)到復(fù)雜度、仿真速度和精度的最佳折中,學(xué)術(shù)界提出眾多基于本機(jī)模擬的緩存建模技術(shù)［10-15］.本機(jī)模擬以應(yīng)用程序在主機(jī)（基于x86架構(gòu)CPU的服務(wù)器或工作站）的執(zhí)行過程和結(jié)果為研究對(duì)象,分析推算出目標(biāo)平臺(tái)執(zhí)行結(jié)果,避免對(duì)目標(biāo)平臺(tái)執(zhí)行過程進(jìn)行復(fù)雜的模擬.與ISS相比,本機(jī)模擬具有仿真速率快、平臺(tái)構(gòu)建簡(jiǎn)單、可移植性強(qiáng)、便于調(diào)試等諸多優(yōu)勢(shì).目前,基于本機(jī)模擬的緩存建模技術(shù)存在一些局限：1）常用源代碼標(biāo)注的方法,以基本塊（basic block）為單位進(jìn)行標(biāo)注,粒度較細(xì),導(dǎo)致仿真過程中與緩存模型頻繁交互［10-12］,影響仿真的速度；2）緩存模型的命中檢查主要基于標(biāo)簽比較（Tag-Search）［13］,進(jìn)一步制約了仿真的速度；3）主機(jī)平臺(tái)與目標(biāo)平臺(tái)指令集和地址空間的差異導(dǎo)致本機(jī)模擬中變量地址分配與實(shí)際地址可能不同,給數(shù)據(jù)緩存模型引入誤差［14］；4）主要集中在單處理器架構(gòu),且?guī)缀鯖]有基于本機(jī)模擬的多級(jí)緩存建模技術(shù)［16-17］.

為了解決以上問題,本文提出靜態(tài)分析和動(dòng)態(tài)標(biāo)注相結(jié)合的方法來建立基于本機(jī)模擬的緩存模型.該方法采用GCC剖析（profiling）技術(shù),避免對(duì)源代碼的大量修改；與文獻(xiàn)［16］相比,完全避免了緩存模型的標(biāo)簽比較,提高了仿真速度；以“段落”為基本單位更新緩存狀態(tài),擴(kuò)展了緩存更新的粒度,降低應(yīng)用進(jìn)程與緩存模型的交互頻率,進(jìn)一步提高了仿真速度；以動(dòng)態(tài)仿真結(jié)果和目標(biāo)平臺(tái)匯編代碼為靜態(tài)分析對(duì)象,建立指令和各類型變量在目標(biāo)平臺(tái)的地址映射表,提高評(píng)估的準(zhǔn)確性；采用線上更新和離線分析相結(jié)合的方法,支持對(duì)多處理器平臺(tái)多級(jí)緩存的建模.

1 GCC剖析技術(shù)

為了結(jié)合動(dòng)態(tài)仿真和靜態(tài)分析的優(yōu)勢(shì),采用Ma等［17］提出的GCC剖析技術(shù)來收集、分析本機(jī)模擬過程中的程序執(zhí)行情況.圖1展示了利用本機(jī)模擬的GCC剖析技術(shù)來配置、更新緩存模型的三大步驟.

1）根據(jù)評(píng)估對(duì)象的架構(gòu)信息配置緩存模型；靜態(tài)分析應(yīng)用軟件源代碼的控制語句,進(jìn)行段落劃分并插入控制緩存狀態(tài)更新的應(yīng)用程序編程接口函數(shù)（以下簡(jiǎn)稱為緩存API）.

2）分別采用主機(jī)和目標(biāo)處理器編譯工具對(duì)待評(píng)估源碼進(jìn)行編譯,生成主機(jī)平臺(tái)的應(yīng)用和緩存狀態(tài)分析可執(zhí)行代碼以及目標(biāo)平臺(tái)反匯編代碼.編譯時(shí),通過開啟Gcov［18］參數(shù),生成該應(yīng)用的.gcno文件,包含了GCC剖析所需要的信息.

3）對(duì)可執(zhí)行代碼進(jìn)行動(dòng)態(tài)仿真,獲得代碼覆蓋率及動(dòng)態(tài)變量相對(duì)地址；通過靜態(tài)分析代碼覆蓋率文件（.gcov文件）和目標(biāo)平臺(tái)反匯編代碼,獲得應(yīng)用程序在目標(biāo)平臺(tái)的指令執(zhí)行流程、次數(shù)、存儲(chǔ)器訪問地址等信息；根據(jù)這些信息,實(shí)時(shí)調(diào)用緩存API更新各緩存模型的狀態(tài),并統(tǒng)計(jì)命中缺失情況給出性能結(jié)果.

圖1 基于GCC剖析技術(shù)的緩存建模流程Fig.1 GCC profiling based cache modeling flow

2 緩存模型

傳統(tǒng)緩存模型［13］一般采用標(biāo)簽比較的方法進(jìn)行緩存塊索引,如圖2所示,以2路組相連緩存為例.當(dāng)處理器對(duì)緩存發(fā)起訪問時(shí),用低位地址對(duì)應(yīng)的組索引字段（index）找到映射的組（set）,然后用高位地址與組內(nèi)所有緩存行（line）的標(biāo)簽字段（tag）比較判斷是否命中.采用該方法可知,緩存的關(guān)聯(lián)度將嚴(yán)重制約仿真速度,組內(nèi)緩存塊的數(shù)目越多,仿真速度越慢；當(dāng)處理器數(shù)目增加時(shí),情況更糟.

圖2 基于標(biāo)簽比較的緩存模型Fig.2 Tag-search based cache model

為了解決傳統(tǒng)緩存模型對(duì)仿真速率的限制,避免耗時(shí)的標(biāo)簽比較,利用主機(jī)內(nèi)存資源豐富和緩存命中率遠(yuǎn)高于缺失率的特點(diǎn)進(jìn)行緩存建模.以采用LRU替換算法的數(shù)據(jù)緩存為例進(jìn)行說明.如圖3所示,采用以下2組數(shù)據(jù)結(jié)構(gòu).

addr_block記錄所有數(shù)據(jù)段的可緩存地址塊在緩存中的狀態(tài)（有效位、臟位等）和緩存中所在的路（way,只用于LRU等基于訪問次數(shù)的緩存替換算法）.其中,將整個(gè)數(shù)據(jù)段可緩存的地址按緩存行的大小進(jìn)行劃分,每一塊稱為地址塊（以下簡(jiǎn)稱為block）.

cache_line和傳統(tǒng)的緩存模型類似,記錄緩存行的標(biāo)簽字段和訪問次數(shù)（count,只用于基于訪問次數(shù)的緩存替換算法,如LRU算法）.

當(dāng)某個(gè)可緩存地址被訪問時(shí),首先查詢block_ status［block］.如果緩存命中,則根據(jù)set和block_ status［block］.way指定的路更新line_status［｛set, way｝］.count信息.若緩存缺失,則遍歷line_status［｛set,*｝］中該組的所有路,得到各路的line_status.count和line_status.tag.各路的line_status.tag連上set即為各路的block,然后根據(jù)block_status［block］和對(duì)應(yīng)的line_status.count以決定分配到哪路中.最后,更新相應(yīng)的line_status和block_ status,若存在對(duì)下一級(jí)存儲(chǔ)器的訪問（一級(jí)緩存缺失）,則記錄在文件中.

圖3 基于地址塊索引的緩存模型Fig.3 Tag-search based cache model

雖然本文提出的模型對(duì)內(nèi)存的消耗有所增加,但對(duì)于配備GB級(jí)內(nèi)存的服務(wù)器是可以忽略的.由于line_status數(shù)組也存在于傳統(tǒng)的基于標(biāo)簽比較的緩存模型中（本文省掉了其中的狀態(tài)位）,額外的存儲(chǔ)開銷即為block_status數(shù)組.對(duì)于32位處理器,地址的最大范圍為232,考慮一個(gè)緩存行大小為2xbyte、狀態(tài)位為y bit的2n路組相連一級(jí)數(shù)據(jù)緩存（對(duì)于嵌入式處理器,x一般為5,y和n一般為2）,block_status數(shù)組的存儲(chǔ)開銷（單位：MB）為

即使是最極端的情況,所有的地址空間都被覆蓋,額外的存儲(chǔ)開銷遠(yuǎn)小于現(xiàn)代服務(wù)器的一般內(nèi)存容量.

3 基于段落的緩存更新機(jī)制

圖4 基本塊、控制塊與段Fig.4 Basic block,control block and segment

軟件代碼一般按照順序、選擇和迭代3種結(jié)構(gòu)進(jìn)行組織［11］.在傳統(tǒng)評(píng)估方法中,以選擇或者迭代語句為邊界,將代碼劃分為只含有順序語句的基本塊,如圖4所示,在仿真過程中以基本塊為單位對(duì)緩存狀態(tài)進(jìn)行更新.

為了進(jìn)一步提高仿真效率,將基本塊按類型特點(diǎn)和一定規(guī)則合并成“段落”,以段落為基本單位進(jìn)行緩存狀態(tài)更新.對(duì)GCC剖析得到的代碼覆蓋率文件進(jìn)行分析,以還原段落內(nèi)代碼執(zhí)行流程.按照控制語句的特點(diǎn),可以將控制類型分為2類：顯式控制和隱式控制.將能夠通過代碼覆蓋率文件還原代碼執(zhí)行流程的控制塊稱為顯式控制塊（如for等循環(huán)語句）,反之稱為隱式控制塊（如if-else等選擇語句）.按照以上原則可知,C／C＋＋控制語句分類結(jié)果如表1所示.

表1 顯式、隱式控制塊分類Tab.1 Divisions of explicit and implicit control blocks

結(jié)合本機(jī)模擬代碼覆蓋率文件,顯式控制塊的執(zhí)行流程能夠通過靜態(tài)分析還原,可以將顯式控制塊合并到一個(gè)段落內(nèi).對(duì)于隱式控制塊,雖然執(zhí)行流程不能通過靜態(tài)分析還原,但如果它的地址空間小于對(duì)應(yīng)的緩存,則可以推斷它只會(huì)在首次執(zhí)行過程中發(fā)生緩存缺失,隨后的執(zhí)行過程中均會(huì)命中緩存.

代碼段落劃分的基本原則如下：連續(xù)的只包含顯示控制塊的段落大小沒有限制；包含隱式控制塊的段落不大于緩存的大小.對(duì)于一個(gè)隱式控制塊,它可以被合并到一個(gè)已存在的段落,但前提是合并后的段落小于緩存的大?。环駝t,若該隱式控制塊不大于緩存的大小,則將為其創(chuàng)建一個(gè)新的段落,否則為其中的每個(gè)基本塊創(chuàng)建一個(gè)段落.

4 指令及變量地址追蹤

為了能夠準(zhǔn)確觀察本機(jī)模擬過程中的緩存訪問情況,分別采用2個(gè)編譯器對(duì)待評(píng)估應(yīng)用軟件源代碼進(jìn)行編譯：通過主機(jī)GCC編譯產(chǎn)生用于本機(jī)模擬和覆蓋率統(tǒng)計(jì)的可執(zhí)行代碼；通過交叉編譯和反匯編得到用于靜態(tài)分析的反匯編代碼.如圖5所示,通過分析目標(biāo)平臺(tái)匯編代碼獲得源代碼與指令間的對(duì)應(yīng)關(guān)系以及這些指令在目標(biāo)平臺(tái)的真正地址（p2_ sw.asm中的PC）.

圖5 指令地址分析Fig.5 Instruction addresses analyzing

不同于指令地址,數(shù)據(jù)變量地址與程序動(dòng)態(tài)執(zhí)行情況緊密相關(guān),很難直接得到.為此,采用靜態(tài)分析與動(dòng)態(tài)仿真結(jié)合方法解決該問題.變量地址追蹤的方法和流程如圖6所示.根據(jù)ELF標(biāo)準(zhǔn)可知,全局變量和靜態(tài)變量由編譯器分配,主要分配在data、rodata和bss段,本文通過靜態(tài)分析Objdump工具產(chǎn)生的反匯編文件獲得；局部變量和動(dòng)態(tài)變量是根據(jù)程序執(zhí)行過程分別從棧（stack）和堆（heap）中動(dòng)態(tài)分配的,不可能直接通過靜態(tài)分析得到這些變量的絕對(duì)地址.由于堆很復(fù)雜,幾乎沒有性能評(píng)估工作解決堆的問題.為此,采用在GDB調(diào)試器腳本中插入標(biāo)注函數(shù)的方法來跟蹤局部變量和動(dòng)態(tài)變量的偏移地址.在GDB調(diào)試器腳本定義局部變量的地方或動(dòng)態(tài)數(shù)據(jù)進(jìn)行存儲(chǔ)器分配的地方設(shè)置斷點(diǎn),讓調(diào)試器把這些變量的地址打印出來,建立堆棧變量的地址表.雖然主機(jī)和目標(biāo)平臺(tái)的絕對(duì)地址不同,它們維護(hù)變量的偏移地址是基本相同的,前提是變量尺寸相同.因此,需要直接修改源代碼以轉(zhuǎn)換變量的類型,例如,若long類型在主機(jī)上是64位,而在目標(biāo)處理器上是32位,則long類型的變量應(yīng)該被轉(zhuǎn)換成int類型.基于本機(jī)模擬中標(biāo)注函數(shù)的打印結(jié)果,根據(jù)下面2個(gè)公式計(jì)算目標(biāo)平臺(tái)的地址：

圖6 變量地址追蹤流程Fig.6 Address tracing flow of variables

式中：LAddrt、DAddrt、SPt和Heapt分別表示目標(biāo)平臺(tái)的局部變量地址、動(dòng)態(tài)變量地址、棧指針和堆的基地址；LAddrh、DAddrh、SPh和Heaph分別表示主機(jī)上相對(duì)應(yīng)的變量.

除了變量地址表,本文還根據(jù)源代碼每條語句的存儲(chǔ)器訪問情況建立一個(gè)存儲(chǔ)器訪問表,如圖7所示.在本機(jī)模擬之前,靜態(tài)分析每條語句以找到所有的變量操作,每個(gè)這樣的操作都指示一個(gè)可緩存的讀／寫訪問.寫訪問發(fā)生的條件如下：一個(gè)變量出現(xiàn)在常規(guī)賦值表達(dá)式（＝、＋＝、－＝等）左邊；自操作符（＋＋或－－等）；調(diào)用函數(shù)時(shí)壓棧.讀訪問發(fā)生的條件如下：變量在賦值表達(dá)式的左邊；比較表達(dá)式（＞、＜ ═══、 等）；函數(shù)出棧.另外,一些系統(tǒng)變量（諸如fp、ip、lr和pc等）應(yīng)該在發(fā)生函數(shù)調(diào)用和退出時(shí)分別被保留和恢復(fù).

圖7 存儲(chǔ)器訪問表Fig.7 Memory access table

5 多級(jí)緩存建模

以二級(jí)緩存為例來說明多級(jí)緩存建模技術(shù).常用的二級(jí)緩存架構(gòu)主要分為2種：私有二級(jí)緩存與共享二級(jí)緩存,如圖8所示.

圖8 私有二級(jí)緩存與共享二級(jí)緩存建模Fig.8 Private L2 cache and shared L2 cache modeling

5.1 私有二級(jí)緩存建模

私有二級(jí)緩存和處理器直接相連,且不存在處理器間的緩存共享,本文采用在線（on-line）更新的策略對(duì)私有二級(jí)緩存進(jìn)行建模.二級(jí)緩存的更新通常是由一級(jí)緩存的操作（缺失、寫回等）引起的,當(dāng)進(jìn)行性能評(píng)估時(shí),對(duì)于每一條或每一段落指令,只需依次對(duì)各級(jí)緩存模型進(jìn)行更新.二級(jí)緩存的緩存行有可能大于一級(jí)緩存,對(duì)于同一地址,各級(jí)緩存的地址塊索引字段一般不同；因此,各級(jí)緩存的地址塊狀態(tài)是分開記錄的.

5.2 共享二級(jí)緩存建模

共享二級(jí)緩存建模的關(guān)鍵是要綜合考慮各個(gè)處理器對(duì)二級(jí)緩存訪問情況,為此,采用離線（offline）分析的策略對(duì)共享二級(jí)緩存進(jìn)行建模.前文提到,在對(duì)各處理器進(jìn)行一級(jí)緩存建模時(shí),引發(fā)二級(jí)緩存訪問的操作會(huì)被按次序記錄到日志文件中,格式為：“訪問時(shí)刻（cycle）,操作類型（type）,二級(jí)緩存地址塊索引字段（block）”.其中,訪問時(shí)刻可以根據(jù)性能評(píng)估的累計(jì)結(jié)果得到；對(duì)于訪問二級(jí)緩存的操作,在本機(jī)模擬分析時(shí)暫不計(jì)算二級(jí)緩存及共享存儲(chǔ)器的訪問延時(shí),最后在離線分析時(shí)進(jìn)行修正.離線分析的優(yōu)點(diǎn)是避免緩存模型間的通信,對(duì)速度影響不大；缺點(diǎn)是對(duì)于包含（inclusive）類型的共享二級(jí)緩存,替換操作可能會(huì)引起對(duì)一級(jí)緩存的反向無效（backward invalidation）操作,這是目前無法模擬的,會(huì)降低準(zhǔn)確度.

離線分析算法如下.

本文將各一級(jí)緩存建模時(shí)生成的日志文件轉(zhuǎn)化為數(shù)組.其中,沖突模型模擬共享二級(jí)緩存對(duì)并發(fā)操作的仲裁；反饋模型給仲裁成功者返回二級(jí)緩存和主存儲(chǔ)器的訪問時(shí)間,給仲裁失敗者返回延遲的時(shí)間.經(jīng)過離線分析,得到各處理器訪問共享二級(jí)緩存及主存儲(chǔ)器的附加延時(shí)以及共享二級(jí)緩存的訪問統(tǒng)計(jì).

結(jié)合在線更新和離線分析的建模方法,可以對(duì)各種多級(jí)緩存架構(gòu)進(jìn)行建模.

6 實(shí)驗(yàn)與分析

為了驗(yàn)證本文技術(shù)的高效性和準(zhǔn)確性,采用相同測(cè)試基準(zhǔn)、針對(duì)相同的目標(biāo)平臺(tái)進(jìn)行性能評(píng)估,與一些現(xiàn)有的緩存建模技術(shù)進(jìn)行對(duì)比.為了進(jìn)一步分析本文技術(shù)的特點(diǎn),在多種緩存配置模式下對(duì)更復(fù)雜的應(yīng)用進(jìn)行性能評(píng)估實(shí)驗(yàn).在實(shí)驗(yàn)中,采用的主機(jī)平臺(tái)的配置如下：2顆工作于3.47 GHz的Intel Xeon X5690處理器,工作于1 333 MHz的40 GB內(nèi)存,采用Cent OS4.8-x64操作系統(tǒng).

6.1 與現(xiàn)有技術(shù)的對(duì)比

本文實(shí)現(xiàn)了目前最先進(jìn)的3個(gè)基于源代碼標(biāo)注的技術(shù)和本文技術(shù)進(jìn)行對(duì)比.其中,Schnerr等［13］采用基于標(biāo)簽比較的緩存查找技術(shù)；Castillo等［11］在Schnerr等［13］提出的技術(shù)基礎(chǔ)上減少了標(biāo)簽比較,以基本塊的粒度更新指令緩存模型；Posadas等［10］減少了標(biāo)簽比較,以每次存儲(chǔ)器訪問的粒度更新數(shù)據(jù)緩存模型.

實(shí)驗(yàn)采用小型測(cè)試基準(zhǔn)Bubble、Hanoi和Factorial作為待評(píng)估程序,目標(biāo)平臺(tái)處理器為ARM920T［19］,配備了16 KB、緩存行大小為32 byte、64路組相連的數(shù)據(jù)／指令緩存.

比較各種緩存建模技術(shù)的準(zhǔn)確性,表2列出了ISS仿真、源代碼標(biāo)注技術(shù)［10］和本文的技術(shù)對(duì)數(shù)據(jù)緩存缺失次數(shù)評(píng)估的結(jié)果.其中,基于ARM920T ISS的仿真結(jié)果可以被認(rèn)為是精準(zhǔn)的.

表2 數(shù)據(jù)緩存缺失次數(shù)評(píng)估Tab.2 Data cache miss estimation of different techniques

圖9顯示了源代碼標(biāo)注技術(shù)和本文技術(shù)相對(duì)于ISS仿真的誤差比較情況.圖中,er為相對(duì)誤差.可見,對(duì)于Bubble系列程序,源代碼標(biāo)注技術(shù)的準(zhǔn)確度高于本文技術(shù).原因是本文的緩存模型只在一個(gè)段落執(zhí)行后才被更新,且分支的執(zhí)行流程是靜態(tài)分析得到的,可能和真實(shí)情況不同.對(duì)于Posadas等［10］提出的源代碼標(biāo)注技術(shù),每當(dāng)發(fā)生存儲(chǔ)器訪問時(shí),緩存模型就要和標(biāo)注程序通信.對(duì)于Hanoi和Factorial程序,源代碼標(biāo)注技術(shù)的誤差高達(dá)15.79%和33.33%,而本文技術(shù)的誤差只有5.26%和5.60%.原因是這2個(gè)程序中存在大量的函數(shù)調(diào)用,因而引起很多對(duì)堆棧的操作,而本文很好地考慮到了和函數(shù)調(diào)用相關(guān)的系統(tǒng)變量及局部變量等,這些是Posadas等［10］所忽略的.可見,針對(duì)存在大量、復(fù)雜函數(shù)調(diào)用的程序,采用本文技術(shù)評(píng)估的準(zhǔn)確度優(yōu)勢(shì)明顯.這種類型的程序往往是MPSoC性能評(píng)估的重點(diǎn)研究對(duì)象.

圖9 數(shù)據(jù)緩存建模相對(duì)誤差比較Fig.9 Relative error comparison between different techniques for data cache modeling

如圖10、11所示為3種技術(shù)的建模速度v對(duì)比情況.其中,建模速度用MIPS（million instruction per second）來衡量,它表示每秒鐘可以模擬的目標(biāo)平臺(tái)指令的百萬條數(shù).從圖11、12可以看出,基于標(biāo)簽比較的技術(shù)是最慢的；對(duì)于指令緩存建模速度,本文基于段落更新的技術(shù)是基于基本塊更新的技術(shù)的2.0～3.0倍；對(duì)于數(shù)據(jù)緩存建模速度,本文技術(shù)是基于逐條指令更新的技術(shù)的1.5～3.0倍.實(shí)驗(yàn)所用測(cè)試基準(zhǔn)的特點(diǎn)如下：它們的指令地址范圍均小于指令緩存的大小,且變量的地址范圍均小于數(shù)據(jù)緩存的大小.對(duì)于本文提出的基于段落的緩存更新技術(shù),整個(gè)程序都可以看作是一個(gè)段落,指令和數(shù)據(jù)緩存模型都在程序執(zhí)行完畢后才被更新,應(yīng)用程序和緩存模型之間的通信開銷遠(yuǎn)低于現(xiàn)有技術(shù),所以建模速度快于現(xiàn)有技術(shù).

6.2 不同緩存架構(gòu)的建模分析

選取適合多核多線程評(píng)估的EEMBC Multibench［20］中有代表性的3個(gè)應(yīng)用對(duì)不同緩存架構(gòu)進(jìn)行性能評(píng)估.其中,md5程序計(jì)算多數(shù)據(jù)流的MD5校驗(yàn)和,數(shù)據(jù)并行度較高,核間通信較少,一級(jí)緩存命中率較高；rotate程序處理一系列二進(jìn)制圖像,將二進(jìn)制圖像旋轉(zhuǎn)90°、180°和270°,數(shù)據(jù)緩存命中率較低,核間共享數(shù)據(jù)較多；x264程序?qū)D像進(jìn)行編碼,程序較復(fù)雜,數(shù)據(jù)量較大,核間通信量較多.程序的核間通信是利用通信郵箱（mailbox）,通過消息傳遞的顯示方式實(shí)現(xiàn)的.

圖10 指令緩存建模速度比較Fig.10 Speed comparison for instruction cache modeling

圖11 數(shù)據(jù)緩存建模速度比較Fig.11 Speed comparison for data cache modeling

圖12 數(shù)據(jù)緩存建模速度比較Fig.12 Speed comparison among different techniques for data cache modeling

選取的待評(píng)估的2個(gè)目標(biāo)平臺(tái)如圖12所示,圖12中省略了核間通信郵箱、定時(shí)器、中斷控制器等一些外設(shè).這2個(gè)平臺(tái)主要由4個(gè)CK810處理器［21］、AXI3總線、二級(jí)緩存（NI／NE）和1個(gè)DDR2類型的共享存儲(chǔ)器組成,不同之處只在于二級(jí)緩存的位置.實(shí)驗(yàn)中緩存架構(gòu)的配置情況如表3所示,從配置#1到配置#8,一級(jí)緩存的大小和緩存塊大小交替增加,二級(jí)緩存的大小間隔增加.以配置#1的2KB_8B為例,它表示緩存大小為2 KB,緩存行大小為8-byte.其中,各級(jí)緩存均采用寫回、寫分配策略；一級(jí)緩存為4路組相連,采用LRU替換算法；二級(jí)緩存為8路組相連,采用隨機(jī)替換算法.在FPGA上分別實(shí)現(xiàn)了各種配置,把程序通過線程劃分分配到各處理器上運(yùn)行,利用硬件計(jì)數(shù)器統(tǒng)計(jì)各緩存的訪問情況,最后與評(píng)估結(jié)果對(duì)比.

表3 緩存架構(gòu)配置Tab.3 Cache architecture schemes

圖13（a）～（c）顯示了在表3配置下,采用本文的建模技術(shù)統(tǒng)計(jì)各程序的緩存缺失次數(shù)與真實(shí)情況（FPGA）的相對(duì)誤差.可見,本文提出的緩存建模技術(shù)準(zhǔn)確度較高,可以對(duì)MPSoC進(jìn)行快速、準(zhǔn)確的性能評(píng)估.

指令緩存建模的準(zhǔn)確度是最高的,基本接近于真實(shí)情況.由于指令的地址是可以準(zhǔn)確獲得的,指令緩存建模的誤差僅由對(duì)指令流的分析不準(zhǔn)所引入.對(duì)于不同程序,相對(duì)誤差和程序的復(fù)雜度（x264＞md5＞rotate）成正相關(guān)；對(duì)于同一程序,隨著指令緩存大小和緩存行容量的增大（命中率升高）,指令流的不準(zhǔn)確性被逐漸掩蓋,相對(duì)誤差呈減小的趨勢(shì).

數(shù)據(jù)緩存建模的準(zhǔn)確度最低,因?yàn)閿?shù)據(jù)緩存建模引入誤差的原因不僅有指令流的不準(zhǔn),還有地址分析的不準(zhǔn).對(duì)于不同程序,相對(duì)誤差與程序復(fù)雜度、數(shù)據(jù)量成正相關(guān)；對(duì)于同一程序,隨著數(shù)據(jù)緩存的增大,開始時(shí)相對(duì)誤差降低,隨后趨向穩(wěn)定,因?yàn)榇藭r(shí)地址分析誤差已占主導(dǎo).數(shù)據(jù)緩存建模的相對(duì)誤差都在6%以內(nèi),比較準(zhǔn)確.為了進(jìn)一步研究數(shù)據(jù)緩存建模的準(zhǔn)確度,將數(shù)據(jù)緩存固定為16 KB_32 B,改變路的數(shù)目,相對(duì)誤差如圖13（d）所示.可見,隨著路數(shù)的增加,相對(duì)誤差呈上升趨勢(shì),但仍在可控的范圍內(nèi).原因是路數(shù)越多,數(shù)據(jù)緩存更新和實(shí)際情況的差異對(duì)替換算法執(zhí)行的影響越大,從而進(jìn)一步放大誤差.

私有二級(jí)緩存建模的相對(duì)誤差變化情況和數(shù)據(jù)緩存相仿.原因是私有二級(jí)緩存較大,掩蓋了一部分指令流不準(zhǔn)的誤差,因此相對(duì)誤差都低于數(shù)據(jù)緩存.至于共享二級(jí)緩存,相對(duì)誤差大于私有二級(jí)緩存,小于數(shù)據(jù)緩存,且rotate和x264的相對(duì)誤差較大.原因是rotate和x264的共享變量較多,從而使沖突／反饋模型的誤差占了主導(dǎo).為了進(jìn)一步研究共享二級(jí)緩存建模的準(zhǔn)確度,將一級(jí)緩存固定為16 KB_32 B,改變處理器的個(gè)數(shù),相應(yīng)的共享二級(jí)緩存配置為（16×2×處理器個(gè)數(shù)）KB_32 B,相對(duì)誤差如圖13（e）所示.可見,隨著處理器個(gè)數(shù)的增加,共享變量較多的x264和rotate的相對(duì)誤差的上升趨勢(shì)較明顯,但都在可控的范圍內(nèi).原因是隨著處理器個(gè)數(shù)的增加,對(duì)AXI3總線行為的模擬將愈加困難,即沖突／反饋模型的誤差將更大地影響對(duì)共享二級(jí)緩存的離線分析.

圖13 不同緩存配置下相對(duì)誤差統(tǒng)計(jì)Fig.13 Relative error statistics of different cache architectures

7 結(jié) 語

本文提出一種高效、準(zhǔn)確的面向MPSoC性能評(píng)估的高速緩存建模技術(shù),支持對(duì)多處理器平臺(tái)多級(jí)緩存的建模.實(shí)驗(yàn)結(jié)果表明,與現(xiàn)有技術(shù)相比,本文提出的技術(shù)建模速度更快、對(duì)復(fù)雜程序的評(píng)估更精準(zhǔn)；對(duì)于多級(jí)緩存架構(gòu),采用本文技術(shù)建模的準(zhǔn)確度很高.

今后,筆者將完善對(duì)共享二級(jí)緩存的建模,重點(diǎn)研究沖突／反饋模型；筆者還將考慮支持高速緩存一致性的建模.

［1］JERRAYA A,WOLF W.Multiprocessor systems-onchips［M］.Amsterdam：Elsevier,2004.

［2］Martin G.Overview of the MPSoC design challenge［C］//Design Automation Conference.San Francisco：ACM／IEEE,2006：274- 279.

［3］POSADAS H,HERRERA F,SáNCHEZ P,et al.System-level performance analysis in SystemC［C］//Design,Automation and Test in Europe Conference and Exhibition.Paris：IEEE,2004：378- 383.

［4］KIRNER R,SCHOEBERL M.Modeling the function cache for worst-case execution time analysis［C］//Design Automation Conference.San Diego：ACM／IEEE, 2007：471- 476.

［5］SONG F,MOORE S,DONGARRA J.L2 cache modeling for scientific applications on chip multi-processors［C］//International Conference on Parallel Processing. Xi’an：IEEE,2007：51.

［6］LI Y T S,MALIK S,WOLFE A.Cache modeling for real-time software：beyond direct mapped instruction caches［C］//Real-Time Systems Symposium.Los Alamitos：IEEE,1996：254- 263.

［7］BENINI L,BERTOZZI D,BOGLIOLO A,et al.Mparm：exploring the multi-processor soc design space with system［J］.Journal of VLSISignal Processing Systems for Signal,Image and Video Technology,2005, 41（2）：169- 182.

［8］EDLER J,HILL M D.Dinero IV trace-driven uniprocessor cache simulator［EB／OL］.［2014-05-23］.http：//pages.cs.wisc.edu／～markhill／DineroIV.

［9］BINKERT N,BECKMANN B,BLACK G,et al.The gem5 simulator［J］.ACM SIGARCH Computer Architecture News,2011,39（2）：1- 7.

［10］POSADAS H,DíAZ L,VILLAR E.Fast data-cache modeling for native co-simulation［C］//ASP-DAC. Yokohama：IEEE,2011：425- 430.

［11］CASTILLO J,POSADAS H,VILLAR E,et al.Fast instruction cache modeling for approximate timed HW／SW co-simulation［C］//Proceedings of the 20th Symposium on Great Lakes Symposium on VLSI.New York：ACM,2010：191- 196.

［12］WANG Z,HENKEL J.Fast and accurate cache modeling in source-level simulation of embedded software［C］//Proceedings of the Conference on Design,Automation and Test in Europe.Grenoble：IEEE,2013：587- 592.

［13］SCHNERR J,BRINGMANN O,VIEHL A,et al.High-performance timing simulation of embedded software［C］//Design Automation Conference.Anaheim：IEEE,2008：290- 295.

［14］KIRCHSTEIGER C M,SCHWEITZER H,TRUMMER C,et al.A software performance simulation methodology for rapid system architecture exploration［C］//15th IEEE International Conference on Electronics,Circuits and Systems.Julien's：IEEE,2008：494- 497.

［15］GERIN P,HAMAYUN M M,PéTROT F.Native MPSoC co-simulation environment for software performance estimation［C］//Proceedings of the 7th IEEE／ACM International Conference on Hardware／Software Codesign and System Synthesis.New York：ACM,2009：403- 412.

［16］YAN R,MA D,HUANG K,et al.Annotation and analysis combined cache modeling for native simulation［C］//Design Automation Conference（ASP-DAC）. Singapore：IEEE,2014：406- 411.

［17］MA D,YAN R,HUANG K,et al.Performance estimation techniques with MPSoC transaction-accurate models［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2013,32（12）：1920- 1933.

［18］GNU.Gcov-a test coverage program［EB／OL］.［2014-05-23］.http：//gcc.gnu.org／onlinedocs／gcc／Gcov.html.

［19］ARM LTD.ARM920T technical reference manual［EB／OL］.［2014-05-23］.http：//infocenter.arm.com／help／topic／com.arm.doc.ddi0151c／ARM920T_ TRM1_S.pdf.

［20］Embedded Microprocessor Benchmark Consortium.MultiBenchTM1.0 Benchmark software［EB／OL］.［2014-05-23］.http：//www.eembc.org／benchmark／multi_sl.php.

［21］C-SKY MICROSYSTEMS CO.,LTD.CK810 introduction［EB／OL］.［2014-05-23］.http：//www.csky.com／product.php?typeid＝103.

Cache modeling for MPSoC performance estimation

XIU Si-wen1,LI Yan-zhe1,HUANG Kai1,MA De2, YAN Rong-jie3,YAN Xiao-lang1
（1.Institute of VLSI Design,Zhejiang University,Hangzhou 310027,China；2.Microelectronics CAD Center,Hangzhou Dianzi University,Hangzhou 310018,China；3.Institute of Software,Chinese Academy of Sciences,Beijing 100080,China）

The disadvantages of existing cache modeling techniques for MPSoC performance estimation were analyzed.An static analysis and dynamic annotation combined cache modeling technique for native simulation was proposed.The technique employs GCC profiling,avoids tag-search for hit／miss judgment,and coarsens the granularity of cache updating.An accurate address mapping table for instruction and all types of data variables was established,which improves both simulation speed and estimation accuracy.Multilevel cache modeling was considered,which extends support for multi-processor platform.Experimental results show that the proposed technique can significantly reduce the simulation time and improve the accuracy of estimation result compared with existing techniques.

MPSoC performance estimation；cache modeling；native simulation；GCC profiling；static analysis；dynamic annotation；multi-level cache

10.3785／j.issn.1008-973X.2015.07.023

TN 47

A

1008- 973X（2015）07- 1367- 09

2014- 05- 23. 浙江大學(xué)學(xué)報(bào)(工學(xué)版)網(wǎng)址：www.journals.zju.edu.cn／eng

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目（2013QNA5008）；國(guó)家科技重大專項(xiàng)基金資助項(xiàng)目（2009ZX01030-001-002）；國(guó)家自然科學(xué)基金資助項(xiàng)目（61100074）.

修思文（1985—）,男,博士生,從事多核處理器設(shè)計(jì)的研究.ORCID：0000-0003-0400-8037.E-mail：xiusw＠vlsi.zju.edu.cn

黃凱,男,副教授.ORCID：0000-0002-5034-7171.E-mail：huangk＠vlsi.zju.edu.cn