基于緩存訪問模式的C-AMAT 測(cè)量方法及其在圖計(jì)算中的應(yīng)用

陳炳彰 劉 偉,2 于蕭鈺

1（武漢理工大學(xué)計(jì)算機(jī)與人工智能學(xué)院 武漢 430073）

2（交通物聯(lián)網(wǎng)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室（武漢理工大學(xué)） 武漢 430073）

（chenbingzhang@whut.edu.cn）

大數(shù)據(jù)時(shí)代下，人類社會(huì)中大規(guī)模與不規(guī)律數(shù)據(jù)信息快速增長，以圖結(jié)構(gòu)對(duì)這些數(shù)據(jù)進(jìn)行存儲(chǔ)分析越來越普遍.基于圖結(jié)構(gòu)的信息存儲(chǔ)方式被廣泛應(yīng)用于人際關(guān)系、社交網(wǎng)絡(luò)分析、社會(huì)科學(xué)等各個(gè)領(lǐng)域，圖數(shù)據(jù)處理變得越來越重要.而目前圖應(yīng)用的主要性能瓶頸就在于其數(shù)據(jù)訪問層面[1]，因此對(duì)于圖應(yīng)用在存儲(chǔ)器中性能的評(píng)估與分析對(duì)于相應(yīng)的硬件開發(fā)和算法設(shè)計(jì)都具有重要意義.

并發(fā)式平均存儲(chǔ)訪問時(shí)間（concurrent average memory access time，C-AMAT）模型通過同時(shí)考慮存儲(chǔ)器訪問的局部性和并發(fā)性[2]，可以更準(zhǔn)確地表征圖應(yīng)用的存儲(chǔ)器性能.但是C-AMAT 的計(jì)算模型認(rèn)為數(shù)據(jù)訪問的命中時(shí)間總是固定的，存在一定的局限性，同時(shí)，又因?yàn)槠錅y(cè)量裝置硬件開銷大，使得其在實(shí)際應(yīng)用中是不易實(shí)現(xiàn)的.

為了利用C-AMAT 準(zhǔn)確地評(píng)估檢測(cè)圖應(yīng)用的存儲(chǔ)器性能，我們基于緩存的訪問模式將C-AMAT 的計(jì)算模型擴(kuò)展為PC-AMAT（parallel C-AMAT）和SCAMAT（serial C-AMAT），并在此基礎(chǔ)上設(shè)計(jì)并實(shí)現(xiàn)了C-AMAT 中純粹缺失周期（pure miss cycle，PMC）的提取算法及所需各項(xiàng)參數(shù)的測(cè)量.最終利用CAMAT 在gem5[3]模擬器中對(duì)各類圖應(yīng)用在存儲(chǔ)器中的性能進(jìn)行了實(shí)驗(yàn)評(píng)估與分析，提出了相應(yīng)的訪存優(yōu)化策略.

本文的主要貢獻(xiàn)包括3 個(gè)方面：

1）基于緩存的數(shù)據(jù)訪問模式將C-AMAT 的計(jì)算模型擴(kuò)展為PC-AMAT 和SC-AMAT，使C-AMAT 的計(jì)算模型與現(xiàn)代計(jì)算機(jī)中不同層次的存儲(chǔ)器訪問模式相匹配，從而為更準(zhǔn)確地測(cè)量和計(jì)算應(yīng)用程序運(yùn)行過程中對(duì)數(shù)據(jù)的并發(fā)式平均存儲(chǔ)訪問時(shí)間提供了理論依據(jù)；

2）設(shè)計(jì)并實(shí)現(xiàn)了計(jì)算C-AMAT 所需的重要中間參數(shù)純粹缺失周期的提取算法，避免了直接測(cè)量所需要的巨大硬件開銷；

3）利用相關(guān)系數(shù)驗(yàn)證了PC-AMAT 和SC-AMAT與?PC 之間的相關(guān)性比C-AMAT 更強(qiáng)，進(jìn)一步設(shè)計(jì)了圖應(yīng)用的存儲(chǔ)器性能評(píng)估實(shí)驗(yàn)，通過應(yīng)用各種規(guī)模的圖數(shù)據(jù)集對(duì)圖應(yīng)用的訪存性能進(jìn)行了系統(tǒng)性地分析.

1 相關(guān)工作

圖處理是大數(shù)據(jù)領(lǐng)域中一類重要的計(jì)算方式，在機(jī)器學(xué)習(xí)、路徑規(guī)劃、傳染病學(xué)、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域都有廣泛應(yīng)用.

現(xiàn)實(shí)世界的圖數(shù)據(jù)往往呈現(xiàn)出小世界性（smallworld）[4]和無尺度性（scale-free）[5]，稀疏矩陣存儲(chǔ)格式是典型的圖數(shù)據(jù)存儲(chǔ)格式，盡管有研究表明基于稀疏矩陣的壓縮稀疏行（compressed sparse row，CSR）、對(duì)角線（diagonal，D?A）[6]等格式存儲(chǔ)效率很高，但仍然改變不了圖數(shù)據(jù)訪問的不規(guī)則性，存儲(chǔ)器性能效率低下已經(jīng)成為圖應(yīng)用發(fā)展中最大的性能瓶頸.目前學(xué)術(shù)界關(guān)于圖數(shù)據(jù)處理性能的研究有很多.Basak等人[1]通過分析亂序CPU 下圖數(shù)據(jù)的訪存行為發(fā)現(xiàn)不同數(shù)據(jù)類型加載指令之間的依賴鏈（load-load dependency chain，LLDC）是實(shí)現(xiàn)高內(nèi)存級(jí)并行（memory level parallelism，MLP）的主要瓶頸；Balaji 等人[7]在末級(jí)緩存（last level cache，LLC）更換不同的數(shù)據(jù)替換策略時(shí)發(fā)現(xiàn)，即使是最先進(jìn)的緩存數(shù)據(jù)替換策略，圖應(yīng)用在LLC 上的MPK?（misses per kilo instructions）依然沒有明顯下降；湯嘉武等人[8]通過實(shí)驗(yàn)分析出通用高層次綜合（high level synthesis，HLS）系統(tǒng)缺乏對(duì)不規(guī)則圖算法有效支撐的問題，提出了一種面向圖計(jì)算的高效HLS 方法，實(shí)現(xiàn)了高效的并行流水執(zhí)行；Faldu等人[9]驗(yàn)證了由于圖分析的高度不規(guī)則訪問模式，最先進(jìn)的硬件緩存管理方案在利用其重用方面依然不盡人意，為此，他們引入了專門用于LLC 上對(duì)圖分析進(jìn)行緩存管理的GRASP，GRASP 專用緩存策略利用了熱頂點(diǎn)固有的高重用，同時(shí)保留了捕獲其他緩存塊中圖數(shù)據(jù)重用的靈活性；Cooksey 等人[10]則從高速緩存行中獲取任何看似合理的地址作為數(shù)據(jù)加載，但是，只有觀察到數(shù)據(jù)結(jié)構(gòu)是一個(gè)指針列表時(shí)，這些指針才將被引用，否則此類方案將顯著超載，從而導(dǎo)致緩存污染和性能下降.

