陳繼承 趙雅倩 李一韓 王恩東 史宏志 唐士斌
(高效能服務器和存儲技術國家重點實驗室(浪潮集團有限公司) 北京 100085)
(chenjch@inspur.com)
緩存一致性維護是影響高速緩存一致性非均勻存儲訪問(cache coherence non-uniform memory access, CC-NUMA)系統性能的關鍵因素.早期的CC-NUMA系統中,處理器數量較少,各處理器間直接互連,系統采用單級一致性域設計即可滿足系統性能需求.但隨著系統規模的擴展,單級一致性域系統的處理器互連結構越來越復雜,消息全局性傳播引發的網絡阻塞延遲越來越大,緩存一致性維護開銷急劇增長,嚴重影響系統性能與擴展性.因此,8路以上的CC-NUMA系統通常采用兩級一致性域設計抑制緩存一致性維護開銷,即:多個處理器互連組成結點后形成結點內一致性域,多個結點互連組成系統后形成結點間一致性域,兩級一致性域間的協議轉換通過一致性協同芯片(coherence chip, CC)實現[1-3].該方法可將一致性維護操作盡量限制在局部區域以避免一致性消息的全局傳播,避免了單級一致性域造成的系統互連結構復雜、跨處理器訪問跳步數多、高負載下阻塞延遲急劇增長等難題[4],從而使系統性能得到有效擴展.
受限于處理器的直連能力和處理器可識別的ID數,CC-NUMA系統所能構建的單結點規模有限,系統擴展只能通過增加結點數目來實現.但是,結點數目的增加會導致一致性目錄存儲開銷上升、跨結點訪問跳步數和延遲增大、系統規模無法進一步有效擴展.針對上述問題,當前CC-NUMA系統采用目錄優化[5]、片外緩存擴展[6-8]、緩存數據預取[9-11]、一致性協議優化[12-14]等方法來降低跨結點訪問頻度,減少一致性開銷.
然而,上述優化方法都是通過減少跨結點訪問頻度間接減少平均訪問延遲,對系統拓撲結構沒有改變,沒有縮短跨結點訪問路徑和跳步數.針對該問題,本文提出了一種可任意配置結點內處理器規模的CC-NUMA系統——多并行緩存一致性域(multiple parallel cache coherency domain, MPD).該系統通過在結點內構建多個并行緩存一致性域來擴大單結點規模,使其不再受限于處理器直連能力和處理器可識別ID數,從而減少系統結點數量,簡化系統拓撲結構,縮短訪問路徑和跳步數,直接減少系統平均訪問延遲.同時,由于結點內的多個緩存一致性域之間是并行關系,連接至1個一致性協同芯片,共同構成結點內一致性域,所以,與傳統CC-NUMA系統相比,MPD系統并未增加緩存一致性域的層級.
為減少緩存遠端訪問頻率,降低緩存一致性維護開銷,CC-NUMA系統通常將緩存資源劃分為2個一致性同步域,使用兩級緩存一致性協議對各一致性域進行一致性管理.圖1是一個典型的多結點CC-NUMA系統,包含結點內一致性域和結點間一致性域的兩級緩存一致性域.
1) 結點內一致性域.n個處理器與1個一致性協同芯片互連,構成結點內一致性域,維護的是本結點內n個處理器間的緩存一致性.
2) 結點間一致性域.M個結點通過一致性協同芯片互連,構成結點間一致性域,維護的是系統內各結點間的緩存一致性.
兩級一致性域系統中,一致性協同芯片用于維護兩級一致性協議的轉換和維護,該芯片通常包含遠端代理(remote proxy, RP)和本地代理(local proxy, LP)兩個處理單元.
1) RP.結點一致性協同芯片的遠端內存代理,存儲遠端地址數據在本地結點內處理器的一致性狀態,監控本地處理器對遠端地址的請求,可與本地處理器及遠端結點一致性協同芯片的LP單元進行通信.
2) LP.結點一致性協同芯片的本地內存代理,存儲本結點地址的數據在其他遠端結點的一致性狀態,監控遠端結點對本地地址的請求,可與本地根目錄及遠端結點一致性協同芯片的RP單元進行通信.
偵聽與目錄是對緩存一致性信息的2種處理方式[15].由于偵聽協議可擴展性差,所以,CC-NUMA系統多采用基于目錄的緩存一致性協議.結點一致性協同芯片的緩存一致性目錄記錄了各緩存行的一致性狀態(State)、共享列表(Share List)和寫權限擁有者(Owner),按緩存數據地址的不同,分別由RP與LP單元維護與更新.
RP目錄存儲了遠端數據在本結點的一致性狀態信息,目錄項如圖2所示:
1) State——狀態位,記錄遠端數據在本結點的一致性狀態,其長度與協議有關,如MI協議占用1 b,MESI協議占用2 b;
2) Share List——共享列表,記錄遠端數據在本地結點內處理器的一致性狀態,其長度與目錄實現技術有關,如全映射目錄[3]的共享列表長度為n;
3) Owner——寫權限擁有者,記錄遠端數據在本結點內處于ME態的處理器ID,其長度為n.
LP目錄存儲了本地數據在遠端結點的一致性狀態信息,目錄項如圖3所示:

Fig. 3 LP directory entry in CC-NUMA system圖3 CC-NUMA系統結點一致性協同芯片LP目錄項
1) State——狀態位,記錄本地數據在本結點的一致性狀態;
2) Share List——共享列表,記錄本地數據在本結點i之外的所有遠端結點的一致性狀態,全映射目錄的共享列表長度為M-1;
3) Owner——寫權限擁有者,記錄本地數據在遠端結點處于ME態的遠端結點ID,其長度為M-1.
MPD系統是一個結點內包含多個并行緩存一致性域的CC-NUMA系統.如圖4所示,n個處理器與結點一致性協同芯片緊耦合互連,構成1個緩存一致性域(cache coherence domain, CCD);k個緩存一致性域并行連接至1個結點一致性協同芯片,共同構成結點內一致性域;m個結點通過結點一致性協同芯片互連,構成結點間一致性域,m=Mk.與圖1的CC-NUMA系統相比,圖4的MPD系統結點數量縮減為原系統的1k.
MPD系統中,結點內的多個緩存一致性域并行連接至1個一致性協同芯片,并由該協同芯片統一維護其結點內的緩存一致性,也就是說,這些并行的緩存一致性域并不單獨維護一致性域.所以,MPD系統的一致性域設計與CC-NUMA系統相同,都是結點內結點間兩級一致性域架構,使用兩級緩存一致性協議,兩級一致性域間的協議轉換通過一致性協同芯片實現.
1) 結點內一致性域.k個緩存一致性域與1個一致性協同芯片互連,構成結點內一致性域,由本結點的一致性協同芯片統一維護結點內nk個處理器間的緩存一致性.

Fig. 4 MPD system with multiple clumps圖4 多結點MPD系統
2) 結點間一致性域.m個結點通過一致性協同芯片互連,構成結點間一致性域,由各結點的一致性協同芯片共同維護系統各結點間的緩存一致性.
與CC-NUMA系統類似,MPD系統的結點一致性協同芯片也包括遠端代理RP和本地代理LP這2個處理單元,但邏輯功能和通信單元略有差異,主要是對LP進行了功能擴展,以同時維護結點內所有處理器的緩存一致性.
1) RP.結點一致性協同芯片的遠端內存代理,存儲遠端地址數據在本地結點內(含本結點內所有緩存一致性域)處理器的一致性狀態,監控本結點內所有處理器對遠端地址的請求,可與本結點內處理器或遠端結點一致性協同芯片的LP單元進行通信.
2) LP.結點一致性協同芯片的本地內存代理,存儲結點內各緩存一致性域的本地數據在本結點內其他緩存一致性域各處理器以及系統內所有遠端結點的一致性狀態,監控各緩存一致性域對結點內其他緩存一致性域的請求以及遠端結點對本地地址的請求,可與本結點內處理器、根目錄以及遠端結點一致性協同芯片的RP單元進行通信.
從CC-NUMA與MPD系統中RP與LP的邏輯功能對比來看,MPD系統中的RP與LP單元需要存儲更多處理器的一致性狀態信息,所以需要對CC-NUMA系統的一致性協同芯片目錄的共享列表進行擴展.
RP目錄存儲了遠端數據在本結點內所有并行緩存一致性域的一致性狀態信息,目錄項如圖5所示.
1) State——狀態位,記錄遠端數據在本結點的一致性狀態;
2) Share List——共享列表,記錄遠端數據在本地結點所有緩存一致性域內處理器的一致性狀態,全映射目錄的共享列表長度為nk;
3) Owner——寫權限擁有者,記錄遠端數據在本結點內處于ME態的處理器ID,其長度為lb(nk).

