《[高等教育]并行計(jì)算-多媒體課件-并行體系結(jié)構(gòu)-lec15-DSM2》由會員分享，可在線閱讀，更多相關(guān)《[高等教育]并行計(jì)算-多媒體課件-并行體系結(jié)構(gòu)-lec15-DSM2（48頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、Title,PCA L16 Chp7.,*,Wu Spring 04 USTC,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,Parallel C,omputer Architecture并行計(jì)算機(jī)體系結(jié)構(gòu)Lecture 16,概要,復(fù)習(xí)第14講,基于目錄高速緩存一致性協(xié)議,放松的存儲一

2、致性模型,并行文件系統(tǒng),工作站機(jī)群上的文件系統(tǒng),并行應(yīng)用一般要處理很大的數(shù)據(jù)集,I/O系統(tǒng)應(yīng)該能允許并行應(yīng)用中協(xié)作化的操作。,因此需要設(shè)計(jì)一個高性能的文件系統(tǒng)來簡化進(jìn)程間的協(xié)作，高效地利用所有資源，并且對用戶是透明的。,考慮機(jī)群系統(tǒng)最根本的兩個特點(diǎn)：,大量資源：如磁盤、內(nèi)存等。,并行存取多個磁盤來提高傳輸帶寬；,利用機(jī)群系統(tǒng)中的內(nèi)存，建立大的文件系統(tǒng)緩沖區(qū)來提高性能；,高速互連網(wǎng)絡(luò),允許系統(tǒng)依賴遠(yuǎn)地節(jié)點(diǎn)完成某些任務(wù)。例如，現(xiàn)在的一些系統(tǒng)依賴遠(yuǎn)地節(jié)點(diǎn)的內(nèi)存來保存本地節(jié)點(diǎn)中放不下的高速緩存塊。,軟件RAID,軟件邏輯RAID：,將RAID的思想用在機(jī)群中，將數(shù)據(jù)分布在機(jī)群系統(tǒng)的多個磁盤中。,軟件R

3、AID表現(xiàn)就象RAID 5，并且與RAID具有相同的優(yōu)缺點(diǎn),與RAID的區(qū)別，就是文件系統(tǒng)需要負(fù)責(zé)分布數(shù)據(jù)和維護(hù)容錯級別。,條塊組Stripe Group：,將機(jī)群系統(tǒng)所有的磁盤組成一個邏輯RAID,向所有磁盤寫的大的寫操作非常困難，導(dǎo)致很多小寫操作。但在RAID 5，小的寫操作效率差。因此，系統(tǒng)就不能充分利用所有磁盤的寫帶寬。,節(jié)點(diǎn)的網(wǎng)絡(luò)連接的帶寬有限，不能夠同時讀/寫所有磁盤，只能利用局部磁盤性能。,發(fā)生故障的可能性大。奇偶校驗(yàn)機(jī)制不夠，可能同時多個磁盤故障。,解決方法是將數(shù)據(jù)條塊化分布到磁盤的一個子集上條塊組。,系統(tǒng)需要執(zhí)行的小的寫操作數(shù)目大量減少。,網(wǎng)絡(luò)連接的帶寬與條塊組中磁盤的集合帶

4、寬相匹配，充分利用資源。,系統(tǒng)中允許多個磁盤失效，只不過不能是屬于同一條塊組的多個磁盤。,代價(jià)：減少了磁盤存儲容量和有效帶寬，因?yàn)槊總€條塊組都必須有一個存放奇偶校驗(yàn)塊磁盤，而在原來的方法中整個系統(tǒng)只要一個存放奇偶校驗(yàn)塊的磁盤。,日志結(jié)構(gòu)的文件系統(tǒng)Log-structure Filesystem,日志結(jié)構(gòu)的文件系統(tǒng)提高磁盤速度。,根本假設(shè)：高速緩存滿足讀操作的比例是很高的，因此磁盤的通信量主要是由寫操作決定。如果能夠改善寫操作的執(zhí)行，順序執(zhí)行所有寫操作，就可防止尋道和查找時間，能極大提高磁盤性能。,日志結(jié)構(gòu)文件系統(tǒng)的根本思想：使大局部寫操作是按順序執(zhí)行。,日志結(jié)構(gòu)文件系統(tǒng)中，將整個文件系統(tǒng)作為一

