一種基于共享轉(zhuǎn)發(fā)態(tài)的多級緩存一致性協(xié)議

陳繼承 李一韓 趙雅倩 王恩東 史宏志 唐士斌

(高效能服務(wù)器和存儲技術(shù)國家重點實驗室(浪潮集團有限公司) 北京 100085)

(chenjch@inspur.com)

當(dāng)前服務(wù)器為多處理器系統(tǒng)，通常采用高速緩存一致性非均勻存儲訪問(cache coherence non-uniform memory access, CC-NUMA)架構(gòu)[1].在CC-NUMA架構(gòu)系統(tǒng)中，緩存一致性維護開銷是影響系統(tǒng)性能有效擴展的關(guān)鍵因素[2].為了提升系統(tǒng)性能，研究人員針對一致性協(xié)議展開了大量的研究工作.在基于監(jiān)聽的一致性協(xié)議中，為了保證系統(tǒng)內(nèi)所有Cache內(nèi)容的一致性，需要在系統(tǒng)范圍內(nèi)廣播一致性消息.監(jiān)聽協(xié)議實現(xiàn)較簡單、延遲較小，一般經(jīng)過2跳即可響應(yīng)請求并返回數(shù)據(jù)[3].由于監(jiān)聽協(xié)議對共享態(tài)數(shù)據(jù)的訪問需要在系統(tǒng)內(nèi)廣播請求消息，容易造成網(wǎng)絡(luò)擁塞，因此適用于4路以下小規(guī)模系統(tǒng).MESI協(xié)議[4]定義了4種數(shù)據(jù)狀態(tài)，約定其他處理器對共享態(tài)數(shù)據(jù)的訪問需要向數(shù)據(jù)所在內(nèi)存發(fā)送請求獲取，因而限制了共享請求的廣播消息數(shù)量，提升了系統(tǒng)性能.Intel公司進(jìn)一步擴展了MESI協(xié)議，提出了MESIF協(xié)議[5]，定義了一種新的共享態(tài)——轉(zhuǎn)發(fā)態(tài)(F態(tài))，使得系統(tǒng)中具有該狀態(tài)的共享副本能夠響應(yīng)其他處理器的共享讀請求，從而可以消除系統(tǒng)中的多余數(shù)據(jù)應(yīng)答消息.為了允許寫狀態(tài)下的數(shù)據(jù)能夠直接轉(zhuǎn)發(fā)共享數(shù)據(jù)給其他請求的處理器，AMD公司在MESI協(xié)議的基礎(chǔ)上引入所有態(tài)(O態(tài))，提出了MOESI協(xié)議[6].這種方法假定程序運行過程中的回寫是非必需的，因而能夠減少大量回寫操作消耗的存儲器帶寬，提升系統(tǒng)性能.

金融、電信等國家關(guān)鍵性基礎(chǔ)設(shè)施信息系統(tǒng)核心業(yè)務(wù)是基于大型關(guān)系型數(shù)據(jù)庫的聯(lián)機事務(wù)處理類(OLTP)業(yè)務(wù).該類業(yè)務(wù)通常具有任務(wù)難以分解、數(shù)據(jù)關(guān)聯(lián)度高、響應(yīng)實時性要求高的特點[7].需要基于大規(guī)模CC-NUMA架構(gòu)的高端服務(wù)器來承載該類業(yè)務(wù).為了提升系統(tǒng)的性能，通常采用具有多級緩存一致性域的CC-NUMA架構(gòu).多級緩存一致性域的基本思想是分層劃域[8-9]，通過構(gòu)建多個一致性協(xié)同芯片(coherence chip, CC)將系統(tǒng)劃分為2個或多個一致性域，使得每個一致性協(xié)同芯片內(nèi)部形成一個統(tǒng)一的邏輯Cache一致性域，結(jié)點(clump)間通過二級一致性協(xié)同芯片構(gòu)建Cache一致性域.通過這種方式構(gòu)建的系統(tǒng)，可以減少多處理器計算機系統(tǒng)中一致性協(xié)同芯片的數(shù)量和結(jié)點間互連的規(guī)模，降低結(jié)點間拓?fù)鋸?fù)雜度，提高CC-NUMA系統(tǒng)的可擴展性.

然而，上述一致性協(xié)議主要是針對單級一致性域優(yōu)化設(shè)計的，在當(dāng)前的多級緩存一致性域體系結(jié)構(gòu)下協(xié)議存在著執(zhí)行效率低的問題，影響大規(guī)模CC-NUMA系統(tǒng)的性能.如MESI協(xié)議應(yīng)用在多級Cache一致性域上會導(dǎo)致各結(jié)點、各處理器頻繁地從內(nèi)存中讀取共享數(shù)據(jù)，產(chǎn)生大量的數(shù)據(jù)交互操作，加劇網(wǎng)絡(luò)擁塞，嚴(yán)重降低系統(tǒng)性能.MESIF協(xié)議雖然引入了F態(tài)，但在多級Cache一致性域系統(tǒng)上容易造成F態(tài)在不同結(jié)點、不同一致性域之間來回遷移，產(chǎn)生顛簸效應(yīng)，進(jìn)而產(chǎn)生較大延遲，使得系統(tǒng)性能難以有效擴展.MOESI協(xié)議擴展到多級Cache一致性域上狀態(tài)復(fù)雜，同時處于O態(tài)的數(shù)據(jù)如果長時間存放在緩存中，一旦數(shù)據(jù)意外產(chǎn)生丟失沒有及時寫回存儲設(shè)備，將造成不可預(yù)知的后果，這使得MOESI協(xié)議無法在大型聯(lián)機事務(wù)處理業(yè)務(wù)中得到廣泛應(yīng)用.

