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

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

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

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

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

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

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

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

處理器動(dòng)作

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é)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院47一個(gè)狀態(tài)轉(zhuǎn)換的例子一覽哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院48六、MESI監(jiān)聽協(xié)議1.前言

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

1．Dragon協(xié)議

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

用來(lái)表示可能有兩個(gè)或更多緩存中擁有該塊，且主存中不是最新的。緩存應(yīng)當(dāng)負(fù)責(zé)當(dāng)該塊由緩存中被替換出時(shí)，更新主存中的數(shù)據(jù)。在某個(gè)時(shí)刻，一個(gè)塊只可能在一個(gè)緩存中處于SM狀態(tài)。然而，一個(gè)塊在某個(gè)緩存中處于SM狀態(tài)，而在另一個(gè)緩存中處于SC狀態(tài)是可以的?；蛘?，一個(gè)塊在任何緩存中都不處于SM狀態(tài)，而在某些緩存中處于SC狀態(tài)。這就是為什么緩存中的塊處于SC狀態(tài)，而主存中卻可能是也可能不是最新的，這依賴于是否在某個(gè)緩存中該塊處于SM狀態(tài)。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院60(3)共享且修改過(guò)SM哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院61（4)修改過(guò)M(Modified)用來(lái)表示該塊僅在該緩存中處于被修改過(guò)(臟狀態(tài))，主存中已經(jīng)過(guò)時(shí)。緩存負(fù)責(zé)在該塊被替換出來(lái)時(shí)更新主存。注意到與前面的協(xié)議不同，這里沒有顯式的無(wú)效狀態(tài)。這是因?yàn)镈ragon是基于更新的協(xié)議，在該協(xié)議中，緩存中的塊總是最新的。只要某塊在緩存中，該塊總是有效的。然而，對(duì)于不在緩存中的塊，可以想像為一種特殊的無(wú)效狀態(tài)。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院61（4)修改過(guò)M(Mod哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院62Dragon協(xié)議中的處理器請(qǐng)求、總線事務(wù)和動(dòng)作，與在MESI協(xié)議中的相似。先來(lái)看一下處理器請(qǐng)求。假設(shè)處理器還是只發(fā)出讀(PrRd)和寫(PrWr)請(qǐng)求。但由于本協(xié)議中不存在無(wú)效狀態(tài)，為了表達(dá)出處理器第一次請(qǐng)求一個(gè)新內(nèi)存塊這個(gè)動(dòng)作，增加了處理器讀缺失(PrRdMiss)和處理器寫缺失(PrWrMiss)兩種處理器請(qǐng)求。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院62Dragon協(xié)議中的處哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院63總線事務(wù)：有總線讀(BusRd)、總線寫回(BusWB)和總線更新(BusUpd)事務(wù)。BusUpd事務(wù)將處理器所寫的內(nèi)容在總線上進(jìn)行廣播，使得所有其他的高速緩存都能進(jìn)行更新。通過(guò)只廣播修改過(guò)的內(nèi)容，而不是整個(gè)內(nèi)存塊，可以更充分利用總線帶寬。為了支持E狀態(tài)，與MESI協(xié)議一樣，也需要一個(gè)共享信號(hào)。另外，高速緩存控制器還要一個(gè)新動(dòng)作，就是根據(jù)總線上出現(xiàn)的BusUpd事務(wù)，來(lái)更新高速緩存中的相應(yīng)塊的內(nèi)容。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院63總線事務(wù)：哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院642．狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換圖如下圖所示。下面就分別描述一下，當(dāng)發(fā)生讀高速緩存缺失、執(zhí)行寫操作以及高速緩存塊被替換出去時(shí)，所發(fā)生的一系列動(dòng)作。(1)讀缺失(ReadMiss)產(chǎn)生一個(gè)BusRd事務(wù)。根據(jù)共享信號(hào)(S)的狀態(tài)，決定該塊被裝入本地高速緩存后，是處于E狀態(tài)，還是SC狀態(tài)。(2)寫(Write)如果所寫的塊在本地高速緩存中處于M狀態(tài)，就不需要執(zhí)行任何動(dòng)作。如果該塊在本地高速緩存中處于E狀態(tài)，則直接將E狀態(tài)改為M狀態(tài)，也不需要再執(zhí)行什么動(dòng)作。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院642．狀態(tài)轉(zhuǎn)換哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院65如果該塊處于SC或SM狀態(tài)，則要產(chǎn)生一個(gè)總線更新(BusUpd)事務(wù)更新(BusUpd)事務(wù)其他任何有該數(shù)據(jù)拷貝的高速緩存，都要置位共享信號(hào)線，更新本地拷貝中對(duì)應(yīng)的字節(jié)，并且如果需要的話，要將狀態(tài)變?yōu)镾C。本地高速緩存根據(jù)共享信號(hào)線來(lái)決定狀態(tài)轉(zhuǎn)換，同時(shí)更新該塊的拷貝，如果共享信號(hào)線被置位，則將它的狀態(tài)變?yōu)镾M。如果共享信號(hào)線未被置位，則表明沒有其他的高速緩存中含有該數(shù)據(jù)的拷貝，則將狀態(tài)變?yōu)镸。主存內(nèi)容不被更新。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院65如果該塊處于SC或SM哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院66哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院66哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院67哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院67哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院68(3)替換(Replacement)在發(fā)生替換時(shí)，只有被替換的塊處于M或SM狀態(tài)時(shí)，才需要用一個(gè)總線事務(wù)將其寫回到內(nèi)存中。如果被替換塊處于SC狀態(tài)，則要么是其他高速緩存中有該塊的處于SM狀態(tài)的拷貝，要么是主存中已經(jīng)有最新的值了。這兩種情況下，都只要將該塊丟棄即可。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院68(3)替換(Repla哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院69八、例：Pentium多處理機(jī)系統(tǒng)采用了MESI協(xié)議哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院69八、例：Pentium哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院70數(shù)據(jù)高速緩存中所有行總是處于下述4種狀態(tài)之一：已修改(modified，M)狀態(tài)獨(dú)占(exclusive，E)狀態(tài)共享(shared，S)狀態(tài)無(wú)效(invalid，I)狀態(tài)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院70數(shù)據(jù)高速緩存中所有行總哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院71哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院71哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院72哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院72哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院73九.本節(jié)總結(jié)一致性協(xié)議具有越多的狀態(tài)，它就能區(qū)分越多的高速緩存事件和可能的狀態(tài)轉(zhuǎn)換。實(shí)現(xiàn)復(fù)雜的協(xié)議要付出實(shí)現(xiàn)效率的代價(jià)。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院73九.本節(jié)總結(jié)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院74并行處理與體系結(jié)構(gòu)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院1并行處理與體系結(jié)構(gòu)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院75第5章分布式存儲(chǔ)器及其時(shí)延容忍1層次存儲(chǔ)器技術(shù)2高緩一致性協(xié)議3共享存儲(chǔ)器的一致性4分布式高速緩/主存體系結(jié)構(gòu)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2第5章分布式存儲(chǔ)器及其哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院76一.問題的提出哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3一.問題的提出哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院771.一種解決方案：哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院41.一種解決方案：哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院782.兩種實(shí)用的方法：寫直達(dá)(Write-through)法：每次寫入Cache時(shí)也把相同的數(shù)寫入主存儲(chǔ)器。特點(diǎn)：這種管理寫操作的方法雖然簡(jiǎn)化了I／O處理器的訪問。它增加了中央處理器與主存儲(chǔ)器之間的信息流量，又降低I／O性能。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院52.兩種實(shí)用的方法：哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院79寫回(Write-back)法寫操作期間中央處理器修改了Cache數(shù)據(jù)之后，并不馬上修改主存儲(chǔ)器的相應(yīng)單元；在Cache中被修改的行從Cache中淘汰時(shí)，才把它寫入主存儲(chǔ)器，這里的“寫回”是指寫回主存儲(chǔ)器。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院6寫回(Write-bac哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院80二、多處理機(jī)環(huán)境下的高速緩存一致性問題1.多個(gè)不同的處理器對(duì)同一高速緩存行的寫操作按所有處理器所見到的存儲(chǔ)器事件的順序而串行化寫。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院7二、多處理機(jī)環(huán)境下的高速哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院81可能引起高速緩存不一致的原因有以下3種：(1)不同處理器對(duì)各自緩存的同一高速緩存行的不同拷貝的異步寫操作；(2)多處理器系統(tǒng)中的進(jìn)程遷移，而又不互相通報(bào)；(3)繞過(guò)高速緩存拷貝擁有者的I/O操作。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院8可能引起高速緩存不一致的哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院822.例題

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

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

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

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

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

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

處理器動(dòng)作

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é)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院47一個(gè)狀態(tài)轉(zhuǎn)換的例子一覽哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院121六、MESI監(jiān)聽協(xié)議1.前言

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

1．Dragon協(xié)議

現(xiàn)在來(lái)看一個(gè)基于寫回高速緩存的寫更新協(xié)議，也稱為Dragon協(xié)議。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院58七、四態(tài)寫回更新(Dr哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院132Dragon協(xié)議有四種狀態(tài)：(1)互斥且干凈E(Exclusive—Clean)：用來(lái)表示僅有一個(gè)緩存(本緩存)擁有該塊的拷貝，并且沒有被修改過(guò)，也就是說(shuō)，主存中是最新的。(2)共享且干凈SC(Shared—