5、個日志來實(shí)現(xiàn)。日志結(jié)構(gòu)的文件系統(tǒng)在每次塊被寫到一個文件時都將數(shù)據(jù)塊加到日志的末尾，同時將以前寫的塊置為無效。這種方法允許每個文件被順序?qū)懭?；不管寫的塊順序，因此提供了更快的寫速度。,降低讀性能的代價(jià)換來很高的寫性能，增加了復(fù)雜性。,塊按照寫時的順序分配使文件以隨機(jī)順序在磁盤中分散放置。,增加一個單獨(dú)的垃圾去除程序來掃描文件系統(tǒng)、移除無效塊。,需要一個復(fù)雜的緩存/查詢機(jī)制來支持高效的查詢，并且每個文件的塊位置信息必須保存起來。,緩存,利用局部性原理,多級緩存：能夠在不同的層次利用緩存機(jī)制。效勞器或客戶端磁盤控制器、操作系統(tǒng)、I/O庫、用戶程序,緩存一致性問題：,放松的文件共享語義：對話語義，增加

6、了程序員負(fù)擔(dān),一致性算法：實(shí)現(xiàn)Unix語義。不緩存寫操作，,令牌：寫之前必須獲得令牌。令牌的回收，租約。,粒度：文件，文件塊，自定義,協(xié)同緩存：,如不同的緩存間沒有協(xié)作，不能充分利用所有的緩存空間；一個節(jié)點(diǎn)需要的文件塊，已經(jīng)緩存在另一個節(jié)點(diǎn)的緩存中了，從該緩存讀提高系統(tǒng)的性能。,第一個實(shí)現(xiàn)協(xié)同文件緩存的系統(tǒng)是xFS。,根本思想：機(jī)群中每個節(jié)點(diǎn)分配一局部主存作為文件緩存。協(xié)同緩存算法利用所有這些主存來創(chuàng)立一個大型的、機(jī)群范圍的文件緩存。當(dāng)客戶不命中局部文件緩存時，轉(zhuǎn)向遠(yuǎn)地客戶的存儲器去取數(shù)據(jù)。,數(shù)據(jù)預(yù)取,預(yù)取：真正存取數(shù)據(jù)塊之前就將其讀入內(nèi)存。,并行預(yù)?。好總€節(jié)點(diǎn)獨(dú)立的預(yù)取數(shù)據(jù)。One-bloc