同時，當(dāng)前的大型數(shù)據(jù)庫應(yīng)用中查詢業(yè)務(wù)量占據(jù)主導(dǎo)地位，讀共享操作要遠(yuǎn)多于寫?yīng)氄疾僮?TPC國際性能委員會在線交易測試模型的數(shù)據(jù)顯示，在線交易程序的讀共享和寫?yīng)氄嫉谋嚷室?guī)定為4.3∶1[10]，在實際的應(yīng)用中這一比例甚至達(dá)到10∶1.對于Cache一致性協(xié)議的性能而言，提高緩存數(shù)據(jù)之間的讀共享效率顯得尤為重要.因此，結(jié)合大型數(shù)據(jù)庫應(yīng)用的特點，針對傳統(tǒng)一致性協(xié)議在多級一致性域系統(tǒng)中應(yīng)用存在的問題，本文提出了一種基于共享轉(zhuǎn)發(fā)態(tài)的多級緩存一致性協(xié)議MESI-SF.該協(xié)議創(chuàng)建了一個共享轉(zhuǎn)發(fā)態(tài)Share-F，允許多個一致性域內(nèi)同時存在遠(yuǎn)端數(shù)據(jù)副本的可讀可轉(zhuǎn)發(fā)狀態(tài)，從而能夠為同一域內(nèi)同地址的讀請求直接提供共享數(shù)據(jù)，有效減少了跨域操作，提升系統(tǒng)性能.

1 研究背景與動機

CC-NUMA系統(tǒng)是一種典型的分布式共享內(nèi)存多處理器系統(tǒng).具有兩級Cache一致性域的CC-NUMA系統(tǒng)的一般結(jié)構(gòu)如圖1所示.

在圖1中，系統(tǒng)的n個結(jié)點通過域間網(wǎng)絡(luò)互連，其中每個結(jié)點內(nèi)的處理器和一致性協(xié)同芯片構(gòu)成了結(jié)點內(nèi)Cache一致性域，而結(jié)點間通過一致性協(xié)同芯片互連構(gòu)成了結(jié)點間Cache一致性域.

Fig. 1 The structure of multiprocessor systems with multiple clumps(each clump contains two CPUs)圖1 多結(jié)點多處理器系統(tǒng)結(jié)構(gòu)示意圖(每結(jié)點含2個CPU)

多級Cache一致性域系統(tǒng)通常采用多級Cache一致性協(xié)議.MESI協(xié)議[4]是一種被廣泛采用的Cache一致性協(xié)議，它定義了4種數(shù)據(jù)狀態(tài)，包括：

1) M(modified)態(tài).M態(tài)為修改態(tài)，表明該緩存數(shù)據(jù)被修改，與內(nèi)存中的數(shù)據(jù)內(nèi)容不一致，為整個系統(tǒng)的唯一最新副本.

2) E(exclusive)態(tài).E態(tài)為獨占態(tài)，表明當(dāng)前副本為該緩存數(shù)據(jù)在系統(tǒng)中的唯一副本，并且未被修改，與內(nèi)存中的數(shù)據(jù)內(nèi)容一致.

3) S(shared)態(tài).S態(tài)為共享態(tài)，表明該數(shù)據(jù)在一個或多個處理器中有副本，而且副本數(shù)據(jù)未被修改，與內(nèi)存中的數(shù)據(jù)內(nèi)容一致.

4) I(invalid)態(tài).I態(tài)為無效態(tài)，表明CPU中該緩存數(shù)據(jù)已經(jīng)失效，對其緩存行可直接覆蓋替換而不需要執(zhí)行緩存一致性操作.

在MESI協(xié)議中，當(dāng)有處理器請求讀共享數(shù)據(jù)時，需要通過向數(shù)據(jù)所在的內(nèi)存發(fā)出請求從而才能得到該共享數(shù)據(jù).Intel在MESI協(xié)議的基礎(chǔ)上引入了F轉(zhuǎn)發(fā)態(tài)，提出了MESIF協(xié)議[5].F態(tài)表明該緩存數(shù)據(jù)在某一處理器中處于具有轉(zhuǎn)發(fā)功能的共享狀態(tài)，并且在其他處理器中可能具有一個或多個相同的但不具備轉(zhuǎn)發(fā)功能的S態(tài)數(shù)據(jù)副本.當(dāng)其他CPU請求共享該數(shù)據(jù)時，需向具有F狀態(tài)的數(shù)據(jù)副本發(fā)出請求，這一定程度上降低了共享延遲，提高了系統(tǒng)效率.AMD公司在MESI協(xié)議的基礎(chǔ)上引入所有態(tài)(O態(tài))，提出了MOESI協(xié)議[6].當(dāng)其他處理器請求讀共享數(shù)據(jù)時，處于O態(tài)的緩存數(shù)據(jù)負(fù)責(zé)提供數(shù)據(jù)，這點與MESIF中的F態(tài)作用類似.處于O態(tài)的緩存數(shù)據(jù)可能與存儲器中對應(yīng)的數(shù)據(jù)不一致，即存儲器中的數(shù)據(jù)可能不是最新的，這點與MESIF中的F態(tài)不同.

