【正文】 PCA L16 Wu Spring 04 169。USTC Parallel Computer Architecture 并行計(jì)算機(jī)體系結(jié)構(gòu) Lecture 16 PCA L16 Wu Spring 04 169。USTC 概要 176。 復(fù)習(xí)第 14講 176。 基于目錄高速緩存一致性協(xié)議 176。 放松的存儲(chǔ)一致性模型 PCA L16 Wu Spring 04 169。USTC 并行文件系統(tǒng) 176。 工作站機(jī)群上的文件系統(tǒng) ? 并行應(yīng)用一般要處理很大的數(shù)據(jù)集 ? I/O系統(tǒng)應(yīng)該能允許并行應(yīng)用中協(xié)作化的操作。 ? 因此需要設(shè)計(jì)一個(gè)高性能的文件系統(tǒng)來(lái)簡(jiǎn)化進(jìn)程間的協(xié)作，高效地利用所有資源，并且對(duì)用戶是透明的。 176。 考慮機(jī)群系統(tǒng)最基本的兩個(gè)特點(diǎn)： ? 大量資源：如磁盤、內(nèi)存等。 并行存取多個(gè)磁盤來(lái)提高傳輸帶寬； 利用機(jī)群系統(tǒng)中的內(nèi)存，建立大的文件系統(tǒng)緩沖區(qū)來(lái)提高性能； ? 高速互連網(wǎng)絡(luò) 允許系統(tǒng)依賴遠(yuǎn)地節(jié)點(diǎn)完成某些任務(wù)。例如，現(xiàn)在的一些系統(tǒng)依賴遠(yuǎn)地節(jié)點(diǎn)的內(nèi)存來(lái)保存本地節(jié)點(diǎn)中放不下的高速緩存塊。 PCA L16 Wu Spring 04 169。USTC 軟件 RAID 176。 軟件（邏輯） RAID： ? 將 RAID的思想用在機(jī)群中，將數(shù)據(jù)分布在機(jī)群系統(tǒng)的多個(gè)磁盤中。 ? 軟件 RAID表現(xiàn)就象 RAID 5，并且與 RAID具有相同的優(yōu)缺點(diǎn) ? 與 RAID的區(qū)別，就是文件系統(tǒng)需要負(fù)責(zé)分布數(shù)據(jù)和維護(hù)容錯(cuò)級(jí)別。 176。 條塊組（ Stripe Group）： ? 將機(jī)群系統(tǒng)所有的磁盤組成一個(gè)邏輯 RAID 向所有磁盤寫的大的寫操作非常困難，導(dǎo)致很多小寫操作。但在 RAID 5，小的寫操作效率差。因此，系統(tǒng)就不能充分利用所有磁盤的寫帶寬。 節(jié)點(diǎn)的網(wǎng)絡(luò)連接的帶寬有限，不能夠同時(shí)讀 /寫所有磁盤，只能利用部分磁盤性能。 發(fā)生故障的可能性大。奇偶校驗(yàn)機(jī)制不夠，可能同時(shí)多個(gè)磁盤故障。 ? 解決方法是將數(shù)據(jù)條塊化分布到磁盤的一個(gè)子集上（條塊組）。 系統(tǒng)需要執(zhí)行的小的寫操作數(shù)目大量減少。 網(wǎng)絡(luò)連接的帶寬與條塊組中磁盤的集合帶寬相匹配，充分利用資源。 系統(tǒng)中允許多個(gè)磁盤失效，只不過(guò)不能是屬于同一條塊組的多個(gè)磁盤。 ? 代價(jià)：減少了磁盤存儲(chǔ)容量和有效帶寬，因?yàn)槊總€(gè)條塊組都必須有一個(gè)存放奇偶校驗(yàn)塊磁盤，而在原來(lái)的方法中整個(gè)系統(tǒng)只要一個(gè)存放奇偶校驗(yàn)塊的磁盤。 PCA L16 Wu Spring 04 169。USTC 日志結(jié)構(gòu)的文件系統(tǒng)（ Logstructure Filesystem） 176。 日志結(jié)構(gòu)的文件系統(tǒng)提高磁盤速度。 ? 基本假設(shè)：高速緩存滿足讀操作的比例是很高的，因此磁盤的通信量主要是由寫操作決定。如果能夠改善寫操作的執(zhí)行，順序執(zhí)行所有寫操作，就可避免尋道和查找時(shí)間，能極大提高磁盤性能。 ? 日志結(jié)構(gòu)文件系統(tǒng)的基本思想：使大部分寫操作是按順序執(zhí)行。 176。 日志結(jié)構(gòu)文件系統(tǒng)中，將整個(gè)文件系統(tǒng)作為一個(gè)日志來(lái)實(shí)現(xiàn)。日志結(jié)構(gòu)的文件系統(tǒng)在每次塊被寫到一個(gè)文件時(shí)都將數(shù)據(jù)塊加到日志的末尾，同時(shí)將以前寫的塊置為無(wú)效。這種方法允許每個(gè)文件被順序?qū)懭耄徊还軐懙膲K順序，因此提供了更快的寫速度。 176。 降低讀性能的代價(jià)換來(lái)很高的寫性能，增加了復(fù)雜性。 ? 塊按照寫時(shí)的順序分配使文件以隨機(jī)順序在磁盤中分散放置。 ? 增加一個(gè)單獨(dú)的垃圾清除程序來(lái)掃描文件系統(tǒng)、移除無(wú)效塊。 ? 需要一個(gè)復(fù)雜的緩存 /查詢機(jī)制來(lái)支持高效的查詢，并且每個(gè)文件的塊位置信息必須保存起來(lái)。 PCA L16 Wu Spring 04 169。USTC 緩存 176。 利用局部性原理 176。 多級(jí)緩存：能夠在不同的層次利用緩存機(jī)制。（服務(wù)器或客戶端磁盤控制器、操作系統(tǒng)、 I/O庫(kù)、用戶程序） 176。 緩存一致性問(wèn)題 ： ? 放松的文件共享語(yǔ)義：對(duì)話語(yǔ)義，增加了程序員負(fù)擔(dān) ? 一致性算法：實(shí)現(xiàn) Unix語(yǔ)義。不緩存寫操作， ? 令牌：寫之前必須獲得令牌。令牌的回收，租約。 ? 粒度：文件，文件塊，自定義 176。 協(xié)同緩存： ? 如不同的緩存間沒(méi)有協(xié)作，①不能充分利用所有的緩存空間；②一個(gè)節(jié)點(diǎn)需要的文件塊，已經(jīng)緩存在另一個(gè)節(jié)點(diǎn)的緩存中了，從該緩存讀提高系統(tǒng)的性能。 ? 第一個(gè)實(shí)現(xiàn)協(xié)同文件緩存的系統(tǒng)是 xFS。 ? 基本思想：機(jī)群中每個(gè)節(jié)點(diǎn)分配一部分主存作為文件緩存。協(xié)同緩存算法利用所有這些主存來(lái)創(chuàng)建一個(gè)大型的、機(jī)群范圍的文件緩存。當(dāng)客戶不命中局部文件緩存時(shí)，轉(zhuǎn)向遠(yuǎn)地客戶的存儲(chǔ)器去取數(shù)據(jù)。 PCA L16 Wu Spring 04 169。USTC 數(shù)據(jù)預(yù)取 176。 預(yù)?。赫嬲嫒?shù)據(jù)塊之前就將其讀入內(nèi)存。 176。 并行預(yù)取：每個(gè)節(jié)點(diǎn)獨(dú)立的預(yù)取數(shù)據(jù) 。 Oneblockahead 或 Stride 176。 透明通知預(yù)取 ：用戶向 I/O系統(tǒng)提供一些存取文件情況的提示信息，系統(tǒng)利用這些信息，能夠更好進(jìn)行預(yù)取 。 176。 積極預(yù)?。阂坏┊?dāng)磁盤準(zhǔn)備好后，就進(jìn)行預(yù)取，將內(nèi)存中最遠(yuǎn)的將來(lái)才用到的數(shù)據(jù)塊替換出去。 表 采用積極預(yù)取算法得到的預(yù)取調(diào)度序列一覽表 時(shí)間 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 服務(wù)塊 F1 A1 B2 C1 D2 E1 F1 塊 1 F1 F1 F1 D2 D2 D2 D2 D2 D2 F1 F1 F1 塊 2 B2 B2 B2 B2 B2 B2 B2 E1 E1 E1 E1 E1 塊 3 A1 A1 A1 C1 C1 C1 C1 C1 C1 C1 PCA L16 Wu Spring 04 169。USTC I/O接口 176。 傳統(tǒng)的 I/O接口不能表達(dá)數(shù)據(jù)并行、協(xié)同化操作等概念，開(kāi)發(fā)一種新的 I/O接口來(lái)表達(dá)這些新的語(yǔ)義信息 . 176。 共享文件指針 : ? 全局共享文件指針 ? 分布共享文件指針 176。 跨步存取模式： ? 簡(jiǎn)單的跨步存取操作 ? 嵌套的跨步操作 M =2KBP =5KBN =3存取塊（塊大?。?Kbyte）PCA L16 Wu Spring 04 169。USTC Berkeley NOW 176。 主動(dòng)消息（ Active Message）：實(shí)現(xiàn)低開(kāi)銷通信的一種異步通信機(jī)制。 ? 在消息頭部控制信息中攜帶一個(gè)用戶級(jí)子例程（稱作消息處理程序）的地址。當(dāng)信息頭到達(dá)目的節(jié)點(diǎn)時(shí)，調(diào)用消息處理程序從網(wǎng)絡(luò)上抽取剩下的數(shù)據(jù)，并把它集成到正在進(jìn)行的計(jì)算中。 176。 GLUnix：全局層（ Global Layer） Unix ? 運(yùn)行在工作站標(biāo)準(zhǔn) Unix之上的一個(gè)軟件層，支持可用性和單一系統(tǒng)映像 ? 易于實(shí)現(xiàn)、可移植性、有效性、魯棒性。 176。 xFS：無(wú)服務(wù)器文件系統(tǒng) ? 文件服務(wù)的功能分布到機(jī)群的所有節(jié)點(diǎn)上 ? 軟件 RAID ? 協(xié)同式文件緩存 ? 分布管理 PCA L16 Wu Spring 04 169。USTC IBM SP2系統(tǒng) 176。 機(jī)群體系結(jié)構(gòu) 176。 標(biāo)準(zhǔn)環(huán)境 176。 標(biāo)準(zhǔn)編程模型 176。 系統(tǒng)可用性 176。 精選的單一系統(tǒng)映像 176。 高性能開(kāi)關(guān) HPS 多級(jí) Ω網(wǎng)絡(luò) 176。 寬節(jié)點(diǎn)、窄節(jié)點(diǎn)和窄節(jié)點(diǎn) 2 176。 網(wǎng)絡(luò)接口 176。 系統(tǒng)軟件 PCA L16 Wu Spring 04 169。USTC 分布式共享存儲(chǔ)系統(tǒng) 176。 共享存儲(chǔ)器分布于各節(jié)點(diǎn)之中，節(jié)點(diǎn)之間通過(guò)可擴(kuò)放性好的互連網(wǎng)絡(luò)相連。 ? 在物理上分布存儲(chǔ)的系統(tǒng)上邏輯地實(shí)現(xiàn)共享存儲(chǔ)模型 ? 對(duì)于程序設(shè)計(jì)者隱藏了遠(yuǎn)程通信機(jī)制，保持了方便性和可移植性。 ? 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。USTC 共享存儲(chǔ)系統(tǒng)的體系結(jié)構(gòu) 176。 無(wú)高速緩存結(jié)構(gòu) ： CrayXMP， YMPC90 向量機(jī)，大型機(jī)，早期分布式共享存儲(chǔ)機(jī)器 176。 共享總線結(jié)構(gòu) ： SMP UMA 小型商用服務(wù)器 176。 CCNUMA結(jié)構(gòu) : 176。 COMA結(jié)構(gòu) ： 176。 NCCNUMA結(jié)構(gòu)： 176。 共享虛擬存儲(chǔ) SVM結(jié)構(gòu) ： PCA L16 Wu Spring 04 169。USTC CCNUMA結(jié)構(gòu) 176。 高速緩存一致的非均勻存儲(chǔ)訪問(wèn)系統(tǒng)： ? 共享存儲(chǔ)器分布于各節(jié)點(diǎn)之中。 ? 節(jié)點(diǎn)之間通過(guò)可擴(kuò)放性好的互連網(wǎng)絡(luò)相連，每個(gè)處理器都能緩存共享單元， ? 通常采用基于目錄的方法來(lái)維持處理器之間的高速緩存一致性。高速緩存一致性的維護(hù)是這類系統(tǒng)的關(guān)鍵，決定著系統(tǒng)的可擴(kuò)放性。 ? Stanford大學(xué)的 DASH和 FLASH， MIT的 Alewife，以及 SGI的 Origin 2022等。 P1P2Pn???x互聯(lián)網(wǎng)絡(luò) 宿主拷貝 拷貝 拷貝x x0m1m2m1(n1)mnm1處理器保證一致性的高速緩存高速緩存控制器分布式共享內(nèi)存PCA L16 Wu Spring 04 169。USTC COMA結(jié)構(gòu) 176。 唯高速緩存存儲(chǔ)結(jié)構(gòu) : ? 共享存儲(chǔ)器的地址是活動(dòng)的，存儲(chǔ)單元與物理地址分離，數(shù)據(jù)可以根據(jù)訪存模式動(dòng)態(tài)地在各節(jié)點(diǎn)的存儲(chǔ)器間移動(dòng)和復(fù)制。 ? 每個(gè)節(jié)點(diǎn)的存儲(chǔ)器相當(dāng)于一個(gè)大容量高速緩存，數(shù)據(jù)一致性也在這一級(jí)維護(hù)。 ? 優(yōu)點(diǎn)是在本地共享存儲(chǔ)器命中的概率較高。其缺點(diǎn)是當(dāng)處理器的訪問(wèn)不在本節(jié)點(diǎn)命中時(shí)，由于存儲(chǔ)器的地址是活動(dòng)的，需要一種機(jī)制來(lái)查找被訪問(wèn)單元的當(dāng)前位置，因此延遲很大。 ? 目前采用唯高速緩存結(jié)構(gòu)的系統(tǒng)有 Kendall Square Research的KSR1和瑞典計(jì)算機(jī)研究院的 DDM。此外， COMA結(jié)