7、k-ahead 或 Stride,透明通知預(yù)?。河脩粝騃/O系統(tǒng)提供一些存取文件情況的提示信息，系統(tǒng)利用這些信息，能夠更好進(jìn)行預(yù)取。,積極預(yù)?。阂坏┊?dāng)磁盤準(zhǔn)備好后，就進(jìn)行預(yù)取，將內(nèi)存中最遠(yuǎn)的將來才用到的數(shù)據(jù)塊替換出去。,表6.6 采用積極預(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,C

8、1,C1,C1,C1,C1,I/O接口,傳統(tǒng)的I/O接口不能表達(dá)數(shù)據(jù)并行、協(xié)同化操作等概念，開發(fā)一種新的I/O接口來表達(dá)這些新的語義信息.,共享文件指針:,全局共享文件指針,分布共享文件指針,跨步存取模式：,簡單的跨步存取操作,嵌套的跨步操作,Berkeley NOW,主動消息Active Message：實(shí)現(xiàn)低開銷通信的一種異步通信機(jī)制。,在消息頭部控制信息中攜帶一個用戶級子例程稱作消息處理程序的地址。當(dāng)信息頭到達(dá)目的節(jié)點(diǎn)時，調(diào)用消息處理程序從網(wǎng)絡(luò)上抽取剩下的數(shù)據(jù)，并把它集成到正在進(jìn)行的計(jì)算中。,GLUnix：全局層Global LayerUnix,運(yùn)行在工作站標(biāo)準(zhǔn)Unix之上的一個軟件層，

9、支持可用性和單一系統(tǒng)映像,易于實(shí)現(xiàn)、可移植性、有效性、魯棒性。,xFS：無效勞器文件系統(tǒng),文件效勞的功能分布到機(jī)群的所有節(jié)點(diǎn)上,軟件RAID,協(xié)同式文件緩存,分布管理,IBM SP2系統(tǒng),機(jī)群體系結(jié)構(gòu),標(biāo)準(zhǔn)環(huán)境,標(biāo)準(zhǔn)編程模型,系統(tǒng)可用性,精選的單一系統(tǒng)映像,高性能開關(guān) HPS 多級網(wǎng)絡(luò),寬節(jié)點(diǎn)、窄節(jié)點(diǎn)和窄節(jié)點(diǎn)2,網(wǎng)絡(luò)接口,系統(tǒng)軟件,分布式共享存儲系統(tǒng),共享存儲器分布于各節(jié)點(diǎn)之中，節(jié)點(diǎn)之間通過可擴(kuò)放性好的互連網(wǎng)絡(luò)相連。,在物理上分布存儲的系統(tǒng)上邏輯地實(shí)現(xiàn)共享存儲模型,對于程序設(shè)計(jì)者隱藏了遠(yuǎn)程通信機(jī)制，保持了方便性和可移植性。,DSM系統(tǒng)底層分布式存儲具有可擴(kuò)放性和代價(jià)有效性,分布式的存儲器和可擴(kuò)

10、放的互連網(wǎng)絡(luò)增加了訪存帶寬，但卻導(dǎo)致了不一致的訪存結(jié)構(gòu),共享存儲系統(tǒng)的體系結(jié)構(gòu),無高速緩存結(jié)構(gòu)：Cray-XMP，YMP-C90 向量機(jī)，大型機(jī)，早期分布式共享存儲機(jī)器,共享總線結(jié)構(gòu)：SMP UMA 小型商用效勞器,CC-NUMA結(jié)構(gòu):,COMA結(jié)構(gòu)：,NCC-NUMA結(jié)構(gòu)：,共享虛擬存儲SVM結(jié)構(gòu)：,CC-NUMA結(jié)構(gòu),高速緩存一致的非均勻存儲訪問系統(tǒng)：,共享存儲器分布于各節(jié)點(diǎn)之中。,節(jié)點(diǎn)之間通過可擴(kuò)放性好的互連網(wǎng)絡(luò)相連，每個處理器都能緩存共享單元，,通常采用基于目錄的方法來維持處理器之間的高速緩存一致性。高速緩存一致性的維護(hù)是這類系統(tǒng)的關(guān)鍵，決定著系統(tǒng)的可擴(kuò)放性。,Stanford大學(xué)的D

11、ASH和FLASH，MIT的Alewife，以及SGI的Origin 2000等。,COMA,結(jié)構(gòu),唯高速緩存存儲結(jié)構(gòu):,共享存儲器的地址是活動的，存儲單元與物理地址別離，數(shù)據(jù)可以根據(jù)訪存模式動態(tài)地在各節(jié)點(diǎn)的存儲器間移動和復(fù)制。,每個節(jié)點(diǎn)的存儲器相當(dāng)于一個大容量高速緩存，數(shù)據(jù)一致性也在這一級維護(hù)。,優(yōu)點(diǎn)是在本地共享存儲器命中的概率較高。其缺點(diǎn)是當(dāng)處理器的訪問不在本節(jié)點(diǎn)命中時，由于存儲器的地址是活動的，需要一種機(jī)制來查找被訪問單元的當(dāng)前位置，因此延遲很大。,目前采用唯高速緩存結(jié)構(gòu)的系統(tǒng)有Kendall Square Research的KSR1和瑞典計(jì)算機(jī)研究院的DDM。此外，COMA結(jié)構(gòu)常用于共

12、享虛擬存儲SVM(Shared Virtual Memory)系統(tǒng)中,共享虛擬存儲,SVM,結(jié)構(gòu),SVM(Shared Virtual Memory)系統(tǒng)，又稱為軟件DSM系統(tǒng)，,SVM系統(tǒng)在基于消息傳遞的MPP或機(jī)群系統(tǒng)中，用軟件把分布于各節(jié)點(diǎn)的多個獨(dú)立編址的存儲器組織成一個統(tǒng)一編址的共享存儲空間。,優(yōu)點(diǎn)是在消息傳遞的系統(tǒng)上實(shí)現(xiàn)共享存儲的編程界面，但主要問題是難以獲得滿意的性能,與硬件共享存儲系統(tǒng)相比，SVM系統(tǒng)中較大的通信和共享粒度(通常是存儲頁)會導(dǎo)致假共享及額外的通信；,在基于機(jī)群的SVM系統(tǒng)中，通信開銷很大?；赟VM系統(tǒng)的并行程序通信量通常比基于消息傳遞的并行程序的通信量大。,SV

13、M系統(tǒng)的實(shí)現(xiàn),在操作系統(tǒng)上改進(jìn)，如Ivy、Mermaid、Mirage和Clouds等；,由運(yùn)行系統(tǒng)來支撐，如CMU Midway、Rice Munin、Rice TreadMarks、Utah Quarks、DIKU CarlOS、Maryland CVM和JIAJIA等；,從語言級來實(shí)現(xiàn)，如MIT CRL、Linda和Orca等。,混合實(shí)現(xiàn)的分布式共享存儲系統(tǒng)，其根本思想是結(jié)合軟硬件實(shí)現(xiàn)的分布式共享存儲系統(tǒng)的優(yōu)點(diǎn)。,Overview,關(guān)于論文辯論與考試,Review of Lec14,基于目錄高速緩存一致性協(xié)議,放松的存儲一致性模型,高速緩存一致性問題的解決,硬件不支持高速緩存一致性(NC

14、C-NUMA結(jié)構(gòu)),為了防止一致性問題，共享數(shù)據(jù)被標(biāo)識為不可高速緩存的，只有私有數(shù)據(jù)才能被高速緩存,好處在于僅需要很少的硬件支持就足夠,缺點(diǎn)在于：,支持透明的軟件高速緩存一致性的編譯機(jī)制非常有限，基于編譯支持的軟件高速緩存一致性是不太現(xiàn)實(shí)的。,如果沒有高速緩存一致性，那么在與訪問遠(yuǎn)地單字所需的同等開銷下系統(tǒng)將失去獲取并使用一個高速緩存行中多個字的優(yōu)點(diǎn)。當(dāng)每次訪問遠(yuǎn)地主存只能獲得一個單字時，共享存儲所具有的空間局部性的優(yōu)點(diǎn)就蕩然無存了。,如果可以同時處理多個字如一個高速緩存行時，那么諸如預(yù)取等延遲容忍技術(shù)效果才能更好。,Context for Scalable Cache Coherence,R

15、ealizing Pgm Models,through net transaction,protocols,-efficient node-to-net interface,-interprets transactions,Caches naturally replicate,data,-coherence through bus,snooping protocols,-consistency,Scalable Networks,-many simultaneous,transactions,Scalable,distributed,memory,Need cache coherence pr

16、otocols that scale!,-no broadcast or single point of order,解決方法:目錄協(xié)議,顯式地包含狀態(tài)向量,與存儲塊狀態(tài)相聯(lián)系,記錄每個存儲塊的狀態(tài),未命中，與目錄通信,決定高速緩存拷貝的地址,決定將要進(jìn)行的操作,確定協(xié)議以保持同步,一個高速緩存一致性系統(tǒng)必須:,提供狀態(tài)集,狀態(tài)轉(zhuǎn)移圖,以及動作,管理一致性協(xié)議,(0)決定何時調(diào)用一致性協(xié)議,(a)找出其他高速緩存上的存儲模塊的信息以決定將要進(jìn)行的操作,是否需要同其他高速緩存拷貝進(jìn)行通信,(b)確定其他拷貝的地址,(c)與這些拷貝通信 (使無效/更新),在所有的系統(tǒng)中都使用同樣的方法進(jìn)行(0),存儲塊的狀態(tài)保存在高速緩存中,假設(shè)未命中那么調(diào)用協(xié)議,不同的方法通過(a)到(c)區(qū)分開來,基于總線的一致性,(a),(b),(c)都是通總線播送實(shí)現(xiàn),訪存失敗的處理器發(fā)出一個“尋找信號,其他的對該信號做出響應(yīng)并采取必要的動作,在規(guī)模不同的網(wǎng)絡(luò)上都可實(shí)現(xiàn),向所有處理器播送,并使它們做出響應(yīng),Conceptually simple,but broadcast doesnt scale with p,