軟件定義高速緩存及其一致性研究

摘要：高速緩存（cache）作為內(nèi)存與CPU中間的存儲器，能夠有效解決內(nèi)存讀寫速度慢導(dǎo)致的計(jì)算機(jī)性能瓶頸問題。現(xiàn)代計(jì)算機(jī)高速緩存通常由多級緩存組成。傳統(tǒng)的高速緩存結(jié)構(gòu)由硬件實(shí)現(xiàn)，在設(shè)計(jì)時(shí)就已經(jīng)固定。然而現(xiàn)代的計(jì)算機(jī)系統(tǒng)中，不同級緩存之間的容量和速度之間的差異變小，緩存層級變多，固定的緩存結(jié)構(gòu)可能導(dǎo)致額外開銷，甚至降低性能。通過將特定的緩存層次結(jié)構(gòu)提供給特定的應(yīng)用程序，可以有效地解決這一問題。這就是軟件定義的緩存層次結(jié)構(gòu)。基于非均一緩存訪問模型，針對不同的應(yīng)用程序提供不同的緩存層次結(jié)構(gòu)，并在此基礎(chǔ)上實(shí)現(xiàn)基于目錄的緩存一致性協(xié)議，在保證緩存對應(yīng)用程序的透明性和多核緩存一致性的前提下，有效提高緩存命中率，最終提高應(yīng)用程序的運(yùn)行效率。

關(guān)鍵詞：高速緩存；分區(qū)訪存；軟件定義緩存；緩存一致性

中圖分類號：TP393" " "文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2025）19-0055-03

開放科學(xué)（資源服務(wù)） 標(biāo)識碼（OSID）

1 傳統(tǒng)緩存結(jié)構(gòu)的局限性

隨著芯片技術(shù)的發(fā)展，CPU的頻率迅速提升，然而相應(yīng)的內(nèi)存總線的速度卻沒有得到成比例的提升，因此內(nèi)存的讀寫速度往往會成為計(jì)算機(jī)性能的瓶頸，造成了著名的“內(nèi)存墻”問題[1]。為解決此問題，引入了高速緩存（cache），根據(jù)高速緩存的容量和讀寫速度不同，可以劃分為多級緩存。

現(xiàn)代計(jì)算機(jī)系統(tǒng)通常采用三級緩存（L1、L2、L3），每一級緩存的速度遞減，容量遞增，如果將內(nèi)存也視為一級緩存，則構(gòu)成四級緩存結(jié)構(gòu)。緩存塊失效時(shí)，通常采用LRU（Least Recently Used）算法從下一級緩存中替換。傳統(tǒng)的cache一般有嚴(yán)格的層次結(jié)構(gòu)，塊替換算法由硬件實(shí)現(xiàn)，在設(shè)計(jì)時(shí)就已經(jīng)固定。在過去的很長一段時(shí)間里，由于其對系統(tǒng)和應(yīng)用程序員的透明性，以及以前的系統(tǒng)通常只有很少的緩存級別，且不同級別之間的速度和容量差距明顯，這種硬性的緩存層次結(jié)構(gòu)都有不錯(cuò)的效果。

硬件定義的層次結(jié)構(gòu)能夠廣泛地應(yīng)用于各種應(yīng)用程序，并且有著相對穩(wěn)定的效果。但是，在某些情況下，硬件定義的層次結(jié)構(gòu)導(dǎo)致的級別之間的延遲也會增加開銷，尤其是當(dāng)某個(gè)級別的緩存大小恰好不能滿足應(yīng)用程序的工作集，且應(yīng)用程序數(shù)據(jù)訪問的空間局部性不強(qiáng)時(shí)，那么這個(gè)級別的緩存反而會成為負(fù)擔(dān)。

1.1 硬性結(jié)構(gòu)導(dǎo)致緩存失效的極端情況

本節(jié)將通過一個(gè)矩陣轉(zhuǎn)置的例子說明硬性緩存結(jié)構(gòu)的局限性。使用一個(gè)簡單的矩陣轉(zhuǎn)置c語言程序，編譯時(shí)禁用編譯優(yōu)化。為排除其他變量對cache的干擾，在轉(zhuǎn)置過程中使用的矩陣下標(biāo)變量均使用寄存器變量，因此可以認(rèn)為在轉(zhuǎn)置的過程中只有保存矩陣的數(shù)據(jù)段參與了cache與主存的調(diào)度。其中L1 Cache配置如表1所示。

運(yùn)行程序?qū)仃囘M(jìn)行轉(zhuǎn)置，并記錄其在不同矩陣大小時(shí)的L1 cache命中率，結(jié)果如表2所示。

