內存與片上滲透緩存之間數據遷移的理論分析

胡九川，范東睿，程建聰，嚴龍，葉笑春，李靈枝，萬良易，鐘海斌

（1.北京交通大學計算機科學與技術學院，北京 100044；2.中國科學院計算技術研究所，北京 100080）

1 引言

計算機存儲程序原理決定了即將被執行的指令或被處理的數據必須分批次地調入處理器，在容量十分有限的處理器片上緩存內中轉停留，而暫時不能調入的大量指令和數據停留在內存乃至硬盤中，等候調遣進入處理器參與運算實現程序運行；同樣，被執行過的指令或處理過的數據也很可能在處理器片上緩存內中轉停留，然后回到內存或硬盤。所以，將那些在時間和空間上具有緊密關聯關系的指令與數據以群組為單位預先放置于緊鄰處理器核的片上緩存的頂端，形成及時局部性環境[1-5]。這樣的環境有利于縮短處理器內核的訪存時延，提高內核的訪存命中率。但是，對指令和數據在片上緩存與內存之間往返遷移的特點和規律缺乏應有的研究和分析。本文將運用數學方法研究指令和數據在處理器片上的遷移，初步探索其特點和規律，以最大限度保持指令和數據之間的時間和空間聯系，該方向的研究具有重要的理論和實踐指導意義。

根據存儲程序原理，指令和數據之間的時空關聯關系來源于程序執行邏輯的內在規定。抽象地看，以指令執行順序、數據安置順序為基本構件形成的邏輯復合體構成了計算機程序，這個邏輯復合體隱含著指令之間、數據之間不可割舍的時空聯系。在遷移進出處理器時，指令和數據之間的時空聯系很可能由于它們在內存和片上緩存的存儲位置變化而發生變化，導致在處理器原計劃遵照程序內在的邏輯展開運算時，前來向處理器“報到”的指令或數據卻打亂了這內在的程序執行邏輯。這樣需求錯位的矛盾局面產生的根源是內存容量和片上緩存容量存在巨大的落差，片上緩存中的指令和數據需要不斷地更新才能將所有指令和數據從內存中推到處理器核的面前，方便處理器核訪問。因此，需求錯位的矛盾是結構性的。

為了緩解需求錯位的矛盾，在處理器內核訪問任意指令或數據時，應該將與之存在時空關系的其他指令、數據組合為一個整體遷移到處理器的片上緩存內，盡量保持指令或數據之間的時空聯系，將指令之間、數據之間的時空關系轉化為指令、數據在片上緩存體系中緊密分布的形態。由于處理器片上緩存是指令和數據進入處理器核的必經之路，此分布形態必然為提高處理器內核的訪存命中率，減緩訪存時延、控制指令和數據遷移以適應處理器運算需要，營造有利的片上及時局部性環境創造條件。

事實上，及時局部性的特質已經體現在處理器體系的內在結構之中。例如，存儲在片上寄存器里的指令操作元分布在諸如指令解碼器、指令流水線等功能單元可就近方便獲取的地方[6-7]，各級流水線中眾多狀態寄存器的存在都是及時局部性存在的例證[8-9]。本文可以把片上通用寄存器理解為片上緩存，而片上緩存是通用寄存功能的具體延展。

本質上，片上及時局部性環境可以使處理器所需要的指令或數據及時、就近地在片上寄存器或緩存內找到[10-13]。因此，掌握指令和數據在片上寄存器、緩存和內存之間往返遷移的規律和特點，必將為人們探索在遷移過程中保持指令或數據之間的時空聯系、營造高質量的及時局部性環境奠定基礎。

以指令解碼器為分水嶺，可以把營造及時局部性環境的工作分為解碼前期和解碼后期2 個階段。在解碼前期，及時局部性環境主要在片上緩存營造，指令和數據在緩存中的分布形態及其更新是人們關注的重點；在解碼后期，及時局部性環境主要通過控制指令和數據在處理器片內各類寄存器中的分布來實現。