在具有多級Cache一致性域的CC-NUMA系統(tǒng)中，上述協(xié)議中共享態(tài)數(shù)據(jù)的轉(zhuǎn)發(fā)可能需要跨結(jié)點訪問完成.這里以MESI協(xié)議為例進(jìn)行說明，結(jié)合圖1進(jìn)行說明.假設(shè)結(jié)點1中CPU2具有對應(yīng)地址為addr的S態(tài)緩存數(shù)據(jù)，addr的內(nèi)存地址位于結(jié)點2的MEM1中.此時結(jié)點1中的CPU1發(fā)起了讀共享該數(shù)據(jù)的請求.圖2(a)給出了這種情況下的數(shù)據(jù)請求流程圖.可以看出，由于結(jié)點1中CPU2的共享態(tài)緩存數(shù)據(jù)無法進(jìn)行轉(zhuǎn)發(fā)，因而結(jié)點1的CPU1需要跨結(jié)點通過CC1,CC2才能最終請求得到數(shù)據(jù).在這種情形下，由于需要跨結(jié)點訪問，這一過程具有較高延遲.觀察到結(jié)點1中CPU2的緩存數(shù)據(jù)已處于S共享狀態(tài)，如圖2(b)所示，當(dāng)結(jié)點1中的CPU1發(fā)起同地址的數(shù)據(jù)共享讀請求時，如果同結(jié)點內(nèi)的CPU2能夠進(jìn)行該數(shù)據(jù)的共享轉(zhuǎn)發(fā)，那么共享請求將在結(jié)點內(nèi)直接完成，而不必跨結(jié)點訪問結(jié)點2，這樣將提高數(shù)據(jù)的共享效率.

Fig. 2 Diagrams of data request process for visiting remote clumps圖2 訪問遠(yuǎn)端結(jié)點數(shù)據(jù)請求流程圖

上面所述問題在MESIF,MOESI協(xié)議中同樣存在.因而，基于上述研究動機，本文針對現(xiàn)有協(xié)議在多級Cache一致性域CC-NUMA中存在的跨結(jié)點訪問效率較低的不足提出了一種基于共享轉(zhuǎn)發(fā)態(tài)的多級緩存一致性協(xié)議，試圖緩解上述存在問題，以期減少跨結(jié)點訪問頻度，降低數(shù)據(jù)訪問延遲，提升系統(tǒng)性能.

2 一種基于共享轉(zhuǎn)發(fā)態(tài)的多級緩存一致性協(xié)議

本文提出的多級緩存一致性協(xié)議MESI-SF，在MESI協(xié)議的基礎(chǔ)上，引入了共享轉(zhuǎn)發(fā)態(tài)Share-F.Share-F的基本思想是通過在兩級Cache一致性域或多級Cache一致性域CC-NUMA系統(tǒng)中的局部域(如結(jié)點內(nèi)Cache一致性域)對同地址S狀態(tài)的緩存數(shù)據(jù)在每個Cache一致性域內(nèi)均構(gòu)造一個Share-F狀態(tài)，Share-F狀態(tài)的緩存數(shù)據(jù)可對同一域內(nèi)的讀請求直接提供共享數(shù)據(jù).本方法在不違反全局Cache一致性協(xié)議規(guī)則基礎(chǔ)上可降低處理器跨結(jié)點訪存頻度和開銷，提升CC-NUMA系統(tǒng)性能.

不失一般性，在本文的后續(xù)討論中，將以兩級Cache一致性域為例進(jìn)行說明.多級Cache一致性域可以看作是兩級Cache一致性域的擴展.本文提出的方法適用于多級Cache一致性域.

MESI-SF協(xié)議包含了MESI協(xié)議中的4種狀態(tài)，這4種狀態(tài)的定義和相互之間的轉(zhuǎn)換與MESI協(xié)議相同.下面重點對本文提出的Share-F狀態(tài)進(jìn)行介紹.Share-F狀態(tài)適用于結(jié)點內(nèi)Cache一致性域處于S狀態(tài)的緩存數(shù)據(jù).具體地，在同一個域內(nèi)，當(dāng)存在同地址狀態(tài)為S的緩存數(shù)據(jù)時，可為其中的緩存數(shù)據(jù)在域內(nèi)構(gòu)造唯一一個Share-F狀態(tài).Share-F狀態(tài)數(shù)據(jù)的意義是在結(jié)點內(nèi)Cache一致性域中Share-F狀態(tài)緩存數(shù)據(jù)是具有轉(zhuǎn)發(fā)能力的F態(tài)數(shù)據(jù)副本，而在結(jié)點間Cache一致性域中Share-F狀態(tài)緩存數(shù)據(jù)是不具備轉(zhuǎn)發(fā)能力的S態(tài)數(shù)據(jù)副本.

從以上描述可知，當(dāng)處理結(jié)點間Cache一致性事務(wù)時，Share-F態(tài)緩存數(shù)據(jù)具有與S態(tài)數(shù)據(jù)相同的邏輯行為；當(dāng)處理結(jié)點內(nèi)Cache一致性事務(wù)時，Share-F態(tài)緩存數(shù)據(jù)具有與F態(tài)數(shù)據(jù)相同的邏輯行為.下面將分別從讀請求和寫請求2方面對具有Share-F狀態(tài)的MESI-SF協(xié)議進(jìn)行描述，最后通過示例分別對MESI-SF,MESI,MESIF的應(yīng)用差異進(jìn)行詳細(xì)說明.

2.1 讀共享請求

圖3給出了MESI-SF協(xié)議在Cache一致性域內(nèi)處理器讀請求情況下的狀態(tài)轉(zhuǎn)換圖.圖3中SF表示Share-F狀態(tài).

Fig. 3 Transition diagram for read request圖3 讀請求下的狀態(tài)轉(zhuǎn)換圖

結(jié)合圖3，當(dāng)結(jié)點內(nèi)具有I狀態(tài)緩存數(shù)據(jù)的處理器CPU1發(fā)起對同地址緩存數(shù)據(jù)的讀請求時，根據(jù)當(dāng)前系統(tǒng)內(nèi)其他處理器的狀態(tài)，CPU1完成讀請求事務(wù)后該緩存數(shù)據(jù)的狀態(tài)有3種情況：

