并行處理與體系結(jié)構(gòu)課件

哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院1并行處理與體系結(jié)構(gòu)哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院2第5章分布式存儲器及其時延容忍

1層次存儲器技術(shù)

2高緩一致性協(xié)議

3共享存儲器的一致性

4分布式高速緩/主存體系結(jié)構(gòu)哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院3一.問題的提出哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院41.一種解決方案：哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院52.兩種實用的方法：寫直達(dá)(Write-through)法：每次寫入Cache時也把相同的數(shù)寫入主存儲器。特點：這種管理寫操作的方法雖然簡化了I／O處理器的訪問。它增加了中央處理器與主存儲器之間的信息流量，又降低I／O性能。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院6寫回(Write-back)法寫操作期間中央處理器修改了Cache數(shù)據(jù)之后，并不馬上修改主存儲器的相應(yīng)單元；在Cache中被修改的行從Cache中淘汰時，才把它寫入主存儲器，這里的“寫回”是指寫回主存儲器。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院7二、多處理機環(huán)境下的高速緩存一致性問題1.多個不同的處理器對同一高速緩存行的寫操作按所有處理器所見到的存儲器事件的順序而串行化寫。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院8可能引起高速緩存不一致的原因有以下3種：(1)不同處理器對各自緩存的同一高速緩存行的不同拷貝的異步寫操作；(2)多處理器系統(tǒng)中的進(jìn)程遷移，而又不互相通報；(3)繞過高速緩存拷貝擁有者的I/O操作。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院92.例題

由共享數(shù)據(jù)寫操作引起的高速緩存一致在寫操作前后高速緩存狀態(tài)的變化由下圖所示。假設(shè)在更新前兩個處理器各自緩存的數(shù)據(jù)(標(biāo)為x)與共享主存中的相應(yīng)數(shù)據(jù)是一致的。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院10哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院113.例題

由進(jìn)程遷移引起的高速緩存不一致

假設(shè)處理器P1的高速緩存中有主存中數(shù)據(jù)x的拷貝，當(dāng)某進(jìn)程從P1，遷移至P2后將主存數(shù)據(jù)x改寫為y。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院12哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院134.例題：由繞過高速緩存的I/O操作引起的不一致

下圖表明將I/O作為WT高速緩存下的輸入設(shè)備和WB高速緩存下的輸出設(shè)備時，由于繞過高速緩存的輸入／輸出操作所引起的不一致。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院14哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院15哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院16結(jié)論：WT和WK不滿足實際的需要。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院17三、監(jiān)聽一致性協(xié)議當(dāng)各處理器的高速緩存都連接到公共總線時，有兩類協(xié)議：寫--無效(write-invalidate)協(xié)議；寫--更新(write-update)協(xié)議。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院18監(jiān)聽一致性協(xié)議體現(xiàn)在：監(jiān)聽協(xié)議需要由總線或環(huán)提供的廣播機制;不斷地監(jiān)聽總線上處理器和存儲器模塊間的高速緩存操作事件哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院19哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院201.寫—無效協(xié)議