盡管學(xué)術(shù)界現(xiàn)有的研究工作從多個(gè)維度對(duì)圖應(yīng)用進(jìn)行性能評(píng)測(cè)都發(fā)現(xiàn)了其性能瓶頸在訪存層面，但采用的系統(tǒng)性能評(píng)估指標(biāo)更多地停留在以計(jì)算為中心的層面，最為廣泛使用的便是每周期完成指令數(shù)（instruction per clock，?PC），但?PC 是被設(shè)計(jì)用來測(cè)試CPU 性能的，并且由于?PC 受指令集、CPU 微架構(gòu)、存儲(chǔ)器層次結(jié)構(gòu)和編譯器技術(shù)等多方面的影響，無法直接用來反映存儲(chǔ)器系統(tǒng)的性能.另一方面，傳統(tǒng)的存儲(chǔ)器性能指標(biāo)，如訪存缺失率（miss rate，MR）、平均缺失代價(jià)（average miss penalty，AMP）、平均存儲(chǔ)器訪問時(shí)間（average memory access time，AMAT），對(duì)于采用流水線緩存[11]、非阻塞緩存[12]等現(xiàn)代設(shè)計(jì)的存儲(chǔ)器系統(tǒng)來說是不合適的.我們?cè)趃em5 中對(duì)內(nèi)核數(shù)量進(jìn)行了倍增，以此提高LLC 上的并發(fā)性，在對(duì)GAP[13]基準(zhǔn)測(cè)試套件中典型的BFS（breadth first search），PR（PageRank），BC（betweenness centrality），CC（connected components）這4 個(gè)算法在LLC 上 的AMAT 進(jìn)行了測(cè)量，其中實(shí)驗(yàn)環(huán)境配置及工作負(fù)載見第4 節(jié).圖1 顯示了當(dāng)并發(fā)性作為一個(gè)因素時(shí)，AMAT 作為衡量?jī)?nèi)存性能的指標(biāo)是失敗的，AMAT指標(biāo)表明：隨著內(nèi)核數(shù)量的增加，LLC 上的總體性能會(huì)下降.這和系統(tǒng)性能提升的事實(shí)相違背，顯然是錯(cuò)誤的.這也進(jìn)一步表明AMAT 已無法準(zhǔn)確反映現(xiàn)代處理器的內(nèi)存性能.

Fig.1 AMAT of LLC at different number of cores圖1 不同內(nèi)核數(shù)量下LLC 的AMAT

2013 年，Sun 等人[2]提出了新的存儲(chǔ)器性能度量標(biāo)準(zhǔn)C-AMAT，C-AMAT 通過給出嚴(yán)格規(guī)整的數(shù)學(xué)表達(dá)式和邏輯證明，將AMAT 進(jìn)行了擴(kuò)展，可以更準(zhǔn)確、全面地評(píng)估現(xiàn)代存儲(chǔ)器系統(tǒng).

在定量上，C-AMAT 被定義為總的存儲(chǔ)訪問周期除以總的存儲(chǔ)訪問次數(shù)[2]：

其中TMemCycle代表總的存儲(chǔ)訪問周期，CMemAcc則代表總的存儲(chǔ)訪問次數(shù).需要注意的是，TMemCycle是以重疊模式計(jì)算的，換句話說，當(dāng)同一周期內(nèi)存在多個(gè)內(nèi)存訪問時(shí)，TMemCycle僅增加1 個(gè)周期.此外，存儲(chǔ)訪問周期與CPU 周期不同，至少有1 次未完成內(nèi)存訪問的CPU 周期才能算作內(nèi)存訪問周期.

根據(jù)相關(guān)系數(shù)的定義，C-AMAT 應(yīng)該與?PC 呈負(fù)相關(guān)[14]，即?PC 增加時(shí)，C-AMAT 減少.此外,當(dāng)?PC 有很大程度的增加時(shí)，C-AMAT 也應(yīng)該有類似程度的變化.然而，當(dāng)我們?cè)趯?duì)GAP 基準(zhǔn)測(cè)試套件中圖應(yīng)用進(jìn)行測(cè)量時(shí)發(fā)現(xiàn)，圖應(yīng)用的?PC 并不總與C-AMAT呈負(fù)相關(guān).實(shí)驗(yàn)結(jié)果如圖2 所示，其中實(shí)驗(yàn)環(huán)境配置及工作負(fù)載見第4 節(jié).為了更直觀地表現(xiàn)?PC 和CAMAT 之間的關(guān)系變化，對(duì)圖算法在各個(gè)數(shù)據(jù)集中的?PC 和C-AMAT 的平均值進(jìn)行了比較.在圖2（a）中我們看到，隨著內(nèi)核數(shù)量的增加，?PC 也隨之遞增.然而從圖2（b）～（d）中發(fā)現(xiàn)，隨著內(nèi)核數(shù)量的增加，在各級(jí)cache 中的C-AMAT 僅BFS 算法在L1 和LLC中呈現(xiàn)出遞減的趨勢(shì)，其他算法在各級(jí)cache 中的變化則是無規(guī)律的，且變化幅度也是遠(yuǎn)小于?PC 的.

Fig.2 ?PC and C-AMAT of each cache level圖2 ?PC 和各級(jí)cache 的C-AMAT

之所以出現(xiàn)圖2 中的現(xiàn)象，是因?yàn)镃-AMAT 的計(jì)算模型總是認(rèn)為數(shù)據(jù)訪問過程中的命中延時(shí)是固定的，忽略了cache 層中的數(shù)據(jù)訪問模式，使用固定的cache 訪問延時(shí)會(huì)導(dǎo)致測(cè)量出的總存儲(chǔ)訪問周期TMemCycle與其理論值有所偏差.

事實(shí)上，現(xiàn)代處理器多采用亂序執(zhí)行來提升CPU的處理效率，典型的如?ntel 在x86 體系中的Pentium Pro，為了提高時(shí)鐘頻率并降低cache 的缺失代價(jià)，對(duì)于cache 中的Tag SRAM 和Data SRAM 這2 部分的訪問模式，現(xiàn)代處理器往往在L1 cache 采用了并行訪問的結(jié)構(gòu)，但其訪問命中時(shí)間并不是簡(jiǎn)單的Tag 與Data 延時(shí)相加得到的.而L2 cache 以及下一級(jí)cache的數(shù)據(jù)訪問則通常采用的是串行訪問模式[15]，即對(duì)于L2 cache 及下一級(jí)cache 而言，它們的命中延時(shí)在訪問命中和訪問缺失時(shí)不再是固定的，因此，CAMAT 的計(jì)算模型可能無法完全正確地表征存儲(chǔ)器系統(tǒng)的整體性能.其中的計(jì)算細(xì)節(jié)我們將在第2 節(jié)重點(diǎn)討論.

