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