Fig. 5 RP directory entry in MPD system圖5 MPD系統RP目錄項
LP目錄存儲了本結點各緩存一致性域的本地數據在結點內其他并行緩存一致性域以及系統遠端結點的一致性狀態信息,目錄項如圖6所示.
1) State——狀態位,記錄本地數據在本結點的一致性狀態;

3) Owner——寫權限擁有者,記錄本地數據在遠端結點處于ME態的遠端結點ID,或緩存一致性域本地數據在結點內其他緩存一致性域處于ME態的處理器ID,長度為

Fig. 6 LP directory entry in MPD system圖6 MPD系統LP目錄項
雖然MPD系統與CC-NUMA系統的緩存一致性域層次相同,但兩者的系統架構不同,因此,2種系統的緩存一致性交互流程略有不同.
1) 緩存一致性域內訪問
MPD系統與CC-NUMA系統的緩存一致性域結構相同,都是由多個處理器與一致性協同芯片互連而成,因此,兩者的緩存一致性域內訪問流程相同,均為CPU與根目錄直接交互,如圖7所示:

Fig. 7 Access within the same CCD in CC-NUMA or MPD system圖7 CC-NUMA系統與MPD系統的緩存一致性域內訪問
2) 緩存一致性域間訪問
CC-NUMA系統內,結點內一致性域由單個緩存一致性域構成,所以,緩存一致性域間訪問即為結點間一致性訪問,如圖8所示:

Fig. 8 Access between different CCDs in CC-NUMA system圖8 CC-NUMA系統的緩存一致性域間(結點間)訪問
MPD系統內,單個結點一致性域內包含多個緩存一致性域,因此,MPD系統的緩存一致性域間訪問包含了結點內的緩存一致性域間訪問和結點間的緩存一致性域間訪問2種類型,如圖9所示:

Fig. 9 Access between CCDs in MPD system圖9 MPD系統的緩存一致性域間訪問
圖9(a)描述了MPD系統獨有的結點內跨緩存一致性域訪問,它將CC-NUMA系統中的遠端跨結點訪問轉換為近端結點內跨域訪問,僅與本地一致性協同芯片進行交互;圖9(b)描述了與CC-NUMA系統相同的結點間的緩存一致性域間訪問,需與本地一致性協同芯片及遠端一致性協同芯片進行交互.
從2種系統的緩存一致性交互流程描述來看,MPD系統中的緩存一致性訪問分為3類:
1) 結點內的緩存一致性域內訪問.該類訪問對應CC-NUMA系統的結點一致性內訪問(即緩存一致性域內訪問),兩者開銷相同.
2) 結點內的緩存一致性域間訪問.該類訪問對應CC-NUMA系統中的結點間訪問,前者僅通過本地CC即可進行交互,而后者需要通過本地CC與遠端CC才可進行交互,前者開銷小于后者.
3) 結點間的緩存一致性域間訪問.該類訪問對應CC-NUMA系統中的結點間訪問,兩者開銷相同.
因此,與CC-NUMA系統相比,MPD系統并未產生額外的一致性開銷,并將部分結點間訪問轉換為結點內訪問,直接縮短了訪問路徑與跳步數,從而降低系統平均訪問延遲,減少一致性維護開銷,提升系統性能.
MPD系統通過在結點內構建多個并行緩存一致性域突破了單結點規模限制,減少了結點數量,從而降低了結點規模和結點間網絡復雜度.
假設某系統規模(即處理器總數)為N,單個緩存一致性域內最多容納處理器數量為n,那么,傳統CC-NUMA系統和MPD系統的結點數Num_C以及結點間全互連的連接數T分別為
Num_CCC-NUMA=Nn,
(1)
TCC-NUMA=N(N-n)2n2,
(2)
Num_CMPD=Nnk,
(3)
TMPD=N(N-nk)2(nk)2,
(4)
其中,k為MPD系統中單個結點內包含的并行緩存一致性域個數.
由式(1)~(4)可以得出,同等系統規模下,傳統CC-NUMA系統和MPD系統的結點數量的比值ηNum_C為
(5)
結點間全互連的連接數比值ηT為
(6)
因此,與傳統CC-NUMA系統相比,MPD系統的結點規模可縮減至1k,結點間全互連的連接數可降低到1k2以下.例如,當N=64,n=4,k=2時,MPD系統的結點規模降低50%,結點間全互連的連接數降低77%;而當N=64,n=4,k=4時,MPD系統的結點規模降低75%,結點間全互連的連接數降低95%.
由于同一結點內不同緩存一致性域間的近端跨域訪問延遲遠小于不同結點間的遠端跨結點訪問延遲,所以MPD系統的平均訪問延遲低于CC-NUMA系統,如圖10所示:

Fig. 10 Clump architecture in different systems built with different CPU圖10 不同規格處理器搭建的系統單結點架構
假設MPD系統中同一緩存一致性域內的平均訪問延遲為l,同一結點內不同緩存一致性域間的平均訪問延遲為3l,不同結點間的平均訪問延遲為7l,緩存一致性域內的緩存次數占比為α,近端結點內跨域的訪問次數占比為β,那么,MPD系統的遠端跨結點的訪問次數占比為1-α-β,而相同規模的CC-NUMA系統的遠端跨結點的訪問次數占比為1-α.因此,同規模的MPD系統與CC-NUMA系統的平均訪問延遲L分別為
LMPD=l×α+3l×β+7l×(1-α-β)=
l×(7-6α-4β),
(7)
LCC-NUMA=l×α+7l×(1-α)=l×(7-6α).
(8)
① 該結論僅針對大規模CC-NUMA系統,單結點等小規模系統不保證不等式結論成立.
由式(7)(8)可得2種系統平均訪問延遲的比值為
(9)
假設α=10%,β=30%,則2種系統的平均訪問延遲之比為1316=0.812 5,即MPD系統的平均訪問延遲降低了近2成,有效提高了系統性能.
CC-NUMA系統中,每個緩存一致性域單獨維護1個結點一致性目錄,結點數量較多,系統的結點一致性目錄開銷較大;而MPD系統中,多個并行緩存一致性域共同維護1個結點一致性目錄,結點數量較少,系統的結點一致性目錄開銷較小.
以MESI(modified,exclusive, shared or invalid)協議的全映射目錄結構為例,假設MPD系統規模為N,單個緩存一致性域內最多容納處理器數量為n,每個結點內共有k個緩存一致性域,內存容量為B,緩存項大小為b,則該系統內單個結點一致性目錄開銷為
(10)
該MPD系統內所有結點的一致性目錄總開銷為

(11)
同等規模的傳統CC-NUMA系統內單個結點目錄開銷為

(12)
該CC-NUMA系統內所有結點的一致性目錄總開銷為

(13)
由式(11)(13)可得,傳統CC-NUMA系統與MPD系統的結點一致性目錄總開銷的差值ΔD為

因為在大規模CC-NUMA系統中,