另一方面，與AMAT 相比，C-AMAT 的計(jì)算方法也更加復(fù)雜，并且需要額外的檢測(cè)邏輯和寄存器來測(cè)量C-AMAT 所需的參數(shù)，盡管文獻(xiàn)[14]給出了每周期訪問（access per cycle，APC）的測(cè)量邏輯，但這種方法卻有著較大的硬件開銷和繁雜的計(jì)數(shù)邏輯，不易實(shí)現(xiàn).因此，如何準(zhǔn)確獲取一段完整應(yīng)用程序中的純粹缺失周期和純粹缺失訪問仍然是測(cè)量C-AMAT的重點(diǎn)和難點(diǎn).

為了準(zhǔn)確度量圖應(yīng)用的存儲(chǔ)性能，本文通過分析前人研究成果，基于現(xiàn)代亂序處理器中不同層次cache 的不同訪問模式，將C-AMAT 的計(jì)算模型擴(kuò)展為PC-AMAT 和SC-AMAT，完善了C-AMAT 的計(jì)算模型.同時(shí)提出并實(shí)現(xiàn)了純粹缺失周期和純粹缺失訪問的提取算法，最終基于PC-AMAT 和SC-AMAT 對(duì)圖應(yīng)用的存儲(chǔ)性能進(jìn)行表征，這使得尋找到適用于圖應(yīng)用系統(tǒng)的整體最佳參數(shù)組合成為可能.

2 PC-AMAT 和SC-AMAT 的計(jì)算模型

由于我們的工作直接基于C-AMAT，因此在本節(jié)首先介紹了C-AMAT 的計(jì)算模型，然后通過分析不同層次cache 的數(shù)據(jù)訪問模式，引入了基于C-AMAT擴(kuò)展的PC-AMAT 和SC-AMAT 的計(jì)算模型.

2.1 C-AMAT 計(jì)算模型

式（1）給出了C-AMAT 的原始定量公式，但并沒有明顯體現(xiàn)出C-AMAT 的局部性和并發(fā)性，為了體現(xiàn)這2 種性質(zhì)，給出了C-AMAT 的詳細(xì)計(jì)算公式[2]：

其中H代表命中延時(shí)，Ch和Cm分別代表命中存儲(chǔ)請(qǐng)求的并發(fā)度和缺失存儲(chǔ)請(qǐng)求的并發(fā)度，Ch和Cm是CAMAT 引入的2 個(gè)新參數(shù).此外，這個(gè)計(jì)算公式首次引入了“純粹缺失”的概念，即只有在缺失訪問中至少包括1 個(gè)純粹缺失周期，在這個(gè)周期中，整個(gè)存儲(chǔ)系統(tǒng)都沒有命中發(fā)生，這樣的缺失才稱為純粹缺失.pMR為純粹缺失率，即純粹缺失訪問的次數(shù)與全部存儲(chǔ)訪問次數(shù)之比.pAMP即純粹平均缺失代價(jià)，代表平均每個(gè)純粹缺失訪問中的純粹缺失周期的數(shù)量[2].

然而，在C-AMAT 中，無論當(dāng)前層級(jí)存儲(chǔ)器中的數(shù)據(jù)是否命中，它的命中時(shí)延總被認(rèn)為是固定的.事實(shí)上，現(xiàn)代處理器中cache 層的數(shù)據(jù)命中時(shí)間與其訪問模式息息相關(guān)，因此，我們基于cache 訪問模式對(duì)C-AMAT 的計(jì)算模型進(jìn)行了細(xì)粒度的擴(kuò)展.

2.2 PC-AMAT 計(jì)算模型

現(xiàn)代處理器中的cache 由Tag 和Data 這2 部分組成，但在實(shí)際的實(shí)現(xiàn)當(dāng)中，cache line 中的Tag 和Data 部分其實(shí)是分開放置的，稱為Tag SRAM 和Data SRAM，如果對(duì)這2 部分的內(nèi)容同時(shí)進(jìn)行訪問，則稱為并行訪問[16]，其結(jié)構(gòu)如圖3 所示；反之，如果先訪問Tag SRAM 部分，根據(jù)Tag 的比較結(jié)果再去訪問Data SRAM 部分，這種方式則稱為串行訪問[16]，其結(jié)構(gòu)如圖4 所示.

Fig.3 Parallel access mode in cache圖3 cache 中的并行訪問模式

當(dāng)對(duì)圖3 這種結(jié)構(gòu)的cache 進(jìn)行訪問時(shí)，在對(duì)某個(gè)Tag 部分的地址訪問的同時(shí)會(huì)對(duì)該地址對(duì)應(yīng)Data部分的數(shù)據(jù)也進(jìn)行訪問，并將它們送到多路選擇器中選擇出指定的數(shù)據(jù)塊，最終經(jīng)過數(shù)據(jù)對(duì)齊便可完成數(shù)據(jù)訪問.由于現(xiàn)代超標(biāo)量處理器使用的是流水線訪問，數(shù)據(jù)塊選擇時(shí)間和數(shù)據(jù)對(duì)齊部分的時(shí)間是可以忽略不計(jì)的，因此，在cache 的并行訪問結(jié)構(gòu)中完成一次數(shù)據(jù)訪問的時(shí)間其實(shí)是由Tag 和Data 中訪問延時(shí)較長的部分所決定的，此時(shí)如將Tag 與Data訪問延時(shí)之和作為cache 命中時(shí)間是錯(cuò)誤的，因?yàn)檫@將會(huì)嚴(yán)重高估C-AMAT 的值.因此，并行結(jié)構(gòu)下基于C-AMAT的PC-AMAT 可以表示為式（3）.

在PC-AMAT 中，PH代表了并發(fā)cache 命中時(shí)間，即在并行訪問結(jié)構(gòu)中，cache 的命中延時(shí)PH由Tag延時(shí)和Data 延時(shí)的較大者決定，因此PH可以表示為：

其中tag_latency和data_latency分別表示Tag 部分訪問和Data 部分訪問所需要的命中時(shí)間，一般情況下，現(xiàn)代處理器中L1 cache 在這2 部分的延遲都在2～5個(gè)周期之間，同一架構(gòu)處理器中的tag_latency和data_latency差距并不會(huì)太大[17]，但文獻(xiàn)[18]中將命中時(shí)延統(tǒng)一成一個(gè)固定的參數(shù)顯然是與事實(shí)不符的，這會(huì)造成Cph和Cm的計(jì)算誤差，最終導(dǎo)致計(jì)算出來的CAMAT 值與實(shí)際值存在較大誤差.Cph和Cm的計(jì)算方式為：

其中access表示當(dāng)前存儲(chǔ)器中總的數(shù)據(jù)訪問次數(shù)，overlap_hitTime表示當(dāng)前cache 訪問過程中的重疊命中時(shí)間，pMissTime表示所有數(shù)據(jù)訪問總的純粹缺失周期，而pMissTime_overlap則代表了所有數(shù)據(jù)訪問過程中總的重疊純粹缺失周期.我們將在第3 節(jié)詳細(xì)解讀上述變量的取值.

2.3 SC-AMAT 計(jì)算模型

