宋雙洋 ,趙 姍 ,楊秋松

1(中國科學(xué)院 軟件研究所,北京 100190)2(中國科學(xué)院大學(xué),北京 100049)

CMFSim:高可配可擴(kuò)展的緩存微架構(gòu)功能模擬器①

宋雙洋1,2,趙 姍1,楊秋松1

1(中國科學(xué)院 軟件研究所,北京 100190)2(中國科學(xué)院大學(xué),北京 100049)

作為提高CPU讀取和存儲數(shù)據(jù)的效率,彌補(bǔ)與主存之間存取速度差距的有效策略,CPU的緩存(Cache)充分利用其對數(shù)據(jù)使用的局部性原理,對最近或最常使用的數(shù)據(jù)進(jìn)行暫存,對CPU的性能起著決定性作用.緩存的微架構(gòu)正是決定緩存性能的關(guān)鍵性因素.然而,現(xiàn)代先進(jìn)的CPU 緩存都具備極為復(fù)雜的結(jié)構(gòu),存在多種策略、多種硬件算法和多個層級等不同維度的設(shè)計,從硬件上直接設(shè)計和論證不僅耗時而且成本很高,Cache微架構(gòu)模擬器正是用軟件方法對硬件微架構(gòu)進(jìn)行模擬和仿真.設(shè)計一款結(jié)構(gòu)優(yōu)良的緩存,對不同微架構(gòu)進(jìn)行評估,是一件具有深遠(yuǎn)意義的工作.本文從硬件結(jié)構(gòu)出發(fā),設(shè)計實(shí)現(xiàn)了一款多級、高可配、高可擴(kuò)展的緩存微架構(gòu)功能模擬器CMFSim(Cache microarchitecture functional simulator),實(shí)現(xiàn)了常見的緩存策略和硬件算法,可以進(jìn)行給定配置下的緩存功能的模擬,從而分析配置參數(shù)與緩存性能間的關(guān)系.

多級 Cache; Cache 微架構(gòu); Cache 模擬器

現(xiàn)代信息技術(shù)的發(fā)展中計算機(jī)始終處于核心地位,不論是移動設(shè)備、嵌入式設(shè)備,還是個人計算機(jī)、企業(yè)服務(wù)器乃至超級計算機(jī).所有這些計算機(jī)系統(tǒng)的核心部件就是其處理器[1].一款CPU的性能極大程度上決定了計算機(jī)系統(tǒng)的信息處理能力.設(shè)計和研發(fā)CPU的最新微架構(gòu),不論是從信息技術(shù)產(chǎn)業(yè)還是從國家戰(zhàn)略上來看,不僅能推動整個信息技術(shù)的前進(jìn),而且能在不斷發(fā)展的過程中保持自身的核心競爭力.CPU的緩存作為用來彌補(bǔ)不斷提高的CPU運(yùn)算速度與主存存取速度間差距的特殊結(jié)構(gòu),充分利用了CPU對數(shù)據(jù)和指令使用時的時間局部性和空間局部性原理[2],將最近或最常使用的數(shù)據(jù)進(jìn)行暫存,從而獲得處理器運(yùn)算性能上極大程度的提升.現(xiàn)代CPU的緩存經(jīng)過了長足的發(fā)展,從普通的讀寫策略、替換策略到不同層級及其包含特性,乃至數(shù)據(jù)一致性問題都得到了長足的發(fā)展并提出了很多設(shè)計要點(diǎn),緩存的微架構(gòu)正是從這些方面入手來構(gòu)建完善的緩存系統(tǒng).

在體系結(jié)構(gòu)研究中,軟件模擬是一種非常有效的構(gòu)建設(shè)計原型并進(jìn)行評估的方式,Cache微架構(gòu)的設(shè)計當(dāng)然也不例外.在充分理解Cache硬件結(jié)構(gòu)的基礎(chǔ)上,使用軟件方法進(jìn)行建模,能夠快速論證不同微架構(gòu)在設(shè)計上的優(yōu)劣,及對性能產(chǎn)生的影響; 同時,還能采用控制變量的方式對感興趣的設(shè)計因素進(jìn)行著重考察,發(fā)現(xiàn)和分析出其與性能間的一般性關(guān)系,從而能夠反過來對原型設(shè)計給出指導(dǎo)和建議.雖然軟件模擬器使用廣泛,但單獨(dú)針對Cache的模擬工具很少,深藏于開源的全CPU模擬器中難以獨(dú)立的去研究Cache,或只是在公司或機(jī)構(gòu)內(nèi)部使用而無法獲取; 另外,由于Cache結(jié)構(gòu)的復(fù)雜性,軟件模擬一般只有某個側(cè)重點(diǎn),可以完成所有Cache的功能實(shí)現(xiàn)模擬,也可以考察精確的時序,二者同時模擬會帶來軟件設(shè)計過于復(fù)雜以及模擬運(yùn)行的速度過于緩慢的問題.