因此,對于大規模CC-NUMA系統,同等規模的MPD系統的結點目錄開銷更小,而且,內存容量越大,目錄開銷降低的幅度越大.
以64顆處理器組成的CC-NUMA系統為例,假設每個緩存一致性域內最多可容納2顆處理器,系統內存容量為16 GB,單個緩存項大小為128 KB.那么傳統CC-NUMA系統共需32個結點一致性協同芯片,目錄開銷為[8×(1 027+31×lb 31)]Mb,約為9.223 Gb;而單結點內含2個并行緩存一致性域的MPD系統僅需16個結點一致性協同芯片,目錄開銷為[8×(293+15×lb 17)]Mb,約為2.768 Gb,不到CC-NUMA系統目錄開銷的13;單結點內含4個并行緩存一致性域的MPD系統僅需8個結點一致性協同芯片,目錄開銷為[8×(118+7×lb 13)]Mb,約為1.124 Gb,不到CC-NUMA系統結點目錄開銷的18.
MPD系統中,單結點規模不再受處理器直連能力的限制,因此,可以選用直連能力較弱的處理器代替直連能力較強的處理器搭建同等結點規模的系統,以降低系統成本與功耗.不同直連能力的處理器價格和功耗差異較大.支持8路直連的處理器有3個一致性互連端口,功耗約為130 W,單價約為2 500美元;支持4路直連的處理器有2個一致性互連端口,功耗為115 W,單價為2 000美元;而支持2路直連的處理器僅有1個一致性互連端口,功耗為100 W,單價為1 500美元.
假設要搭建8結點的32路系統,傳統CC-NUMA系統需要32顆具有8路直連能力的處理器,結點內結構如圖10(a)所示;而結點內含2個并行緩存一致性域的MPD1系統則只需要32顆具有4路直連能力的處理器,結點內結構如圖10(b)所示;結點內含4個并行緩存一致性域的MPD2系統僅需要32顆具有2路直連能力的處理器,結點內結構如圖10(c)所示.
假定一致性協同芯片的單價為1 000美元,那么,CC-NUMA,MPD1,MPD2這3種8結點32路系統的硬件成本和處理器功耗如表1所示.相比于傳統CC-NUMA系統,單結點內含2個并行緩存一致性域的MPD1系統可降低功耗11.5%,降低成本20%;單結點內含4個并行緩存一致性域的MPD2系統可降低功耗23.1%,降低成本40%.

Table 1 Comparison of Power and Cost AmongDifferent Systems
① 本文實驗設置較小的內存容量是為了避免部分緩存密集訪問,以便更好地模擬大規模系統的多結點間的緩存一致性維護.
本文選用gem5[16]對兩級緩存一致性域的MPD系統和CC-NUMA系統進行模擬,模擬系統中,系統結點無結點緩存功能,對接收的消息均做轉發處理.各級訪問延遲比為∶緩存域內訪問延遲∶結點內訪問延遲∶結點間訪問延遲=1∶3∶7.實驗的主要系統參數如表2所示.實驗測試程序選用了SPLASH2[17]的1個內核程序和3個應用程序,以及PARSEC[18]中的3個應用程序,各配置如表3所示.

Table 2 Parameters of System Configuration表2 系統參數配置

Table 3 Benchmark SPLASH2 and PARSEC表3 測試集SPLASH2與PARSEC
為驗證MPD系統對系統性能有效擴展能力的提升,以及低功耗低成本MPD系統構建的可行性,本節分別對16路、32路和64路的傳統CC-NUMA系統與不同配置的MPD系統進行了對比測試.測試實驗數據顯示,不同處理器規模的系統對比結果類似.因此,為了避免重復,本節僅選用32路系統的對比測試數據進行說明.另外,為便于數據比較的直觀性,各組數據均以傳統CC-NUMA的系統性能為標準進行了歸一化處理.
4.2.1 平均訪問延遲對比
圖11顯示了CC-NUMA系統與各MPD系統中不同類型訪問的數量占比.圖11中的橫坐標m×k代表了系統的緩存一致性域規模:m代表結點數,k代表單結點內緩存一致性域數量.因此,m×1就代表了結點數為m的CC-NUMA系統.從圖11中各類訪問占比來看,由于MPD系統擴大了單結點處理器規模,有效減少了結點數量,部分結點間遠端訪問轉換為結點內跨域近端訪問,而且,單結點處理器規模越大,轉換為結點內跨域訪問的結點間訪問量越多.圖11中結點間訪問量減少最多的是OCEAN_NS.當單結點內有8個并行緩存一致性域時,OCEAN_NS有58%的結點間訪問轉換為結點內跨域訪問.

Fig. 11 Comparison of the access ratio among different 32-way systems圖11 32路CC-NUMA系統與MPD系統的各類型訪問量對比
因為結點內跨域訪問延遲遠小于結點間訪問延遲,所以結點間訪問數量的減少直接降低了系統平均訪問延遲.例如,單結點內有8個并行緩存一致性域時,OCEAN_NS的系統平均訪存延遲降低32%.從圖12的對比結果來看,系統平均訪問延遲的變化趨勢與結點間訪問占比類似,均隨結點內緩存一致性域數量k的增加而減少.當k=2時,與CC-NUMA系統相比,MPD系統的平均訪問延遲降低3.9%;當k=4時,與CC-NUMA系統相比,MPD系統的平均訪問延遲降低11.7%;當k=8時,與CC-NUMA系統相比,MPD系統的平均訪問延遲降低27.9%.