圖4 展示了cache 的串行訪問結(jié)構(gòu)，在對(duì)數(shù)據(jù)進(jìn)行訪問時(shí)，首先需要對(duì)Tag SRAM 進(jìn)行訪問，進(jìn)行Tag 比對(duì)之后，若Tag 對(duì)應(yīng)的Data 部分中的數(shù)據(jù)在當(dāng)前cache 層中存在，則對(duì)其進(jìn)行選擇訪問，此時(shí)就不再需要進(jìn)行數(shù)據(jù)對(duì)齊即可對(duì)指定的數(shù)據(jù)塊進(jìn)行訪問，這樣的1 次數(shù)據(jù)訪問命中時(shí)間就是Tag 與Data 的訪問延時(shí)之和；但若對(duì)Tag 進(jìn)行訪問后在當(dāng)前cache 層中未檢測(cè)到對(duì)應(yīng)的數(shù)據(jù)部分，則進(jìn)入下一級(jí)存儲(chǔ)器進(jìn)行訪問，此時(shí)當(dāng)前cache 層中數(shù)據(jù)訪問的命中時(shí)間只需將Tag 部分延時(shí)包含在內(nèi).

因此，串行訪問結(jié)構(gòu)是不需要多路選擇器進(jìn)行數(shù)據(jù)選擇的，而只需要訪問數(shù)據(jù)部分指定的那個(gè)SRAM，其他的SRAM 由于都不需要被訪問，可以將它們的使能信號(hào)置為無效，這樣就可以節(jié)省很多功耗，串行訪問結(jié)構(gòu)也多被應(yīng)用于現(xiàn)代處理器的L2 cache 和LLC.即串行結(jié)構(gòu)下的cache 訪問，其命中時(shí)間是由數(shù)據(jù)是否命中所決定的.因此，串行結(jié)構(gòu)下基于C-AMAT 的SC-AMAT 可以表示為：

盡管在SC-AMAT 中，SH也代表著cache 的命中時(shí)間，但不同于式（2）中的PH，SH的大小是由數(shù)據(jù)是否命中決定的，因此，SH可表示為：

當(dāng)數(shù)據(jù)訪問命中時(shí)，命中時(shí)間SH是tag_latency和data_latency相加，而當(dāng)數(shù)據(jù)訪問缺失時(shí)，其命中時(shí)間SH則只由tag_latency決定.現(xiàn)代處理器中L2 cache 在這2 部分的延遲都在6～12 個(gè)周期，LLC 在這2 部分的延遲一般在32～64 個(gè)周期[17]，當(dāng)然，精確的訪問延時(shí)需要根據(jù)具體的CPU 架構(gòu)來確定.但顯而易見，此時(shí)命中延時(shí)SH不是固定值，使用式（2）中的H將會(huì)對(duì)并發(fā)式平均訪問時(shí)間的計(jì)算結(jié)果造成不可忽略的誤差.相應(yīng)地，串行訪問結(jié)構(gòu)下數(shù)據(jù)訪問的命中并發(fā)度Csh的表達(dá)式為：

其中hit代表當(dāng)前存儲(chǔ)器中數(shù)據(jù)訪問的命中次數(shù)，miss表示當(dāng)前存儲(chǔ)器中數(shù)據(jù)訪問的缺失次數(shù)，與Cph一樣，Csh的分母overlap_hitTime依然是當(dāng)前cache 訪問過程中的重疊命中時(shí)間.

第4 節(jié)中我們將會(huì)根據(jù)?PC 與C-AMAT，PCAMAT，SC-AMAT 這3 個(gè)指標(biāo)的相關(guān)系數(shù)來度量這3個(gè)指標(biāo)的精確度，以驗(yàn)證擴(kuò)展C-AMAT 為PC-AMAT與SC-AMAT 的必要性與合理性.

3 純粹缺失周期提取算法

本節(jié)詳細(xì)介紹如何提取PC-AMAT 和SC-AMAT測(cè)量過程中所需的重要中間參數(shù)—純粹缺失周期，并據(jù)此計(jì)算出pMR，pAMP，Cm等依賴PMC 的計(jì)算參數(shù)，進(jìn)而計(jì)算出PC-AMAT和SC-AMAT.

根據(jù)式（2），我們知道想要計(jì)算C-AMAT 首先需要測(cè)量Ch和Cm.文獻(xiàn)[18]提供了Ch和Cm的計(jì)算方法，如圖5 所示.通過在原有的硬件結(jié)構(gòu)上增加了2個(gè)探測(cè)器，分別是命中并發(fā)度探測(cè)器和缺失并發(fā)度探測(cè)器，這2 個(gè)探測(cè)器都由檢測(cè)邏輯和寄存器組成，命中并發(fā)度探測(cè)器中的檢測(cè)邏輯用來監(jiān)控是否有緩存Tag 查詢活動(dòng).通過使用寄存器來統(tǒng)計(jì)總的命中周期和每個(gè)命中階段的同時(shí)命中情況，并計(jì)算平均命中并發(fā)度.因此，每個(gè)命中階段至少需要2 個(gè)寄存器，分別用來記錄開始周期和結(jié)束周期.缺失并發(fā)度探測(cè)器中的檢測(cè)邏輯監(jiān)控是否有新的請(qǐng)求到達(dá)MSHR（missing status holding register）[18]，并通過寄存器來探測(cè)純粹缺失周期的數(shù)量和每個(gè)純粹缺失階段的并發(fā)度.缺失并發(fā)度探測(cè)器所需的寄存器數(shù)量計(jì)算和命中并發(fā)度探測(cè)器數(shù)量的計(jì)算方法是類似的，不同之處在于選擇的寄存器的數(shù)量需要考慮同一周期內(nèi)共存的最大缺失訪問數(shù)，即MSHR 表項(xiàng)的數(shù)量乘以MSHR 表項(xiàng)中目標(biāo)的數(shù)量.

Fig.5 C-AMAT measuring device圖5 C-AMAT 測(cè)量裝置

基于上述分析，我們發(fā)現(xiàn)僅是測(cè)量C-AMAT 的Ch和Cm便會(huì)導(dǎo)致很大的硬件開銷，因此想要通過這種測(cè)量裝置直接測(cè)量出應(yīng)用程序的C-AMAT 是比較困難的.據(jù)此，我們?cè)跍y(cè)量圖應(yīng)用的C-AMAT 時(shí)并沒有直接使用文獻(xiàn)[18]中的這種測(cè)量裝置.同樣如圖5 所示，我們并沒有在程序運(yùn)行的過程中去監(jiān)測(cè)訪存的命中并發(fā)度與缺失并發(fā)度，對(duì)于每個(gè)命中與缺失階段，都只需要2 個(gè)寄存器分別用來記錄開始周期與結(jié)束周期，在一次訪存結(jié)束后，便可立即釋放當(dāng)前寄存器，而無需一直保留用來計(jì)算訪問并發(fā)度.最后通過設(shè)計(jì)相應(yīng)的純粹缺失周期提取算法，計(jì)算出PC-AMAT和SC-AMAT 計(jì)算所需要的相關(guān)參數(shù).這種方法大大降低了C-AMAT 測(cè)量所需的硬件開銷，同時(shí)避免了程序運(yùn)行階段探測(cè)并發(fā)度時(shí)繁雜的訪存檢測(cè)邏輯.