在內(nèi)存中，矩陣同一行相鄰的兩個(gè)元素在內(nèi)存中的地址是相鄰的，但是同一列相鄰的兩個(gè)元素在內(nèi)存中的地址相差了矩陣一行的距離。以512×512矩陣為例，同一列相鄰的兩個(gè)元素的地址差正好是512個(gè)int的大小，共2 048個(gè)字節(jié)。對應(yīng)到cache的組相聯(lián)映射中，由于每一個(gè)分組的大小為512字節(jié)，矩陣某一列的所有元素都被映射到cache的同一個(gè)分組中。而組中每塊的大小為64字節(jié)，因此在遍歷矩陣某一列時(shí)會不斷地在組內(nèi)進(jìn)行替換卻不會產(chǎn)生命中，L1級緩存會成為累贅。同理，當(dāng)矩陣大小為513時(shí)，需要交換的兩個(gè)矩陣元素aij和aji內(nèi)存地址相差（i-j）×512×4，同樣存在此問題。因此當(dāng)程序頻繁訪問地址差為cache塊大小的整數(shù)倍的內(nèi)存時(shí)，會存在cache失效的問題，這就是硬件定義的層次結(jié)構(gòu)在某些特定場合帶來的性能不佳甚至完全失效的問題。

1.2 應(yīng)用程序最佳緩存結(jié)構(gòu)研究

上述的實(shí)驗(yàn)僅僅是例舉了一種極端情況，但事實(shí)上，不同的應(yīng)用程序都有其各自最合適的緩存結(jié)構(gòu)。在Sotware-Defined Cache Hierarchies[2]中，運(yùn)行SPECCPU2006應(yīng)用程序的簡單單核系統(tǒng)。處理器固定為32KB L1和128KB L2。為了找到每個(gè)應(yīng)用程序的最佳層次結(jié)構(gòu)，考慮不同大小的SRAM和堆疊DRAM緩存：SRAM為512KB至32MB，堆疊DRAM為128MB至2GB，測試各個(gè)應(yīng)用程序在所有單層或雙層的緩存結(jié)構(gòu)上運(yùn)行（SRAM或DRAM分別作為L3或L4） 。

研究表明，不同應(yīng)用的最佳緩存層次結(jié)構(gòu)不同，不合適的緩存層次結(jié)構(gòu)會導(dǎo)致低命中率和頻繁的無效cache訪問。過去曾有一些技術(shù)來減少不合適的層次結(jié)構(gòu)帶來的延遲，例如在訪問時(shí)并行地預(yù)測接下來的命中情況，雖然通過提前的預(yù)測減少延遲，能夠有效地提高運(yùn)行速度，但本質(zhì)上并沒有消除這些不必要的訪問，只是相當(dāng)于在用能耗和帶寬換取時(shí)間。因此，對特定的應(yīng)用程序定義特定的緩存層級和每層的緩存容量，將成為提高cache加速效果的研究方向。

2 非均一緩存訪問模型

非均一緩存訪問（Non-Uniform Cache Access，簡稱NUCA） 模型[3]，類似于非均勻存儲訪問模型（Non-uniform memery access，簡稱NUMA） ，其特點(diǎn)是：被共享訪問的緩存物理布局上是分布式的，所有這些緩存（內(nèi)存） 的集合就是全部的地址空間。具體表現(xiàn)為，硬件設(shè)計(jì)師在設(shè)計(jì)芯片系統(tǒng)時(shí)，將最外層的緩存分成多塊，使其分布在不同的核心附近，這些緩存雖然是所有核心共享的，但不同核心訪問不同緩存的延遲是不一樣的，訪問其他核心緩存的延遲也是不一樣的，每個(gè)核心訪問本地緩存塊及其附近的緩存塊的速度比訪問全局共享存儲或其他處理器的緩存快很多。

NUCA 技術(shù)減少了大型高速緩存的延遲和能耗。靜態(tài)NUCA（S-NUCA） 利用固定的線組映射在所有存儲體上傳播數(shù)據(jù)，其特點(diǎn)是數(shù)據(jù)到緩存組的映射是基于塊的地址索引的，某個(gè)地址的數(shù)據(jù)只會保存到某個(gè)固定的緩存組中。動(dòng)態(tài)NUCA（D-NUCA） 方案通過使用混合放置自適應(yīng)地將數(shù)據(jù)放置在請求核心附近來改進(jìn)S-NUCA ，由于數(shù)據(jù)到緩存組的映射是可變的，因此可以將頻繁訪問的數(shù)據(jù)遷移到訪問延遲較小的緩存組中，提高了訪問速度，但也增加了數(shù)據(jù)的映射與搜索復(fù)雜度，同時(shí)還需解決數(shù)據(jù)在不同緩存組中的搬運(yùn)問題。