本文基于現(xiàn)代CPU Cache的硬件結(jié)構(gòu),設(shè)計實(shí)現(xiàn)了一個高可配、可擴(kuò)展的獨(dú)立Cache功能模擬器CMFSim,對不同緩存結(jié)構(gòu)、寫策略、替換策略、包含特性等多個維度提供了細(xì)粒度的配置,著重功能模擬,針對單核情形下實(shí)現(xiàn),并與DRAMSim2主存模擬模塊整合,提供了統(tǒng)一的訪存接口來進(jìn)行功能模擬.

1 相關(guān)工作

現(xiàn)有的開源模擬器項(xiàng)目都集中在功能全面且龐大的單處理器的全系統(tǒng)模擬,以進(jìn)行整個CPU微架構(gòu)的仿真與模擬.gem5[3]就是這樣的開源全系統(tǒng)微架構(gòu)模擬器的典型代表,提供了系統(tǒng)調(diào)用模擬與全系統(tǒng)模擬兩種工作模式,提供x86、ARM、MIPS、Power、Alpha等多種指令集架構(gòu),同時支持目錄式和廣播式兩種cache一致性協(xié)議,提供基于TCP/IP的網(wǎng)絡(luò)訪問模擬等諸多特性.gem5通過社區(qū)共同維護(hù)和開發(fā),功能全面體系龐大,對于進(jìn)行全系統(tǒng)模擬而言是一個很好的工具,但主要問題是設(shè)計結(jié)構(gòu)過于復(fù)雜,難以拆解用于獨(dú)立研究某個模塊.

Zesto[4]是另一個新一代的全系統(tǒng)模擬器,這是一個在單周期水平上進(jìn)行CPU微架構(gòu)的模擬,在硬件上最接近當(dāng)前最先進(jìn)的高性能x86處理器,主要目標(biāo)就是在非常底層的微架構(gòu)設(shè)計上進(jìn)行x86指令集架構(gòu)下時鐘周期精確的模擬.但是,由于過于精確的模擬,模擬器的運(yùn)行速度非常緩慢,對于運(yùn)行模擬器的巨量指令流來說其運(yùn)行時間難以接受.同時,Zesto也是一個全系統(tǒng)模擬器,也存在難以拆解的困難.

除此之外,還有SimpleScalar[5]由多種模擬工具構(gòu)建的模擬工具家族,這些工具已廣泛使用和流行了數(shù)十年時間,基于該工具集和衍生的模擬工具遍布于大量的學(xué)術(shù)文章中.但隨著處理器硬件工藝的不斷發(fā)展,很多模擬工具特別是時鐘周期精確模擬工具的硬件設(shè)定或者假設(shè)還停留在二十年前的水平[4].MARSS[6]是最新的開源全系統(tǒng)模擬器,提供了針對x86架構(gòu)下單核與多核的順序與亂序支持的時鐘精確模擬,可以直接運(yùn)行操作系統(tǒng)和x86架構(gòu)的二進(jìn)制應(yīng)用程序,是一個從處理器到內(nèi)存、磁盤到其他外部設(shè)備,從操作系統(tǒng)到共享庫和應(yīng)用程序的超全模擬器.