3.1 PC-AMAT 與SC-AMAT 實(shí)例

為了更好地解釋和理解純粹缺失周期等相關(guān)概念，我們基于PC-AMAT 舉了一個(gè)簡(jiǎn)單的例子，如圖6 所示，圖6 中共存在5 個(gè)不同的存儲(chǔ)訪問.由于PC-AMAT 是針對(duì)并行訪問結(jié)構(gòu)的cache 而言的，我們假設(shè)當(dāng)前cache 中Tag SRAM 部分的命中時(shí)間為2個(gè)周期，Data SRAM 部分的命中時(shí)間為3 個(gè)周期，因此，每次數(shù)據(jù)訪問都必須經(jīng)過3 個(gè)周期的命中階段.如果訪問沒有在當(dāng)前cache 中命中，即訪問缺失時(shí)，則會(huì)產(chǎn)生1 個(gè)缺失代價(jià)，缺失代價(jià)的大小取決于最終該缺失的數(shù)據(jù)在哪一級(jí)存儲(chǔ)層次中被找到.圖6 中，訪問請(qǐng)求1，2，5 是命中訪問，訪問3 和4 是缺失訪問.訪問3 包含了4 個(gè)周期的缺失代價(jià)，其中有2 個(gè)周期與訪問5 的命中周期出現(xiàn)了重疊，因此，從并發(fā)存儲(chǔ)的角度來看，訪問3 只存在2 個(gè)純粹缺失周期.訪問4 有1 個(gè)缺失周期，但該周期也與訪問5 的命中周期重疊，因此不是純粹缺失周期.因此，訪問3 是純粹缺失訪問，訪問4 不是，所以這5 個(gè)訪問的缺失率為0.4，而純粹缺失率僅為0.2，純粹平均訪問缺失代價(jià)pAMP=1.同時(shí)，對(duì)于式（5）和式（9）中提到的命中重疊時(shí)間overlap_hitTime，我們將其定義為在所有訪問請(qǐng)求中，只要當(dāng)前周期存在命中周期，那該周期則算作1 次重疊命中周期.類似地，純粹缺失重疊時(shí)間pMissTime_overlap為在所有請(qǐng)求訪問中，當(dāng)前周期都是純粹缺失周期時(shí)視作1 次純粹缺失重疊周期.

Fig.6 An example of PC-AMAT principle圖6 PC-AMAT 原理示例

因此，從圖6 中我們可以觀察到這5 個(gè)訪問總的命中重疊時(shí)間為7，總的純粹缺失重疊時(shí)間為1，根據(jù)式（5）和式（6）計(jì)算可得Cph=15/7 和Cm=2，最后由式（3）得到PC-AMAT 的每次訪問周期個(gè)數(shù)為1.8.事實(shí)上，圖6 中5 個(gè)訪問請(qǐng)求總共經(jīng)歷了8 個(gè)時(shí)鐘周期，并且這8 個(gè)周期都屬于訪問周期，因此我們也可以直接將總重疊訪問周期除以訪問次數(shù)得到PCAMAT 的每次訪問周期個(gè)數(shù)為9/5=1.8.

而對(duì)于SC-AMAT，其與PC-AMAT 最大的區(qū)別就在于當(dāng)前存儲(chǔ)器中的命中訪問與缺失訪問的命中時(shí)間是不一致的，為了更好地解釋SC-AMAT，我們同樣舉了一個(gè)簡(jiǎn)單的例子，如圖7 所示，圖7 中也存在5 個(gè)不同的存儲(chǔ)訪問.我們假設(shè)當(dāng)前cache 中Tag SRAM 和Data SRAM 的命中時(shí)間都為3 個(gè)周期，因此，每次數(shù)據(jù)訪問若是在當(dāng)前cache 中命中，則其命中時(shí)間為6 個(gè)周期.若是訪問缺失，則只會(huì)經(jīng)歷3 個(gè)周期的Tag 訪問命中時(shí)間，接下來該缺失訪問同樣會(huì)根據(jù)數(shù)據(jù)最終查找到位置，產(chǎn)生相應(yīng)的缺失代價(jià).圖7 中，由于訪問請(qǐng)求1，2，5 的命中時(shí)間都為6 個(gè)周期，因此都屬于命中訪問；而訪問3，4 則屬于缺失訪問，它們?cè)诋?dāng)前cache 上的命中時(shí)間都僅為3 個(gè)周期，訪問3 包含了8 個(gè)周期的缺失代價(jià)，其中有5 個(gè)周期與訪問5 的命中周期重疊，因此訪問3 存在3 個(gè)純粹缺失周期.與訪問3 類似，訪問4 的缺失代價(jià)為5 個(gè)周期，其中有2 個(gè)周期為純粹缺失周期.通過以上分析，我們可以計(jì)算出圖7 示例中5 個(gè)訪問的純粹缺失率為0.4，純粹平均訪問缺失代價(jià)pAMP=2.5，同時(shí)將命中重疊時(shí)間和純粹缺失重疊時(shí)間分別等于9 和3時(shí)代入式（9）和式（6），可以計(jì)算出Csh=8/3 和Cm=5/3，最后由式（7）計(jì)算得到SC-AMAT 每次訪問2.4 個(gè)周期.同樣，由于這5 個(gè)訪問所經(jīng)歷的總重疊時(shí)間為12個(gè)周期，我們也可以得到SC-AMAT 每次訪問2.4 個(gè)周期（12/5）.

Fig.7 An example of SC-AMAT principle圖7 SC-AMAT 原理示例

3.2 純粹缺失周期提取算法

在實(shí)際應(yīng)用程序中，并不是所有周期都屬于訪問周期，數(shù)據(jù)訪問過程中存在著停滯周期，因此3.1節(jié)中的計(jì)算示例的計(jì)算方法并不適用于實(shí)際應(yīng)用程序中C-AMAT 的測(cè)量.準(zhǔn)確測(cè)量PC-AMAT 和SCAMAT 的值的難點(diǎn)就在于如何準(zhǔn)確地判斷每個(gè)缺失周期是命中、失效重疊，還是純失效.據(jù)此，我們?cè)O(shè)計(jì)了純粹缺失周期PMC 提取方法，具體過程如圖8所示.

Fig.8 An example of missing cost scenario in missing access圖8 缺失訪問中的缺失代價(jià)情景示例

為了獲取每個(gè)缺失周期的屬性值，我們首先將缺失訪問進(jìn)行了合并.我們將所有缺失訪問的缺失代價(jià)按照它們的開始周期進(jìn)行遞增排序，然后通過一個(gè)結(jié)構(gòu)體missCycle記錄每一個(gè)缺失周期的絕對(duì)時(shí)間start、該缺失周期被缺失訪問占有的次數(shù)count以及該缺失周期所在的缺失訪問請(qǐng)求parent.我們通過分類和迭代便可獲取到每個(gè)缺失周期的屬性值，包括該缺失周期總共被占有的缺失訪問的次數(shù)以及存在于哪些缺失訪問中.算法描述如算法1 所示.