在下圖中，可以看到對主存數(shù)據(jù)x存在3份高速緩存中的拷貝。當(dāng)某一處理器想要進(jìn)行寫操作時，首先它必須獲得對x訪問的獨占權(quán)，然后更新數(shù)據(jù)為x’，并使其他處理器高速緩存中的相應(yīng)數(shù)據(jù)拷貝失效。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院21哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院22使用WB高速緩存時，主存相應(yīng)數(shù)據(jù)行也被設(shè)置為無效。若使用WT高速緩存，該主存數(shù)據(jù)行將會立即更新為x’。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院232.寫--更新協(xié)議當(dāng)某一處理器對高速緩存數(shù)據(jù)x作寫操作時，它必須通過廣播x’的方法來更新x在所有處理器高速緩存中的拷貝。當(dāng)其它的處理器要訪問修改過的x’時，會在本地高速緩存命中。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院24哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院25寫更新協(xié)議具有明顯的缺點？大多數(shù)多處理機設(shè)計者選擇使用WB高速緩存的寫無效一致性協(xié)議哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院263.基于更新和基于作廢協(xié)議的對比問題：對一個緩存中某個塊的寫操作應(yīng)該使用更新操作，還是無效操作？基于更新和基于無效協(xié)議的相對性能在很大程度上取決于應(yīng)用程序負(fù)載表現(xiàn)出來的共享模式，以及各種操作的代價；如果處理器采用更新，并可能希望要在將來看到新的值，更新就會比無效有更好的性能擁有老數(shù)據(jù)的處理器再不用此數(shù)據(jù)了，更新就不必要無效操作清除舊的拷貝，消除了明顯的共享哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院27結(jié)論：更新協(xié)議的流量相當(dāng)大由于同一個處理器對相同的塊發(fā)出的多個寫操作都要產(chǎn)生更新。而對無效協(xié)議來說，第一個寫可能引起作廢，但可以簡單地存放在本地塊中，在回寫或者向別的緩存提供數(shù)據(jù)時以一次總線事務(wù)傳送。如果采用復(fù)雜的更新方案會延遲更新的時機。帶寬要求支持更新所帶來緩存塊變大的趨勢，以及多道順序程序負(fù)載的收集現(xiàn)象，使得基于更新的協(xié)議用得越來越少。更新對多處理器系統(tǒng)設(shè)計者的吸引力越來越低哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院28四、偵聽的狀態(tài)轉(zhuǎn)換圖表示狀態(tài)轉(zhuǎn)換圖實際上是一個有限狀態(tài)機，它決定了高速緩存塊在它的狀態(tài)之間是如何轉(zhuǎn)換的與每個高速緩存塊相關(guān)的狀態(tài)轉(zhuǎn)換圖。對于每一個高速緩存塊，除了標(biāo)記(Tag)和數(shù)據(jù)外，還有一個與它相關(guān)的狀態(tài)。在多處理機系統(tǒng)中，一個內(nèi)存塊在每個處理器的高速緩存中都有一個狀態(tài)，所有的這些狀態(tài)都按照狀態(tài)轉(zhuǎn)換圖來轉(zhuǎn)換。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院29一般來說，在偵聽高速緩存一致性協(xié)議中，每個高速緩存控制器接收兩方面輸入：處理器發(fā)出的內(nèi)存請求總線上偵聽到的事務(wù)作為對這些輸入的響應(yīng)，高速緩存控制器可能要根據(jù)相應(yīng)塊的當(dāng)前狀態(tài)及狀態(tài)轉(zhuǎn)換圖來更新該塊的狀態(tài)，并且也可能要執(zhí)行一些動作。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院30偵聽協(xié)議實際上是一組互相協(xié)作的有限狀態(tài)機所表示的分布式算法，它由三部分組成：①狀態(tài)集合：一個與本地高速緩存中內(nèi)存塊相關(guān)聯(lián)的狀態(tài)集合；②狀態(tài)轉(zhuǎn)換圖：以當(dāng)前狀態(tài)和處理器請求或觀察到的總線事務(wù)作為輸入，輸出該塊的下一個狀態(tài)；③動作：與每個狀態(tài)轉(zhuǎn)換相關(guān)的實際動作，這是由總線、高速緩存和處理器的具體設(shè)計來決定的。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院31動作：一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)換由一個帶箭頭的弧線表示，弧線由記號A／B來標(biāo)記。A／B表示高速緩存控制器觀察到事件A發(fā)生了，或者說由于事件A導(dǎo)致了該轉(zhuǎn)換的發(fā)生，除了發(fā)生狀態(tài)轉(zhuǎn)換外，還要產(chǎn)生一個動作B哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院32對同一個塊的不同狀態(tài)機不是獨立操作的，而是通過總線事務(wù)來相互協(xié)調(diào)的。下圖描述了一個簡單的使無效協(xié)議的狀態(tài)轉(zhuǎn)換圖，該協(xié)議采用了寫直達(dá)且寫不分配的高速緩存。其中，每個高速緩存塊有無效I和有效V兩個狀態(tài)。對于不在高速緩存中的塊，可看做處于無效狀態(tài)。每個轉(zhuǎn)換由一個輸入和輸出來表示。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院33哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院34輸入表示引發(fā)該轉(zhuǎn)換的條件，輸出表示該轉(zhuǎn)換產(chǎn)生的總線事務(wù)當(dāng)控制器看到一個處理器發(fā)出的讀請求在高速緩存中缺失時，發(fā)出一個總線讀(BusRd)事務(wù)，并在總線事務(wù)完成時，將該塊狀態(tài)變?yōu)橛行顟B(tài)當(dāng)控制器看到處理器發(fā)出寫請求時，產(chǎn)生一個總線寫(BusWr)事務(wù)來更新主存，但不改變塊狀態(tài)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院35這個狀態(tài)轉(zhuǎn)換圖與單處理機情況下的主要不同點是：當(dāng)高速緩存控制器在總線上偵聽到一個總線寫事務(wù)，并且在本地高速緩存中有該事務(wù)請求的內(nèi)存塊的拷貝時，就將該內(nèi)存塊在本地高速緩存中的拷貝狀態(tài)置為無效狀態(tài)所有的高速緩存控制器相互合作來保證在任意時刻只能有一個處理器對一個數(shù)據(jù)塊進(jìn)行寫操作，但同時可以有多個處理器進(jìn)行讀操作哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院36分析該協(xié)議保證高速緩存一致性按照高速緩存一致性的定義總線上同時只能有一個事務(wù)，處理器必須等到前一個總線事務(wù)完成后才發(fā)出下一個內(nèi)存請求。在寫直達(dá)策略中所有的寫操作都出現(xiàn)在總線上，但由于同時只能有一個總線事務(wù)出現(xiàn)在總線上，所以在任意執(zhí)行中所有對同一個位置的寫操作都按照它們出現(xiàn)在總線上的次序——總線序(BusOrder)被全局串行化了。使無效也按總線序被全局串行化了，由于所有的偵聽高速緩存控制器在總線事務(wù)中都執(zhí)行了使無效動作。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院37讀操作未被完全全局串行化，因為讀命中不產(chǎn)生總線事務(wù)，所以它們可以獨立產(chǎn)生。讀缺失與寫操作一起被總線序全局串行化，從而它可根據(jù)全局的總線序來獲得最新寫入的值。讀命中獲得的值或者是同一個處理器中對該位置的一個最近的寫操作所產(chǎn)生的，或是在同一個處理器中最近一次讀缺失獲得的值，因為這兩種情況都出現(xiàn)在總線上，所以讀命中同樣也是按照一致的全局總線序來獲得值。可見在該協(xié)議下，總線序和程序序共同保證了對高速緩存一致性的要求。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院38五、三態(tài)寫回?zé)o效MSI協(xié)議1.MSI(ModifiedSharedlnvalid)協(xié)議三種狀態(tài)：①無效(I)狀態(tài)：該塊在高速緩存中是無效的，或者該塊還沒有進(jìn)入高速緩存，在其他高速緩存中可能有，也可能沒有該塊的有效拷貝；②共享(S)狀態(tài)：該塊在高速緩存中未被修改過，主存中是最新的，在其他高速緩存中可能有，也可能沒有該塊的有效拷貝；③修改過(M)狀態(tài)：也叫做臟狀態(tài)，只有該高速緩存中有該塊的最新拷貝，主存中的拷貝是過時的(Stale)，在其他高速緩存中沒有該塊的有效拷貝。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院39已知在偵聽高速緩存一致性協(xié)議中，每個高速緩存控制器接收兩方面輸入：處理器發(fā)出的請求和總線上偵聽到的事務(wù)。對于前者，處理器發(fā)出處理器讀(PrRd)和處理器寫(PrWr)兩種類型的請求，并且讀或?qū)懚加锌赡苁菍σ呀?jīng)在或者不在高速緩存中的內(nèi)存塊進(jìn)行。假如是對不在高速緩存中的內(nèi)存塊進(jìn)行讀或?qū)?，若緩存已滿，則當(dāng)前高速緩存中的一塊就必須被新請求的塊替換出去。并且，若被替換出去的塊處于M狀態(tài)的話，則必須將其內(nèi)容寫回到內(nèi)存中。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院40對于后者，假設(shè)總線允許以下三種事務(wù)：①總線讀(BusRd)：高速緩存控制器將地址放到總線上，請求一個它不準(zhǔn)備去修改的數(shù)據(jù)塊，由主存或者另一個高速緩存提供數(shù)據(jù)。②總線互斥讀(BusRdX)：高速緩存控制器將地址放到總線上，請求一個它準(zhǔn)備修改的互斥拷貝，由主存或者另一個高速緩存提供數(shù)據(jù)。所有其他高速緩存中的拷貝都必須被置為無效。該事務(wù)是由對某個不在緩存或雖然在緩存但沒有被標(biāo)記為M的塊的寫操作引起的。一旦緩存獲得互斥拷貝，寫操作就能在緩存中執(zhí)行，處理器可能會要求一個確認(rèn)信號作為該事務(wù)的結(jié)果。總線互斥讀事務(wù)是唯一一個為了實現(xiàn)高速緩存一致性才引入的新事務(wù)。③總線寫回(BusWB)：緩存控制器將主存塊的地址和內(nèi)容放到總線上，主存用該最新的內(nèi)容來更新。這種事務(wù)由緩存控制器的寫回操作引起，處理器并不知道，也不期望得到響應(yīng)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院41除此之外：④刷新(Flush)：為支持寫回協(xié)議，除了改變緩存塊的狀態(tài)外，還需要一種新的動作，即高速緩存控制器能夠響應(yīng)出現(xiàn)在總線上的事務(wù)，并能把該事務(wù)所請求的塊從緩存中放到總線上，而不是讓內(nèi)存提供數(shù)據(jù)，這個動作稱為刷新(Flush)。當(dāng)然，高速緩存控制器的工作還包括發(fā)出一個新的總線事務(wù)，為寫回提供數(shù)據(jù)以及接受主存提供的數(shù)據(jù)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院422．狀態(tài)轉(zhuǎn)換在MSI偵聽協(xié)議中，控制每個高速緩存中的某個塊的狀態(tài)轉(zhuǎn)換圖如下圖中M、S和I分別代表相應(yīng)的修改過、共享和無效狀態(tài)。記號A／B中，“—”表示空動作；Flush動作表示由高速緩存來提供請求塊到總線上。有些弧線上有多個記號，表示這些事件引起相同的狀態(tài)轉(zhuǎn)換。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院43哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院443.從狀態(tài)轉(zhuǎn)換圖可以看出的轉(zhuǎn)換：當(dāng)一個處理器讀一個無效塊時，高速緩存控制器就通過產(chǎn)生一個BusRd事務(wù)來得到該塊，并且該塊狀態(tài)變?yōu)镾狀態(tài)；當(dāng)寫一個共享或者無效塊時，產(chǎn)生一個BusRdX事務(wù)來得到該塊的互斥擁有權(quán)，并將該塊狀態(tài)置為M；如果高速緩存控制器在總線上觀察到一個BusRd事務(wù)，并且該事務(wù)請求的塊在本地高速緩存中處于M狀態(tài)，則將該塊內(nèi)容放到總線上(Flush)，同時將該塊狀態(tài)置為S態(tài)如果在總線上觀察到BusRdX事務(wù)，并且所請求的塊在本地高速緩存處于S狀態(tài)，則只要簡單將該塊置為I狀態(tài)；如果在本地高速緩存中處于M狀態(tài)，則要將該塊內(nèi)容放到總線上(Flush)，然后將該塊狀態(tài)置為I狀態(tài)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院454.例題具體的一個狀態(tài)轉(zhuǎn)換的例子可看下表，顯示了在下圖的例子中采用MSI協(xié)議時，所產(chǎn)生的總線事務(wù)和內(nèi)存塊狀態(tài)的轉(zhuǎn)換情況。

哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院46哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院47一個狀態(tài)轉(zhuǎn)換的例子一覽表

處理器動作

P1中狀態(tài)

P2中狀態(tài)

P3中狀態(tài)總線事務(wù)數(shù)據(jù)提供者Pl讀u

S————BusRd主存P3讀u

S——

SBusRd主存P3寫u

I——

MBusRdX主存P1讀u

S——

SBusRd

P3高速緩存P2讀u

S

S

SBusRd主存哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院48六、MESI監(jiān)聽協(xié)議1.前言

MESI屬于寫無效協(xié)議。它根據(jù)所有的讀、寫、命中或不命中，與在總線上監(jiān)聽的事件來跟蹤高速緩存行的狀態(tài)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院49MESI(ModifiedExclusiveSharedlnvalid)協(xié)議是MSI協(xié)議的改進(jìn)協(xié)議。這個協(xié)議最初是由在Urbana—Champaign的Illinois大學(xué)的研究者提出的，所以也稱為Illinois協(xié)議。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院50許多現(xiàn)代微處理器設(shè)計中已經(jīng)實現(xiàn)了MESI協(xié)議，例如IntelPentium、i860、PowerPC601等。與MSI協(xié)議相比，MESI協(xié)議增加了一個互斥(E)狀態(tài)。小規(guī)模的SMP機器的一類主要的工作負(fù)載是順序程序，假如采用MSI協(xié)議，當(dāng)一個順序程序先讀入一個數(shù)據(jù)項，然后修改一個數(shù)據(jù)項時，就要產(chǎn)生兩個總線事務(wù)：哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院51①一個BusRd事務(wù)，用來得到內(nèi)存塊，并置為S狀態(tài)產(chǎn)生一個BusRdX事務(wù)，用來將該塊狀態(tài)從S變?yōu)镸狀態(tài)。而在順序程序中數(shù)據(jù)項不存在共享者，因此只會在一個高速緩存有該塊拷貝，②后一個BusRdX事務(wù)是不必要的。為了改進(jìn)這種情況，加入了一個E狀態(tài)，用來表示只有一個高速緩存中有這個內(nèi)存塊，且該塊內(nèi)容沒有被修改過。只要開始發(fā)出BusRd事務(wù)，得到內(nèi)存塊，并置為E狀態(tài)，就可以直接進(jìn)行修改，而不需要產(chǎn)生BusRdX事務(wù)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院52MESI協(xié)議由四個狀態(tài)組成：修改過(M)(或稱為臟狀態(tài))、互斥干凈(E)、共享(S)和無效。其中，M和I狀態(tài)和MSI協(xié)議中意思是相同的；E狀態(tài)表示只有一個高速緩存中有這個內(nèi)存塊，且該塊內(nèi)容沒有被修改過主存中是最新的共享狀態(tài)表示有兩個或者更多高速緩存中有該塊拷貝。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院53MESI協(xié)議對總線信號有一些新要求。在產(chǎn)生BusRd事務(wù)并裝入內(nèi)存塊時，高速緩存控制器要知道別的高速緩存中是否存在該塊的拷貝，來決定將該塊置為S狀態(tài)還是E狀態(tài)。這就需要總線提供一個額外的共享(S)信號線。在總線事務(wù)的地址階段，所有的高速緩存都要檢查是否含有請求塊的拷貝，若有，則置位共享信號線。發(fā)出總線事務(wù)的高速緩存控制器，只要檢查一下共享信號線，就能判斷出是否有別的高速緩存中存在該塊拷貝，以此決定該塊裝入后置為S狀態(tài)還是E狀態(tài)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院54在S狀態(tài)下，如果發(fā)生一個處理器寫，由于該高速緩存已經(jīng)有最新的拷貝了，因此不需要獲得數(shù)據(jù)，這時可以采用一個新的總線事務(wù)——總線升級(BusUpgr)，然后轉(zhuǎn)換到M狀態(tài)。所有其他的高速緩存?zhèn)陕牭皆撌聞?wù)，將其相關(guān)的拷貝置為無效狀態(tài)不同點在于總線升級事務(wù)不需要數(shù)據(jù)響應(yīng)，也就不會導(dǎo)致實際的數(shù)據(jù)傳輸，主存或其他的高速緩存不需要提供數(shù)據(jù)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院552．狀態(tài)轉(zhuǎn)換下圖所示是MESI協(xié)議的狀態(tài)轉(zhuǎn)換圖。圖中的記號與MSI狀態(tài)轉(zhuǎn)換圖相似，具體的協(xié)議轉(zhuǎn)換也與MSI協(xié)議類似。若在無效狀態(tài)I下有處理器讀(PrRd)發(fā)生，則根據(jù)S線是否被置位，來決定是轉(zhuǎn)換到E狀態(tài)還是S狀態(tài)，若置位則轉(zhuǎn)換到S狀態(tài)，否則轉(zhuǎn)換到E狀態(tài)，其中BusRd(S)表示在BusRd事務(wù)中S線被置位。在E狀態(tài)下，若發(fā)生處理器寫(PrWr)，將導(dǎo)致由E狀態(tài)轉(zhuǎn)換到M狀態(tài)，不產(chǎn)生總線事務(wù)；若觀察到一個總線讀(BusRd)事務(wù)，將導(dǎo)致由E狀態(tài)轉(zhuǎn)換到S狀態(tài)，同時由該高速緩存提供數(shù)據(jù)；若觀察到一個總線互斥讀(BusRdX)事務(wù)，將導(dǎo)致由E狀態(tài)轉(zhuǎn)換到I狀態(tài)，同時由該高速緩存提供數(shù)據(jù)。其他狀態(tài)轉(zhuǎn)換與MSI協(xié)議類似。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院56還有一個不同點在于當(dāng)高速緩存和主存中都有最新數(shù)據(jù)時由誰來提供數(shù)據(jù)。在S狀態(tài)下，若觀察到一個總線讀(BusRd)事務(wù)或總線互斥讀(BusRdX)事務(wù)，在進(jìn)行狀態(tài)轉(zhuǎn)換的同時，在MSI協(xié)議中由主存提供數(shù)據(jù)，而在MESI中由處于S狀態(tài)下的某一個高速緩存提供數(shù)據(jù)，其他的高速緩存不產(chǎn)生動作。這一點在協(xié)議設(shè)計時可酌情處理。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院57哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院58七、四態(tài)寫回更新(Dragon)協(xié)議