為了更好地緩解需求錯位的矛盾，文獻[1]給出了一個由2 個傳統緩存耦合而成的新型片上緩存，稱之為滲透緩存，并在指令或數據的遷移中將具有時空關聯關系的指令和數據以及時局部組的整體形式從內存遷往滲透緩存，同時控制指令和數據在滲透緩存內一方面似泉水涌出般地“涌”向滲透緩存的頂端，另一方面似泉水被吸入泉眼般地被“吸”回內存，使指令和數據在片上緩存內流動起來。

圖1 給出了一個滲透緩存結構及數據遷入規則示意，其中地址4 是處理器核的訪存焦點，相鄰地址3 與地址5、地址2 與地址6、地址1 與地址7構成內存中一個對稱的及時局部組。當地址4 上的指令或數據被遷往滲透緩存中的泉吸緩存的頂端時，及時局部組內的其他指令或數據被分別遷往滲透緩存中的第一級、第二級、第三級泉涌緩存。由于地址4 的及時局部性程度最高，與之鄰近的地址3 和地址5 的及時局部性程度也比較高，因此地址3 和地址5 上的指令或數據被遷移到泉涌緩存的第一級。如果處理器內核在隨后的訪存中其訪存焦點仍然是地址4，那么該地址的及時局部性仍然保持最高；如果訪存焦點不是地址4 而是地址5，那么它的及時局部性程度變為最高，地址4 的及時局部性降低。此刻，地址4 中指令或數據可以停留在原地或被降級遷往滲透緩存中的第二級泉吸緩存，地址5 中的指令或數據被升級遷往第一級泉吸緩存，地址6 中的指令或數據被升級遷往第一級泉涌緩存，地址7 中的指令或數據被升級遷往第二級泉涌緩存，如此，指令或數據在滲透緩存中變成流動的趨勢。仿真實驗表明[4]，將處理器片上緩存改進為滲透緩存提高了處理器內核訪存的效率和訪存命中率，為縮短訪存時延營造了及時局部性環境[2-3]。

圖1 滲透緩存結構及數據遷入規則示意

顯然，如果及時局部組內的指令或數據都能夠滿足處理器內核的訪存需要，那將是一個理想狀態，而滲透緩存是一種逼近這種理想狀態的手段。本文將探討這種理想狀態產生的合理性。

及時局部組是一個以處理器訪存焦點即當前被訪問的指令或數據為中心、一定范圍內的指令或數據組成的、具有時空關聯關系的指令或數據族群。所以，應該以族群內的指令或數據之間的關聯關系在遷移過程中發生的變化為入手點，去認識及時局部環境內在機制，發現理想狀態產生的前提條件。為了從理論上深入認識及時局部環境的內在機制，實現理想的及時局部性狀態，本文將運用抽象的數學方法研究分析指令或數據在處理器片上緩存和內存之間往返遷移的規律，尋找遷移過程中保持指令或數據及時局部性的前提條件。文獻[1]具體介紹了滲透緩存中的數據遷移方式的有效性，本文將以數學抽象的方式證明滲透緩存結構的內在合理性。

2 內存、片上緩存的抽象描述

2.1 內存、地址和基本可尋址單位

地址是計算機體系結構中的核心概念，是建立存儲體系的基本工具。地址的組成結構規定了計算機內存和片上緩存的關聯法則[4,14]。下面，給出內存、地址和基本可尋址單位的抽象定義。由于存儲空間是描述地址結構及其形式的基礎，因此先給出存儲空間的抽象定義。設m為自然數，集合D={0,1}，稱集合Dm={(dl,d2,…,dm)|di∈D,i=1,2,3,…,m}為存儲空間，自然數m為存儲空間維數。存儲空間維數m決定存儲空間的容量。由于m維存儲空間中的向量是m位的二進制數，存儲空間中的所有向量構成一個由m位二進制數組成、按數值大小關系排列順序的全序集合[15]，這種序關系本質上就是地址的序關系。因此從存儲空間演化出地址空間。

定義1設m為自然數，Dm為m維的存儲空間，≤為存儲空間中的全序關系，稱集合{Dm,}≤為地址空間，地址空間中的向量為地址。

定義2設m,n,p,q,k為自然數，m=kn，Dn為地址空間，Dm為存儲空間，設