算法1.缺失周期合并算法.

對(duì)于圖8 中的缺失訪問1 和情景1 下的缺失訪問2，第n個(gè)缺失周期的絕對(duì)時(shí)間即為n，該缺失周期當(dāng)前被缺失訪問占有的次數(shù)為2，其所在的缺失訪問請(qǐng)求為缺失訪問1，2.在經(jīng)過上述處理時(shí)，缺失訪問2 相對(duì)于缺失訪問1 可能會(huì)出現(xiàn)圖8 所示的3 種情況.其中行④～?是當(dāng)缺失訪問2 出現(xiàn)如圖8 中的情景1 和情景2 時(shí)，需要將每個(gè)curr_cycle屬性進(jìn)行更新，根據(jù)缺失訪問2 的結(jié)束時(shí)間是否大于缺失訪問1來決定是否需要將其進(jìn)行缺失訪問合并操作，而行?～?則是當(dāng)缺失訪問2 的開始時(shí)間大于缺失訪問1 時(shí)，此時(shí)這2 次的缺失訪問無法進(jìn)行合并，則對(duì)缺失訪問2 的每個(gè)缺失周期進(jìn)行初始化后開始新一輪的合并迭代操作.通過對(duì)缺失訪問的合并操作，我們便可以清晰地獲取到每個(gè)缺失周期的信息，包括該缺失周期所處的缺失訪問位置及出現(xiàn)次數(shù).同樣，為了更快速地判斷每個(gè)缺失周期是否是純粹缺失周期，我們對(duì)命中階段的周期也進(jìn)行了合并操作，需要注意的是，此處命中階段的含義不僅代表命中訪問所經(jīng)歷的時(shí)間，而且缺失訪問的命中時(shí)間也應(yīng)該算作命中階段，具體算法描述如算法2 所示.

算法2.命中周期合并算法.

我們?cè)趯?duì)命中階段按開始周期以遞增方式進(jìn)行排序后，根據(jù)下一命中階段的開始周期是否大于當(dāng)前命中階段的結(jié)束周期來決定是否將當(dāng)前2 個(gè)命中階段進(jìn)行合并.通過這樣的預(yù)處理，我們可以最小化每個(gè)缺失周期與命中周期的比較次數(shù)，從而快速判斷該周期是否是純粹缺失周期.具體算法如算法3 所示.

算法3.純粹缺失周期的提取算法.

該P(yáng)MC 的判斷算法通過將經(jīng)過缺失訪問合并后的每個(gè)缺失訪問的每個(gè)缺失周期與每個(gè)命中周期進(jìn)行start屬性比較，若當(dāng)前缺失周期的start屬性與某個(gè)命中周期的start相同，則該缺失周期不是純粹缺失周期，反之則是.

4 實(shí)驗(yàn)評(píng)估

由于本文研究C-AMAT 的目的是為了度量圖應(yīng)用的存儲(chǔ)器性能，發(fā)掘圖應(yīng)用在存儲(chǔ)器中的性能優(yōu)化方向，因此，本節(jié)將通過PC-AMAT 和SC-AMAT 對(duì)大規(guī)模圖數(shù)據(jù)集進(jìn)行存儲(chǔ)器性能測(cè)試和評(píng)估，并分析其內(nèi)存性能表現(xiàn).

4.1 實(shí)驗(yàn)環(huán)境

我們?cè)趃em5 模擬器中采用了亂序超標(biāo)量CPU模型，該模型支持單核模式下的分支預(yù)測(cè)和多線程執(zhí)行.為了更準(zhǔn)確地測(cè)量緩存/內(nèi)存架構(gòu)設(shè)計(jì)下圖應(yīng)用的PC-AMAT 和SC-AMAT，我們參考了WikiChip[17]和丹麥技術(shù)大學(xué)[19]最新整理的?ceLake CPU 架構(gòu)及其參數(shù)，在gem5 中增加了3 級(jí)共享緩存的架構(gòu)，并重新進(jìn)行了緩存參數(shù)配置，以使緩存架構(gòu)及其對(duì)應(yīng)的Tag 延時(shí)與Data 延時(shí)更加接近真實(shí)的硬件環(huán)境.對(duì)于每個(gè)圖應(yīng)用的測(cè)量點(diǎn)，我們都根據(jù)4×108個(gè)模擬指令收集了圖應(yīng)用的訪問數(shù)據(jù)，PC-AMAT 和SCAMAT 的計(jì)算及其參數(shù)都來源于對(duì)這些訪問數(shù)據(jù)的處理.具體配置情況如表1 所示.

Table 1 Simulator Configuration表1 模擬器配置

4.2 工作負(fù)載

本文使用GAP 基準(zhǔn)套件[13]，它是典型的圖處理基準(zhǔn)套件，能夠有效標(biāo)準(zhǔn)化圖應(yīng)用的指標(biāo)評(píng)估.GAP之中的圖算法均使用C++編寫，并使用了優(yōu)化多線程技術(shù)，我們之所以選擇GAP 是因?yàn)樗梢耘懦魏闻c框架相關(guān)的性能開銷，從而真正發(fā)現(xiàn)圖應(yīng)用在存儲(chǔ)器中的性能瓶頸.我們選取了其中最具代表性的BFS[20]，PR[21]，BC[22]，CC[23]4 種算法作為工作負(fù)載進(jìn)行測(cè)試，具體算法介紹如表2 所示.

Table 2 Graph Algorithm List表2 圖算法列表

表2 中的圖算法分別代表了社交網(wǎng)絡(luò)中心、工程應(yīng)用領(lǐng)域和科學(xué)中的諸多應(yīng)用，由于不同的圖算法計(jì)算方式是不同的，主要以遍歷為中心和以計(jì)算為中心，并且它們對(duì)于圖的屬性考慮也各有側(cè)重，因此為了更全面地評(píng)估各類圖應(yīng)用的存儲(chǔ)器性能，我們采用的圖數(shù)據(jù)集如表3 所示.

Table 3 Experimental Datasets表3 實(shí)驗(yàn)數(shù)據(jù)集

4.3 負(fù)載性能測(cè)試

由于存儲(chǔ)器系統(tǒng)的性能對(duì)整體性能有很大的影響，因此應(yīng)該選擇一個(gè)適當(dāng)?shù)闹笜?biāo)來反映它們之間的關(guān)系.我們使用相關(guān)系數(shù)（correlation coefficient）[15]來描述內(nèi)存指標(biāo)PC-AMAT，SC-AMAT，C-AMAT 與?PC 之間的變化相似度，并作為它們的評(píng)價(jià)精度.相關(guān)系數(shù)的取值范圍為-1～1.相關(guān)系數(shù)的絕對(duì)值越高，代表內(nèi)存指標(biāo)和?PC 這2 個(gè)變量之間的關(guān)系就越密切[25].相關(guān)系數(shù)的數(shù)學(xué)定義為：

相關(guān)系數(shù)是通過積差方法進(jìn)行計(jì)算的，通過以2 個(gè)變量與各自平均值的離差為基礎(chǔ)，將2 個(gè)變量的離差相乘來反映2 個(gè)變量之間的相關(guān)程度.其中數(shù)組X和Y是2 個(gè)變量的采樣點(diǎn).