相對于全面、龐大的單處理器全系統(tǒng)模擬器而言,針對多處理器場景也存在較多模擬器項(xiàng)目.上世紀(jì)八十年代提出的高可擴(kuò)展的多處理器模擬器[7],主要模擬了各個處理器通過時序共享的單一總線進(jìn)行主存一致性訪問的架構(gòu).Augmint[8]填補(bǔ)了CISC架構(gòu)和指令混合的模擬器空缺,是一款執(zhí)行驅(qū)動的多處理器模擬工具包.MICA[9]是新一代主要用來進(jìn)行分布式共享內(nèi)存的多處理器場景的模擬,運(yùn)行于多個廉價機(jī)器組成的集群上,使用應(yīng)用程序的執(zhí)行流來作為輸入,提供了各核調(diào)度與內(nèi)存互聯(lián)的算法與接口.

多處理器模擬器主要用于分布式架構(gòu)下的系統(tǒng)模擬,作為體系架構(gòu)的模擬在本質(zhì)上與單處理器相似.

現(xiàn)代CPU體系結(jié)構(gòu)的各個模塊的設(shè)計都非常復(fù)雜,各個模塊的功能和結(jié)構(gòu)很大程度上是可以獨(dú)立考察的,但全系統(tǒng)模擬器重點(diǎn)在整個系統(tǒng)的整體模擬,因此各個獨(dú)立的模塊耦合過于緊密,被淹沒與整個模擬器中,難以去獨(dú)立構(gòu)建與研究.

2 系統(tǒng)設(shè)計與實(shí)現(xiàn)

2.1 Cache硬件結(jié)構(gòu)

現(xiàn)代主流Cache的基本硬件結(jié)構(gòu)主要包括這幾個方面的內(nèi)容:Cache組織結(jié)構(gòu)、地址映射、替換策略、寫策略、多級包含性等,下面詳細(xì)闡述.

2.1.1 組織結(jié)構(gòu)與地址映射

Cache的基本硬件結(jié)構(gòu)是由SRAM構(gòu)成的陣列,陣列中每個基本存儲塊稱為一個cache line,所有對Cache的操作都是以cache line為基本單位進(jìn)行.由于Cache的大小遠(yuǎn)不及主存和外部存儲設(shè)備,需要進(jìn)行映射.對于 Cache 中的 cache line,有兩種常見的組織方式:一個地址對應(yīng)的數(shù)據(jù)只能存儲到固定的一個cache line中,稱為直接映射 (direct-mapped); 一個地址對應(yīng)的數(shù)據(jù)可以存儲在任意cache line中,稱為全相聯(lián)(fully associative).前者對 Cache 的空間利用率很低,有可能某些cache line一直沒有數(shù)據(jù)存儲和讀取,容易發(fā)生沖突,但實(shí)現(xiàn)上最簡單; 后者能充分利用不常用的cache line,空間利用率很高,不容易發(fā)生沖突,但硬件實(shí)現(xiàn)上很復(fù)雜.因此,將二者結(jié)合,兼顧空間利用率、沖突概率和實(shí)現(xiàn)難易程度,就是現(xiàn)代Cache主要的組織結(jié)構(gòu)——多路組相連(set associative).

圖1 8 個 cache line 的不同組織結(jié)構(gòu)示意

硬件上為了支持一個周期處理多個請求,提出了bank的概念,在上述多路組相連的Cache結(jié)構(gòu)基礎(chǔ)上構(gòu)建為一個bank,然后多個bank再構(gòu)建為一級Cache.

在進(jìn)行cache line查詢的時候,需要使用訪問地址進(jìn)行索引,圖2是一個64位物理地址下各索引劃分的實(shí)例,從低位到高位有cache line內(nèi)的偏移、組索引、組內(nèi)標(biāo)簽,若分為多個bank則還需要放置bank索引.

圖2 物理地址索引劃分實(shí)例

為了索引查詢的方便,除tag外,一般各個索引地址的比特數(shù)如果為N,那么對應(yīng)部分總數(shù)就是2N.圖2中組數(shù)(Set)共11比特,則總組數(shù)為2048組; Bank數(shù)占用 3 個比特,則一共有 8 個 bank; cache line 的大小一般都為64,則Offset占用6比特.每次Cache操作都基于地址索引出各部分,是進(jìn)行相應(yīng)操作的基礎(chǔ).

2.1.2 替換策略

由于Cache空間有限,當(dāng)數(shù)據(jù)填充滿之后,或者需要填充的cache line被之前的占用了,那么就會發(fā)生替換,為最新的請求開辟新的位置.對于多路組相連的結(jié)構(gòu),每個組通過組索引只能在組內(nèi)替換,但同一個組內(nèi)的多路是可以任意選擇的,這里就存在多種替換方式的選擇了,常見策略如下:

① 隨機(jī)替換:隨機(jī)選擇一路 cache line 剔除;

② 先進(jìn)先出[10](FIFO):維護(hù)每一路寫入的順序,按照先進(jìn)先出的方式剔除最先進(jìn)入的;

③ LRU[10]:維護(hù)對每一路最近訪問的次數(shù),替換時選擇最近使用最少次數(shù)的;

④ Tree-based PLRU[11]:使用一個二叉樹結(jié)構(gòu)來維護(hù)各路的優(yōu)先級,替換時剔除最不優(yōu)先的.

2.1.3 寫策略與包含性

對于Cache的寫操作,也存在不同的策略.這些策略主要作用于多級Cache結(jié)構(gòu)中,使得上下各級Cache所執(zhí)行的操作會有不同.

圖3 寫請求的不同策略

對于寫缺失的情況下,按照是否先分配一個cache line之后在進(jìn)行Cache寫操作分為write allocate和write no-allocate 兩種策略,其中 write allocate 方式雖然硬件實(shí)現(xiàn)復(fù)雜一些但依然是絕大多數(shù)設(shè)計的選擇.

當(dāng)引入了多層Cache之后,還有另一個需要考慮的問題就是各級Cache之間的包含關(guān)系,分為inclusive和exclusive兩種,前者要求強(qiáng)制包含,上一級的每個cache line都會在下一級存在,為了維護(hù)這種包含性需要額外的操作而花費(fèi)時鐘周期,但各級之間的數(shù)據(jù)一致性維護(hù)相對簡單一些; 后者則沒有這種要求,可以上一級出現(xiàn)的cache line并不存在于下一級中,此時對于各級Cache數(shù)據(jù)一致性的維護(hù)會比較復(fù)雜.

2.2 軟件建模

基于前文所述的Cache硬件結(jié)構(gòu),從軟件建模的角度出發(fā),設(shè)計和定義了各個硬件結(jié)構(gòu)的軟件抽象對應(yīng)的數(shù)據(jù)結(jié)構(gòu),并在此基礎(chǔ)上通過指定的配置參數(shù),選定相應(yīng)的替換算法、寫策略、包含性,并根據(jù)相應(yīng)參數(shù)實(shí)例化指定的Cache結(jié)構(gòu),構(gòu)建起整個CMFSim功能模擬器.首先,對一個單獨(dú)Cache的基本軟件模擬的系統(tǒng)架構(gòu)如圖4所示.

圖4 單級 Cache 軟件建模架構(gòu)

一個完整的Cache的核心為一個CacheController,封裝為一個類,負(fù)責(zé)控制該Cache的所有行為,其所需的主要數(shù)據(jù)結(jié)構(gòu)就是DataArray和TagArray,前者用來存儲實(shí)際緩存的cache line數(shù)據(jù),后者則保存每個cache line相對應(yīng)的標(biāo)簽、狀態(tài)、有效性等信息.與此同時如果有多個bank,則據(jù)此構(gòu)成多個bank,Cache-Controller負(fù)責(zé)控制到某個bank的訪問,將每個請求都以AccessContext對象的方式進(jìn)行包裝,該對象是內(nèi)部各個接口之間傳遞數(shù)據(jù)的通用數(shù)據(jù)結(jié)構(gòu).每個cache默認(rèn)為一個bank,通過讀取用戶在配置文件中給定的配置,來實(shí)例化每個DataArray和TagArray的大小,同時構(gòu)造出相應(yīng)數(shù)目的bank; 與此同時,還根據(jù)指定的替換算法進(jìn)行選擇,決定構(gòu)建相應(yīng)的ReplacePolicy對象; 最后,還需要依據(jù)配置中給定的索引劃分起始比特與長度,來使用Indexer類進(jìn)行物理地址各部分的劃分.另外,對運(yùn)行過程和結(jié)果中的各項(xiàng)關(guān)鍵信息需要進(jìn)行日志記錄,如總的讀寫次數(shù)、命中失效次數(shù)、讀取和寫入的數(shù)據(jù)量等信息.

2.2.1 DataArray 與 TagArray 抽象