則稱Dn×Dm為內存；Dm中的向量為存儲槽，內存空間中的向量為基本可尋址單位。

根據定義2，基本可尋址單位由地址和存儲槽構成，具有唯一的地址，泛指存儲在內存中的指令或數據。2 個基本可尋址單元在內存中的距離可以定義為地址之間的距離。

2.2 片上緩存

在處理器運行過程中，被訪問過或從內存取出等待訪問的數據被置于一個具有層次結構的片上緩存內。片上緩存實質是內存層次化的自然延伸。片上緩存的結構及其上的數據分布策略影響處理器的性能。處理器內核應該盡可能在緩存層級的高層級內訪問到原本需要到內存或低緩存層級中才能訪問到的數據。所以，必須將加載到內存的數據遷移到容量相對有限的片上緩存高層級內。將一個大容量結構內的數據納入一個容量相對小的結構內的根本方法是將大容量結構內的數據分成等價類，將等價類的代表放入容量相對小的結構之中。只有這樣才能在邏輯意義上將一個大容量結構置于小容量結構之中。目前，片上緩存與內存之間的關聯結構主要是通過等價分類實現的[16]。定義3 描述了該等價類方法的本質。

定義3設m,n,p,q為自然數，Dp×Dq和Dn×Dm為內存。如果映射

使對內存Dn×Dm中任意的基本可尋址單位

存在內存中的基本可尋址單位v=(i1,i2,…,ip,c1,c2,…,cq)的地址滿足

其中，g為自然數，2p＞I，I=i12p-1+。則稱內存Dp×Dq為內存Dn×Dm的常規緩存，I為基本可尋址單位u在緩存Dp×Dq的索引號，映射Q為從Dn×Dm到Dp×Dq為常規相聯。

圖2 是一個內存和緩存關聯關系示意。內存里的數據地址按照定義3 中規定的模運算進行換算，并以模運算的余數為索引號為該地址上的數據在緩存中確定新位置，即存儲槽索引號。例如，圖2 中緩存容量值c為7，以其為模數，對數值為8的地址進行模運算得到余數為1，則位于內存位置8 上的數據被遷移到緩存中后，其在緩存中的索引號為1。圖2 中的平面坐標系內給出了從內存地址空間U到片上緩存地址空間H（緩存槽索引號）之間的對應關系。

圖2 內存和緩存關聯關系示意

一般地，內存空間Dn×Dm中的基本可尋址單位u的地址與另一個內存空間Dp×Dq的容量2p進行模運算，所得余數正好為基本可尋址單位v在內存空間Dp×Dq里的地址，即緩存槽索引號。根據拓撲學的知識[15]，模運算將內存空間中的所有基本可尋址單位分成2p個等價類。

定義3 說明了緩存是層次結構意義上的內存，只是離處理器核更近。根據定義3，直接相聯緩存和集合相聯緩存是常規緩存。在大多數情況下，常規緩存用來建立一般情況下的片上緩存。但是，全相聯緩存為非常規緩存，這是因為Dn×Dm內的可尋址單位可以在Dp×Dq內任意放置，不用模運算來定位。非常規緩存用于在特殊的條件下建立片上緩存。除非特別指出，本文的討論圍繞常規緩存展開。

2.3 訪存焦點與及時局部性

處理器當前訪存所指向的內存位置稱為處理器的訪存焦點。