1) 如果請求的數(shù)據(jù)在當(dāng)前其他所有處理器中不存在副本，需要從內(nèi)存中讀取數(shù)據(jù)，則緩存數(shù)據(jù)在CPU1中將為E狀態(tài)；

2) 如果請求的數(shù)據(jù)由結(jié)點間其他任一處理器響應(yīng)發(fā)送，則緩存數(shù)據(jù)在CPU1中將為SF狀態(tài)；

3) 如果同結(jié)點內(nèi)存在同地址緩存數(shù)據(jù)狀態(tài)為SF的處理器時，緩存數(shù)據(jù)由該處理器響應(yīng)發(fā)送，請求完成后，緩存數(shù)據(jù)在CPU1中將為SF狀態(tài).

當(dāng)CPU1中的緩存數(shù)據(jù)處于ME其中之一的狀態(tài)時，處理器CPU2發(fā)起對同地址數(shù)據(jù)讀請求時，根據(jù)發(fā)起讀請求時CPU2處理器的狀態(tài)，讀請求事務(wù)完成后CPU1中緩存數(shù)據(jù)的狀態(tài)有2種情況：

1) 如果CPU2,CPU1位于同一結(jié)點內(nèi)，則緩存數(shù)據(jù)將變?yōu)镾狀態(tài)；

2) 如果CPU2,CPU1位于不同的結(jié)點內(nèi)，則緩存數(shù)據(jù)將變?yōu)镾F狀態(tài).

當(dāng)CPU1中的緩存數(shù)據(jù)處于SF狀態(tài)時，同結(jié)點內(nèi)的其他處理器發(fā)起了對同地址數(shù)據(jù)的讀請求時，讀請求事務(wù)完成后CPU1中緩存數(shù)據(jù)將變?yōu)镾狀態(tài).

圖3中其他狀態(tài)之間的相互轉(zhuǎn)換與MESI協(xié)議相同，這里不再重復(fù)敘述.

由上面的分析可以看出，引入SF狀態(tài)后，當(dāng)結(jié)點內(nèi)存在SF態(tài)緩存數(shù)據(jù)時，結(jié)點內(nèi)其他處理器請求對同地址數(shù)據(jù)的讀共享時，都將由SF態(tài)緩存數(shù)據(jù)直接響應(yīng)提供數(shù)據(jù).這種情況下請求事務(wù)直接在結(jié)點內(nèi)響應(yīng)并完成，跨結(jié)點訪問將減少，從而降低數(shù)據(jù)訪問延遲.

2.2 寫?yīng)氄颊埱?/h3>

圖4給出了MESI-SF協(xié)議在Cache一致性域內(nèi)處理器寫請求情況下的部分狀態(tài)轉(zhuǎn)換圖.在寫請求情況下的其他狀態(tài)轉(zhuǎn)換圖可參考MESI協(xié)議[4].

Fig. 4 Transition diagram for write request圖4 寫請求下的狀態(tài)轉(zhuǎn)換圖

結(jié)合圖4，當(dāng)結(jié)點內(nèi)的處理器CPU1中的緩存數(shù)據(jù)處于SF狀態(tài)時，當(dāng)有處理器CPU2發(fā)起同地址數(shù)據(jù)寫請求時，根據(jù)發(fā)起讀請求時CPU2處理器所處位置，寫請求事務(wù)完成后CPU1中緩存數(shù)據(jù)的狀態(tài)有2種情況：

1) 如果CPU2,CPU1為同一處理器，即CPU1發(fā)起了寫請求，此時產(chǎn)生了寫缺失，那么最終緩存數(shù)據(jù)將變?yōu)镸狀態(tài)；

2) 如果CPU2,CPU1不是同一處理器，無論CPU2,CPU1位于同一結(jié)點內(nèi)還是結(jié)點間，緩存數(shù)據(jù)最終都將變?yōu)镮狀態(tài).

可以看出，Share-F態(tài)在寫請求下的事務(wù)處理邏輯與S態(tài)相同.

2.3 示例說明

本節(jié)通過示例分別說明MESI-SF,MESI,MESIF在數(shù)據(jù)共享方面的差異.

2.3.1 MESI-SF與MESI對比

結(jié)合圖1，假設(shè)在當(dāng)前狀態(tài)下，結(jié)點1的CPU1中addr地址緩存數(shù)據(jù)的狀態(tài)處于I態(tài)，同時該緩存數(shù)據(jù)的內(nèi)存地址位于結(jié)點2的MEM1中，CC2中記錄該緩存數(shù)據(jù)為I態(tài).圖5和圖6分別給出了MESI,MESI-SF的數(shù)據(jù)獲取過程，其中圖5(a)、圖6(a)都是結(jié)點1的CPU1請求讀同地址緩存數(shù)據(jù)，圖5(b)、圖6(b)都是結(jié)點1的CPU2請求讀該緩存數(shù)據(jù).

Fig. 5 Data retrieval under the MESI protocol圖5 MESI協(xié)議下數(shù)據(jù)獲取過程

Fig. 6 Data retrieval under the MESI-SF protocol圖6 MESI-SF協(xié)議下數(shù)據(jù)獲取過程

結(jié)合圖5(a)，CC1結(jié)點內(nèi)的處理器CPU1對遠(yuǎn)端CC2結(jié)點內(nèi)處理器CPU1處的緩存數(shù)據(jù)地址addr進(jìn)行讀共享訪問.在MESI協(xié)議下其訪問過程如下:

Step1. 處理器發(fā)出訪問請求操作在本地緩存未命中，向CC1發(fā)出訪問addr地址的內(nèi)存數(shù)據(jù)請求.