1．Dragon協(xié)議

現(xiàn)在來看一個基于寫回高速緩存的寫更新協(xié)議，也稱為Dragon協(xié)議。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院59Dragon協(xié)議有四種狀態(tài)：(1)互斥且干凈E(Exclusive—Clean)：用來表示僅有一個緩存(本緩存)擁有該塊的拷貝，并且沒有被修改過，也就是說，主存中是最新的。(2)共享且干凈SC(Shared—Clean)：用來表示可能有兩個或更多緩存中擁有該塊，并且主存中可能是,也可能不是最新的。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院60(3)共享且修改過SM(Shared—Modified)

用來表示可能有兩個或更多緩存中擁有該塊，且主存中不是最新的。緩存應(yīng)當(dāng)負(fù)責(zé)當(dāng)該塊由緩存中被替換出時，更新主存中的數(shù)據(jù)。在某個時刻，一個塊只可能在一個緩存中處于SM狀態(tài)。然而，一個塊在某個緩存中處于SM狀態(tài)，而在另一個緩存中處于SC狀態(tài)是可以的?；蛘撸粋€塊在任何緩存中都不處于SM狀態(tài)，而在某些緩存中處于SC狀態(tài)。這就是為什么緩存中的塊處于SC狀態(tài)，而主存中卻可能是也可能不是最新的，這依賴于是否在某個緩存中該塊處于SM狀態(tài)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院61（4)修改過M(Modified)用來表示該塊僅在該緩存中處于被修改過(臟狀態(tài))，主存中已經(jīng)過時。緩存負(fù)責(zé)在該塊被替換出來時更新主存。注意到與前面的協(xié)議不同，這里沒有顯式的無效狀態(tài)。這是因為Dragon是基于更新的協(xié)議，在該協(xié)議中，緩存中的塊總是最新的。只要某塊在緩存中，該塊總是有效的。然而，對于不在緩存中的塊，可以想像為一種特殊的無效狀態(tài)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院62Dragon協(xié)議中的處理器請求、總線事務(wù)和動作，與在MESI協(xié)議中的相似。先來看一下處理器請求。假設(shè)處理器還是只發(fā)出讀(PrRd)和寫(PrWr)請求。但由于本協(xié)議中不存在無效狀態(tài)，為了表達(dá)出處理器第一次請求一個新內(nèi)存塊這個動作，增加了處理器讀缺失(PrRdMiss)和處理器寫缺失(PrWrMiss)兩種處理器請求。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院63總線事務(wù)：有總線讀(BusRd)、總線寫回(BusWB)和總線更新(BusUpd)事務(wù)。BusUpd事務(wù)將處理器所寫的內(nèi)容在總線上進(jìn)行廣播，使得所有其他的高速緩存都能進(jìn)行更新。通過只廣播修改過的內(nèi)容，而不是整個內(nèi)存塊，可以更充分利用總線帶寬。為了支持E狀態(tài)，與MESI協(xié)議一樣，也需要一個共享信號。另外，高速緩存控制器還要一個新動作，就是根據(jù)總線上出現(xiàn)的BusUpd事務(wù)，來更新高速緩存中的相應(yīng)塊的內(nèi)容。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院642．狀態(tài)轉(zhuǎn)