宋雙洋 ,趙 姍 ,楊秋松
1(中國(guó)科學(xué)院 軟件研究所,北京 100190)2(中國(guó)科學(xué)院大學(xué),北京 100049)
CMFSim:高可配可擴(kuò)展的緩存微架構(gòu)功能模擬器①
宋雙洋1,2,趙 姍1,楊秋松1
1(中國(guó)科學(xué)院 軟件研究所,北京 100190)2(中國(guó)科學(xué)院大學(xué),北京 100049)
作為提高CPU讀取和存儲(chǔ)數(shù)據(jù)的效率,彌補(bǔ)與主存之間存取速度差距的有效策略,CPU的緩存(Cache)充分利用其對(duì)數(shù)據(jù)使用的局部性原理,對(duì)最近或最常使用的數(shù)據(jù)進(jìn)行暫存,對(duì)CPU的性能起著決定性作用.緩存的微架構(gòu)正是決定緩存性能的關(guān)鍵性因素.然而,現(xiàn)代先進(jìn)的CPU 緩存都具備極為復(fù)雜的結(jié)構(gòu),存在多種策略、多種硬件算法和多個(gè)層級(jí)等不同維度的設(shè)計(jì),從硬件上直接設(shè)計(jì)和論證不僅耗時(shí)而且成本很高,Cache微架構(gòu)模擬器正是用軟件方法對(duì)硬件微架構(gòu)進(jìn)行模擬和仿真.設(shè)計(jì)一款結(jié)構(gòu)優(yōu)良的緩存,對(duì)不同微架構(gòu)進(jìn)行評(píng)估,是一件具有深遠(yuǎn)意義的工作.本文從硬件結(jié)構(gòu)出發(fā),設(shè)計(jì)實(shí)現(xiàn)了一款多級(jí)、高可配、高可擴(kuò)展的緩存微架構(gòu)功能模擬器CMFSim(Cache microarchitecture functional simulator),實(shí)現(xiàn)了常見的緩存策略和硬件算法,可以進(jìn)行給定配置下的緩存功能的模擬,從而分析配置參數(shù)與緩存性能間的關(guān)系.
多級(jí) Cache; Cache 微架構(gòu); Cache 模擬器
現(xiàn)代信息技術(shù)的發(fā)展中計(jì)算機(jī)始終處于核心地位,不論是移動(dòng)設(shè)備、嵌入式設(shè)備,還是個(gè)人計(jì)算機(jī)、企業(yè)服務(wù)器乃至超級(jí)計(jì)算機(jī).所有這些計(jì)算機(jī)系統(tǒng)的核心部件就是其處理器[1].一款CPU的性能極大程度上決定了計(jì)算機(jī)系統(tǒng)的信息處理能力.設(shè)計(jì)和研發(fā)CPU的最新微架構(gòu),不論是從信息技術(shù)產(chǎn)業(yè)還是從國(guó)家戰(zhàn)略上來看,不僅能推動(dòng)整個(gè)信息技術(shù)的前進(jìn),而且能在不斷發(fā)展的過程中保持自身的核心競(jìng)爭(zhēng)力.CPU的緩存作為用來彌補(bǔ)不斷提高的CPU運(yùn)算速度與主存存取速度間差距的特殊結(jié)構(gòu),充分利用了CPU對(duì)數(shù)據(jù)和指令使用時(shí)的時(shí)間局部性和空間局部性原理[2],將最近或最常使用的數(shù)據(jù)進(jìn)行暫存,從而獲得處理器運(yùn)算性能上極大程度的提升.現(xiàn)代CPU的緩存經(jīng)過了長(zhǎng)足的發(fā)展,從普通的讀寫策略、替換策略到不同層級(jí)及其包含特性,乃至數(shù)據(jù)一致性問題都得到了長(zhǎng)足的發(fā)展并提出了很多設(shè)計(jì)要點(diǎn),緩存的微架構(gòu)正是從這些方面入手來構(gòu)建完善的緩存系統(tǒng).
在體系結(jié)構(gòu)研究中,軟件模擬是一種非常有效的構(gòu)建設(shè)計(jì)原型并進(jìn)行評(píng)估的方式,Cache微架構(gòu)的設(shè)計(jì)當(dāng)然也不例外.在充分理解Cache硬件結(jié)構(gòu)的基礎(chǔ)上,使用軟件方法進(jìn)行建模,能夠快速論證不同微架構(gòu)在設(shè)計(jì)上的優(yōu)劣,及對(duì)性能產(chǎn)生的影響; 同時(shí),還能采用控制變量的方式對(duì)感興趣的設(shè)計(jì)因素進(jìn)行著重考察,發(fā)現(xiàn)和分析出其與性能間的一般性關(guān)系,從而能夠反過來對(duì)原型設(shè)計(jì)給出指導(dǎo)和建議.雖然軟件模擬器使用廣泛,但單獨(dú)針對(duì)Cache的模擬工具很少,深藏于開源的全CPU模擬器中難以獨(dú)立的去研究Cache,或只是在公司或機(jī)構(gòu)內(nèi)部使用而無法獲取; 另外,由于Cache結(jié)構(gòu)的復(fù)雜性,軟件模擬一般只有某個(gè)側(cè)重點(diǎn),可以完成所有Cache的功能實(shí)現(xiàn)模擬,也可以考察精確的時(shí)序,二者同時(shí)模擬會(huì)帶來軟件設(shè)計(jì)過于復(fù)雜以及模擬運(yùn)行的速度過于緩慢的問題.
本文基于現(xiàn)代CPU Cache的硬件結(jié)構(gòu),設(shè)計(jì)實(shí)現(xiàn)了一個(gè)高可配、可擴(kuò)展的獨(dú)立Cache功能模擬器CMFSim,對(duì)不同緩存結(jié)構(gòu)、寫策略、替換策略、包含特性等多個(gè)維度提供了細(xì)粒度的配置,著重功能模擬,針對(duì)單核情形下實(shí)現(xiàn),并與DRAMSim2主存模擬模塊整合,提供了統(tǒng)一的訪存接口來進(jìn)行功能模擬.
現(xiàn)有的開源模擬器項(xiàng)目都集中在功能全面且龐大的單處理器的全系統(tǒng)模擬,以進(jìn)行整個(gè)CPU微架構(gòu)的仿真與模擬.gem5[3]就是這樣的開源全系統(tǒng)微架構(gòu)模擬器的典型代表,提供了系統(tǒng)調(diào)用模擬與全系統(tǒng)模擬兩種工作模式,提供x86、ARM、MIPS、Power、Alpha等多種指令集架構(gòu),同時(shí)支持目錄式和廣播式兩種cache一致性協(xié)議,提供基于TCP/IP的網(wǎng)絡(luò)訪問模擬等諸多特性.gem5通過社區(qū)共同維護(hù)和開發(fā),功能全面體系龐大,對(duì)于進(jìn)行全系統(tǒng)模擬而言是一個(gè)很好的工具,但主要問題是設(shè)計(jì)結(jié)構(gòu)過于復(fù)雜,難以拆解用于獨(dú)立研究某個(gè)模塊.
Zesto[4]是另一個(gè)新一代的全系統(tǒng)模擬器,這是一個(gè)在單周期水平上進(jìn)行CPU微架構(gòu)的模擬,在硬件上最接近當(dāng)前最先進(jìn)的高性能x86處理器,主要目標(biāo)就是在非常底層的微架構(gòu)設(shè)計(jì)上進(jìn)行x86指令集架構(gòu)下時(shí)鐘周期精確的模擬.但是,由于過于精確的模擬,模擬器的運(yùn)行速度非常緩慢,對(duì)于運(yùn)行模擬器的巨量指令流來說其運(yùn)行時(shí)間難以接受.同時(shí),Zesto也是一個(gè)全系統(tǒng)模擬器,也存在難以拆解的困難.
除此之外,還有SimpleScalar[5]由多種模擬工具構(gòu)建的模擬工具家族,這些工具已廣泛使用和流行了數(shù)十年時(shí)間,基于該工具集和衍生的模擬工具遍布于大量的學(xué)術(shù)文章中.但隨著處理器硬件工藝的不斷發(fā)展,很多模擬工具特別是時(shí)鐘周期精確模擬工具的硬件設(shè)定或者假設(shè)還停留在二十年前的水平[4].MARSS[6]是最新的開源全系統(tǒng)模擬器,提供了針對(duì)x86架構(gòu)下單核與多核的順序與亂序支持的時(shí)鐘精確模擬,可以直接運(yùn)行操作系統(tǒng)和x86架構(gòu)的二進(jìn)制應(yīng)用程序,是一個(gè)從處理器到內(nèi)存、磁盤到其他外部設(shè)備,從操作系統(tǒng)到共享庫和應(yīng)用程序的超全模擬器.
相對(duì)于全面、龐大的單處理器全系統(tǒng)模擬器而言,針對(duì)多處理器場(chǎng)景也存在較多模擬器項(xiàng)目.上世紀(jì)八十年代提出的高可擴(kuò)展的多處理器模擬器[7],主要模擬了各個(gè)處理器通過時(shí)序共享的單一總線進(jìn)行主存一致性訪問的架構(gòu).Augmint[8]填補(bǔ)了CISC架構(gòu)和指令混合的模擬器空缺,是一款執(zhí)行驅(qū)動(dòng)的多處理器模擬工具包.MICA[9]是新一代主要用來進(jìn)行分布式共享內(nèi)存的多處理器場(chǎng)景的模擬,運(yùn)行于多個(gè)廉價(jià)機(jī)器組成的集群上,使用應(yīng)用程序的執(zhí)行流來作為輸入,提供了各核調(diào)度與內(nèi)存互聯(lián)的算法與接口.
多處理器模擬器主要用于分布式架構(gòu)下的系統(tǒng)模擬,作為體系架構(gòu)的模擬在本質(zhì)上與單處理器相似.
現(xiàn)代CPU體系結(jié)構(gòu)的各個(gè)模塊的設(shè)計(jì)都非常復(fù)雜,各個(gè)模塊的功能和結(jié)構(gòu)很大程度上是可以獨(dú)立考察的,但全系統(tǒng)模擬器重點(diǎn)在整個(gè)系統(tǒng)的整體模擬,因此各個(gè)獨(dú)立的模塊耦合過于緊密,被淹沒與整個(gè)模擬器中,難以去獨(dú)立構(gòu)建與研究.
現(xiàn)代主流Cache的基本硬件結(jié)構(gòu)主要包括這幾個(gè)方面的內(nèi)容:Cache組織結(jié)構(gòu)、地址映射、替換策略、寫策略、多級(jí)包含性等,下面詳細(xì)闡述.
2.1.1 組織結(jié)構(gòu)與地址映射
Cache的基本硬件結(jié)構(gòu)是由SRAM構(gòu)成的陣列,陣列中每個(gè)基本存儲(chǔ)塊稱為一個(gè)cache line,所有對(duì)Cache的操作都是以cache line為基本單位進(jìn)行.由于Cache的大小遠(yuǎn)不及主存和外部存儲(chǔ)設(shè)備,需要進(jìn)行映射.對(duì)于 Cache 中的 cache line,有兩種常見的組織方式:一個(gè)地址對(duì)應(yīng)的數(shù)據(jù)只能存儲(chǔ)到固定的一個(gè)cache line中,稱為直接映射 (direct-mapped); 一個(gè)地址對(duì)應(yīng)的數(shù)據(jù)可以存儲(chǔ)在任意cache line中,稱為全相聯(lián)(fully associative).前者對(duì) Cache 的空間利用率很低,有可能某些cache line一直沒有數(shù)據(jù)存儲(chǔ)和讀取,容易發(fā)生沖突,但實(shí)現(xiàn)上最簡(jiǎn)單; 后者能充分利用不常用的cache line,空間利用率很高,不容易發(fā)生沖突,但硬件實(shí)現(xiàn)上很復(fù)雜.因此,將二者結(jié)合,兼顧空間利用率、沖突概率和實(shí)現(xiàn)難易程度,就是現(xiàn)代Cache主要的組織結(jié)構(gòu)——多路組相連(set associative).
圖1 8 個(gè) cache line 的不同組織結(jié)構(gòu)示意
硬件上為了支持一個(gè)周期處理多個(gè)請(qǐng)求,提出了bank的概念,在上述多路組相連的Cache結(jié)構(gòu)基礎(chǔ)上構(gòu)建為一個(gè)bank,然后多個(gè)bank再構(gòu)建為一級(jí)Cache.
在進(jìn)行cache line查詢的時(shí)候,需要使用訪問地址進(jìn)行索引,圖2是一個(gè)64位物理地址下各索引劃分的實(shí)例,從低位到高位有cache line內(nèi)的偏移、組索引、組內(nèi)標(biāo)簽,若分為多個(gè)bank則還需要放置bank索引.
圖2 物理地址索引劃分實(shí)例
為了索引查詢的方便,除tag外,一般各個(gè)索引地址的比特?cái)?shù)如果為N,那么對(duì)應(yīng)部分總數(shù)就是2N.圖2中組數(shù)(Set)共11比特,則總組數(shù)為2048組; Bank數(shù)占用 3 個(gè)比特,則一共有 8 個(gè) bank; cache line 的大小一般都為64,則Offset占用6比特.每次Cache操作都基于地址索引出各部分,是進(jìn)行相應(yīng)操作的基礎(chǔ).
2.1.2 替換策略
由于Cache空間有限,當(dāng)數(shù)據(jù)填充滿之后,或者需要填充的cache line被之前的占用了,那么就會(huì)發(fā)生替換,為最新的請(qǐng)求開辟新的位置.對(duì)于多路組相連的結(jié)構(gòu),每個(gè)組通過組索引只能在組內(nèi)替換,但同一個(gè)組內(nèi)的多路是可以任意選擇的,這里就存在多種替換方式的選擇了,常見策略如下:
① 隨機(jī)替換:隨機(jī)選擇一路 cache line 剔除;
② 先進(jìn)先出[10](FIFO):維護(hù)每一路寫入的順序,按照先進(jìn)先出的方式剔除最先進(jìn)入的;
③ LRU[10]:維護(hù)對(duì)每一路最近訪問的次數(shù),替換時(shí)選擇最近使用最少次數(shù)的;
④ Tree-based PLRU[11]:使用一個(gè)二叉樹結(jié)構(gòu)來維護(hù)各路的優(yōu)先級(jí),替換時(shí)剔除最不優(yōu)先的.
2.1.3 寫策略與包含性
對(duì)于Cache的寫操作,也存在不同的策略.這些策略主要作用于多級(jí)Cache結(jié)構(gòu)中,使得上下各級(jí)Cache所執(zhí)行的操作會(huì)有不同.
圖3 寫請(qǐng)求的不同策略
對(duì)于寫缺失的情況下,按照是否先分配一個(gè)cache line之后在進(jìn)行Cache寫操作分為write allocate和write no-allocate 兩種策略,其中 write allocate 方式雖然硬件實(shí)現(xiàn)復(fù)雜一些但依然是絕大多數(shù)設(shè)計(jì)的選擇.
當(dāng)引入了多層Cache之后,還有另一個(gè)需要考慮的問題就是各級(jí)Cache之間的包含關(guān)系,分為inclusive和exclusive兩種,前者要求強(qiáng)制包含,上一級(jí)的每個(gè)cache line都會(huì)在下一級(jí)存在,為了維護(hù)這種包含性需要額外的操作而花費(fèi)時(shí)鐘周期,但各級(jí)之間的數(shù)據(jù)一致性維護(hù)相對(duì)簡(jiǎn)單一些; 后者則沒有這種要求,可以上一級(jí)出現(xiàn)的cache line并不存在于下一級(jí)中,此時(shí)對(duì)于各級(jí)Cache數(shù)據(jù)一致性的維護(hù)會(huì)比較復(fù)雜.
基于前文所述的Cache硬件結(jié)構(gòu),從軟件建模的角度出發(fā),設(shè)計(jì)和定義了各個(gè)硬件結(jié)構(gòu)的軟件抽象對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu),并在此基礎(chǔ)上通過指定的配置參數(shù),選定相應(yīng)的替換算法、寫策略、包含性,并根據(jù)相應(yīng)參數(shù)實(shí)例化指定的Cache結(jié)構(gòu),構(gòu)建起整個(gè)CMFSim功能模擬器.首先,對(duì)一個(gè)單獨(dú)Cache的基本軟件模擬的系統(tǒng)架構(gòu)如圖4所示.
圖4 單級(jí) Cache 軟件建模架構(gòu)
一個(gè)完整的Cache的核心為一個(gè)CacheController,封裝為一個(gè)類,負(fù)責(zé)控制該Cache的所有行為,其所需的主要數(shù)據(jù)結(jié)構(gòu)就是DataArray和TagArray,前者用來存儲(chǔ)實(shí)際緩存的cache line數(shù)據(jù),后者則保存每個(gè)cache line相對(duì)應(yīng)的標(biāo)簽、狀態(tài)、有效性等信息.與此同時(shí)如果有多個(gè)bank,則據(jù)此構(gòu)成多個(gè)bank,Cache-Controller負(fù)責(zé)控制到某個(gè)bank的訪問,將每個(gè)請(qǐng)求都以AccessContext對(duì)象的方式進(jìn)行包裝,該對(duì)象是內(nèi)部各個(gè)接口之間傳遞數(shù)據(jù)的通用數(shù)據(jù)結(jié)構(gòu).每個(gè)cache默認(rèn)為一個(gè)bank,通過讀取用戶在配置文件中給定的配置,來實(shí)例化每個(gè)DataArray和TagArray的大小,同時(shí)構(gòu)造出相應(yīng)數(shù)目的bank; 與此同時(shí),還根據(jù)指定的替換算法進(jìn)行選擇,決定構(gòu)建相應(yīng)的ReplacePolicy對(duì)象; 最后,還需要依據(jù)配置中給定的索引劃分起始比特與長(zhǎng)度,來使用Indexer類進(jìn)行物理地址各部分的劃分.另外,對(duì)運(yùn)行過程和結(jié)果中的各項(xiàng)關(guān)鍵信息需要進(jìn)行日志記錄,如總的讀寫次數(shù)、命中失效次數(shù)、讀取和寫入的數(shù)據(jù)量等信息.
2.2.1 DataArray 與 TagArray 抽象
對(duì)于Cache的行為可以從軟件角度抽象出讀和寫兩種接口,分別對(duì)DataArray和TagArray兩個(gè)數(shù)據(jù)結(jié)果進(jìn)行操作,這也正好對(duì)應(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都是一個(gè)類似“二維數(shù)組”的結(jié)構(gòu),來支持多路組相連的 cache line 組織結(jié)構(gòu),第一維為組數(shù),第二維為路數(shù).每個(gè)元素,也就是表1中Entry的定義,代表了“數(shù)組”中每一項(xiàng)的具體內(nèi)容.對(duì)于DataArray,其讀寫接口只提供組索引和路索引的方式進(jìn)行執(zhí)行,因?yàn)檫@些操作是以TagArray的Tag和狀態(tài)進(jìn)行比較和判定為基礎(chǔ)的,直接操作的就是Cache中的數(shù)據(jù).但TagArray首先提供了針對(duì)Tag的讀寫接口,同時(shí)提供了針對(duì)狀態(tài)位的讀寫操作中,這類狀態(tài)位的操作接口以get與set開頭來命名,可以按照Tag進(jìn)行匹配后執(zhí)行,也可以用路索引進(jìn)行強(qiáng)制設(shè)置的方式執(zhí)行,從而滿足不同場(chǎng)景下對(duì)TagArray狀態(tài)的設(shè)置需求.另外,還提供了判斷某一組cache line是否是全部被占用的“busy”接口,可以用來判斷是否需要對(duì)當(dāng)前組內(nèi)的某個(gè)cache line進(jìn)行替換操作.
2.2.2 替換策略與索引劃分
圖4中的ReplacePolicy類維護(hù)了每個(gè)cache line相對(duì)應(yīng)的狀態(tài),這些狀態(tài)也是一個(gè)二維數(shù)組的結(jié)構(gòu).對(duì)于給定的某一組,通過索引第一維,得到該組內(nèi)各個(gè)cache line的一維狀態(tài)數(shù)組,前文所述的四種替換算法均能以此為基礎(chǔ)實(shí)現(xiàn),通過建模和驗(yàn)證,以C++模板方式實(shí)現(xiàn),只需要提供如下兩個(gè)通用的接口:
傳入的參數(shù)ref表示當(dāng)前訪問的cache line所在組的各cache line的狀態(tài)數(shù)組,update接口用來更新指定路索引的cache line狀態(tài),get接口用來獲取當(dāng)前組內(nèi)需要剔除的cache line的路索引.這兩個(gè)接口能夠兼容前文所述的四種算法的實(shí)現(xiàn).FIFO替換算法的update接口描述如下:
ref數(shù)組中每個(gè)值為路索引,第一個(gè)元素保存的是上一次訪問的,第二個(gè)為上上一次訪問的,以此類推,最后一個(gè)元素保存的是最早訪問的.每次更新的時(shí)候找到當(dāng)前訪問的路(第2到5行),將數(shù)組中在其之前的向后移動(dòng)一個(gè)元素(第6到7行),然后把當(dāng)前路索引放在數(shù)組第一個(gè)位置(第8行).調(diào)用get接口進(jìn)行獲取替換的路索引時(shí),直接返回?cái)?shù)組最后一個(gè)元素的值即可.對(duì)于PLRU算法,則只需要使用狀態(tài)數(shù)組的前N-1個(gè)元素(N為每一組的路數(shù)),模擬一個(gè)完全二叉樹,其update和get接口的實(shí)現(xiàn)算法描述如下:
每個(gè)元素要么為0要么為1,0往左子樹走1往右子樹走,通過與二叉堆相似的方式,在進(jìn)行更新的時(shí)候把路索引的二進(jìn)制表示在樹中進(jìn)行遍歷,將遍歷路徑上的每一個(gè)元素的值進(jìn)行反轉(zhuǎn)(第6行).調(diào)用get接口就直接依據(jù)樹中每個(gè)元素的值進(jìn)行遍歷得到相應(yīng)的二進(jìn)制值就是需要替換的路索引(第3行).對(duì)于,LRU和隨機(jī)替換,均能在狀態(tài)數(shù)組的基礎(chǔ)上實(shí)現(xiàn),在此不予贅述.
與此同時(shí),CacheController需要使用Indexer類對(duì)輸入請(qǐng)求的物理地址進(jìn)行劃分,需要執(zhí)行的就是對(duì)給定的物理地址進(jìn)行按位操作即可,劃分的依據(jù)是Config中給出的各部分起始比特和長(zhǎng)度.
2.2.3 CacheSystem 與完整訪存系統(tǒng)
在構(gòu)建完整的單級(jí)Cache之后,就可以著手構(gòu)建多級(jí)的Cache系統(tǒng).圖5描述了一個(gè)指定的典型三級(jí)Cache系統(tǒng)與DRAMSim2構(gòu)建的完整訪存系統(tǒng)架構(gòu).多級(jí)Cache之間目前僅支持對(duì)相互的包含性的設(shè)置.CacheSystem的架構(gòu)可以通過不同的配置來自行設(shè)置和定義,配置文件以ini格式的語法描述并進(jìn)行解析,圖5中的三級(jí)結(jié)構(gòu)配置以及L3的索引配置如下:
其他完整配置類似,還包括各級(jí)的替換策略、寫命中與寫失效的策略等,使用者可以依據(jù)配置文件的語法進(jìn)行自定義配置,來構(gòu)建不同微架構(gòu)的CacheSystem.
CacheSystem通過讀取和解析配置文件,依次傳遞給各單級(jí)Cache的Config去構(gòu)建每一級(jí)Cache,得到的多級(jí)Cache實(shí)例被CacheSystem類操縱和使用.CacheSystem最終在整個(gè)系統(tǒng)中以單例形式呈現(xiàn),并整合了開源的主存模擬模塊DRAMSim2,對(duì)外提供了統(tǒng)一的訪存讀寫接口來調(diào)用.
圖5 CacheSystem 與 DRAMSim2 構(gòu)建的訪存系統(tǒng)
整個(gè)系統(tǒng)除了提供以動(dòng)態(tài)鏈接庫的形式作為獨(dú)立模塊供外部調(diào)用之外,圖5中還給出了其提供的Trace模塊,可以一起編譯為一個(gè)可執(zhí)行文件,來接收應(yīng)用程序進(jìn)行訪存操作的trace流文件作為輸入,單獨(dú)進(jìn)行Cache微架構(gòu)的研究和功能驗(yàn)證.
基于本文實(shí)現(xiàn)的CMFSim功能模擬器,編譯為接收訪存操作的trace為輸入的可執(zhí)行文件來進(jìn)行測(cè)試.測(cè)試平臺(tái)為 64 位 Ubuntu 14.04 操作系統(tǒng),Intel i5 雙核 CPU,1 GB 內(nèi)存.
首先使用二進(jìn)制分析平臺(tái)Pin[16],實(shí)現(xiàn)了獲取應(yīng)用程序訪存操作trace的工具,對(duì)Ubuntu系統(tǒng)下的“/bin/ls”程序的訪存操作trace進(jìn)行了捕獲,共得到了34萬多條訪存操作記錄.獲取的trace記錄示例如下:
其中的第一列的“R”和“W”分別代表讀請(qǐng)求和寫請(qǐng)求,緊接著的一列為當(dāng)前請(qǐng)求的物理地址,最后一列為一個(gè)整數(shù),代表此次請(qǐng)求的數(shù)據(jù)長(zhǎng)度.
以上述trace為輸入,首先構(gòu)建了測(cè)試不同Cache結(jié)構(gòu)與命中率關(guān)系的實(shí)驗(yàn),分別配置不同大小的組數(shù)來統(tǒng)計(jì)命中率.
圖6為測(cè)試結(jié)果,S表示組數(shù)(Set),W代表路數(shù)(Way),可以看出隨著組數(shù)不斷增加,命中率是不斷提高的,但是當(dāng)增加到一定程度,命中率提高的幅度就不太明顯了,當(dāng)命中率的提高不足以彌補(bǔ)硬件成本的增加時(shí)就需要進(jìn)行折中,這對(duì)特定結(jié)構(gòu)的Cache設(shè)計(jì)具有驗(yàn)證和指導(dǎo)意義.
圖6 Cache 結(jié)構(gòu)與命中率的關(guān)系
對(duì)于Cache使用物理地址進(jìn)行劃分索引,其劃分位置非常深刻地影響了命中率.因此設(shè)計(jì)了如下的實(shí)驗(yàn):從物理地址的第6比特開始依次往后滑動(dòng),分別統(tǒng)計(jì)不同組索引位置下的命中率,從圖7中可以很明顯的看出,隨著組索引逐漸向高比特移動(dòng)命中率逐漸上升,在第11比特進(jìn)行劃分的組索引的命中率最好,而且兩種不同Cache結(jié)構(gòu)都是如此,當(dāng)超過11比特再往高比特移動(dòng)命中率就開始下降了.但是,對(duì)于Cache最終設(shè)計(jì)方案,需要綜合考慮不同類型的程序,若是針對(duì)某一特定領(lǐng)域的設(shè)計(jì)可以進(jìn)行特殊設(shè)計(jì),否則針對(duì)通用領(lǐng)域需要進(jìn)行折中,該Cache模擬器可以對(duì)這些設(shè)計(jì)進(jìn)行驗(yàn)證和評(píng)估.
圖7 Cache 劃分組索引與命中率關(guān)系
按照?qǐng)D5所標(biāo)注的配置,構(gòu)建了一個(gè)三級(jí)的Cache系統(tǒng),L1配置為4路512組,L2配置為4路1024組,L3 配置為 4 個(gè) bank,每個(gè) 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)計(jì)的L1、L2、L3各自的命中率見圖8.
圖8 三級(jí) Cache 系統(tǒng)的命中率
與圖7中的結(jié)果對(duì)比,L1和L2都達(dá)到了最優(yōu)命中率但L1、L2的組數(shù)明顯要小很多,可以看出這種多級(jí)配置下的緩存系統(tǒng)對(duì)命中率的提升,在硬件設(shè)計(jì)上可以增加L1、L2的硬件成本,而減小L3的硬件成本,從而可以在保證命中率的基礎(chǔ)上降低整體的成本.
針對(duì)處理器體系結(jié)構(gòu)中的緩存這一獨(dú)立模塊的模擬器大都深藏于大量的全功能模擬器中,本文以現(xiàn)代先進(jìn)CPU緩存的硬件結(jié)構(gòu)為依托,從軟件建模與仿真的角度,設(shè)計(jì)實(shí)現(xiàn)了一個(gè)功能完善、高可配、模塊獨(dú)立的單核下的多級(jí)緩存功能模擬器CMFSim,并與開源的DRAMSim2整合,封裝了統(tǒng)一的訪存接口方便調(diào)用,能夠從功能驗(yàn)證的角度完成緩存微架構(gòu)的模擬.通過實(shí)驗(yàn)分析,驗(yàn)證了緩存微架構(gòu)設(shè)計(jì)與命中率之間的關(guān)系,能夠表明該獨(dú)立的緩存功能模擬模塊的有效性,可以作為獨(dú)立模塊去構(gòu)建完整的全功能模擬器.
本文僅針對(duì)單核下的功能模擬為主要目標(biāo),因?yàn)橹挥脕磉M(jìn)行功能驗(yàn)證和性能評(píng)估,對(duì)于多核情況只需進(jìn)行相應(yīng)的橫向擴(kuò)展,比如以多線程方式將CMFSim運(yùn)行多個(gè)實(shí)例的方式即可進(jìn)行功能模擬.在未來的研究與開發(fā)中,將考慮多核下的精確時(shí)序模擬與數(shù)據(jù)一致性的模擬,實(shí)現(xiàn)更加精細(xì)化的微架構(gòu)建模與評(píng)估.
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ì)算機(jī)系統(tǒng)應(yīng)用,2017,26(10):36–43.http://www.c-sa.org.cn/1003-3254/5990.html
國(guó)家“核高基”科技重大專項(xiàng)(2014ZX01029101-002)
2017-01-19; 采用時(shí)間:2017-02-15