Step2.CC1經(jīng)過域間互連網(wǎng)絡(luò)向遠(yuǎn)端CC2結(jié)點發(fā)送訪問請求消息.

Step3.CC2查詢共享信息后發(fā)現(xiàn)對應(yīng)addr地址的數(shù)據(jù)副本在結(jié)點內(nèi)處于I態(tài)后，則向CPU1轉(zhuǎn)發(fā)數(shù)據(jù)請求.

Step4.CPU1接收到數(shù)據(jù)請由求后，從內(nèi)存MEM1讀取數(shù)據(jù)，并將數(shù)據(jù)返回給CC2.

Step5.CC2收到數(shù)據(jù)后，將CPU1對應(yīng)addr地址的數(shù)據(jù)副本狀態(tài)由I態(tài)改為S態(tài)，同時將數(shù)據(jù)信息轉(zhuǎn)發(fā)給CC1.

Step6.CC1接收到CC2轉(zhuǎn)發(fā)的數(shù)據(jù)信息后，將該數(shù)據(jù)信息發(fā)送給CPU1，同時將對應(yīng)addr地址的數(shù)據(jù)副本狀態(tài)由I改為S態(tài).

完成圖5(a)中的事務(wù)后，緊接著，圖5(b)中CC1結(jié)點內(nèi)的另一處理器CPU2同樣要訪問遠(yuǎn)端CC2結(jié)點內(nèi)處理器CPU1中addr地址的緩存數(shù)據(jù)，其訪問過程與圖5(a)類似.可以看到，雖然此刻同一結(jié)點內(nèi)的CPU1具有S態(tài)的共享數(shù)據(jù)，但CPU2仍然需要跨結(jié)點并從內(nèi)存中讀數(shù)來獲取共享數(shù)據(jù).

接著，圖6(b)中，CC1結(jié)點內(nèi)的處理器CPU2同樣對addr地址的緩存數(shù)據(jù)進(jìn)行訪問.其訪問過程如下:

Step1. 處理器發(fā)出訪問請求操作在本地緩存未命中，向CC1發(fā)出訪問addr地址的內(nèi)存數(shù)據(jù)請求.

Step2.CC1查詢共享信息后，發(fā)現(xiàn)CPU1中對應(yīng)addr地址的緩存數(shù)據(jù)狀態(tài)為Share-F態(tài)后，向CPU1轉(zhuǎn)發(fā)數(shù)據(jù)請求信息.

Step3.CPU1接收到數(shù)據(jù)請求后，向CPU2發(fā)送對應(yīng)addr地址的緩存數(shù)據(jù).

圖6(b)中，由于CPU1中該緩存數(shù)據(jù)狀態(tài)為Share-F，因而CPU2請求的數(shù)據(jù)將由CPU1直接提供.

通過對比圖5(b)和圖6(b)，容易看出在相同場景下，當(dāng)結(jié)點內(nèi)有共享態(tài)數(shù)據(jù)存在時，結(jié)點內(nèi)其他處理器發(fā)起讀共享該數(shù)據(jù)，在MESI協(xié)議下需要跨結(jié)點訪問內(nèi)存才能獲取到數(shù)據(jù)，具有較大的延遲;而在MESI-SF協(xié)議下共享數(shù)據(jù)獲取在同一結(jié)點內(nèi)完成，無需跨結(jié)點訪問內(nèi)存，具有較小的延遲.

2.3.2 MESI-SF與MESIF對比

Fig. 7 Data retrieval for two protocols圖7 2種協(xié)議數(shù)據(jù)獲取過程

本節(jié)通過示例詳細(xì)說明MESI-SF與MESIF協(xié)議在數(shù)據(jù)共享方面的差異.結(jié)合圖1，假設(shè)結(jié)點1中的CPU1和結(jié)點2中的CPU1先后對位于結(jié)點2中的同地址數(shù)據(jù)進(jìn)行讀訪問.當(dāng)2次讀訪問完成后，在MESI-SF協(xié)議下，結(jié)點1中存在SF態(tài)的該緩存數(shù)據(jù)；而在MESIF協(xié)議下，結(jié)點1中存在S態(tài)的該緩存數(shù)據(jù)，結(jié)點2中存在F態(tài)的該緩存數(shù)據(jù).當(dāng)結(jié)點1中的CPU2接著發(fā)起對該緩存數(shù)據(jù)的讀訪問時，圖7列出了2種協(xié)議在這種狀態(tài)下的數(shù)據(jù)獲取過程.通過對比圖7(a)和圖7(b)，不難發(fā)現(xiàn)，在相同場景下，MESI-SF協(xié)議只需在結(jié)點內(nèi)完成數(shù)據(jù)獲取過程，而MESIF需要跨結(jié)點訪問F態(tài)數(shù)據(jù)才能完成數(shù)據(jù)獲取過程，產(chǎn)生較大訪問延遲.特別地，當(dāng)結(jié)點之間連續(xù)頻繁交替訪問同地址數(shù)據(jù)時，MESIF協(xié)議中的F態(tài)數(shù)據(jù)會頻繁在結(jié)點之間遷移，具有較大的延遲；而MESI-SF在這種情形下，由于結(jié)點內(nèi)在訪問過同地址數(shù)據(jù)后，結(jié)點內(nèi)已存在SF態(tài)數(shù)據(jù)，因而接下來對同地址數(shù)據(jù)的訪問只在結(jié)點內(nèi)完成，具有較小的延遲.

3 性能評估

3.1 實驗平臺