定義4設m,n為自然數，r為非負整數，為內存Dn×Dm中任意一個基本尋址單位，，稱集合N(u,r)={u′:e(u-u′)＜r}為以基本尋址單位u為中心的鄰域。其中，e(u-u')為2 個基本可尋址單位u和u′之間的距離。

以一個處理器的當前訪存焦點u為中心，以距離r為半徑，可在內存中劃定一個不超出此半徑的對稱區域，區域內匯集了一簇按照地址順序排列的基本可尋址單位，訪存焦點位于隊列正中央，形成一個以訪存焦點為中心的鄰域N(u,r)，構成一個對稱及時局部組。控制鄰域半徑，即可控制鄰域規模；控制鄰域規模，即可控制遷移數據的規模。

在處理器運行中，訪存焦點u可能被再次訪問，多次成為處理器的執行焦點，這種執行焦點短暫保持在固定位置的處理器運行態勢稱為時間局部性。當訪存焦點發生改變時，處理器要訪問鄰域N(u,r)內其他的基本尋址單位，且執行焦點不超出鄰域范圍的微漂移執行態勢。執行焦點在固定位置重復出現，或相對于固定位置產生微漂移的執行態勢說明了及時局部組內數據之間具有相對突出的匯聚性，是及時局部性的動態形式。

因此，以基本尋址單位的鄰域為媒介，可為處理器的運行營造快捷訪問數據的及時局部性環境，進而在片上緩存內完善遷移數據的機制，將改進計算性能的視野從靜止固定的緩存結構層面，提升到動態靈活利用數據關聯特征的高度。

3 及時局部性的分拆與折疊

為了在片上緩存的高端層級營造理想的服務處理器核的及時局部性環境，作為整體遷移的及時局部組鄰域N(u,r) 內各基本尋址單位之間相互靠攏的位置關系應該盡力保持穩定。然而，及時局部組內基本可尋址單位相互靠攏的態勢可能會因內存和片上緩存的關聯結構限制而在從內存遷移到緩存過程中發生形變，造成及時局部組鄰域被分拆或折疊。

例1圖3 顯示了一個常規緩存中緩存槽索引號和內存地址的對應關系。例如，索引號為2 的緩存槽可以接納來自內存地址為2、10、18、26 等的數據。以任意一個內存地址為中心，取鄰域半徑為2，可以構成一個以該地址為中心的及時局部組。從圖3 可以看出，那些以與緩存存儲槽索引號為2、3、4、5 對應的地址為中心的及時局部組可以不破壞地址相鄰連續性關系地遷移到緩存內。例如，以地址19 為中心的及時局部組占據一個連續的地址段17、18、19、20、21。這些內存地址上數據之間的關聯關系可以不被分拆地遷移到緩存內一組相鄰索引號1、2、3、4、5 所指定的緩存槽內。然而，以那些與索引號0、1、6、7 相對應的地址為中心的及時局部組卻只能被分拆后遷移到緩存內。例如，以地址23 為中心的及時局部組占據一個連續地址段21、22、23、24、25，該地址段上的數據被遷移到緩存內一組不相鄰的索引號5、6、7、0、1所指定的片上緩存槽內。索引號為5 的緩存槽與索引號為1 的緩存槽之間的距離為3，超過了及時局部組的鄰域半徑2。

圖3 片上緩存中數據分配示意

及時局部組遷移后其鄰域半徑被拉長的情形稱為及時局部性分拆。反過來，如果及時局部組半徑過大，會出現一個緩存槽被來自內存中地址不同的2 個數據同時占據的不合理情形。

例2在圖3 中，選擇及時局部組鄰域半徑為6，以地址14 為中心的及時局部組占據一個連續地址段8、…、13、14、15、…、20。這些地址上的數據被遷移到緩存內后，一些緩存槽同時被2 個來自不同內存地址的數據所占據。例如，索引號為3的緩存槽被來自內存地址11、19 的不同數據同時占據，這顯然是不合理的。

同一緩存槽被來自不同地址的數據同時占據的情形稱為及時局部性折疊。及時局部性折疊是數據過度靠攏的畸形形態，在基本可尋址單位從內存遷往緩存的過程中，應杜絕及時局部性折疊。定理1 給出了消除及時局部性折疊的充分必要條件。

定理1設m,n,p,q為自然數，內存Dp×Dq為內存Dn×Dm的常規緩存，r為對稱及時局部組的半徑，則發生及時局部性折疊的充分必要條件是r≥c/2。其中，c=2p為緩存Dp×Dq的容量。

證明必要性。任取內存Dn×Dm里一個基本可尋址單位，設其在常規緩存Dp×Dq內的索引號為h。如果出現及時局部組折疊，則只能出現圖4和圖5 這2 種情形中。在圖4 中，索引號為h的緩存槽到索引號為c的緩存槽的距離c-h小于及時局部組的鄰域半徑r，且

圖4 靠近緩存高地址端

于是r-c+h≥h-r，則2r≥c，即

同理，在圖5 中，索引號為h的緩存槽到索引號為0 的緩存槽的距離h小于及時局部組的鄰域半徑r且

圖5 靠近緩存低地址端

于是r-h≥c-h-r，則2r≥c，即

所以，如果發生及時局部性折疊，則必然有r≥c/2。

充分性。假設不發生及時局部性折疊，則r-(c-h)＜h-r而且r-h＜c-(h+r)，于是根據上述2 個不等式，有

所以，如果r≥c/2，則一定發生及時局部性折疊。

定理2設m,n,p,q為自然數，內存Dp×Dq為內存Dn×Dm的常規緩存，r為對稱及時局部組的半徑，則不發生及時局部性折疊的充要條件是

其中，c=2p為緩存Dp×Dq的容量。

證明根據定理1，此結果是顯然的。

定理1 和定理2 指出控制及時局部組的鄰域半徑在一定范圍內能杜絕及時局部性發生折疊。然而，及時局部性發生撕裂卻是一定的。只要控制內存地址的取值范圍和及時局部組鄰域半徑規模，直接相連和組相連的內存與片上緩存的連接關系能夠使及時局部組在從內存遷往片上緩存的過程中，及時局部組內各個數據之間的相對關系不被破壞，這意味著當前處理器中片上緩存和內存之間的相聯機制能夠實現保持數據及時局部性的遷移。

4 滲透緩存內命中率分析

數據遷移到片上緩存的中心地帶可能會產生及時局部性分拆（由于通常的及時局部組鄰域半徑遠小于片上緩存容量的一半，本文在此假設及時局部性折疊的情況可以忽略）。例如，考慮數據從圖6中的內存Cs遷移到緩存Ct的情形。如果及時局部組鄰域某個基本可尋址單位的地址值為緩存Ct容量值的整數倍，那么如圖6 中的陰影區域所示，這些陰影區域內的數據遷入緩存后將被分拆為兩部分，陰影左半部分內的數據被安置在緩存Ct的右端，陰影右半部分的數據被安置在緩存Ct的左端。否則，及時局部組鄰域內的數據遷入緩存Ct內后不發生分拆，直接安置在緩存Ct內連續的存儲槽號所指定的緩存槽里。

圖6 數據從內存Cs遷移到緩存Ct

如果在遷移中保持局部性不被分拆，那么數據可以在片上緩存內接收處理器內核的訪問，免除了處理器內核“遠涉”內存去獲得數據；但是，當處理器訪存焦點移出該及時局部組時，后續到來的數據及時局部組很可能全面覆蓋之前到來的及時局部組，此刻，若處理器內核的訪存焦點移回之前的及時局部組，那么處理器內核將不能在片上緩存內訪問到之前及時局部組內的數據，只能“遠涉”內存再次遷移數據。因此，處理器內核訪問片上緩存的命中率會在這種條件下降低，訪存時延會相應增加。

如果遷移過程中發生及時局部性分拆，那么及時局部組內的數據就會分拆開來，分布在片上緩存的兩端。此時，該及時局部組被后續到來的及時局部組全面覆蓋的可能性存在降低的可能。如果及時局部組在遷移到片上緩存的過程中，及時局部組內的數據分布在如圖1 所示的三級緩存內，那么，這些局部組內的數據被隨后到來的新的局部組全部覆蓋的可能性就更低了。這就是本文在第1 節中介紹的滲透緩存能夠提高處理器訪存命中率、縮短訪存時延的原因。下面的仿真實驗證實了本文的理論分析。

5 仿真實驗

本文利用modelsim 10.1a 仿真平臺對向傳統緩存和滲透緩存實施數據遷移的過程進行了模擬，核心工作是模擬處理器load/store 指令的數據傳輸過程。為此，本文構建了處理器模塊、緩存模塊、內存模塊、滲透次數收集模塊。其中處理器模塊用來解析測試集地址以及產生訪存請求；緩存模塊用來處理數據的替換、滲透以及向滲透次數收集模塊反饋單次滲透完成信號；內存模塊用來處理數據的替換、滲透遷移以及存儲數據；滲透次數收集模塊用來統計單輪滲透次數信號，當收集到一輪完整的滲透信號之后，向處理器匯報，使處理器開始下一輪工作，各模塊通過數據傳輸協調工作，如圖7 所示。實驗中傳統緩存和滲透緩存的配置規格如表1 所示。

圖7 仿真模塊協調工作示意

表1 傳統緩存和滲透緩存參數設置

實驗結果表明，在內存和片上緩存之間實施滲透數據遷移之后，相比傳統的數據遷移做法，處理器內核訪問片上緩存的命中率總體上得到了有效提高，自然相應地縮短了處理器的訪存時延。由于篇幅的限制，本文在此給出部分實驗數據，如表2～表4 所示。其中，程序Wordcount、Cholesky 以及LU 是通常測試處理器性能的測試程序，具有典型的代表性，Wordcount 的指令和數據的地址存放序列具有突出的時間局部性，LU 具有突出的空間局部性，而Cholesky 兼具時間與空間局部性。以Wordcount 測試集作為處理器訪問內存的請求地址，將訪存命中率從傳統緩存的88.036%提升至滲透緩存的92.336%；以Cholesky 測試集作為處理器訪存的請求地址，將訪存命中率從傳統緩存的90.118%提升至99.920%；以LU 測試集作為處理器訪存的請求地址，將訪存命中率從傳統緩存的0.076%提升至92.160%。由于滲透緩存由泉吸緩存與泉涌緩存構成，而傳統緩存在結構上相當于泉涌緩存容量為零的滲透緩存，且滲透緩存比傳統緩存更加注重空間局部性，對于LU 這種具有極端的空間局部訪存特性的測試集，滲透緩存對訪存命中率的提升幅度更大。從實驗結果分析，在LU 測試集中，大部分處理器內核所需要的數據在被遷移滲透訪問的過程中駐留在滲透緩存里，這可以從表4 絕大部分成功訪問發生在緩存L2-push 中的結果得到驗證。從整體上看，訪存總的命中率得到提升，在滲透緩存各層級的命中率較傳統緩存中對應層級的命中率也得到提升。

表2 傳統緩存和滲透緩存上的命中率（Wordcount）

表3 傳統緩存和滲透緩存上的命中率（LU）

表4 傳統緩存和滲透緩存上的命中率（Cholesky）

在片上緩存容量固定不變的條件下，被遷移的緩存塊大小變化與處理器內核訪問緩存的命中率之間的關系比較復雜。確定緩存塊的規模需要以形成片上及時局部性環境為目標，在動態調控緩存塊的規模和遷移過程中盡量使包含在程序中的計算邏輯或業務邏輯在片上及時局部性環境得到保持。為此，本文下一步將進行動態調控緩存塊大小規模方面的探索研究。

6 結束語

從本文的討論中可以發現，數據遷移到處理器片上緩存中之后，自然不存在處理器內核到內存里訪問數據的時間消耗，縮減了處理器內核的訪存時延；如果處理器內核在片上緩存內的訪存命中率得到提高，那么縮減訪存時延的積累效應就更加理想。

所以，構成及時局部組的數據整體遷移到處理器片上后，處理器訪問內存數據的時間消耗將進一步減少；如果以及時局部組的形式整體到片上緩存內的數據能夠化整為零地分布在緩存內的各個層級，那么這些數據就可能在片上緩存內停留更長的時間而不被后續到來的及時局部組所覆蓋，進而為處理器內核的訪存焦點再次轉移到這些化整為零的數據上創造了更好的命中率，如此迭代積累，必然在片上緩存內建立起理想的及時局部性環境，為改進處理器計算性能挖掘出新的潛力。本文給出的理論分析證明了以及時局部組形態遷移數據從內存遷往片上緩存不僅是可行的，而且營造處理器片上緩存內及時局部性環境是合理的。在內存和片上緩存之間的數據遷移方式蘊含了在微觀層面實施數據通信的潛在基礎。