【正文】 fo (cont) 176。 distributed memory and directory ? flat schemes directory distributed with memory: at the home location based on address (hashing): work xaction sent directly to home ? hierarchical schemes Hierarchical of caches that guarantee the inclusion property。 Suggests techniques to reduce storage overhead PCA L16 Wu Spring 04 169。 Potential for cost and performance advantages ? amortization of node fixed costs over multiple processors applies even if processors simply packaged together but not coherent ? can use modity SMPs ? less nodes for directory to keep track of ? much munication may be contained within node (cheaper) ? nodes prefetch data for each other (fewer “remote” misses) ? bining of requests (like hierarchical, only twolevel) ? can even share caches (overlapping of working sets) ? benefits depend on sharing pattern (and mapping) good for widely readshared: . tree data in BarnesHut good for nearestneighbor, if properly mapped not so good for alltoall munication PCA L16 Wu Spring 04 169。 Examples: ? Convex Exemplar: directorydirectory ? Sequent, Data General, HAL: directorysnoopy 176。 Twolevel “hierarchy” 176。 turn dirtybit ON。 supply recalled data to i。 } ? if dirtybit ON then { recall line from dirty proc (cache state to shared)。 Many alternatives for anizing directory information PCA L16 Wu Spring 04 169。 Problems: ? high latency: multiple levels, and snoop/lookup at every level ? bandwidth bottleneck at root 176。 Scalable coherence: ? can have same cache states and state transition diagram ? different mechanisms to manage protocol PCA L16 Wu Spring 04 169。USTC 基于總線的一致性 176。 提供狀態(tài)集 , 狀態(tài)轉(zhuǎn)移圖 , 以及動(dòng)作 176。USTC 解決方法 : 目錄協(xié)議 176。當(dāng)每次訪問(wèn)遠(yuǎn)地主存只能獲得一個(gè)單字時(shí)，共享存儲(chǔ)所具有的空間局部性的優(yōu)點(diǎn)就蕩然無(wú)存了。 放松的存儲(chǔ)一致性模型 PCA L16 Wu Spring 04 169。USTC Overview 176。 176。USTC 共享虛擬存儲(chǔ) SVM結(jié)構(gòu) 176。 ? 優(yōu)點(diǎn)是在本地共享存儲(chǔ)器命中的概率較高。 P1P2Pn???x互聯(lián)網(wǎng)絡(luò) 宿主拷貝 拷貝 拷貝x x0m1m2m1(n1)mnm1處理器保證一致性的高速緩存高速緩存控制器分布式共享內(nèi)存PCA L16 Wu Spring 04 169。 高速緩存一致的非均勻存儲(chǔ)訪問(wèn)系統(tǒng)： ? 共享存儲(chǔ)器分布于各節(jié)點(diǎn)之中。 COMA結(jié)構(gòu) ： 176。USTC 共享存儲(chǔ)系統(tǒng)的體系結(jié)構(gòu) 176。USTC 分布式共享存儲(chǔ)系統(tǒng) 176。 高性能開(kāi)關(guān) HPS 多級(jí) Ω網(wǎng)絡(luò) 176。 標(biāo)準(zhǔn)環(huán)境 176。 176。 ? 在消息頭部控制信息中攜帶一個(gè)用戶級(jí)子例程（稱作消息處理程序）的地址。 共享文件指針 : ? 全局共享文件指針 ? 分布共享文件指針 176。 積極預(yù)?。阂坏┊?dāng)磁盤準(zhǔn)備好后，就進(jìn)行預(yù)取，將內(nèi)存中最遠(yuǎn)的將來(lái)才用到的數(shù)據(jù)塊替換出去。 并行預(yù)?。好總€(gè)節(jié)點(diǎn)獨(dú)立的預(yù)取數(shù)據(jù) 。 PCA L16 Wu Spring 04 169。 ? 第一個(gè)實(shí)現(xiàn)協(xié)同文件緩存的系統(tǒng)是 xFS。不緩存寫(xiě)操作， ? 令牌：寫(xiě)之前必須獲得令牌。 利用局部性原理 176。 ? 增加一個(gè)單獨(dú)的垃圾清除程序來(lái)掃描文件系統(tǒng)、移除無(wú)效塊。這種方法允許每個(gè)文件被順序?qū)懭?；不管?xiě)的塊順序，因此提供了更快的寫(xiě)速度。 ? 日志結(jié)構(gòu)文件系統(tǒng)的基本思想：使大部分寫(xiě)操作是按順序執(zhí)行。USTC 日志結(jié)構(gòu)的文件系統(tǒng)（ Logstructure Filesystem） 176。 網(wǎng)絡(luò)連接的帶寬與條塊組中磁盤的集合帶寬相匹配，充分利用資源。 發(fā)生故障的可能性大。 條塊組（ Stripe Group）： ? 將機(jī)群系統(tǒng)所有的磁盤組成一個(gè)邏輯 RAID 向所有磁盤寫(xiě)的大的寫(xiě)操作非常困難，導(dǎo)致很多小寫(xiě)操作。USTC 軟件 RAID 176。 考慮機(jī)群系統(tǒng)最基本的兩個(gè)特點(diǎn)： ? 大量資源：如磁盤、內(nèi)存等。USTC 并行文件系統(tǒng) 176。USTC 概要 176。USTC Parallel Computer Architecture 并行計(jì)算機(jī)體系結(jié)構(gòu) Lecture 16 PCA L16 Wu Spring 04 169。 放松的存儲(chǔ)一致性模型 PCA L16 Wu Spring 04 169。 176。 PCA L16 Wu Spring 04 169。 176。 節(jié)點(diǎn)的網(wǎng)絡(luò)連接的帶寬有限，不能夠同時(shí)讀 /寫(xiě)所有磁盤，只能利用部分磁盤性能。 系統(tǒng)需要執(zhí)行的小的寫(xiě)操作數(shù)目大量減少。 PCA L16 Wu Spring 04 169。如果能夠改善寫(xiě)操作的執(zhí)行，順序執(zhí)行所有寫(xiě)操作，就可避免尋道和查找時(shí)間，能極大提高磁盤性能。日志結(jié)構(gòu)的文件系統(tǒng)在每次塊被寫(xiě)到一個(gè)文件時(shí)都將數(shù)據(jù)塊加到日志的末尾，同時(shí)將以前寫(xiě)的塊置為無(wú)效。 ? 塊按照寫(xiě)時(shí)的順序分配使文件以隨機(jī)順序在磁盤中分散放置。USTC 緩存 176。 緩存一致性問(wèn)題 ： ? 放松的文件共享語(yǔ)義：對(duì)話語(yǔ)義，增加了程序員負(fù)擔(dān) ? 一致性算法：實(shí)現(xiàn) Unix語(yǔ)義。 協(xié)同緩存： ? 如不同的緩存間沒(méi)有協(xié)作，①不能充分利用所有的緩存空間；②一個(gè)節(jié)點(diǎn)需要的文件塊，已經(jīng)緩存在另一個(gè)節(jié)點(diǎn)的緩存中了，從該緩存讀提高系統(tǒng)的性能。當(dāng)客戶不命中局部文件緩存時(shí)，轉(zhuǎn)向遠(yuǎn)地客戶的存儲(chǔ)器去取數(shù)據(jù)。 176。 176。 傳統(tǒng)的 I/O接口不能表達(dá)數(shù)據(jù)并行、協(xié)同化操作等概念，開(kāi)發(fā)一種新的 I/O接口來(lái)表達(dá)這些新的語(yǔ)義信息 . 176。 主動(dòng)消息（ Active Message）：實(shí)現(xiàn)低開(kāi)銷通信的一種異步通信機(jī)制。 GLUnix：全局層（ Global Layer） Unix ? 運(yùn)行在工作站標(biāo)準(zhǔn) Unix之上的一個(gè)軟件層，支持可用性和單一系統(tǒng)映像 ? 易于實(shí)現(xiàn)、可移植性、有效性、魯棒性。 機(jī)群體系結(jié)構(gòu) 176。 精選的單一系統(tǒng)映像 176。 系統(tǒng)軟件 PCA L16 Wu Spring 04 169。 ? DSM系統(tǒng)底層分布式存儲(chǔ)具有可擴(kuò)放性和代價(jià)有效性 ? 分布式的存儲(chǔ)器和可擴(kuò)放的互連網(wǎng)絡(luò)增加了訪存帶寬，但卻導(dǎo)致了不一致的訪存結(jié)構(gòu) ?網(wǎng)絡(luò)控制器存儲(chǔ)器處理器高速緩存網(wǎng)絡(luò)控制器存儲(chǔ)器處理器高速緩存網(wǎng)絡(luò)控制器存儲(chǔ)器處理器高速緩存DSM 共享地址空間互連網(wǎng)絡(luò)PCA L16 Wu Spring 04 169。 CCNUMA結(jié)構(gòu) : 176。USTC CCNUMA結(jié)構(gòu) 176。 ? Stanford大學(xué)的 DASH和 FLASH， MIT的 Alewife，以及 SGI的 Origin 2022等。 ? 每個(gè)節(jié)點(diǎn)的存儲(chǔ)器相當(dāng)于一個(gè)大容量高速緩存，數(shù)據(jù)一致性也在這一級(jí)維護(hù)。此外， COMA結(jié)構(gòu)常用于共享虛擬存儲(chǔ) SVM(Shared Virtual Memory)系統(tǒng)中 P1P2Pn???x x x互聯(lián)網(wǎng)絡(luò)拷貝 屬主 拷貝處理器高速緩存保證一致性的共享內(nèi)存高速緩存控制器PCA L16 Wu Spring 04 169。 基于 SVM系統(tǒng)的并行程序通信量通常比基于消息傳遞的并行程序的通信量大 。 PCA L16 Wu Spring 04 169。 基于目錄高速緩存一致性協(xié)議 176。 ②如果沒(méi)有高速緩存一致性，那么在與訪問(wèn)遠(yuǎn)地單字所需的同等開(kāi)銷下系統(tǒng)將失去獲取并使用一個(gè)高速緩存行中多個(gè)字的優(yōu)點(diǎn)。USTC Context for Scalable Cache Coherence ? ? ? ? ?S c a l a b l e n e t w o r kC AP$S w i t c hMS w i t c h S w i t c hRealizing Pgm Models through