圖1顯示了2個(gè)核心分別運(yùn)行一個(gè)應(yīng)用程序的軟件定義緩存系統(tǒng)。每個(gè)芯片都有一個(gè)核心，一個(gè)私有緩存層次結(jié)構(gòu)（L1和L2） 和一個(gè)SRAM緩存庫。存在多個(gè)DRAM高速緩存存儲體，例如由插入器連接的堆疊DRAM存儲體。根據(jù)訪問內(nèi)存的方式，軟結(jié)構(gòu)高速緩存可根據(jù)共享緩存庫（即SRAM和DRAM庫，不包括私有緩存） 為每個(gè)應(yīng)用程序構(gòu)建自定義虛擬緩存層次結(jié)構(gòu)。字母顯示每個(gè)應(yīng)用程序的運(yùn)行位置，顏色顯示其數(shù)據(jù)的放置位置，陰影表示第二個(gè)虛擬層次結(jié)構(gòu)級別（如果存在） 。其中，A核心使用了臨近的10個(gè)SRAM塊作為自己的L1，將DRAM作為L2；B核心使用最近的1個(gè)SRAM塊作為L1，臨近的3個(gè)SRAM作為L2。

現(xiàn)有的多核處理器在處理器內(nèi)部一般會設(shè)有高速緩存，片內(nèi)的高速緩存層次結(jié)構(gòu)能有效地緩解片外存儲器訪問的延遲和能耗。緩存通常占用芯片面積的50％以上，并且為了最大限度地利用，大部分空間被構(gòu)造為所有內(nèi)核之間共享的最后一級緩存。然而，由于摩爾定律使處理器具有數(shù)十到數(shù)百個(gè)內(nèi)核，共享緩存面臨兩個(gè)基本限制。首先，隨著系統(tǒng)擴(kuò)展，共享緩存的能延遲和能量會降低。在具有分布式緩存的大型芯片中，與指定塊的直接訪問相比，遍歷花費(fèi)的延遲和能量更多。其次，當(dāng)某個(gè)單芯片多處理器有多個(gè)工作負(fù)載共享時(shí)，它們會受到共享緩存訪問的干擾。這會導(dǎo)致較大的性能變化，從而妨礙服務(wù)質(zhì)量（Quality-of-Service， QoS） 保證并降低吞吐量[4]。

3 多核緩存一致性問題

緩存一致性問題是指多個(gè)核心并發(fā)訪問共享內(nèi)存時(shí)，由于緩存的存在可能導(dǎo)致數(shù)據(jù)不一致。若要對緩存結(jié)構(gòu)進(jìn)行優(yōu)化，首先必須保證緩存一致性。

3.1 緩存一致性協(xié)議

緩存一致性協(xié)議指當(dāng)多個(gè)核心同時(shí)操作同一段地址時(shí)所需要遵守的規(guī)則，從而避免緩存一致性問題。根據(jù)不同的原理，緩存一致性協(xié)議有多種實(shí)現(xiàn)方式，其中應(yīng)用最廣泛的是基于目錄的MSI協(xié)議。

在MSI協(xié)議中，二級緩存保存了的每個(gè)緩存塊在一級緩存中的狀態(tài)，每個(gè)緩存塊都處于以下三種狀態(tài)之一。MSI協(xié)議緩存塊狀態(tài)，如表3所示。

表3" MSI協(xié)議緩存塊狀態(tài)

[狀態(tài) 名稱 定義 具體描述 M Modified 有效，修改過且未寫回 本核心完全控制（可讀寫） 該緩存塊，其他核心不可讀寫 S Shared 有效且只讀 本核心和其他多個(gè)核心共享該緩存塊，均為可讀但不可寫 I Invalid 無效 本核心無法訪問該緩存塊（一級緩存中無此緩存塊） ]

當(dāng)某個(gè)核心（一級緩存） 需要以可讀寫的方式獲取某緩存塊時(shí)，二級緩存根據(jù)該緩存塊的狀態(tài)執(zhí)行不同的動(dòng)作。如果該緩存塊處于S狀態(tài)，二級緩存根據(jù)目錄信息，發(fā)送處于S狀態(tài)的一級緩存預(yù)期計(jì)數(shù)，并響應(yīng)其讀寫請求；如果該緩存塊處于M狀態(tài)，則二級緩存首先向處于M狀態(tài)的一級緩存發(fā)送寫回請求，當(dāng)請求完成后，響應(yīng)本次讀寫請求；如果該緩存塊處于I狀態(tài)，則二級緩存直接響應(yīng)其讀寫請求。最后，所有處于S狀態(tài)的其他一級緩存無效化該緩存塊，并向發(fā)出請求的一級緩存發(fā)出一個(gè)計(jì)數(shù)，當(dāng)計(jì)數(shù)達(dá)到二級緩存發(fā)送的預(yù)期值時(shí)，將該緩存塊轉(zhuǎn)化為M狀態(tài)并完成讀寫請求。