本文在gem5[11]模擬器上實現(xiàn)了MESI,MESIF,MESI-SF協(xié)議，并構(gòu)建了多級Cache一致性域系統(tǒng).在實驗中，gem5的參數(shù)配置如表1所示.為了驗證本文提出方法的有效性，本文采用SPLASH-2測試程序集[12]，它被廣泛地應(yīng)用于驗證Cache一致性協(xié)議的正確性及有效性[13-14].同時，SPLASH-2測試程序集中平均讀寫比達(dá)到了3∶1，其中CHOLESKY的讀寫比甚至達(dá)到了10.4∶1.因而，SPLASH-2程序集表現(xiàn)出來的高讀寫比可以很好地用來模擬大型關(guān)系型數(shù)據(jù)庫中較頻繁的讀共享這一特性.表2列出了測試程序及其數(shù)據(jù)輸入情況.

Table 1 Configuration of gem5表1 gem5模擬器參數(shù)配置

Table 2 Data Input of SPLASH-2 Programs表2 SPLASH-2測試程序及其數(shù)據(jù)輸入

3.2 評估結(jié)果

在實驗評估過程中，我們首先與MESI,MESIF協(xié)議方法分別在2 GHz主頻、8結(jié)點規(guī)模系統(tǒng)下進(jìn)行了實驗比較;接著，我們評估了不同主頻、讀寫比和結(jié)點數(shù)對協(xié)議性能的影響.

3.2.1 指令平均執(zhí)行周期數(shù)(CPI)

圖8給出了MESI,MESIF,MESI-SF協(xié)議在各個程序測試集上的指令平均執(zhí)行周期數(shù)(CPI)比較數(shù)據(jù).圖8的所有實驗數(shù)據(jù)均經(jīng)過相對于MESI協(xié)議方案的歸一化處理.從圖8可以看出，與MESI協(xié)議相比，MESI-SF在所有測試程序上的相對指令執(zhí)行性能都小于1，指令平均執(zhí)行周期數(shù)降低7.5%；與MESIF協(xié)議相比，MESI-SF在所有測試程序上的相對指令執(zhí)行周期數(shù)更小，指令平均執(zhí)行周期數(shù)降低5.95%.這說明了程序在MESI-SF協(xié)議上表現(xiàn)出了更少的平均執(zhí)行時間.圖9進(jìn)一步給出了3個協(xié)議在各個程序測試集上的平均讀缺失延遲比較情況下.通過分別對比相同程序在平均指令執(zhí)行周期數(shù)和平均讀缺失延遲的表現(xiàn)可以看出，與MESI和MESIF協(xié)議相比，采用MESI-SF協(xié)議，在所有CPI出現(xiàn)減少的程序上平均讀缺失延遲也減少了.這是因為相比其他2個協(xié)議，MESI-SF在結(jié)點內(nèi)引入了Share-F狀態(tài)，原先在MESI和MESIF協(xié)議中需要跨結(jié)點訪問的請求，在MESI-SF中可能只需在結(jié)點內(nèi)通過Share-F狀態(tài)的數(shù)據(jù)就能獲取到共享數(shù)據(jù)，這降低了訪問延遲，因而CPI出現(xiàn)了減少.

Fig. 8 Comparison of normalized CPI圖8 歸一化CPI比較

3.2.2 結(jié)點內(nèi)讀缺失率

圖10給出了3個協(xié)議在各個程序測試集上的結(jié)點內(nèi)讀缺失率比較情況.從圖10可以看出，MESI協(xié)議在所有程序測試集上表現(xiàn)出較高的結(jié)點內(nèi)讀缺失率，平均讀缺失率為98.9%；MESIF結(jié)點內(nèi)讀缺失率為86.7%；MESI-SF在所有程序測試集上都表現(xiàn)出了較低的結(jié)點內(nèi)讀缺失率，與MESI和MESIF相比結(jié)點內(nèi)讀缺失率平均降低23%,12.2%.3個協(xié)議在程序集上呈現(xiàn)出了不同的結(jié)點內(nèi)讀缺失率，這是由于當(dāng)結(jié)點內(nèi)有其他處理器請求讀共享內(nèi)存地址位于其他結(jié)點內(nèi)的數(shù)據(jù)時，MESI協(xié)議不管結(jié)點內(nèi)存不存在共享態(tài)數(shù)據(jù)，總是需要跨結(jié)點訪問來獲取數(shù)據(jù)，因而讀缺失率較高；當(dāng)結(jié)點內(nèi)存在同地址F態(tài)可轉(zhuǎn)發(fā)的數(shù)據(jù)時，MEISF協(xié)議對這類讀請求可在結(jié)點內(nèi)由F態(tài)數(shù)據(jù)轉(zhuǎn)發(fā)進(jìn)行共享；MESI-SF協(xié)議當(dāng)結(jié)點內(nèi)存在1個或多個擁有共享態(tài)數(shù)據(jù)的處理器時，共享請求可由其中一個擁有共享轉(zhuǎn)發(fā)態(tài)數(shù)據(jù)的響應(yīng)轉(zhuǎn)發(fā)完成，從而降低了跨結(jié)點訪問的請求.因而從以上分析可以看出，與MESI,MESIF相比，MESI-SF能夠有效地減少跨結(jié)點讀訪問次數(shù)，降低了結(jié)點內(nèi)讀缺失率，從而提升數(shù)據(jù)共享效率.

3.2.3 CPU主頻對性能的影響

