【正文】 一、正確性需求 滿足一致性需求 滿足 Cache一致性需求，保持存儲一致性模型的語義。 54 第四節(jié) 基于監(jiān)聽的 Cache一致性實(shí)現(xiàn) 影響 Cache一致性協(xié)議性能的因素： 總線設(shè)計(jì)、 Cache設(shè)計(jì)、存儲系統(tǒng)整合。 優(yōu)點(diǎn)： 在柵障頻率較高的機(jī)器中較有用； 缺點(diǎn)： OS不易管理進(jìn)程在 PE間遷移，同一 PE多個(gè)進(jìn)程問題。 優(yōu)化的總線原語同樣適用于互斥中獲得鎖的等待期間的高度總線爭用。 while ( == 0 ) ()。 = local_sense。 if ( mycount == p ) { UNLOCK()。 LOCK()。 } else while ( == 0 ) ()。 if ( mycount == p ) { = 0。 mycount = ++。 常規(guī)柵障： BARRIER(bar_name, p) { LOCK()。 /*use a*/ 結(jié)論：用普通變量作為標(biāo)記，在標(biāo)記上用忙等待或阻塞實(shí)現(xiàn)點(diǎn)對點(diǎn)同步。 /*use a*/ P1 P2 a=f(x)。 flag=1。 P1 P2 a=f(x)。 硬件支持 — 滿 空位 使每個(gè)存儲字均和滿 空位狀態(tài)相聯(lián)，寫后滿，讀后空。 設(shè)計(jì)：根據(jù)系統(tǒng)的應(yīng)用特性及性能 /價(jià)格要求進(jìn)行選擇。 50 基于數(shù)組的鎖： （實(shí)現(xiàn)了兩個(gè)目標(biāo)） 進(jìn)程取得存儲單元（內(nèi)容為下一個(gè)進(jìn)程取得的存儲單元地址和本進(jìn)程狀態(tài)），進(jìn)程讀取該單元上狀態(tài)，不忙時(shí)獲得鎖； 釋放時(shí)向該單元中對應(yīng)的下一個(gè)進(jìn)程的單元寫不忙值。 服務(wù)單元加一實(shí)現(xiàn)： 普通寫操作。 加號鎖： （實(shí)現(xiàn)了第一個(gè)目標(biāo)） 進(jìn)程取某單元值并加一，進(jìn)程讀另一單元（正在服務(wù)）值，去和讀的值相等時(shí)獲得鎖； 釋放時(shí)將正在服務(wù)單元值加一。 LLSC原語應(yīng)用： 可合成多種原子操作，如取并加 1。 look: ll reg1, location //取鎖變量到 reg1 bnz reg1, lock //如果變量已加鎖，轉(zhuǎn) look sc location, reg2 //LL后沒有其他 PE對變量的寫操作， //且第一個(gè)將 sc指令送到總線的 PE將成功操作 beqz look //如果失敗，轉(zhuǎn) look ret LLSC與 Test and Testamp。 時(shí)延 流量 可擴(kuò)展性 存儲代價(jià) 公平性 測試并設(shè)置鎖 小 大 差 好 不保證 帶回退測試并設(shè)置鎖 小 中 中 好 不保證 測試 測試并設(shè)置鎖 略大 小 好 好 不保證 流量（ p每個(gè) PE各獲得一次） 測試并設(shè)置鎖 O(p m), m=∑k ci 帶回退測試并設(shè)置鎖 O(p i ) 測試 測試并設(shè)置鎖 O(p2) 結(jié)論：理所當(dāng)然用測試 測試并設(shè)置鎖代替測試并設(shè)置鎖。 優(yōu)化設(shè)計(jì)： 帶回退的測試并設(shè)置鎖 — 減少等待期間指令發(fā)出的頻率， 操作失敗后插入的延遲時(shí)間可變（ t=k ci）； 測試 測試并設(shè)置鎖（ Test and Testamp。Set） 測試并設(shè)置鎖特點(diǎn)： 等待期間每次測試產(chǎn)生一次寫的總線事務(wù)。 可選方案： （原子性指令） 測試并設(shè)置指令、交換指令、取并操作指令、比較交換指令。 該方法不靈活，所數(shù)量有限，基本不采用。 說明：本節(jié)的討論均基于忙等待進(jìn)行。 優(yōu)化 — 先采用忙等待，超過某時(shí)間閥值后轉(zhuǎn)為阻塞。 等待算法： 忙等待、阻塞。 44 第三節(jié) 同步操作 同步操作： 互斥、點(diǎn)對點(diǎn)事件、全局事件。 43 Cache中總線帶寬需求與存儲塊大小選擇的折中 在塊大小 撲空率曲線中，選擇認(rèn)可的撲空率范圍的塊大小； 在塊大小 流量曲線中，從上述所選的塊大小范圍內(nèi)，選擇流量相對較小的最大塊大小。 采用放松的存儲一致性模型實(shí)現(xiàn)。 （ 2）偽共享撲空的緩解方法 減少訪問模式的空間交叉、適當(dāng)?shù)臄?shù)據(jù)拷貝提高空間局部性、數(shù)據(jù)不跨塊邊界。 通信撲空： 分固有通信撲空（真共享撲空）和附加通信撲空（包含偽共享撲空）。 （ 1） Cache訪問撲空類型 冷啟動(dòng)撲空、容量撲空、沖突撲空、通信撲空。 結(jié)論 — MESI協(xié)議較 MSI優(yōu)化型協(xié)議略好，較 MSI普通型好得多。 39 不同協(xié)議的帶寬需求比較： 方法 選擇一些具體的應(yīng)用，在不同協(xié)議上運(yùn)行； 統(tǒng)計(jì)出各種協(xié)議對應(yīng)的總線流量； 對所得結(jié)果進(jìn)行統(tǒng)計(jì)與分析。 不同類型協(xié)議有不同的撲空率，存儲塊的大小也影響撲空率。 不同協(xié)議有不同的總線流量，需要不同的總線帶寬。 37 五、一致性協(xié)議設(shè)計(jì)中的折中 一致性協(xié)議的性能指標(biāo) 總線帶寬需求、存儲訪問時(shí)延。 36 協(xié)議評價(jià)： 撲空率 — 更新協(xié)議、混合協(xié)議、作廢協(xié)議遞增，三者差別不太大； 升級 /更新速率 更新協(xié)議、混合協(xié)議、作廢協(xié)議遞減，三者差別較大，但更新的時(shí)延相對撲空時(shí)延不太重要； 流量 更新協(xié)議、混合協(xié)議、作廢協(xié)議遞減，三者差別較大。 轉(zhuǎn)上頁 返回上二頁 35 更新、作廢 一致性 協(xié)議 比較 協(xié)議特性： 更新協(xié)議 — 實(shí)現(xiàn)一對多共享及所有處理器共享數(shù)據(jù)寫的次數(shù)少于訪問的次數(shù)時(shí)性能較好； 作廢協(xié)議 實(shí)現(xiàn)點(diǎn)對點(diǎn)共享及所有處理器共享數(shù)據(jù)寫的次數(shù)多于訪問的次數(shù)時(shí)性能較好。 替換操作： 被替換的塊 — Sm/M態(tài)產(chǎn)生 BusWB操作， E/Sc態(tài)無總線操作。 32 處理器操作： PrRd— 均不產(chǎn)生總線操作，不改變狀態(tài)； PrRdMiss— 由新塊裝入引起的撲空，產(chǎn)生 BusRd操作 ，根據(jù)有無監(jiān)聽命中指示 (S)，塊以 Sc態(tài)或 E態(tài)裝入 ； PrWr— Sc/Sm態(tài)產(chǎn)生 BusUpd操作 ，根據(jù)有無監(jiān)聽命中指示(S)， Sc狀態(tài)變?yōu)?Sm或 M態(tài)， Sm狀態(tài)變?yōu)?Sm或 M態(tài) ； PrWrMiss— 由對新塊寫引起的撲空，首先產(chǎn)生 BusRd操作 ，有監(jiān)聽命中指示 (S)時(shí)， 塊以 Sm態(tài)裝入，并產(chǎn)生 BusUpd操作；無監(jiān)聽命中指示時(shí)，塊以 M態(tài)裝入，并進(jìn)行 PrWr操作 。 30 狀態(tài)轉(zhuǎn)換圖： PrWr/ PrRd/ PrRd/ M I PrRd/BusRd(S) S E PrRd/ PrWr/ PrWr/BusRdX 說明： PrWr操作除圖中標(biāo)出的總線操作外，還有 newPrWr操作； M/E/S的 BusRd監(jiān)聽命中時(shí)，向總線發(fā)監(jiān)聽命中指示信號。 轉(zhuǎn)下頁 總線操作： BusRd— 由撲空的 PrRd產(chǎn)生，由存儲系統(tǒng)（可為其他的Cache）提供數(shù)據(jù)，其他 Cache相應(yīng)塊（讀監(jiān)聽命中）返回監(jiān)聽命中指示信號，數(shù)據(jù)塊有效； BusRdX— 由 PrWr產(chǎn)生，由存儲系統(tǒng)（可為其他的 Cache）提供數(shù)據(jù)，其他 Cache相應(yīng)塊（排他讀 /寫監(jiān)聽命中）作廢； BusWB— 與 MSI協(xié)議相同。 28 三、 MESI寫回作廢式協(xié)議 Cache塊狀態(tài)： 修改態(tài) (M)： 此塊與主存不相同 (臟塊 ) ，同一塊的拷貝最多只在一個(gè) Cache中存在； 獨(dú)占態(tài) (E)： 此塊與主存相同 (干凈塊 ) ，同一塊的拷貝只在一個(gè) Cache中存在； 共享態(tài) (S)： 此塊與主存相同 (干凈塊 ) ，同一塊的拷貝可在多個(gè) Cache中存在； 無效態(tài) (I)： 此塊已作廢 (空塊 )。 從充分條件看： 總線串行仲裁保證一個(gè)寫操作完成前另一個(gè)寫操作的排他讀得不到總線不響應(yīng)。 27 對順序一致性的保證 從定義看： 總線串行仲裁定義了針對所有存儲塊（不只是某個(gè)塊）的總線事務(wù)的全序。 寫傳播保證： 發(fā)生寫操作的 Cache為該塊唯一的擁有者，其他 Cache該塊的狀態(tài)變?yōu)?I態(tài)， M態(tài)連續(xù)寫狀態(tài)不變，后續(xù)對該塊的訪問均由擁有者提供數(shù)據(jù)，故寫操作的效果對任何進(jìn)程都是可見的。 轉(zhuǎn)上頁 25 思考 1： 為何 I態(tài)塊的 PrWr操作，需要先取得整塊數(shù)據(jù)？ 思考 2： 某 Cache控制器進(jìn)行 BusRd操作時(shí)，其他塊為 M態(tài)的 Cache控制器如何能替代主存提供數(shù)據(jù)？ 思考 3： 塊為 M態(tài)的 Cache控制器如何優(yōu)先 BusRdX操作更新數(shù)據(jù)到主存？ 協(xié)議的優(yōu)化： M態(tài) BusRd監(jiān)聽命中時(shí)，采用 MS非 MI，使原 M態(tài)的處理器可繼續(xù)使用該塊； SM的 BusRdX采用 BusUpgr（新增加的總線事務(wù)），減少總線流量； 轉(zhuǎn)上二頁 增加一種狀態(tài) E，使 S態(tài)的拷貝只有一個(gè)時(shí)的操作不產(chǎn)生總線操作事務(wù)。 被替換的塊 — M態(tài)時(shí)產(chǎn)生 BusWB操作，其他態(tài)無總線操作。 PrWr/(BusRdX+newPrWr) PrWr/(BusRdX+newPrWr) BusRd/ BusRd/Flush BusRd/ BusRdX/ BusRdX/Flush BusRdX/ CaInvd/BusWB CaInvd/ 24 替換操作： 由邏輯上 I態(tài)（不存在）的塊的 PrRd或 PrWr操作產(chǎn)生，此時(shí) Cache中無 I態(tài)的塊存在。 總線操作（事務(wù)）： BusRd— 由撲空的 PrRd產(chǎn)生，由存儲系統(tǒng)（可為其他的Cache）提供數(shù)據(jù)，其他 Cache相應(yīng)塊（讀監(jiān)聽命中）有效； BusRdX— 由 PrWr產(chǎn)生，由存儲系統(tǒng)（可為其他的 Cache）提供數(shù)據(jù)，其他 Cache相應(yīng)塊（排他讀 /寫監(jiān)聽命中）作廢； 轉(zhuǎn)下頁 BusWB由替換動(dòng)作產(chǎn)生，處理器觀察不到，由 Cache提供數(shù)據(jù)，主存被更新。 塊的擁有者負(fù)責(zé)提供對該塊的訪問請求。 21 二、 MSI寫回作廢式協(xié)議 狀態(tài)轉(zhuǎn)換圖 Cache塊狀態(tài)： 修改態(tài) (M)： 此塊與主存不相同 (臟塊 ) ，同一塊的修改態(tài)最多只在一個(gè) Cache中存在； 共享態(tài) (S)： 此塊與主存相同 (干凈塊 ) ，同一塊的共享態(tài)可在多個(gè) Cache中存在； 無效態(tài) (I)： 此塊已作廢 (空塊 )。 狀態(tài)轉(zhuǎn)換圖： V I PrWr/BusWr PrRd/ PrWr/BusWr PrRd/BusRd BusWr/ BusRd/ BusWr/ BusRd/ 處理器啟動(dòng)的事務(wù) 總線啟動(dòng)的事務(wù) 說明： A/B表示若 A事務(wù)被觀察到，則生成 B事務(wù)。 一、 VI寫直達(dá)協(xié)議 處理器操作： PrRd、 PrWr。 寫直達(dá)法一般與不按寫分配方法配對； 寫回法一般與按寫分配方法配對。 19 第二節(jié) 基于監(jiān)聽的 Cache一致性協(xié)議 Cache更新策略： 寫策略：寫直達(dá)法、寫回法； 寫丟失分配策略：不按寫分配方法、按寫分配方法。 P0： R W1 W2 P1： W2 R1 R2 SA1 SR1 SA1 SR1 R R3 R1 P0： R W1 W2 P1： W2 R1 R2 SA1 SR1