我們首先分別計(jì)算了當(dāng)內(nèi)核數(shù)量為1，2，4 時(shí)對(duì)應(yīng)各級(jí)cache 的相關(guān)系數(shù).對(duì)于各級(jí)cache，這2 種存儲(chǔ)器性能指標(biāo)的相關(guān)系數(shù)，如圖9 所示.圖9（a）顯示了L1 cache 上C-AMAT 與PC-AMAT 的相關(guān)系數(shù)的對(duì)比，我們發(fā)現(xiàn)隨著內(nèi)核數(shù)量的增加，C-AMAT 的相關(guān)系數(shù)并未出現(xiàn)明顯變化，PC-AMAT 在相關(guān)系數(shù)上則始終高于C-AMAT，并且內(nèi)核數(shù)量并未明顯影響其相關(guān)系數(shù)變化，之所以出現(xiàn)這樣的原因，是因?yàn)長1 cache 中的數(shù)據(jù)訪問命中時(shí)間是固定的，內(nèi)核數(shù)量的增加對(duì)于總的數(shù)據(jù)訪問周期的測(cè)量誤差并沒有表現(xiàn)出比較明顯的影響，但由于PC-AMAT 在數(shù)據(jù)訪問時(shí)的命中時(shí)間參數(shù)選取更加準(zhǔn)確，因此其相關(guān)系數(shù)相比C-AMAT 也更高.圖9（b）（c）分別代表了L2 cache和LLC 上C-AMAT 和SC-AMAT 的相關(guān)系數(shù)對(duì)比，隨著內(nèi)核數(shù)量的增加，C-AMAT 的相關(guān)系數(shù)都有小幅度提升，我們分析這是由于內(nèi)核數(shù)量的增加，導(dǎo)致數(shù)據(jù)訪問并發(fā)度也隨之增加，盡管L2 cache 和LLC 上的數(shù)據(jù)訪問命中時(shí)間存在不一致性，但并發(fā)度的提升導(dǎo)致數(shù)據(jù)訪問重疊周期也更多，掩蓋了一部分?jǐn)?shù)據(jù)訪問周期計(jì)算過程中的誤差，但其相關(guān)系數(shù)始終與SC-AMAT 有一段距離.

Fig.9 The correlations coefficients of performance indicators in each cache level with different number of cores圖9 各級(jí)cache 在不同內(nèi)核數(shù)量中性能指標(biāo)的相關(guān)系數(shù)

以內(nèi)核數(shù)量為4 時(shí)各個(gè)圖應(yīng)用中?PC 與C-AMAT，PC-AMAT 和SC-AMAT 的相關(guān)系數(shù)為例，進(jìn)一步驗(yàn)證了將C-AMAT 的計(jì)算模型擴(kuò)展為PC-AMAT 和SCAMAT 的有效性與合理性，實(shí)驗(yàn)結(jié)果如圖10 所示.從圖10（a）可以看出，在幾乎所有的圖應(yīng)用中，L1 cache中PC-AMAT 的相關(guān)系數(shù)都高于C-AMAT，相比CAMAT，PC-AMAT 的相關(guān)系數(shù)提升了11.7%.從圖10（b）（c）中我們觀察到，在L2 cache 與LLC 中，SC-AMAT在L2 cache 和LLC 上的相關(guān)系數(shù)分別提升了26.1%和15.8%.

由于PC-AMAT 和SC-AMAT 只是在計(jì)算與測(cè)量過程中對(duì)C-AMAT 進(jìn)行的擴(kuò)展，因此在接下來的結(jié)果評(píng)估中將不再對(duì)PC-AMAT 和SC-AMAT 進(jìn)行區(qū)分.我們首先將圖應(yīng)用運(yùn)行在單核模式下，我們計(jì)算了各級(jí)cache 的C-AMAT 和相關(guān)的內(nèi)存性能參數(shù)，整體性能表現(xiàn)如圖11 所示.

由圖11 可以看出，PR 算法的整體內(nèi)存性能表現(xiàn)是優(yōu)于其他算法的，同時(shí)對(duì)于L1 data cache 來說，各類圖應(yīng)用程序性能表現(xiàn)類似，但值得注意的是，在絕大部分算法中，L2 cache 的C-AMAT 都明顯高于LLC，這個(gè)現(xiàn)象直接暴露出了L2 cache 的存在對(duì)于圖數(shù)據(jù)訪問而言是負(fù)收益的，而導(dǎo)致這種現(xiàn)象的本質(zhì)還是圖計(jì)算運(yùn)行過程中不規(guī)則的細(xì)粒度訪存導(dǎo)致CPU的L2 cache 和LLC 的命中率極低[26].

這些圖應(yīng)用負(fù)載的命中并發(fā)度和缺失并發(fā)度如圖12 和圖13 所示.命中并發(fā)度與缺失并發(fā)度是影響C-AMAT 的關(guān)鍵因素，可以看出，單核模式下，所有圖應(yīng)用在L2 cache 的命中并發(fā)度表現(xiàn)都是最低的且其值都徘徊在1 附近，這進(jìn)一步表明了傳統(tǒng)L2 cache 的存在對(duì)于圖應(yīng)用并沒有多大意義，甚至影響到了整體的圖應(yīng)用訪存時(shí)間，現(xiàn)代處理器中的3 級(jí)緩存存儲(chǔ)器層次結(jié)構(gòu)的設(shè)計(jì)對(duì)于圖應(yīng)用而言負(fù)面影響較大.為了提高圖應(yīng)用的命中并發(fā)度，我們可以采用多端口緩存、多bank 緩存來提高命中時(shí)間的重疊；同時(shí)，為了提高缺失并發(fā)度，我們也可以通過設(shè)置合理的MSHR 數(shù)量來允許更多的缺失訪問相互重疊.

Fig.13 Miss concurrency in each level of cache圖13 各級(jí)cache 中的缺失并發(fā)度

這些圖應(yīng)用的純粹平均缺失代價(jià)如圖14 所示.與命中并發(fā)度和缺失并發(fā)度類似，各類圖應(yīng)用在在L2 cache 上所表現(xiàn)出來的純粹平均缺失代價(jià)都是最高的，這也從側(cè)面反映了L2 cache 中圖數(shù)據(jù)訪問缺失率高，而為了避免這種現(xiàn)象，最簡(jiǎn)單的方式就是在L2 cache 上進(jìn)行旁路策略，可以有效降低總體的圖數(shù)據(jù)訪問時(shí)間.

Fig.14 Pure average miss penalty in each level of cache圖14 各級(jí)cache 中的純粹平均缺失代價(jià)