本節(jié)研究不同CPU主頻對MESI,MESI-SF性能的影響.圖11列出了不同主頻下的歸一化指令執(zhí)行性能比較數(shù)據(jù).圖11的所有實驗數(shù)據(jù)均經(jīng)過相對于MESI協(xié)議方案在2 GHz主頻下性能的歸一化處理.從圖11可以看出，在相同CPU主頻下，在MESI-SF協(xié)議上運行的程序的歸一化指令執(zhí)行性能總是要高于MESI，也就是說MESI-SF的性能效率總是要優(yōu)于MESI.進(jìn)一步觀察可以看到，MESI-SF的指令執(zhí)行性能曲線總是位于MESI的相應(yīng)曲線上方.因而，當(dāng)2個協(xié)議的運行性能相同時，即擁有相等的指令執(zhí)行性能時，MESI-SF的CPU主頻總是要低于MESI的CPU主頻.這里以2 GHz CPU主頻下的MESI協(xié)議性能為例.MESI-SF達(dá)到同等性能只需要運行在1.82 GHz左右.這說明了基于MESI-SF協(xié)議的系統(tǒng)在1.82 GHz的CPU主頻下達(dá)到了傳統(tǒng)MESI協(xié)議方法在2 GHz主頻的運行性能，提升了系統(tǒng)能效.

Fig. 11 Comparison of instruction execution performance for different frequencies圖11 不同主頻下的指令執(zhí)行性能比較

3.2.4 讀寫比對MESI-SF性能的影響

Fig. 12 Readwrite ratio for different programs圖12 不同程序的讀寫比

MESI-SF針對緩存數(shù)據(jù)的讀請求進(jìn)行了優(yōu)化，本節(jié)進(jìn)一步研究在不同程序的讀寫比對MESI-SF性能的影響.在實驗中，我們收集了各個程序集運行過程中由處理器內(nèi)核發(fā)起的讀請求和寫請求的數(shù)量，并據(jù)此得出讀寫比.圖12列出了不同程序的讀寫比例.結(jié)合圖8可以看出，具有較高讀寫比的程序在MESI-SF協(xié)議下其性能往往有較高程度的提升.如CHOLESKY和BARNES，其讀寫比分別達(dá)到10.4∶1和4.2∶1，性能提升程度在所有程序中是較為顯著的；而讀寫比較低的程序，如FFT,LU,NLU，其性能提升不顯著.結(jié)合圖10，可以看到，雖然RADIX具有較高的讀寫比，但其在MESI-SF協(xié)議下具有較高的結(jié)點內(nèi)讀缺失率，也就是具有較低的結(jié)點內(nèi)讀命中率，在這種情況下有較多的共享數(shù)據(jù)的讀請求仍然需要跨結(jié)點訪問完成，這說明結(jié)點內(nèi)的緩存數(shù)據(jù)由于狀態(tài)發(fā)生變化導(dǎo)致不常擁有Share-F態(tài)，在這種情形下本文提出的優(yōu)化方法性能提升并不顯著.

3.2.5 結(jié)點數(shù)對MESI-SF性能的影響

本節(jié)進(jìn)一步研究不同結(jié)點數(shù)對MESI-SF性能的影響.在實驗過程中統(tǒng)一采用64個處理器，分別研究在4結(jié)點、8結(jié)點和16結(jié)點情形下MESI-SF性能的變化情況.圖13～圖15分別給出了相應(yīng)的實驗對比結(jié)果.

Fig. 13 Impact of the number of clumps on CPI圖13 結(jié)點數(shù)量對CPI的影響

Fig. 14 Impact of the number of clumps on read-miss latency圖14 結(jié)點數(shù)量對程序平均讀缺失延遲的影響

Fig. 15 Impact of the number of clumps on read-miss ratio within clumps圖15 結(jié)點數(shù)量對結(jié)點內(nèi)讀缺失率的影響

結(jié)合圖13和圖14可以看出，隨著結(jié)點數(shù)量的增加，結(jié)點內(nèi)CPU數(shù)量減少，各個程序測試集的平均執(zhí)行周期數(shù)均出現(xiàn)了不同程度的增加，平均讀缺失延遲相應(yīng)呈現(xiàn)增加的趨勢.以FFT程序為例說明.當(dāng)結(jié)點數(shù)量為4個，歸一化CPI為1，平均延遲為4.89 cycle；當(dāng)結(jié)點數(shù)量增加到16個，歸一化CPI增加到1.43，平均延遲增加到7.21 cycle.這是因為，隨著結(jié)點數(shù)量的增加，結(jié)點內(nèi)CPU數(shù)量減少，那么數(shù)據(jù)被結(jié)點內(nèi)CPU訪問的概率就變小，在此基礎(chǔ)上，結(jié)點內(nèi)存在Share-F態(tài)數(shù)據(jù)的概率就減小，從而導(dǎo)致跨結(jié)點訪問增加，因而CPI和平均延遲均呈現(xiàn)出了增加趨勢.

另外，從圖15可以看出，隨著結(jié)點數(shù)量的增加，各個程序的結(jié)點內(nèi)讀缺失率呈現(xiàn)出增加的趨勢.這也解釋了上述實驗中CPI隨著結(jié)點數(shù)量的增加而增大的現(xiàn)象.

4 討 論

本節(jié)對MESI-SF協(xié)議可能存在的問題進(jìn)行討論.

在MESI-SF協(xié)議中，同一結(jié)點內(nèi)存在Share-F態(tài)的緩存數(shù)據(jù)時，其他處理器請求該緩存數(shù)據(jù)時并不一定總是會由該Share-F態(tài)的緩存數(shù)據(jù)提供轉(zhuǎn)發(fā)數(shù)據(jù).這是因為Share-F態(tài)會因替換(replacement)操作轉(zhuǎn)換成I態(tài)，此時由于靜默降級[15](silent replacement)策略而不通知一致性協(xié)同芯片.在這種情況下，同結(jié)點內(nèi)讀請求仍需要跨結(jié)點訪問來完成.結(jié)合圖16進(jìn)行說明.結(jié)點1的CPU1具有對應(yīng)地址為addr2的Share-F態(tài)緩存數(shù)據(jù)，CPU2對應(yīng)addr2的緩存數(shù)據(jù)為I態(tài).同時該緩存數(shù)據(jù)的內(nèi)存地址addr2位于結(jié)點2的MEM2中.由于結(jié)點1的CPU1中addr2地址緩存數(shù)據(jù)產(chǎn)生了替換(replacement)操作，其狀態(tài)變?yōu)镮態(tài).而此時CC1處仍然記錄CPU1具有Share-F態(tài).在這種情況下，結(jié)點1的CPU2對地址addr2處的數(shù)據(jù)發(fā)起了讀請求訪問，此時數(shù)據(jù)請求需要通過結(jié)點2的CPU2來完成，當(dāng)訪問請求事務(wù)完成后，CPU2中addr2將具有Share-F態(tài).具體流程如下：