對于Cache的行為可以從軟件角度抽象出讀和寫兩種接口,分別對DataArray和TagArray兩個數(shù)據(jù)結(jié)果進(jìn)行操作,這也正好對應(yīng)了Cache硬件上的基本結(jié)構(gòu).其詳細(xì)定義見表1.

3.3.1 合理的植物景觀結(jié)構(gòu) 植物景觀空間中的形態(tài)要素是水平要素、垂直要素、頂面要素，3種要素的組合形成了結(jié)構(gòu)多樣的植物景觀空間[5]，如疏林草地與密林草地，開闊草坪與密林空間等，不同的植物結(jié)構(gòu)其固碳效應(yīng)也不同。此外，在垂直空間上的樹叢的層次結(jié)構(gòu)豐富程度也影響著植物景觀的固碳效應(yīng)，常見的樹叢垂直結(jié)構(gòu)分為大喬—中喬—小喬(灌木)—地被植物，這種垂直結(jié)構(gòu)植物景觀模式的總?cè)~片面積較大，故其固碳效應(yīng)也較高。

表1 DataArray 與 TagArray 主要接口定義

讀寫接口均以bool方式作為返回標(biāo)志以表明是否成功,數(shù)據(jù)均以引用方式傳遞.DataArray和TagArray都是一個類似“二維數(shù)組”的結(jié)構(gòu),來支持多路組相連的 cache line 組織結(jié)構(gòu),第一維為組數(shù),第二維為路數(shù).每個元素,也就是表1中Entry的定義,代表了“數(shù)組”中每一項(xiàng)的具體內(nèi)容.對于DataArray,其讀寫接口只提供組索引和路索引的方式進(jìn)行執(zhí)行,因?yàn)檫@些操作是以TagArray的Tag和狀態(tài)進(jìn)行比較和判定為基礎(chǔ)的,直接操作的就是Cache中的數(shù)據(jù).但TagArray首先提供了針對Tag的讀寫接口,同時提供了針對狀態(tài)位的讀寫操作中,這類狀態(tài)位的操作接口以get與set開頭來命名,可以按照Tag進(jìn)行匹配后執(zhí)行,也可以用路索引進(jìn)行強(qiáng)制設(shè)置的方式執(zhí)行,從而滿足不同場景下對TagArray狀態(tài)的設(shè)置需求.另外,還提供了判斷某一組cache line是否是全部被占用的“busy”接口,可以用來判斷是否需要對當(dāng)前組內(nèi)的某個cache line進(jìn)行替換操作.

2.2.2 替換策略與索引劃分

圖4中的ReplacePolicy類維護(hù)了每個cache line相對應(yīng)的狀態(tài),這些狀態(tài)也是一個二維數(shù)組的結(jié)構(gòu).對于給定的某一組,通過索引第一維,得到該組內(nèi)各個cache line的一維狀態(tài)數(shù)組,前文所述的四種替換算法均能以此為基礎(chǔ)實(shí)現(xiàn),通過建模和驗(yàn)證,以C++模板方式實(shí)現(xiàn),只需要提供如下兩個通用的接口:

傳入的參數(shù)ref表示當(dāng)前訪問的cache line所在組的各cache line的狀態(tài)數(shù)組,update接口用來更新指定路索引的cache line狀態(tài),get接口用來獲取當(dāng)前組內(nèi)需要剔除的cache line的路索引.這兩個接口能夠兼容前文所述的四種算法的實(shí)現(xiàn).FIFO替換算法的update接口描述如下:

ref數(shù)組中每個值為路索引,第一個元素保存的是上一次訪問的,第二個為上上一次訪問的,以此類推,最后一個元素保存的是最早訪問的.每次更新的時候找到當(dāng)前訪問的路(第2到5行),將數(shù)組中在其之前的向后移動一個元素(第6到7行),然后把當(dāng)前路索引放在數(shù)組第一個位置(第8行).調(diào)用get接口進(jìn)行獲取替換的路索引時,直接返回數(shù)組最后一個元素的值即可.對于PLRU算法,則只需要使用狀態(tài)數(shù)組的前N-1個元素(N為每一組的路數(shù)),模擬一個完全二叉樹,其update和get接口的實(shí)現(xiàn)算法描述如下:

每個元素要么為0要么為1,0往左子樹走1往右子樹走,通過與二叉堆相似的方式,在進(jìn)行更新的時候把路索引的二進(jìn)制表示在樹中進(jìn)行遍歷,將遍歷路徑上的每一個元素的值進(jìn)行反轉(zhuǎn)(第6行).調(diào)用get接口就直接依據(jù)樹中每個元素的值進(jìn)行遍歷得到相應(yīng)的二進(jìn)制值就是需要替換的路索引(第3行).對于,LRU和隨機(jī)替換,均能在狀態(tài)數(shù)組的基礎(chǔ)上實(shí)現(xiàn),在此不予贅述.

與此同時,CacheController需要使用Indexer類對輸入請求的物理地址進(jìn)行劃分,需要執(zhí)行的就是對給定的物理地址進(jìn)行按位操作即可,劃分的依據(jù)是Config中給出的各部分起始比特和長度.

2.2.3 CacheSystem 與完整訪存系統(tǒng)

在構(gòu)建完整的單級Cache之后,就可以著手構(gòu)建多級的Cache系統(tǒng).圖5描述了一個指定的典型三級Cache系統(tǒng)與DRAMSim2構(gòu)建的完整訪存系統(tǒng)架構(gòu).多級Cache之間目前僅支持對相互的包含性的設(shè)置.CacheSystem的架構(gòu)可以通過不同的配置來自行設(shè)置和定義,配置文件以ini格式的語法描述并進(jìn)行解析,圖5中的三級結(jié)構(gòu)配置以及L3的索引配置如下:

其他完整配置類似,還包括各級的替換策略、寫命中與寫失效的策略等,使用者可以依據(jù)配置文件的語法進(jìn)行自定義配置,來構(gòu)建不同微架構(gòu)的CacheSystem.

CacheSystem通過讀取和解析配置文件,依次傳遞給各單級Cache的Config去構(gòu)建每一級Cache,得到的多級Cache實(shí)例被CacheSystem類操縱和使用.CacheSystem最終在整個系統(tǒng)中以單例形式呈現(xiàn),并整合了開源的主存模擬模塊DRAMSim2,對外提供了統(tǒng)一的訪存讀寫接口來調(diào)用.

圖5 CacheSystem 與 DRAMSim2 構(gòu)建的訪存系統(tǒng)

整個系統(tǒng)除了提供以動態(tài)鏈接庫的形式作為獨(dú)立模塊供外部調(diào)用之外,圖5中還給出了其提供的Trace模塊,可以一起編譯為一個可執(zhí)行文件,來接收應(yīng)用程序進(jìn)行訪存操作的trace流文件作為輸入,單獨(dú)進(jìn)行Cache微架構(gòu)的研究和功能驗(yàn)證.

3 測試與結(jié)果

基于本文實(shí)現(xiàn)的CMFSim功能模擬器,編譯為接收訪存操作的trace為輸入的可執(zhí)行文件來進(jìn)行測試.測試平臺為 64 位 Ubuntu 14.04 操作系統(tǒng),Intel i5 雙核 CPU,1 GB 內(nèi)存.

首先使用二進(jìn)制分析平臺Pin[16],實(shí)現(xiàn)了獲取應(yīng)用程序訪存操作trace的工具,對Ubuntu系統(tǒng)下的“/bin/ls”程序的訪存操作trace進(jìn)行了捕獲,共得到了34萬多條訪存操作記錄.獲取的trace記錄示例如下:

其中的第一列的“R”和“W”分別代表讀請求和寫請求,緊接著的一列為當(dāng)前請求的物理地址,最后一列為一個整數(shù),代表此次請求的數(shù)據(jù)長度.

3.1 Cache結(jié)構(gòu)的驗(yàn)證

以上述trace為輸入,首先構(gòu)建了測試不同Cache結(jié)構(gòu)與命中率關(guān)系的實(shí)驗(yàn),分別配置不同大小的組數(shù)來統(tǒng)計命中率.

圖6為測試結(jié)果,S表示組數(shù)(Set),W代表路數(shù)(Way),可以看出隨著組數(shù)不斷增加,命中率是不斷提高的,但是當(dāng)增加到一定程度,命中率提高的幅度就不太明顯了,當(dāng)命中率的提高不足以彌補(bǔ)硬件成本的增加時就需要進(jìn)行折中,這對特定結(jié)構(gòu)的Cache設(shè)計具有驗(yàn)證和指導(dǎo)意義.