多發(fā)射流水線技術(shù)是處理器微體系結(jié)構(gòu)設(shè)計(jì)的一個(gè)重要改進(jìn)，它允許在同一周期內(nèi)取指、解碼、發(fā)射、執(zhí)行和提交多個(gè)指令，大幅度提高了指令集并行度.由于算法數(shù)據(jù)依賴、分支錯(cuò)誤預(yù)測(cè)的高額代價(jià)、負(fù)載數(shù)據(jù)約束，以及一般的功率墻限制，增加發(fā)射帶寬不是一個(gè)可行的選擇，所以大多數(shù)商業(yè)處理器在不同的處理階段對(duì)每個(gè)內(nèi)核采用4～8 大小的帶寬[27].為了探究發(fā)射帶寬對(duì)圖應(yīng)用的影響，我們通過設(shè)置不同大小的發(fā)射帶寬，觀察了其對(duì)圖數(shù)據(jù)在各級(jí)cache中訪存時(shí)間的影響.由于L1 data cache 的數(shù)據(jù)訪問時(shí)間最能表現(xiàn)圖應(yīng)用的存儲(chǔ)器性能，因此這里我們只統(tǒng)計(jì)了不同發(fā)射帶寬下L1 data cache 的C-AMAT，其結(jié)果如圖15 所示.可以看到，當(dāng)發(fā)射帶寬設(shè)置為4 時(shí)，圖應(yīng)用的C-AMAT 相較于其他數(shù)值的發(fā)射帶寬都呈現(xiàn)出下降的趨勢(shì)，訪存速度最快.

Fig.15 C-AMAT of L1 data cache at different issue widths圖15 不同發(fā)射帶寬下L1 data cache 的C-AMAT

現(xiàn)代處理器中的非阻塞緩存為了在緩存缺失時(shí)依然能夠提供數(shù)據(jù)，往往采用了失效狀態(tài)保存寄存器MSHR.對(duì)于LLC，當(dāng)其MSHR 表為空時(shí)，表示沒有未完成的主存訪問，而當(dāng)MSHR 表為滿時(shí)，則表示緩存無法提供更多的緩存訪問，將阻塞CPU 對(duì)內(nèi)存或下一級(jí)內(nèi)存的訪問.因此，MSHR 表項(xiàng)的數(shù)量可以直接決定缺失并發(fā)度，進(jìn)而影響到C-AMAT.我們將LLC 的MSHR 表項(xiàng)的數(shù)量分別設(shè)置為4，8，16，并對(duì)圖應(yīng)用的C-AMAT 進(jìn)行了測(cè)量，結(jié)果如圖16 所示.不難發(fā)現(xiàn)，當(dāng)MSHR 表項(xiàng)的數(shù)量設(shè)置為8 時(shí)，就已經(jīng)對(duì)圖應(yīng)用的數(shù)據(jù)訪問不再產(chǎn)生影響，因此盡管圖數(shù)據(jù)在LLC 上的缺失率很高，但圖應(yīng)用在LLC 數(shù)據(jù)訪問總占比是極低的，尤其是單核模式下，MSHR 表項(xiàng)的數(shù)量的設(shè)置越大對(duì)于圖應(yīng)用而言意義不大，對(duì)于圖應(yīng)用而言LLC 的MSHR 表項(xiàng)的數(shù)量設(shè)置在4～8 已足夠使用，不必再浪費(fèi)額外的硬件資源.

Fig.16 C-AMAT of LLC at different sizes of MSHR圖16 不同MSHR 大小下LLC 的C-AMAT

指令集并行技術(shù)帶來的圖應(yīng)用訪存性能的提升仍存在很大的限制，增加每個(gè)CPU 內(nèi)核數(shù)量是提高系統(tǒng)總體性能的最直接和最高效的手段.我們將內(nèi)核數(shù)量進(jìn)行了倍增，將圖應(yīng)用在L1 data cache 的CAMAT 進(jìn)行了統(tǒng)計(jì)分析，實(shí)驗(yàn)結(jié)果如圖17 所示.內(nèi)核數(shù)量的增加明顯降低了圖應(yīng)用的C-AMAT，但并不總是如此，尤其對(duì)于PR 算法而言，在其中3 個(gè)數(shù)據(jù)集中雙核CPU 下的L1 data cache 的C-AMAT 相對(duì)于單核反而出現(xiàn)上升，我們推測(cè)產(chǎn)生這種現(xiàn)象是由于圖應(yīng)用中加載指令之間的依賴鏈過短，從而導(dǎo)致了流水線的斷流和低內(nèi)存級(jí)并行.但總的來說，多核CPU 在處理圖應(yīng)用過程中所表現(xiàn)的存儲(chǔ)器性能依然是要高于單核CPU 的.

Fig.17 C-AMAT of L1 data dcache at different number of cores圖17 不同內(nèi)核數(shù)量下L1 data cache 的C-AMAT

5 總結(jié)

圖計(jì)算應(yīng)用擁有特有的不規(guī)則執(zhí)行行為，其引發(fā)的不規(guī)則負(fù)載和不規(guī)則訪問是加速圖應(yīng)用面臨的主要挑戰(zhàn)之一.認(rèn)識(shí)圖應(yīng)用高度復(fù)雜的存儲(chǔ)系統(tǒng)的局部性信息和并發(fā)性信息對(duì)于加速圖計(jì)算架構(gòu)設(shè)計(jì)至關(guān)重要.C-AMAT 可以有效表征應(yīng)用程序運(yùn)行過程中高度復(fù)雜的存儲(chǔ)系統(tǒng)的局部性和并發(fā)性的信息，但是其計(jì)算模型沒有考慮cache 層的訪問方式，原始測(cè)量裝置硬件開銷巨大.因此本文基于不同cache 層的訪問結(jié)構(gòu)，對(duì)C-AMAT 的計(jì)算模型擴(kuò)展為PCAMAT 和SC-AMAT，并在此基礎(chǔ)上設(shè)計(jì)并實(shí)現(xiàn)了純粹缺失周期提取算法及各參數(shù)的測(cè)量與計(jì)算，能夠有效實(shí)現(xiàn)C-AMAT 的測(cè)量.實(shí)驗(yàn)結(jié)果表明，在單核和多核模式下，PC-AMAT 和SC-AMAT 與?PC 之間的相關(guān)性比C-AMAT 與?PC 的相關(guān)性更強(qiáng)，在4 核模式下，L1 cache 中PC-AMAT 相比C-AMAT 的相關(guān)系數(shù)提升了11.7%，SC-AMAT 在L2 cache 和LLC 上的相關(guān)系數(shù)分別提升了26.1%和15.8%.最終，我們通過更改相關(guān)的硬件配置利用C-AMAT 評(píng)估和分析了圖應(yīng)用在存儲(chǔ)器中的訪存性能，并提出了相應(yīng)的訪存優(yōu)化策略.我們的下一步工作將根據(jù)如何提高圖應(yīng)用的命中并發(fā)度和缺失并發(fā)度，以及如何降低圖應(yīng)用的純粹缺失率展開，擬從cache 層面優(yōu)化圖應(yīng)用的存儲(chǔ)器性能.

作者貢獻(xiàn)聲明：陳炳彰提出算法思路和實(shí)驗(yàn)方案，并完成實(shí)驗(yàn)與論文撰寫；劉偉指導(dǎo)方案設(shè)計(jì)并修改論文；于蕭鈺協(xié)助論文修改.