Step1.CPU2發(fā)出訪問請求操作在本地緩存未命中，向CC1發(fā)出訪問addr2地址的內(nèi)存數(shù)據(jù)請求.

Step2.CC1查詢共享信息后發(fā)現(xiàn)對應(yīng)addr2地址的數(shù)據(jù)副本在本結(jié)點內(nèi)CPU1處為Share-F態(tài)，向CPU1轉(zhuǎn)發(fā)數(shù)據(jù)請求.

Fig. 16 Data retrieval under the condition of invalid states圖16 無效狀態(tài)下的數(shù)據(jù)獲取過程

Step3.CPU1接收到數(shù)據(jù)請求后，發(fā)現(xiàn)對應(yīng)addr2地址的緩存數(shù)據(jù)狀態(tài)為I態(tài)，向CC1發(fā)送請求無效消息.

Step4.CC1收到請求無效消息后，通過域間互連網(wǎng)絡(luò)向CC2發(fā)送數(shù)據(jù)請求消息.

Step5.CC2收到請求后發(fā)現(xiàn)緩存數(shù)據(jù)處于共享態(tài)，向CPU2轉(zhuǎn)發(fā)數(shù)據(jù)請求.

Step6.CPU2接收到數(shù)據(jù)請求后，從內(nèi)存中讀取數(shù)據(jù)，并將數(shù)據(jù)返回給CC2.

Step7.CC2收到數(shù)據(jù)后，將數(shù)據(jù)信息轉(zhuǎn)發(fā)給CC1.

Step8.CC1接收到CC2轉(zhuǎn)發(fā)的數(shù)據(jù)信息后，將該數(shù)據(jù)信息發(fā)送給CPU2，同時將對應(yīng)addr2地址的數(shù)據(jù)副本狀態(tài)由I改為Share-F態(tài).

為了避免此種情形的發(fā)生，一種可行的做法是當(dāng)結(jié)點內(nèi)的Share-F態(tài)靜默降級為I態(tài)時，向結(jié)點一致性協(xié)同芯片發(fā)送無效(invalid)信息,然而這可能會加劇網(wǎng)絡(luò)擁塞.我們將在以后的工作中進(jìn)一步研究這種方法對性能的影響.

在目錄存儲開銷方面，與MESI,MESIF相比，MESI-SF引入了新的狀態(tài)，由于在目錄項的狀態(tài)位上SF依然能夠用來表示結(jié)點內(nèi)有共享數(shù)據(jù)存在，因而狀態(tài)位仍然可以采用2位編碼.但是在目錄項中為了指定哪一個CPU中數(shù)據(jù)處于SF狀態(tài)，需要增加lbn位來標(biāo)記(其中n為結(jié)點內(nèi)CPU數(shù)量)，這在一定程度上會增加目錄的存儲開銷.我們將在以后的工作中研究降低目錄存儲開銷的方法.

5 結(jié)束語

在CC-NUMA架構(gòu)系統(tǒng)中，緩存一致性維護開銷是影響系統(tǒng)性能有效擴展的關(guān)鍵因素.為了減少緩存一致性維護開銷，CC-NUMA架構(gòu)通常采用多級緩存一致性域.傳統(tǒng)的MESI,MOESI,MESIF協(xié)議主要是針對單級一致性域優(yōu)化設(shè)計，在多級緩存一致性域場景下存在著跨域操作頻度高、執(zhí)行效率低等缺點.針對該類一致性協(xié)議在多級一致性域系統(tǒng)中應(yīng)用存在的問題，結(jié)合大型數(shù)據(jù)庫應(yīng)用中查詢業(yè)務(wù)量占據(jù)主導(dǎo)地位的特點，本文提出了一種基于共享轉(zhuǎn)發(fā)態(tài)的多級緩存一致性協(xié)議MESI-SF.該協(xié)議創(chuàng)建了一個共享轉(zhuǎn)發(fā)態(tài)Share-F，允許多個一致性域內(nèi)同時存在遠(yuǎn)端數(shù)據(jù)副本的可讀可轉(zhuǎn)發(fā)狀態(tài)，從而能夠為同一域內(nèi)同地址的讀請求直接提供共享數(shù)據(jù)，有效減少了跨域操作，提升系統(tǒng)性能.SPLASH-2程序集模擬結(jié)果表明，對于兩級Cache一致性域系統(tǒng)，相比MESI協(xié)議，MESI-SF能夠減少23%跨結(jié)點訪問次數(shù)，指令平均執(zhí)行周期數(shù)降低7.5%；相比MESIF協(xié)議，MESI-SF能夠減少12.2%跨結(jié)點訪問次數(shù)，指令平均執(zhí)行周期數(shù)降低5.95%.進(jìn)一步降頻實驗表明，基于MESI-SF協(xié)議的系統(tǒng)在1.82 GHz的主頻下達(dá)到了傳統(tǒng)MESI協(xié)議方法在2 GHz主頻的運行性能，提升了系統(tǒng)能效.