圖6 Cache 結(jié)構(gòu)與命中率的關(guān)系

3.2 組索引劃分的評估

對于Cache使用物理地址進(jìn)行劃分索引,其劃分位置非常深刻地影響了命中率.因此設(shè)計了如下的實(shí)驗(yàn):從物理地址的第6比特開始依次往后滑動,分別統(tǒng)計不同組索引位置下的命中率,從圖7中可以很明顯的看出,隨著組索引逐漸向高比特移動命中率逐漸上升,在第11比特進(jìn)行劃分的組索引的命中率最好,而且兩種不同Cache結(jié)構(gòu)都是如此,當(dāng)超過11比特再往高比特移動命中率就開始下降了.但是,對于Cache最終設(shè)計方案,需要綜合考慮不同類型的程序,若是針對某一特定領(lǐng)域的設(shè)計可以進(jìn)行特殊設(shè)計,否則針對通用領(lǐng)域需要進(jìn)行折中,該Cache模擬器可以對這些設(shè)計進(jìn)行驗(yàn)證和評估.

圖7 Cache 劃分組索引與命中率關(guān)系

3.3 多級Cache系統(tǒng)的測試

按照圖5所標(biāo)注的配置,構(gòu)建了一個三級的Cache系統(tǒng),L1配置為4路512組,L2配置為4路1024組,L3 配置為 4 個 bank,每個 bank 8 路 2048 組,L2 包含L1,L3 包含 L2,其中 L1、L2 為 write through 與 write no-allocate,L3 為 write back 與 write allocate.使用這些配置構(gòu)建的訪存系統(tǒng),運(yùn)行相同的訪存trace,統(tǒng)計的L1、L2、L3各自的命中率見圖8.

圖8 三級 Cache 系統(tǒng)的命中率

與圖7中的結(jié)果對比,L1和L2都達(dá)到了最優(yōu)命中率但L1、L2的組數(shù)明顯要小很多,可以看出這種多級配置下的緩存系統(tǒng)對命中率的提升,在硬件設(shè)計上可以增加L1、L2的硬件成本,而減小L3的硬件成本,從而可以在保證命中率的基礎(chǔ)上降低整體的成本.

4 總結(jié)

針對處理器體系結(jié)構(gòu)中的緩存這一獨(dú)立模塊的模擬器大都深藏于大量的全功能模擬器中,本文以現(xiàn)代先進(jìn)CPU緩存的硬件結(jié)構(gòu)為依托,從軟件建模與仿真的角度,設(shè)計實(shí)現(xiàn)了一個功能完善、高可配、模塊獨(dú)立的單核下的多級緩存功能模擬器CMFSim,并與開源的DRAMSim2整合,封裝了統(tǒng)一的訪存接口方便調(diào)用,能夠從功能驗(yàn)證的角度完成緩存微架構(gòu)的模擬.通過實(shí)驗(yàn)分析,驗(yàn)證了緩存微架構(gòu)設(shè)計與命中率之間的關(guān)系,能夠表明該獨(dú)立的緩存功能模擬模塊的有效性,可以作為獨(dú)立模塊去構(gòu)建完整的全功能模擬器.

本文僅針對單核下的功能模擬為主要目標(biāo),因?yàn)橹挥脕磉M(jìn)行功能驗(yàn)證和性能評估,對于多核情況只需進(jìn)行相應(yīng)的橫向擴(kuò)展,比如以多線程方式將CMFSim運(yùn)行多個實(shí)例的方式即可進(jìn)行功能模擬.在未來的研究與開發(fā)中,將考慮多核下的精確時序模擬與數(shù)據(jù)一致性的模擬,實(shí)現(xiàn)更加精細(xì)化的微架構(gòu)建模與評估.

1González A,Latorre F,Magklis G.Processor Microarchitecture:An Implementation Perspective.Morgan & Claypool,2010.

2Patterson DA.Computer Architecture:A Quantitative Approach.5th ed.Morgan Kaufmann,2011.