Fig. 12 Comparison of the average access latency among different 32-way systems圖12 32路CC-NUMA系統與MPD系統的平均訪問延遲對比
4.2.2 指令平均執行周期對比
相較于系統平均訪問延遲,CC-NUMA系統和MPD系統的指令平均執行周期(cycles per instruction,CPI)差異較小,但仍是MPD系統性能較優,且系統CPI隨結點內緩存一致性域數量k的增加而減少.這主要是因為,系統平均訪問延遲僅與訪問類型占比有關,而CPI還與程序指令數、指令類型等有關.圖13中各程序的CPI變化幅度不同也是因為這個原因.盡管各測試程序的CPI降幅不同,但MPD系統整體平均性能仍呈現較明顯的線性下降趨勢:當k取值為2,4,8時,MPD系統比傳統CC-NUMA系統的CPI分別降低3.6%,7.6%,12.6%,即MPD系統性能提升3.5%,8.2%,14.4%.
本文3.4節所述,MPD系統中可采用直連能力較弱的處理器代替直連能力較強的處理器搭建同等規模的系統,以降低功耗、節約成本.但是,MPD系統采用的是單結點內多緩存一致性域架構;原CC-NUMA系統中的部分緩存一致性域內訪問將轉換為結點內跨一致性域訪問,從而導致系統平均訪問延遲增加,性能下降.

Fig. 13 Comparison of CPI among different 32-way systems圖13 32路CC-NUMA系統與MPD系統的CPI對比
為測試這種低功耗低成本的MPD系統與傳統CC-NUMA系統的性能差異度,本節對不同規格處理器搭建的4結點16路系統、8結點32路系統和16結點64路系統進行了性能測試.各組測試數據均表明,與傳統CC-NUMA系統相比,采用較低規格處理器搭建的MPD系統性能下降有限.以圖14中的32路系統為例,當處理器為4路直連時,每個結點內有2個緩存一致性域,系統CPI上升1.7%;當處理器為2路直連時,每個結點內有4個緩存一致性域,系統CPI上升2.6%,上升幅度變小.
與表1中處理器硬件成本的下降程度相比,這種MPD系統的性能下降幅度較小,因此,使用低規格處理器搭建的MPD系統具有更高的性價比.如圖15所示,與8路直連處理器搭建的CC-NUMA系統相比,4路直連處理器搭建的32路MPD系統性價比提升1.20倍,2路直連處理器搭建的32路MPD系統性價比提升1.53倍.

Fig. 14 Comparison of CPI among 8 clumps 32-way systems built by different processors圖14 不同處理器搭建的8結點32路系統的CPI對比

Fig. 15 Cost-effective of different systems圖15 不同處理器系統的性價比
處理器直連能力和處理器可識別ID數的有限性限制了CC-NUMA系統的單個結點規模,導致系統規模的擴張只能通過結點數量的增加來實現.而結點數量的增加致使緩存一致性維護開銷增大,結點間互連結構復雜,降低了系統性能的有效擴展.本文提出的MPD系統突破了單結點的處理器規模限制,能夠任意設置單結點規模,大幅減少結點數量.與其他系統性能優化方法相比,這種擴大單結點規模的方法直接縮短了系統平均訪問路徑和跳步數,從而降低了平均訪問延遲,實現了系統性能的有效擴展.另一方面,由于MPD系統的單結點規模與處理器直連能力無關,MPD系統還可用于構建低功耗低成本系統,提升系統性價比.實驗數據表明,32路系統中,采用同規格處理器時,結點內4個并行緩存一致性域的MPD系統平均訪問延遲降低27.9%,系統性能提升14.4%;采用不同規格處理器時,與8路直連處理器搭建的CC-NUMA系統相比,2路直連處理器搭建的MPD系統性價比提升1.53倍.
未來的工作中,我們將增加結點緩存功能,進一步優化MPD系統的一致性協議實現,提升大規模系統性能.