當(dāng)某個(gè)核心（一級緩存） 需要以只讀的方式獲取某緩存塊時(shí)，如果該緩存塊處于S或I狀態(tài)，則二級緩存直接響應(yīng)其只讀請求；如果該緩存塊處于M狀態(tài)，則二級緩存首先向處于M狀態(tài)的一級緩存發(fā)送寫回請求，并將該一級緩存由M狀態(tài)轉(zhuǎn)換為S狀態(tài)，當(dāng)請求完成后，響應(yīng)本次讀請求。

當(dāng)某個(gè)核心（一級緩存） 因緩存替換需要釋放某緩存塊時(shí)，將該緩存塊置為I狀態(tài)。MSI協(xié)議狀態(tài)轉(zhuǎn)換圖，如圖2所示。

目前應(yīng)用較為廣泛的緩存一致性協(xié)議一般基于MSI協(xié)議擴(kuò)展更多的狀態(tài)，雖然增加了目錄的大小，但同時(shí)提高了一級緩存的命中率，且降低了一級緩存寫回的次數(shù)，均能有效提高緩存效率。

3.2 非均一緩存訪問對緩存一致性的影響

非均一緩存訪問（NUCA） 結(jié)構(gòu)中，最外層緩存（本文中以二級緩存為例） 的緩存塊分布在不同的區(qū)中。由于該結(jié)構(gòu)下的二級緩存既是分布式結(jié)構(gòu)，又理論上可以被所有一級緩存共享（但訪問延時(shí)有較大差別） ，因此對緩存一致性協(xié)議的影響在于維護(hù)緩存一致性的目錄的存儲方式。

對于靜態(tài)NUCA（S-NUCA） ，某一級緩存的緩存塊在二級緩存中的實(shí)際地址是固定的，因而可以將目錄信息在二級緩存中與其緩存塊存放在一起，以避免二級緩存中跨區(qū)域獲取目錄所帶來的額外消耗。

然而對于動(dòng)態(tài)NUCA（D-NUCA） ，某一級緩存的緩存塊在二級緩存中的實(shí)際地址是可變的，D-NUCA有基于硬件或軟件的多種實(shí)現(xiàn)方式，但始終無法繞過緩存一致性問題。通常一級緩存需要訪問二級緩存時(shí)，需要通過查表獲取其二級緩存的實(shí)際地址。這個(gè)表必須是分布式的，因?yàn)槿绻楸聿僮餍枰ㄟ^二級緩存的片上通信來完成（通常需要較長時(shí)間） ，那么D-NUCA的優(yōu)化將沒有意義。同理，其目錄信息也必須是分布式的，因此與S-NUCA相同，目錄信息需要在二級緩存中與其緩存塊存放在一起，例如，基于TLB（Translation Lookaside Buffer，轉(zhuǎn)譯后備緩沖器） 實(shí)現(xiàn)的D-NUCA中，將維護(hù)每個(gè)二級緩存的D-NUCA的虛擬-物理地址映射表與該緩存塊MSI協(xié)議的目錄信息分布在各個(gè)二級緩存所屬的TLB。維護(hù)MSI協(xié)議目錄與維護(hù)緩存地址映射表具有相同的消耗，因此保證緩存一致性的同時(shí)不會影響NUCA結(jié)構(gòu)對緩存的優(yōu)化。

參考文獻(xiàn)：

[1] WULF W A，MCKEE S A.Hitting the memory wall[J].ACM SIGARCH Computer Architecture News，1995，23（1）：20-24.

[2] TSAI P A，BECKMANN N，SANCHEZ D.Jenga[J].ACM SIGARCH Computer Architecture News，2017，45（2）：652-665.

[3] KURD N A，BHAMIDIPATI S，MOZAK C，et al.Westmere：a family of 32nm IA processors[C]//2010 IEEE International Solid-State Circuits Conference - （ISSCC）.February 7-11，2010.San Francisco，CA，USA.IEEE，2010：96-97.

[4] NAVADA S，CHOUDHARY N K，WADHAVKAR S V，et al.Jigsaw：scalable software-defined caches[C]//Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques.September 7-11，2013.Edinburgh.IEEE，2013：213-224.

【通聯(lián)編輯：朱寶貴】