3Binkert N,Beckmann B,Black G,et al.The gem5 simulator.ACM SIGARCH Computer Architecture News,2011,39(2):1–7.[doi:10.1145/2024716]

4Loh GH,Subramaniam S,Xie YJ.Zesto:A cycle-level simulator for highly detailed microarchitecture exploration.Proc.of IEEE International Symposium on Performance Analysis of Systems and Software.Boston,MA,USA.2009.53–64.

5Austin T,Larson E,Ernst D.SimpleScalar:An infrastructure for computer system modeling.Computer,2002,35(2):59–67.[doi:10.1109/2.982917]

6Patel A,Afram F,Chen SF,et al.MARSS:A full system simulator for multicore x86 CPUs.Proc.of the 48th ACM/EDAC/IEEE Design Automation Conference.New York,NY,USA.2011.1050–1055.

7Papamarcos MS,Patel JH.A low-overhead coherence solution for multiprocessors with private cache memories.ACM SIGARCH Computer Architecture News,1984,12(3):348–354.[doi:10.1145/773453]

8Nguyen AT,Michael M,Sharma A,et al.The Augmint multiprocessor simulation toolkit for Intel x86 architectures.Proc.of 1996 IEEE International Computer Design:VLSI in Computers and Processors.Austin,TX,USA.1996.486–490.

9Hsiao HC,King CT.MICA:A memory and interconnect simulation environment for cache-based architectures.Proc.of the 33rd Annual Simulation Symposium.Washington,DC,USA.2000.317–325.

10Dan A,Towsley D.An approximate analysis of the LRU and FIFO buffer replacement schemes.Proc.of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems.Boulder,Colorado,USA.1990.

11Smith MB,Tresidder MJ.Pseudo-LRU cache memory replacement method and apparatus utilizing nodes.U.S.,US5594886A.1997-01-14.

12Dubois M,Annavaram M,Stenstr?m P.Parallel computer organization and design.Cambridge:Cambridge University Press,2012.

13Jacob B,Ng S,Wang D.Memory Systems:Cache,DRAM,Disk.Morgan Kaufmann,2007.

14Drepper U.What Every Programmer Should Know About Memory.Red Hat,Inc.,2007.

15Rosenfeld P,Cooper-balis E,Jacob B.DRAMSim2:A cycle accurate memory system simulator.IEEE Computer Architecture Letters,2011,10(1):16–19.[doi:10.1109/L-CA.2011.4]

16Luk CK,Cohn R,Muth R,et al.Pin:Building customized program analysis tools with dynamic instrumentation.Proc.of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation.Chicago,IL,USA.2005.190–200.

CMFSim:A Highly Configurable and Extensible Cache Microarchitecture Functional Simulator

SONG Shuang-Yang1,2,ZHAO Shan1,YANG Qiu-Song1

1(Institute of Software,Chinese Academy of Sciences,Beijing 100190,China)2(University of Chinese Academy of Sciences,Beijing 100049,China)

As an effective strategy to improve the efficiency for CPU reading and writing,and to fill the speed gap between CPU and the main memory,the cache in CPU makes the best of the locality theory by storing the latest or the most frequently used data.It dominates the performance of a CPU,and the microarchitecture of the cache,however,dominates the cache performance.The modern advanced cache commonly constructed with very complicated structures,contain multiple cache strategies,hardware algorithm and multi-level design,making it expensive to design and verify directly with hardware for time as well as money.Thus,it is far-reaching to simulate the hardware microarchitecture by software modeling.Cache microarchitecture simulator exactly assists the design or the evaluation of an excellent cache.In this article,a highly configurable and extensible cache microarchitecture functional simulator CMFSim is developed on the basis of hardware structure.It implements the common cache strategies and hardware algorithm,which can conveniently simulate the cache microarchitecture for the given configuration and analyze the performance with the specified parameters.

multi-level Cache; Cache microarchitecture; Cache simulator

宋雙洋,趙姍,楊秋松.CMFSim:高可配可擴(kuò)展的緩存微架構(gòu)功能模擬器.計算機(jī)系統(tǒng)應(yīng)用,2017,26(10):36–43.http://www.c-sa.org.cn/1003-3254/5990.html

國家“核高基”科技重大專項(xiàng)(2014ZX01029101-002)

2017-01-19; 采用時間:2017-02-15