第9章 多處理機(jī)

1、第第9章章 多處理機(jī)多處理機(jī)9.1 多處理機(jī)結(jié)構(gòu)多處理機(jī)結(jié)構(gòu)9.2 多處理機(jī)性能模型多處理機(jī)性能模型9.3 多處理機(jī)的多處理機(jī)的Cache一致性一致性9.4 大規(guī)模并行處理機(jī)大規(guī)模并行處理機(jī)9.5 對(duì)稱多處理機(jī)對(duì)稱多處理機(jī)9.6 機(jī)群系統(tǒng)機(jī)群系統(tǒng)多處理機(jī)定義：多處理機(jī)定義：兩個(gè)或兩個(gè)以上處理機(jī)兩個(gè)或兩個(gè)以上處理機(jī)( (包括包括PUPU和和CU)CU)，通，通過(guò)高速互連網(wǎng)絡(luò)連接起來(lái)，在統(tǒng)一的操作過(guò)高速互連網(wǎng)絡(luò)連接起來(lái)，在統(tǒng)一的操作系統(tǒng)管理下，實(shí)現(xiàn)指令以上級(jí)（任務(wù)級(jí)、系統(tǒng)管理下，實(shí)現(xiàn)指令以上級(jí)（任務(wù)級(jí)、作業(yè)級(jí)）并行。作業(yè)級(jí)）并行。按照Flynn分類法，多處理機(jī)系統(tǒng)屬于MIMD計(jì)算機(jī)研究多處理機(jī)的目

2、的：提前提前10年得到性能高年得到性能高100倍的高性能計(jì)算機(jī)系統(tǒng)。倍的高性能計(jì)算機(jī)系統(tǒng)。9.1.1 多處理機(jī)分類多處理機(jī)分類9.1.2 松散偶合多處理機(jī)松散偶合多處理機(jī)9.1.3 緊密偶合多處理機(jī)緊密偶合多處理機(jī)9.1.4 多處理機(jī)系統(tǒng)的特點(diǎn)多處理機(jī)系統(tǒng)的特點(diǎn)9.1 多處理機(jī)結(jié)構(gòu)多處理機(jī)結(jié)構(gòu)9.1.1 多處理機(jī)分類多處理機(jī)分類 多處理機(jī)系統(tǒng)由多個(gè)獨(dú)立的處理機(jī)多個(gè)獨(dú)立的處理機(jī)組成，每個(gè)處理機(jī)都能夠獨(dú)立執(zhí)行自己的程序。按照處理機(jī)之間的連接程度：緊密偶合緊密偶合和松散松散偶合多處理機(jī)偶合多處理機(jī)按照是否共享主存儲(chǔ)器：共享存儲(chǔ)器共享存儲(chǔ)器和分布存分布存儲(chǔ)器多處理機(jī)儲(chǔ)器多處理機(jī)按照處理機(jī)類型：同構(gòu)型同

3、構(gòu)型和異構(gòu)型多處理機(jī)異構(gòu)型多處理機(jī)按照處理機(jī)的個(gè)數(shù)：大規(guī)模并行處理機(jī)大規(guī)模并行處理機(jī)MPP和對(duì)稱多處理機(jī)對(duì)稱多處理機(jī)SMP 按照按照PEPE與與IOPIOP之間互連方式：之間互連方式：對(duì)稱型對(duì)稱型：每個(gè)IOP能夠連接到所有PE上非對(duì)稱型非對(duì)稱型：每個(gè)IOP只與一個(gè)PE連接。冗余對(duì)稱型冗余對(duì)稱型：一個(gè)PE與多個(gè)IOP連接。 按照存儲(chǔ)器的訪問(wèn)方式：按照存儲(chǔ)器的訪問(wèn)方式：均均存儲(chǔ)器，UMAUMA模型模型非均均存儲(chǔ)器，NUMANUMA模型模型只有Cache，COMACOMA模型模型 另外，多向量處理機(jī)另外，多向量處理機(jī)，機(jī)群系統(tǒng)機(jī)群系統(tǒng)等也稱為多處理機(jī)系統(tǒng)。處理機(jī)之間的連接頻帶比較低處理機(jī)之間的連接頻

4、帶比較低處理機(jī)之間互為外圍設(shè)備進(jìn)行連接。通過(guò)并行口或串行口通過(guò)并行口或串行口把多臺(tái)計(jì)算機(jī)連接起來(lái)。多臺(tái)計(jì)算機(jī)之間的連接需要有多個(gè)接口。通過(guò)通過(guò)Ethernet網(wǎng)絡(luò)接口網(wǎng)絡(luò)接口連接多臺(tái)計(jì)算機(jī)。速度達(dá)10Mb、100Mb、1Gb，Mynet已經(jīng)達(dá)到1.28Gb和2.56Gb。當(dāng)通信速度要求更高時(shí)，可以通過(guò)一個(gè)通道和仲裁開(kāi)關(guān)CAS (Channel and Arbiter Switch)直接載存儲(chǔ)器總線之間建立連接。9.1.2 松散偶合多處理機(jī)松散偶合多處理機(jī) 通通 過(guò)過(guò) 輸輸 入入 輸輸 出出 接接 口口 連連 接接 的的 多多 處處 理理 機(jī)機(jī)C P U0C P U1C P Un -1L M0L

5、 M1IO P0IO P1互 連 網(wǎng) 絡(luò)L Mn -1IO Pn -1 模塊0 模塊n-1通通過(guò)過(guò)消消息息傳傳送送系系統(tǒng)統(tǒng)連連接接的的松松散散偶偶合合多多處處理理機(jī)機(jī)CPU0CPUn-1LM0IOP0互連網(wǎng)絡(luò)LMn-1IOPn-1CASCAS處理機(jī)之間共享主存儲(chǔ)器，通過(guò)高速總線或高處理機(jī)之間共享主存儲(chǔ)器，通過(guò)高速總線或高速開(kāi)關(guān)連接。速開(kāi)關(guān)連接。每個(gè)CPU能夠訪問(wèn)任意一個(gè)存儲(chǔ)器模塊通過(guò)映象部件把全局邏輯地址變換成局部物理地址通過(guò)互連網(wǎng)絡(luò)尋找合適的路徑，并分解訪問(wèn)存儲(chǔ)器的沖突多個(gè)輸入輸出處理機(jī)IOP也連接在互連網(wǎng)絡(luò)上，輸入輸出設(shè)備與CPU共享主存儲(chǔ)器。處理機(jī)個(gè)數(shù)不能太多處理機(jī)個(gè)數(shù)不能太多，一般幾個(gè)

6、到幾十個(gè)。9.1.3 緊密偶合多處理機(jī)緊密偶合多處理機(jī)緊密偶合方式要求有很高通信頻帶要求有很高通信頻帶?？梢圆捎萌缦麓胧嚎梢圆捎萌缦麓胧?1)采用高速互連網(wǎng)絡(luò)(2)增加存儲(chǔ)模塊個(gè)數(shù)，一般nm，取12倍之間。(3)每個(gè)存儲(chǔ)模塊再分成多個(gè)小模塊，并采用流水線方式工作。(4)每個(gè)CPU都有自己的局部存儲(chǔ)器LM。(5)每個(gè)CPU設(shè)置一個(gè)Cache。 緊緊 密密 偶偶 合合 多多 處處 理理 機(jī)機(jī) 模模 型型C P U0C P U1C P Un-1M A PM A PIO P0IO P1C P U-M M -IO P 互 連 網(wǎng) 絡(luò)M A PIO Pd-1M M0M M1M Mm -1 帶帶 有有

7、二二 維維 共共 享享 存存 儲(chǔ)儲(chǔ) 器器 和和 局局 部部C a c h e 及及 存存 儲(chǔ)儲(chǔ) 器器 的的 多多 處處 理理 機(jī)機(jī)C P U0C P U1C P Up - 1M A PM A PIO P0IO P1C P U - M M互 連 網(wǎng) 絡(luò)M A PIO Pd - 1C P U - I O P互 連 網(wǎng) 絡(luò)L ML MC a c h eC a c h eC a c h eM M0 ， 0M M0 ， n - 1M M1 ， 0M M1 ， n - 1M Mm - 1 ， 0M Mm - 1 ， n - 1L M1. 結(jié)構(gòu)靈活結(jié)構(gòu)靈活并行處理機(jī)：專用，PE數(shù)多，固定有限通信多處理機(jī)：多

8、處理機(jī)： 通用通用，PE數(shù)少，數(shù)少，高速靈活通信高速靈活通信2. 程序并行性程序并行性并行處理機(jī)的并行性存在于指令內(nèi)部，識(shí)別比較容易。多處理機(jī)的并行性存在于指令外并行性存在于指令外部部，在多個(gè)任務(wù)之間，識(shí)別難度較大。一個(gè)簡(jiǎn)單的例子：一個(gè)簡(jiǎn)單的例子：Y = A+B*C*D/E+F，用兩個(gè)處理機(jī)計(jì)算：，用兩個(gè)處理機(jī)計(jì)算：CPU1：B*C， A+F， A+B*C*D/E+FCPU2：D/E， B*C*D/E，9.1.4 多處理機(jī)系統(tǒng)的特點(diǎn)多處理機(jī)系統(tǒng)的特點(diǎn)3. 并行任務(wù)派生并行任務(wù)派生并行處理機(jī)把同種操作集中，由指令直接啟動(dòng)各PE同時(shí)工作。多處理機(jī)用專門的指令來(lái)表示并發(fā)關(guān)系用專門的指令來(lái)表示并發(fā)關(guān)系

9、，一個(gè)任務(wù)執(zhí)行時(shí)能夠派生出與它并行的另一些任務(wù)如果沒(méi)有空閑處理機(jī)，任務(wù)進(jìn)入排隊(duì)器等待4. 進(jìn)程同步進(jìn)程同步并行處理機(jī)僅一個(gè)CU，自然是同步的。多處理機(jī)中，各處理機(jī)執(zhí)行不同的指令，工作進(jìn)度不會(huì)也不必保持相同。先做完的要停下等待。有數(shù)據(jù)相關(guān)和控制相關(guān)也要停下等待。要采取同步措施來(lái)保持程序要求的正確順序要采取同步措施來(lái)保持程序要求的正確順序5. 資源分配和進(jìn)程調(diào)度資源分配和進(jìn)程調(diào)度并行處理機(jī)的PE是固定的，用屏蔽來(lái)改變實(shí)際參加操作的PE數(shù)目。多處理機(jī)執(zhí)行并發(fā)任務(wù)，需用處理機(jī)的數(shù)目不固定，各處理機(jī)進(jìn)出任務(wù)的時(shí)刻不相同，所需共享資源的品種、數(shù)量隨時(shí)變化。資源分配和進(jìn)程調(diào)度問(wèn)題資源分配和進(jìn)程調(diào)度問(wèn)題，對(duì)整

10、個(gè)系統(tǒng)的效率有很大的影響。2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)16引起峰值性能下降的原因：引起峰值性能下降的原因：(1)由于處理機(jī)之間通信而產(chǎn)生的延遲。(2)一臺(tái)處理機(jī)與其它處理機(jī)同步所需的開(kāi)銷。(3)當(dāng)沒(méi)有足夠多任務(wù)時(shí)，一臺(tái)或多臺(tái)處理機(jī)處于空閑狀態(tài)。(4)由于一臺(tái)或多臺(tái)處理機(jī)執(zhí)行無(wú)用的工作。(5)系統(tǒng)控制和操作調(diào)度所需的開(kāi)銷。9.2 多處理機(jī)性能模型多處理機(jī)性能模型2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)17研究多處理機(jī)的目的：研究多處理機(jī)的目的： 單處理機(jī)的速度提高很快，單處理機(jī)的速度提高很快，為什么還要研究多處理機(jī)？為什么還要研究多處理機(jī)？提前5年得到速度高1

11、0倍的機(jī)器。 或用1/10的價(jià)格獲得一臺(tái)高性能的機(jī)器。在某些適合進(jìn)行并行處理得應(yīng)用領(lǐng)域，可以達(dá)到：提前提前1010年得到速度高年得到速度高100100倍的機(jī)器。倍的機(jī)器。 或用或用1/1001/100的價(jià)格獲得一臺(tái)高性能的機(jī)器。的價(jià)格獲得一臺(tái)高性能的機(jī)器。18并行性在很大程度上依賴于并行性在很大程度上依賴于R/C比值比值其中：R: 程序執(zhí)行時(shí)間，程序執(zhí)行時(shí)間，C: 通信開(kāi)銷通信開(kāi)銷R/C小，并行度低。R/C大，并行性高。把作業(yè)分解成較大的塊，能得到較大的R/C，但所得到的并行性小R/C是衡量任務(wù)粒度是衡量任務(wù)粒度(Granularity)的尺度的尺度粗粒度(Coarsegrain)并行：R/C

12、大，通信開(kāi)銷小 細(xì)粒度(Finegrain)并行：R/C小，通信開(kāi)銷大細(xì)粒度并行性是程序盡可能地分解成小任務(wù)，在極端情況下，一個(gè)小任務(wù)只完成一個(gè)操作目標(biāo)：目標(biāo)：由由M個(gè)任務(wù)組成的程序，在個(gè)任務(wù)組成的程序，在N臺(tái)處理機(jī)組成的系臺(tái)處理機(jī)組成的系統(tǒng)上運(yùn)行，求最短執(zhí)行時(shí)間？統(tǒng)上運(yùn)行，求最短執(zhí)行時(shí)間？基本模型僅考慮由兩臺(tái)處理機(jī)組成的系統(tǒng)。 總處理時(shí)間總處理時(shí)間Rmax(MK，K)C(MK)K 其中：R：每個(gè)任務(wù)的執(zhí)行時(shí)間， C：通信開(kāi)銷， K：任務(wù)分配參數(shù)。當(dāng)通信時(shí)間很小時(shí)，把M個(gè)任務(wù)平均分給兩臺(tái)處理機(jī)當(dāng)通信時(shí)間很大時(shí)，把M個(gè)任務(wù)分配給一臺(tái)處理機(jī)9.2.1 基本模型基本模型 時(shí)間時(shí)間 時(shí)間時(shí)間 總的處理

13、時(shí)間100 總的處理時(shí)間 50 90 80 40 70 60 通信時(shí)間 30 50 40 20 執(zhí)行時(shí)間 30 20 10 通信時(shí)間 10 執(zhí)行時(shí)間 0 0 10 20 30 40 50 0 10 20 30 40 50 任務(wù)分配參數(shù)任務(wù)分配參數(shù) k 任務(wù)分配參數(shù)任務(wù)分配參數(shù) k ()最佳分配參數(shù) K0 ()最佳分配參數(shù) KM/22022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)21通信時(shí)間：通信時(shí)間： C(M-K)K是一個(gè)開(kāi)口向下的二次函數(shù)， 任務(wù)執(zhí)行時(shí)間是兩根相交的直線。 當(dāng)通信時(shí)間比較大時(shí)，總時(shí)間的最小值發(fā)生在端點(diǎn)， 當(dāng)通信時(shí)間比較小時(shí)，總時(shí)間的最小值發(fā)生在中點(diǎn)。結(jié)論：結(jié)論： (1)總

14、時(shí)間的最小值只可能出現(xiàn)在中點(diǎn)或兩個(gè)端點(diǎn)總時(shí)間的最小值只可能出現(xiàn)在中點(diǎn)或兩個(gè)端點(diǎn)， (2)如果總時(shí)間的最小值發(fā)生在中點(diǎn)，必須滿足： M R R M/2 + C M/2 M/2 R/C M/2總時(shí)間最短的結(jié)論：總時(shí)間最短的結(jié)論：當(dāng)當(dāng)R/CM/2時(shí)，把所有任務(wù)分配給同一臺(tái)處理機(jī)，時(shí)，把所有任務(wù)分配給同一臺(tái)處理機(jī)，K0；當(dāng)當(dāng)R/CM/2時(shí)，把任務(wù)平均分配給兩臺(tái)處理機(jī)，時(shí)，把任務(wù)平均分配給兩臺(tái)處理機(jī)，KM/2。2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)22要解決的問(wèn)題：要解決的問(wèn)題：把把M個(gè)任務(wù)分配給個(gè)任務(wù)分配給N臺(tái)處理機(jī)，求總處理時(shí)間的最臺(tái)處理機(jī)，求總處理時(shí)間的最小值。小值。實(shí)際的最小值發(fā)生

15、在極端分配情況下，實(shí)際的最小值發(fā)生在極端分配情況下， 或者將所有的任務(wù)集中在一臺(tái)處理機(jī)上，或者將所有的任務(wù)集中在一臺(tái)處理機(jī)上， 或者將任務(wù)平均分配給所有處理機(jī)?；蛘邔⑷蝿?wù)平均分配給所有處理機(jī)。先討論平均分配方法平均分配方法：9.2.2 N臺(tái)處理機(jī)系統(tǒng)的基本模型臺(tái)處理機(jī)系統(tǒng)的基本模型2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)23平均分配方法：平均分配方法：例1：個(gè)任務(wù)平均分給臺(tái)處理機(jī)： 例2： 11個(gè)任務(wù)平均分給臺(tái)處理機(jī)：方案 P1 P2 P3 執(zhí)行時(shí)間 通信時(shí)間 總處理時(shí)間 一 2 1 1 2R 5C 2R+5C 二二 2 2 2 2 0 0 2R2R 4C4C 2R+4C2R+4C

16、 方案 P1 P2 P3 P4 P5 執(zhí)行時(shí)間 通信時(shí)間 總處理時(shí)間 一 3 2 2 2 2 3R 48C 3R+48C 二 3 3 2 2 1 3R 47C 3R+47C 三三 3 3 3 3 3 3 2 2 0 0 3R3R 45C45C 3R+45C3R+45C M個(gè)任務(wù)分配給個(gè)任務(wù)分配給N臺(tái)處理機(jī)的最佳分配方法：臺(tái)處理機(jī)的最佳分配方法： 臺(tái)處理機(jī)，每臺(tái) 個(gè)任務(wù)如果M/N0，則：另外有1臺(tái)處理機(jī)分得剩下的 個(gè)任務(wù)；剩下的 臺(tái)處理機(jī)不分配任何任務(wù)。例如：101個(gè)任務(wù)平均分給50臺(tái)處理機(jī)： 有33臺(tái)處理機(jī)，每臺(tái)分給3個(gè)任務(wù)； 另有臺(tái)處理機(jī)分給個(gè)任務(wù)； 剩下的16臺(tái)處理機(jī)不分配任務(wù)。NMM/N

17、M /NMM/mod1/NMMN假設(shè)Ki個(gè)任務(wù)分給了第臺(tái)處理機(jī)：第一項(xiàng)求出N臺(tái)處理機(jī)中最大執(zhí)行時(shí)間；第二項(xiàng)計(jì)算出Ki與（MKi）任務(wù)之間兩兩通信的開(kāi)銷時(shí)間，它是關(guān)于Ki的二次函數(shù)。Ki最多有3個(gè)取值： 、 和0當(dāng) M 是 N 的倍數(shù)時(shí)，當(dāng)當(dāng)R/CR/CM/2M/2時(shí)采用平均分配方法，時(shí)采用平均分配方法， 當(dāng)當(dāng)R/CR/CM/2M/2時(shí)采用集中分配方法。時(shí)采用集中分配方法。)(2)(21221NiiNiiikMCNMRkMkCNMR總處理時(shí)間NM /NMM/mod)11 (22NMCNRM總處理時(shí)間26多處理機(jī)系統(tǒng)的加速比：一個(gè)計(jì)算問(wèn)題在一臺(tái)處理機(jī)一個(gè)計(jì)算問(wèn)題在一臺(tái)處理機(jī)上運(yùn)行時(shí)間與在多處理機(jī)系

18、統(tǒng)上運(yùn)行時(shí)間的比值上運(yùn)行時(shí)間與在多處理機(jī)系統(tǒng)上運(yùn)行時(shí)間的比值 當(dāng)M是N的倍數(shù)時(shí)，有：如果M和N較小，R/C較大，即分母中的第一項(xiàng)遠(yuǎn)大于第二項(xiàng)，則加速比與處理機(jī)臺(tái)數(shù)N成正比。當(dāng)處理機(jī)臺(tái)數(shù)N很大，加速比 ，趨近于一個(gè)常數(shù)。這時(shí)如果再增加處理機(jī)，性能的提高很小。21)222）（加速比NMCRNCRNMMCNRMRM)(2122NiikMCNMRRM加速比CMR22022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)27每個(gè)任務(wù)要和其它所有任務(wù)通信，而且通信的內(nèi)容相同。把M個(gè)任務(wù)分配給N臺(tái)處理機(jī)時(shí)，當(dāng)M是N的倍數(shù)時(shí)，很明顯，這個(gè)函數(shù)有一個(gè)極小值: 9.2.3 通信開(kāi)銷為線性函數(shù)的模型通信開(kāi)銷為線性函數(shù)的

19、模型CNNMR總處理時(shí)間CRMCN CNNMR總處理時(shí)間2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)28因此得到最小的總處理時(shí)間：這種模型的加速比為：當(dāng)M是N的倍數(shù)時(shí)，最大加速比為：RMCCRMCCCRMCRM2/總處理時(shí)間的最小值CRMCRMCRM22最大加速比CNNMRRM加速比由于通信與計(jì)算可以在兩個(gè)獨(dú)立的功能部件中進(jìn)行，由于通信與計(jì)算可以在兩個(gè)獨(dú)立的功能部件中進(jìn)行，因此，能夠采用重疊或流水線方式并行進(jìn)行。因此，能夠采用重疊或流水線方式并行進(jìn)行。一個(gè)理想模型，通信與計(jì)算完全重疊。對(duì)于兩臺(tái)處理機(jī)的系統(tǒng)：當(dāng)當(dāng)R/CM/2時(shí)，執(zhí)行時(shí)間與通信時(shí)間的交點(diǎn)就是總時(shí)，執(zhí)行時(shí)間與通信時(shí)間的交點(diǎn)就

20、是總處理時(shí)間的最小值；處理時(shí)間的最小值； 當(dāng)當(dāng)R/CM/2時(shí)，采用平均分配方法，在這一點(diǎn)運(yùn)行時(shí)，采用平均分配方法，在這一點(diǎn)運(yùn)行時(shí)間足夠長(zhǎng)，完全能夠屏蔽通信時(shí)間。時(shí)間足夠長(zhǎng)，完全能夠屏蔽通信時(shí)間。9.2.4 通信與計(jì)算完全重疊的模型通信與計(jì)算完全重疊的模型)(2,(122NiikMCNMRMax總處理時(shí)間 時(shí)時(shí)間間 時(shí)時(shí)間間 50 50 40 通信時(shí)間 40 總處理時(shí)間最小 30 30 20 執(zhí)行時(shí)間 20 執(zhí)行時(shí)間 10 總處理時(shí)間最小 10 通信時(shí)間 0 0 10 20 30 40 50 0 10 20 30 40 50通通信信與與計(jì)計(jì)算算完完全全重重疊疊的的模模型型直線與二次曲線的交點(diǎn)：R

21、(MK)C(MK)K即：KR/C （其中：1KM/2）總處理時(shí)間總處理時(shí)間R(MR/C)，兩臺(tái)處理機(jī)系統(tǒng)的加速比在1與2之間；當(dāng)R/CM/2，即把任務(wù)平均分配給兩臺(tái)處理機(jī)時(shí)，加速比最大；當(dāng)R/C逐漸減為1時(shí)，加速比也逐漸減為1，最優(yōu)分配變得越來(lái)越不均衡了。至于N臺(tái)處理機(jī)的系統(tǒng)：當(dāng)N比較大時(shí)，近似為：處理機(jī)數(shù)N由一個(gè)關(guān)于R/C和M的函數(shù)式 給出。CMR/11加速比)11 (22NCMNRM2NMCRCMRN22022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)32通信鏈路隨通信鏈路隨的增加而增加，讓每臺(tái)處理機(jī)與別的任的增加而增加，讓每臺(tái)處理機(jī)與別的任何一臺(tái)處理機(jī)都有專門的鏈路相連。何一臺(tái)處理機(jī)都

22、有專門的鏈路相連。當(dāng)任務(wù)數(shù)M是處理機(jī)數(shù)N的倍數(shù)時(shí)，盡可能平分任務(wù)可以使總處理時(shí)間達(dá)到最?。喊烟幚頇C(jī)臺(tái)數(shù)作為自變量，該函數(shù)有一個(gè)極大值9.2.5 具有多條通信鏈的模型具有多條通信鏈的模型）（總處理時(shí)間NiikMNCNMR1222)11 (22NNCMNRM總處理時(shí)間2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)33由于分母大于1，因此總處理時(shí)間的極大值出現(xiàn)在2時(shí),當(dāng)當(dāng)22時(shí)，隨著處理機(jī)臺(tái)時(shí)，隨著處理機(jī)臺(tái)增加，總處理時(shí)間肯定減小。增加，總處理時(shí)間肯定減小。為了驗(yàn)證N臺(tái)處理機(jī)是否比一臺(tái)處理機(jī)效果更佳： 相等點(diǎn)在：在相等點(diǎn)參數(shù)R/C與N成反比例，N越大，允許的粒度越小；N臺(tái)處理機(jī)的總性能等價(jià)于一

23、臺(tái)處理機(jī)。)11)(2(2NNCMNRMRMNMCR2CMRNNMCNMCNRMNNCMNRMN21202220)11 (22(322222022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)34總結(jié)上面幾個(gè)模型，可以得出如下結(jié)論：總結(jié)上面幾個(gè)模型，可以得出如下結(jié)論：(1)多處理機(jī)系統(tǒng)結(jié)構(gòu)所需的額外開(kāi)銷多處理機(jī)系統(tǒng)結(jié)構(gòu)所需的額外開(kāi)銷，包括調(diào)度，對(duì)共享資源的競(jìng)爭(zhēng)，同步，處理機(jī)之間通信等。(2)當(dāng)處理機(jī)臺(tái)數(shù)增加時(shí)，額外開(kāi)銷時(shí)間也增加當(dāng)處理機(jī)臺(tái)數(shù)增加時(shí)，額外開(kāi)銷時(shí)間也增加。有時(shí)，額外開(kāi)銷的增加可能比處理機(jī)數(shù)目的線性增加更快。(3)R/CR/C比值越大，越有利于計(jì)算過(guò)程比值越大，越有利于計(jì)算過(guò)程。如果采

24、用粗粒度，能夠獲得較大的R/C比值；但是并行程度將大為降低。(4)為了使價(jià)格和性能都比較合理，處理機(jī)數(shù)目存在一為了使價(jià)格和性能都比較合理，處理機(jī)數(shù)目存在一個(gè)極大值個(gè)極大值，這個(gè)值主要依賴于機(jī)器的系統(tǒng)結(jié)構(gòu)、基本技術(shù)（尤其是通信技術(shù)）和具體的應(yīng)用問(wèn)題。在并行處理機(jī)和多處理機(jī)系統(tǒng)中，采用局部在并行處理機(jī)和多處理機(jī)系統(tǒng)中，采用局部CacheCache會(huì)引起會(huì)引起CacheCache與共享存儲(chǔ)器之間的一與共享存儲(chǔ)器之間的一致性問(wèn)題。致性問(wèn)題。出現(xiàn)不一致性問(wèn)題的原因有三個(gè)：出現(xiàn)不一致性問(wèn)題的原因有三個(gè)：共享可寫的數(shù)據(jù)、進(jìn)程遷移、共享可寫的數(shù)據(jù)、進(jìn)程遷移、I/OI/O傳輸傳輸9.3 多處理機(jī)的多處理機(jī)的Ca

25、che一致性一致性1.寫共享數(shù)據(jù)引起的不一致性寫共享數(shù)據(jù)引起的不一致性使用多個(gè)局部使用多個(gè)局部Cache時(shí)，可能發(fā)生時(shí)，可能發(fā)生Cache不一致性問(wèn)題：不一致性問(wèn)題：當(dāng)P1把X的值寫為X之后，如果P1采用寫通過(guò)方式，內(nèi)存中的內(nèi)容也變?yōu)閄，但是P2處理機(jī)Cache中的內(nèi)容還是X。 如果P1采用寫回策法，內(nèi)存中的內(nèi)容還是X，當(dāng)P2處理機(jī)要讀X時(shí)，讀到的是X而不是X。9.3.1 問(wèn)題由來(lái)問(wèn)題由來(lái)處理機(jī) Cache 總線 共享 存儲(chǔ)器 更新之前 寫通過(guò)方式 寫回方式P1P2XXXP1P2XXXP1P2XXX2.進(jìn)程遷移引起的數(shù)據(jù)不一致性進(jìn)程遷移引起的數(shù)據(jù)不一致性P1和P2中都有共享數(shù)據(jù)X的拷貝，P2修

26、改了X，并采用寫通過(guò)方式，所以內(nèi)存中的X修改成了X。如果該進(jìn)程遷移到P1上，P1的Cache中仍然是X。P1中有共享數(shù)據(jù)X的拷貝，而P2中沒(méi)有該共享數(shù)據(jù)，P1進(jìn)程對(duì)X進(jìn)行了修改，如果該進(jìn)程遷移到了P2上，P2運(yùn)行時(shí)從內(nèi)存中讀到是X。處理機(jī) Cache 總線 共享 存儲(chǔ)器 更新之前 寫通過(guò)方式 寫回方式P1P2XXXP1P2XXXP1P2XXX3.I/O造成數(shù)據(jù)不一致性造成數(shù)據(jù)不一致性如果P1和P2在各自的局部Cache中都有X的拷貝，當(dāng)I/O將一個(gè)新數(shù)據(jù)X寫入存儲(chǔ)器時(shí)就導(dǎo)致存儲(chǔ)器和Cache的數(shù)據(jù)不一致。如果兩個(gè)局部Cache中都有X的拷貝，并采用寫回方式，當(dāng)P1把X修改成X之后；輸出部件讀X

27、，存儲(chǔ)器把X傳給輸出部件一種解決I/O操作引起數(shù)據(jù)不一致性的方法是把I/O處理機(jī)分別連接到各自的局部Cache上。處理機(jī) Cache 總線 存儲(chǔ)器 I/O 存儲(chǔ)器 輸入 存儲(chǔ)器 輸出 更新之前 寫通過(guò)方式 寫回方式P1P2XXXP1P2XXXP1P2XXXXX2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)39有兩類解決Cache不一致性問(wèn)題的協(xié)議：在總線互連的多處理機(jī)系統(tǒng)中，通常采在總線互連的多處理機(jī)系統(tǒng)中，通常采用用監(jiān)聽(tīng)協(xié)議監(jiān)聽(tīng)協(xié)議。在其他多處理機(jī)系統(tǒng)中，通常采用在其他多處理機(jī)系統(tǒng)中，通常采用基于基于目錄協(xié)議目錄協(xié)議。9.3.2 監(jiān)聽(tīng)協(xié)議監(jiān)聽(tīng)協(xié)議2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九

28、章 多處理機(jī)401.兩種監(jiān)聽(tīng)協(xié)議兩種監(jiān)聽(tīng)協(xié)議使用監(jiān)聽(tīng)協(xié)議，有兩種方法：方法一：方法一：寫無(wú)效（寫無(wú)效（Write InvalidateWrite Invalidate）策略）策略，在本地Cache的數(shù)據(jù)塊修改時(shí)使遠(yuǎn)程數(shù)據(jù)塊都無(wú)效。方法二：方法二：寫更新（寫更新（Write UpdateWrite Update）策略）策略，在本地Cache數(shù)據(jù)塊修改時(shí)通過(guò)總線把新的數(shù)據(jù)塊廣播給含該塊的所有其他Cache采用寫無(wú)效或?qū)懜虏呗耘cCache采用寫回方式（Write Back）還是寫通過(guò)方式（Write Through）無(wú)關(guān)。如果Cache采用的寫通過(guò)方式，在使遠(yuǎn)程數(shù)據(jù)塊無(wú)效或更新其他Cache的同時(shí)

29、，還要同時(shí)修改共享存儲(chǔ)器中的內(nèi)容。由于寫更新策略在本地Cache修改時(shí)需要通過(guò)總線把修改過(guò)的數(shù)據(jù)塊廣播給所有含該數(shù)據(jù)塊的其他Cache，增加了總線的負(fù)擔(dān)。大部分多處理機(jī)系統(tǒng)使用寫無(wú)效策略。處理機(jī) Cache 總線 共享 存儲(chǔ)器 更新之前 寫無(wú)效策略 寫更新策略P1P2XXXP1P2XIXP1P2XXX2.采用寫通過(guò)方式的采用寫通過(guò)方式的Cache數(shù)據(jù)塊有兩種狀態(tài): 有效和無(wú)效有效和無(wú)效。有效表示該數(shù)據(jù)塊內(nèi)容正確，兩種狀態(tài)的轉(zhuǎn)換如下圖：RL、WL表示本地處理機(jī)對(duì)Cache的讀和寫操作，RR、WR表示遠(yuǎn)程處理機(jī)對(duì)Cache中相同內(nèi)容數(shù)據(jù)的讀和寫操作。 RL,WLRL,WL RR,WR RR 有效

30、無(wú)效 WR2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)433.采用寫回方式的采用寫回方式的Cache只讀狀態(tài)只讀狀態(tài)表示整個(gè)系統(tǒng)中有多個(gè)數(shù)據(jù)塊拷貝是正確的，讀寫狀態(tài)讀寫狀態(tài)表示數(shù)據(jù)塊至少被修改過(guò)一次，存儲(chǔ)器中相應(yīng)數(shù)據(jù)塊還沒(méi)有修改，在整個(gè)系統(tǒng)中只有一個(gè)數(shù)據(jù)塊拷貝是正確的。對(duì)于只讀的數(shù)據(jù)塊，本地的和遠(yuǎn)程的讀操作都是安全的，本地的寫操作使?fàn)顟B(tài)轉(zhuǎn)移為讀寫，遠(yuǎn)程的寫操作使之變?yōu)闊o(wú)效。對(duì)于讀寫狀態(tài)的數(shù)據(jù)塊，本地的讀、寫操作都是安全的，而遠(yuǎn)程的讀操作將數(shù)據(jù)塊傳遞給遠(yuǎn)程處理機(jī)的Cache，使兩個(gè)Cache都轉(zhuǎn)移至只讀狀態(tài)，遠(yuǎn)程寫操作使遠(yuǎn)程處理機(jī)Cache轉(zhuǎn)移至讀寫狀態(tài)，而本地Cache轉(zhuǎn)移至無(wú)效狀態(tài)。

31、對(duì)于無(wú)效狀態(tài)，本地讀操作，使?fàn)顟B(tài)轉(zhuǎn)移至只讀；本地寫操作，使?fàn)顟B(tài)轉(zhuǎn)移至讀寫，同時(shí)使其他Cache中相應(yīng)數(shù)據(jù)塊轉(zhuǎn)移為無(wú)效狀態(tài)。 WLRL,WL RL,RR 讀 寫 只 讀 RR WL WR WR RL 無(wú) 效 RR, WR采采 用用 寫寫 回回 方方 式式 的的 C C a a c c h h e e 狀狀 態(tài)態(tài) 圖圖RL：本地處理機(jī)對(duì)Cache的讀操作WL：本地處理機(jī)對(duì)Cache的寫操作 RR：遠(yuǎn)程處理機(jī)對(duì)Cache中相同內(nèi)容數(shù)據(jù)的讀操作 WR：遠(yuǎn)程處理機(jī)對(duì)Cache中相同內(nèi)容數(shù)據(jù)的寫操作454.寫一次寫一次(Write-Once)協(xié)議協(xié)議方法：第一次寫第一次寫CacheCache采用寫通過(guò)方式

32、，采用寫通過(guò)方式， 以后采用寫回方式。以后采用寫回方式。為了區(qū)分第一次寫，把“讀寫”狀態(tài)分為：保留(Reserved)和重寫(Dirty)。共有4種狀態(tài)(1)有效有效(Valid, 相當(dāng)于寫回方式中的只讀)：(2)無(wú)效無(wú)效(Invalid)：在Cache中找不到或數(shù)據(jù)塊已作廢。(3)保留保留(Reserved)：數(shù)據(jù)從存儲(chǔ)器讀入Cache后只被寫過(guò)一次，Cache和存儲(chǔ)器中都正確。(4)重寫重寫(Dirty)：Cache中的數(shù)據(jù)塊被寫過(guò)多次，而且是唯一正確的數(shù)據(jù)塊。2022年6月25日46整個(gè)系統(tǒng)中只有一份正確的拷貝。整個(gè)系統(tǒng)中只有一份正確的拷貝。主要優(yōu)點(diǎn)主要優(yōu)點(diǎn)：減少大量的無(wú)效操作，提高了總

33、線減少大量的無(wú)效操作，提高了總線效率。效率。主要缺點(diǎn)主要缺點(diǎn)：當(dāng)主存儲(chǔ)器的內(nèi)容無(wú)效時(shí)當(dāng)主存儲(chǔ)器的內(nèi)容無(wú)效時(shí), ,讀缺失引讀缺失引起的總線讀操作必須禁止訪問(wèn)主存儲(chǔ)器，而起的總線讀操作必須禁止訪問(wèn)主存儲(chǔ)器，而大多數(shù)總線不支持這種操作大多數(shù)總線不支持這種操作IEEE Futurebus+總線支持該操作。47 RLRL,RR RR,WR 有效 無(wú)效 WR WL RR WL WR WR RL 保留 重寫 RL,WL WLRL：本地處理機(jī)對(duì)Cache的讀操作WL：本地處理機(jī)對(duì)Cache的寫操作 RR：遠(yuǎn)程處理機(jī)對(duì)Cache中相同內(nèi)容數(shù)據(jù)的讀操作 WR：遠(yuǎn)程處理機(jī)對(duì)Cache中相同內(nèi)容數(shù)據(jù)的寫操作CPUCP

34、U讀讀CacheCache：有兩種可能性。：有兩種可能性。 (1)數(shù)據(jù)塊在Cache中存在(包括有效、保留或重寫)，CPU直接讀取數(shù)據(jù)。 (2)Cache中的數(shù)據(jù)塊處于無(wú)效狀態(tài)。 如果存在處于有效、保留或重寫狀態(tài)的相應(yīng)數(shù)據(jù)塊，則將其調(diào)入本地Cache；在相應(yīng)數(shù)據(jù)塊處于重寫狀態(tài)時(shí)，還要同時(shí)禁止存儲(chǔ)器操作。 如果不存在處于有效、保留或重寫狀態(tài)的相應(yīng)數(shù)據(jù)塊，則直接從存儲(chǔ)器中讀入(只有存儲(chǔ)器中是唯一正確的拷貝)。 把讀入Cache中的相應(yīng)數(shù)據(jù)塊置為“有效”狀態(tài)。CPUCPU寫寫CacheCache：也有兩種可能。：也有兩種可能。 (1)寫命中，當(dāng)Cache處于“有效”狀態(tài)時(shí)，采用寫通過(guò)方式，把寫入Ca

35、che的內(nèi)容同時(shí)寫入存儲(chǔ)器，將Cache的狀態(tài)轉(zhuǎn)移為“保留”，將其他Cache的相應(yīng)數(shù)據(jù)塊狀態(tài)置為“無(wú)效”； 當(dāng)Cache處于“保留”或“重寫”態(tài)時(shí)，使用寫回方式，Cache的狀態(tài)轉(zhuǎn)移至“重寫”,其他的存有相同內(nèi)容的Cache處于“無(wú)效”態(tài)。 (2)寫不命中，將數(shù)據(jù)塊調(diào)入Cache，采用寫通過(guò)方式,同時(shí)寫存儲(chǔ)器;將本地Cache的狀態(tài)置為“保留”，同時(shí)將其他Cache的狀態(tài)置為“無(wú)效”。 在非總線結(jié)構(gòu)的多處理機(jī)系統(tǒng)中，采用基于目錄的在非總線結(jié)構(gòu)的多處理機(jī)系統(tǒng)中，采用基于目錄的CacheCache一致一致性協(xié)議。性協(xié)議。1.Cache目錄結(jié)構(gòu)目錄結(jié)構(gòu)Cache目錄中存放的內(nèi)容是大量的指針，用以指

36、明塊拷貝的地址，每個(gè)目錄項(xiàng)還有一個(gè)重寫位，指明是否有一個(gè)Cache允許寫入數(shù)據(jù)。根據(jù)Cache目錄的存放形式，有集中式和分布式兩種有集中式和分布式兩種。根據(jù)目錄的結(jié)構(gòu)，目錄協(xié)議分成三類：全映射全映射(Full-Map)(Full-Map)目錄目錄：存放全局存儲(chǔ)器每個(gè)塊的有關(guān)數(shù)據(jù)。有限有限(Limited)(Limited)目錄目錄：每個(gè)目錄項(xiàng)的指針數(shù)固定。鏈?zhǔn)芥準(zhǔn)?Chained)(Chained)目錄目錄：把目錄分布到所有Cache中。9.3.3 基于目錄的協(xié)議基于目錄的協(xié)議目錄的使用規(guī)則目錄的使用規(guī)則： 當(dāng)一個(gè)CPU對(duì)Cache進(jìn)行寫操作時(shí)，要根據(jù)Cache目錄中的內(nèi)容將所有其他存有相同內(nèi)

37、容的所有Cache拷貝無(wú)效，并置重寫位。 在CPU對(duì)Cache進(jìn)行讀操作時(shí)，如果讀命中，澤直接讀Cache即可。 如果重寫位為“0”，則從主存或其他Cache中讀入該塊，并修改目錄。2.全映射目錄全映射目錄目錄項(xiàng)中有目錄項(xiàng)中有N個(gè)處理機(jī)位和一個(gè)重寫位。個(gè)處理機(jī)位和一個(gè)重寫位。處理機(jī)位表示相應(yīng)處理機(jī)對(duì)應(yīng)的Cache塊的狀態(tài)。只有一個(gè)處理機(jī)的重寫位為“1”，則該處理機(jī)可以對(duì)該塊進(jìn)行寫操作。Cache的每個(gè)數(shù)據(jù)塊有兩個(gè)狀態(tài)位。一位表示數(shù)據(jù)塊是否有效，另一位表示有效塊是否允許寫。 讀X 讀X 讀X 寫X (a)所有Cache中 都沒(méi) 有X的拷 貝 (b)三個(gè) 處理 機(jī)都 有X的拷 貝 (c) P3處理

38、 機(jī)獲 得對(duì)X的 寫權(quán)P 1P 2P 3Cache1Cache2Cache3 X: 共享存儲(chǔ)器C000 數(shù)據(jù)P 1P 2P 3Cache1X：數(shù)據(jù)Cache2X：數(shù)據(jù)Cache3X：數(shù)據(jù) X: 共享存儲(chǔ)器0111 數(shù)據(jù)P 1P 2P 3Cache1Cache2Cache3X：數(shù)據(jù) X: 共享存儲(chǔ)器1001 數(shù)據(jù)53從第二種狀態(tài)從第二種狀態(tài)(b)轉(zhuǎn)移至第三種狀態(tài)轉(zhuǎn)移至第三種狀態(tài)(c)的過(guò)程如下的過(guò)程如下：(1)Cache3發(fā)現(xiàn)包含X單元的塊有效，但不允許寫(2)Cache3向包含X單元的存儲(chǔ)器模塊發(fā)寫請(qǐng)求，并暫停P3工作(3)該存儲(chǔ)器模塊發(fā)無(wú)效請(qǐng)求至Cache1和Cache2(4)Cache1和

39、Cache2接到無(wú)效請(qǐng)求后，將對(duì)應(yīng)塊置為無(wú)效態(tài)，并發(fā)回答信號(hào)給存儲(chǔ)器模塊。(5)存儲(chǔ)器模塊接到Cache1和Cache2的回答信號(hào)后，置重寫位為“1”，清除指向Cache1和Cache2的指針，發(fā)允許寫信號(hào)到Cache3。(6)Cache3接到允許寫信號(hào)，更新Cache狀態(tài)，激活P3。優(yōu)點(diǎn)：全映射目錄協(xié)議的效率比較高效率比較高。缺點(diǎn)：開(kāi)銷與處理機(jī)數(shù)目的平方成正比，開(kāi)銷與處理機(jī)數(shù)目的平方成正比， 不具有擴(kuò)展性。不具有擴(kuò)展性。3.有限目錄有限目錄當(dāng)處理機(jī)數(shù)目為N時(shí)，限制目錄大小為限制目錄大小為O(N log2 N)。目錄指針需要對(duì)N進(jìn)行二進(jìn)制編碼，每個(gè)指針占log2 N位，目錄所占的總存儲(chǔ)空間與（

40、Nlog2 N）成正比。當(dāng)Cache1和Cache2中都有X的拷貝時(shí)，若P3請(qǐng)求訪問(wèn)X，則必須在在Cache1和Cache2中選擇一個(gè)使之無(wú)效，這種替換過(guò)程稱為驅(qū)逐。有限目錄的驅(qū)逐需要一種驅(qū)逐策略，驅(qū)逐策略的好壞對(duì)系統(tǒng)的性能具有很大的影響。驅(qū)逐策略與Cache替換策略在很多方面是相同的。 讀X (a) (b)有有限限目目錄錄的的驅(qū)驅(qū)逐逐P1P2P3Cache1X：數(shù)據(jù)Cache2X：數(shù)據(jù)Cache3 X:共享存儲(chǔ)器C數(shù)據(jù)P1P2P3Cache1X：數(shù)據(jù)Cache2Cache3X：數(shù)據(jù) X:共享存儲(chǔ)器C數(shù)據(jù)2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)564. 鏈?zhǔn)侥夸涙準(zhǔn)侥夸?通過(guò)維護(hù)一

41、個(gè)目錄指針鏈來(lái)跟蹤共享數(shù)據(jù)拷貝。通過(guò)維護(hù)一個(gè)目錄指針鏈來(lái)跟蹤共享數(shù)據(jù)拷貝。當(dāng)P1讀X時(shí)，存儲(chǔ)器送X到Cache1,同時(shí)寫Cache1的一個(gè)鏈結(jié)束指針CT，在存儲(chǔ)器中也保存一個(gè)指向Cache1的指針。當(dāng)P2讀X時(shí)，存儲(chǔ)器送X給Cache2, 同時(shí)給Cache2一個(gè)指向Cache1的指針,存儲(chǔ)器則保存一個(gè)指向Cache2的指針。當(dāng)某一處理機(jī)需要寫X時(shí),它必須沿整個(gè)目錄鏈發(fā)送一個(gè)數(shù)據(jù)無(wú)效信息。在收到所有處理機(jī)的回答信號(hào)之后，存儲(chǔ)器才給該處理機(jī)寫允許權(quán)。57當(dāng)Cache中的數(shù)據(jù)塊需要替換時(shí)，要把該Cache從目錄鏈中刪除。有如下解決辦法： (1)把Cachei+1的指針指向Cachei-1。在Cach

42、ei中存放新數(shù)據(jù)塊。 (2)使Cachei及在鏈中位于其后的所有Cache中的單元X無(wú)效。 (3)使用雙向鏈。在替換時(shí)不再需要遍歷整個(gè)鏈。但指針增加了一倍，一致性協(xié)議也更加復(fù)雜。優(yōu)點(diǎn)：不限制共享數(shù)據(jù)塊的拷貝數(shù)目，又保持了可擴(kuò)不限制共享數(shù)據(jù)塊的拷貝數(shù)目，又保持了可擴(kuò)展性。展性。指針的長(zhǎng)度以處理機(jī)數(shù)目的對(duì)數(shù)關(guān)系增長(zhǎng)，Cache的每個(gè)數(shù)據(jù)塊的指針數(shù)目與處理機(jī)數(shù)目無(wú)關(guān)。缺點(diǎn)：鏈?zhǔn)侥夸浀膹?fù)雜程度超過(guò)了前兩種目錄。鏈?zhǔn)侥夸浀膹?fù)雜程度超過(guò)了前兩種目錄。 讀X 寫X (a) (b)鏈鏈 式式 目目 錄錄P1P2P3Cache1X： 數(shù)據(jù)Cache2Cache3 X:共享存儲(chǔ)器C數(shù)據(jù)CTP1P2P3Cache3

43、 X:共享存儲(chǔ)器C數(shù)據(jù)Cache1X： 數(shù)據(jù) CTCache2X： 數(shù)據(jù)9.4 大規(guī)模并行處理機(jī)大規(guī)模并行處理機(jī)多處理機(jī)系統(tǒng)主要有四大類：多處理機(jī)系統(tǒng)主要有四大類：(1)多向量處理機(jī)系統(tǒng)：多向量處理機(jī)系統(tǒng)：如CRAY YMP-90，NEC SX-3和FUJITSU VP-2000(2)SMP(Symmetry MultiProcessors)對(duì)稱多處理機(jī)對(duì)稱多處理機(jī) SMP(Shared Memory mulptiProcessors)共享存儲(chǔ)多處理機(jī) 如SGI Challenge、Sun SparcCenter 2000(3)MPP(massively parallel processing

44、)大規(guī)模并行處理大規(guī)模并行處理機(jī)機(jī) 如Intel Paragon，CM-5，Cray T3D(4)Cluster 機(jī)群系統(tǒng)機(jī)群系統(tǒng)（NOW或COM）1. 科學(xué)計(jì)算中的重大課題要求提供科學(xué)計(jì)算中的重大課題要求提供3T性能：性能：(1) 1Teraflops計(jì)算能力(2) 1Terabyte主存儲(chǔ)器(3) 1Terabyte/s 輸入輸出頻帶寬度目前，速度還慢1000倍左右，存儲(chǔ)容量和I/O帶寬差距更大?？茖W(xué)計(jì)算中的重大課題：全球氣候預(yù)報(bào), 基因工程 ,飛行動(dòng)力學(xué) ,海洋環(huán)流, 流體動(dòng)力學(xué), 超導(dǎo)建模, 半導(dǎo)體建模, 量子染色動(dòng)力學(xué), 視覺(jué)2. 采用的關(guān)鍵技術(shù)：采用的關(guān)鍵技術(shù)：VLSI, 可擴(kuò)展技

45、術(shù), 共享虛擬存儲(chǔ)技術(shù)虛擬共享存儲(chǔ)器(Shared Virtual Memory)也稱為共享分布存儲(chǔ)器(Distributed Shared Memory)；物理上分布存儲(chǔ)器，邏輯上共享的存儲(chǔ)器。虛擬共享存儲(chǔ)器的優(yōu)點(diǎn)：編程容易編程容易, 系統(tǒng)結(jié)構(gòu)靈活系統(tǒng)結(jié)構(gòu)靈活可擴(kuò)充性好可擴(kuò)充性好, 有較好的軟件移植性有較好的軟件移植性與消息傳遞方式相比，程序運(yùn)行效率高，主要原因： (1)數(shù)據(jù)塊緩存在本地, 可以多次使用(2)通信時(shí)間分散，提高了并行性(3)擴(kuò)大存儲(chǔ)空間，減少換頁(yè)操作虛擬共享存儲(chǔ)器實(shí)現(xiàn)途徑：虛擬共享存儲(chǔ)器實(shí)現(xiàn)途徑：(1)硬件實(shí)現(xiàn)硬件實(shí)現(xiàn), 利用Cache,需要增加專用硬件(2)操作系統(tǒng)和庫(kù)實(shí)現(xiàn)

46、操作系統(tǒng)和庫(kù)實(shí)現(xiàn)，通過(guò)虛擬存儲(chǔ)機(jī)制取得共享和一致性。在松耦合的分布存儲(chǔ)多處理機(jī)上，不需要增加任何硬件(3)編譯實(shí)現(xiàn)編譯實(shí)現(xiàn)，自動(dòng)將共享訪問(wèn)轉(zhuǎn)換成同步和一致原語(yǔ)。大多數(shù)系統(tǒng)采用途徑(1)和(2)，或這兩種途徑結(jié)合實(shí)現(xiàn)3. 同步同步MIMD機(jī)器機(jī)器 SIMD與與MIMD的優(yōu)點(diǎn)結(jié)合在一起。的優(yōu)點(diǎn)結(jié)合在一起。 CM-5同時(shí)支持SIMD與MIMD兩種并行計(jì)算方式。 數(shù)據(jù)并行可以采用數(shù)據(jù)并行可以采用SIMD、多、多SIMD或同步或同步MIMD模式。模式。 32到16384個(gè)處理器結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有一個(gè)SPARC處理機(jī)，32MB存儲(chǔ)器，64位浮點(diǎn)和整數(shù)操作，128Mflops向量處理部件 處處 理理 機(jī)機(jī) 結(jié)

47、結(jié) 點(diǎn)點(diǎn) 控控制制處處理理機(jī)機(jī) I/O接接口口控控 制制 網(wǎng)網(wǎng) 格格數(shù)數(shù) 據(jù)據(jù) 網(wǎng)網(wǎng) 格格診診斷斷網(wǎng)網(wǎng)格格NIPMNIPMNIPMNIPMNIPMNINII/OI/O 三個(gè)網(wǎng)絡(luò)：三個(gè)網(wǎng)絡(luò)：數(shù)據(jù)網(wǎng)絡(luò)數(shù)據(jù)網(wǎng)絡(luò)提供點(diǎn)對(duì)點(diǎn)通信?？刂凭W(wǎng)絡(luò)控制網(wǎng)絡(luò)提供廣播、同步、掃描和系統(tǒng)管理功能。診斷網(wǎng)絡(luò)診斷網(wǎng)絡(luò)從后臺(tái)訪問(wèn)所有系統(tǒng)硬件，測(cè)試系統(tǒng)完整性，檢測(cè)和隔離錯(cuò)誤。數(shù)據(jù)網(wǎng)絡(luò)和控制網(wǎng)絡(luò)有很好的可擴(kuò)展性。 可以劃分成一個(gè)或多個(gè)分區(qū)供用戶使用可以劃分成一個(gè)或多個(gè)分區(qū)供用戶使用每個(gè)分區(qū)一臺(tái)控制處理機(jī)，一組處理結(jié)點(diǎn)，數(shù)據(jù)和控制網(wǎng)絡(luò)的專用部分。4. CM-5網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu) 數(shù)據(jù)網(wǎng)絡(luò)采用胖樹(shù)型網(wǎng)數(shù)據(jù)網(wǎng)絡(luò)采用胖樹(shù)型網(wǎng)，數(shù)據(jù)處理結(jié)點(diǎn)

48、、控制處理機(jī)和I/O通道都位于胖樹(shù)的葉子上。 利用胖樹(shù)的層次結(jié)構(gòu)特性，可以劃分一棵子利用胖樹(shù)的層次結(jié)構(gòu)特性，可以劃分一棵子樹(shù)給一個(gè)用戶樹(shù)給一個(gè)用戶。采用4元胖樹(shù)實(shí)現(xiàn)，每個(gè)內(nèi)部開(kāi)關(guān)結(jié)點(diǎn)由n個(gè)尋徑器芯片組成。每個(gè)尋徑器與4個(gè)子芯片和2或4個(gè)父芯片相連。 可以分配不同的子樹(shù)處理不同的作業(yè)，子樹(shù)可以分配不同的子樹(shù)處理不同的作業(yè)，子樹(shù)的大小可以任意。的大小可以任意。 每臺(tái)處理機(jī)與數(shù)據(jù)網(wǎng)絡(luò)有兩條連接通路。用用四四元元胖胖樹(shù)樹(shù)實(shí)實(shí)現(xiàn)現(xiàn)的的CM-5數(shù)數(shù)據(jù)據(jù)網(wǎng)網(wǎng)絡(luò)絡(luò)5. 控制處理機(jī)控制處理機(jī)控制處理機(jī)由CPU、存儲(chǔ)器、本地磁盤、網(wǎng)絡(luò)接口、以太網(wǎng)組成。它相當(dāng)于一臺(tái)標(biāo)準(zhǔn)工作站。網(wǎng)絡(luò)接口通過(guò)控制網(wǎng)絡(luò)和數(shù)據(jù)網(wǎng)絡(luò)使處理機(jī)

49、與系統(tǒng)的其它部分相連。控制處理機(jī)專門執(zhí)行管理功能，不需要高性能的運(yùn)算部件。每臺(tái)控制處理機(jī)都能夠運(yùn)行操作系統(tǒng)，負(fù)責(zé)并行處理資源的管理。一部分控制處理機(jī)管理用戶區(qū)的計(jì)算資源，其它管理I/O資源。 數(shù)數(shù) 據(jù)據(jù) 網(wǎng)網(wǎng) 絡(luò)絡(luò) 控控 制制 網(wǎng)網(wǎng) 絡(luò)絡(luò)標(biāo)標(biāo) 準(zhǔn)準(zhǔn) 工工 作作 站站 本本 地地 網(wǎng)網(wǎng) 絡(luò)絡(luò)存存 儲(chǔ)儲(chǔ) 器器網(wǎng)網(wǎng) 絡(luò)絡(luò) 接接 口口CPUI OI/O6.處理結(jié)點(diǎn)處理結(jié)點(diǎn)通過(guò)控制網(wǎng)絡(luò)和數(shù)據(jù)網(wǎng)絡(luò)將結(jié)點(diǎn)與系統(tǒng)的其它部分相連。每個(gè)向量部件有一個(gè)流水ALU和64個(gè)64位的寄存器。每條向量指令可傳送給一個(gè)向量部件、或一對(duì)向量部件、或同時(shí)廣播給所有4個(gè)向量部件。標(biāo)量處理機(jī)負(fù)責(zé)地址轉(zhuǎn)換和循環(huán)控制，向量處理部件的操作

50、與標(biāo)量處理部件并行執(zhí)行。16384個(gè)處理結(jié)點(diǎn)的總峰值速度為：21427221 Mflops=2Tflops 數(shù)數(shù)據(jù)據(jù)網(wǎng)網(wǎng) 絡(luò)絡(luò) 控控 制制網(wǎng)網(wǎng)絡(luò)絡(luò) 64 位位總總 線線 64 位位總總 線線CM-5 的的 處處 理理 機(jī)機(jī) 結(jié)結(jié) 點(diǎn)點(diǎn)CPU網(wǎng)網(wǎng) 絡(luò)絡(luò) 接接 口口存存 儲(chǔ)儲(chǔ) 器器存存 儲(chǔ)儲(chǔ) 控控 制制器器存存 儲(chǔ)儲(chǔ) 器器存存 儲(chǔ)儲(chǔ) 器器存存 儲(chǔ)儲(chǔ) 器器 數(shù)數(shù)據(jù)據(jù)網(wǎng)網(wǎng)絡(luò)絡(luò) 控控制制網(wǎng)網(wǎng)絡(luò)絡(luò) 64 位位總總線線CM-5 中中帶帶向向量量部部件件的的處處理理機(jī)機(jī)結(jié)結(jié)點(diǎn)點(diǎn)標(biāo)標(biāo)量量處處理理機(jī)機(jī)網(wǎng)網(wǎng)絡(luò)絡(luò)接接口口存存儲(chǔ)儲(chǔ)器器存存儲(chǔ)儲(chǔ)器器存存儲(chǔ)儲(chǔ)器器存存儲(chǔ)儲(chǔ)器器向向量量部部件件向向量量部部件件向向量量部部件件向

51、向量量部部件件9.5 對(duì)稱多處理機(jī)對(duì)稱多處理機(jī)對(duì)稱多處理機(jī) (Symmetry MultiProcessors) 共享存儲(chǔ)多處理機(jī) (Shared Memory mulptiProcessors)，有，有三種模型：三種模型：1. UMA多處理機(jī)多處理機(jī)均勻存儲(chǔ)器存取模型 (Uniform Memory Access), 存儲(chǔ)器被所有處理機(jī)均勻共享所有處理機(jī)對(duì)所有存儲(chǔ)單元具有相同的存取時(shí)間, 每臺(tái)處理機(jī)有局部Cache外圍設(shè)備可以共享 UMA多多處處理理機(jī)機(jī)模模型型P1P2Pn系系統(tǒng)統(tǒng)互互連連網(wǎng)網(wǎng)絡(luò)絡(luò)（總總線線、交交叉叉開(kāi)開(kāi)關(guān)關(guān)、多多級(jí)級(jí)網(wǎng)網(wǎng)絡(luò)絡(luò)）SM1SM2SMmI/O2. NUMA多處理機(jī)多

52、處理機(jī)非均勻存儲(chǔ)器存取 (Nonuniform Memory Access)模型存儲(chǔ)器訪問(wèn)時(shí)間隨存儲(chǔ)單元的位置不同而變化。共享存儲(chǔ)器在物理上是分布在所有處理機(jī)中的本地存儲(chǔ)器。所有局部存儲(chǔ)器地址空間的集合就組成了全局地址空間。處理機(jī)訪問(wèn)本地存儲(chǔ)器比較快，訪問(wèn)屬于另一臺(tái)處理機(jī)的遠(yuǎn)程存儲(chǔ)器則比較慢，因?yàn)橥ㄟ^(guò)互連網(wǎng)絡(luò)會(huì)產(chǎn)生附加的時(shí)間延遲。 P1P2Pn系系統(tǒng)統(tǒng)互互連連網(wǎng)網(wǎng)絡(luò)絡(luò)LM1LM2LMm只有Cache的存儲(chǔ)器結(jié)構(gòu) (Cache-Only Memory Architecture) 模型；COMA是一種只用Cache的多處理機(jī)系統(tǒng)實(shí)際上，COMA模型是NUMA模型的一種特例，后者分布存儲(chǔ)器換成了Ca

53、che在每個(gè)處理機(jī)結(jié)點(diǎn)上沒(méi)有主存儲(chǔ)器，全部Cache組成了全局虛擬地址空間遠(yuǎn)程Cache訪問(wèn)通過(guò)分布Cache目錄進(jìn)行共享存儲(chǔ)系統(tǒng)擁有統(tǒng)一的尋址空間，程序員不必參與數(shù)據(jù)分配和傳輸。3. COMA多處理機(jī)多處理機(jī) D1D2Dn互互 連連 網(wǎng)網(wǎng) 絡(luò)絡(luò)Cache1Cache2Cachen12n 1996年SGI公司的Origin 2000服務(wù)器，首先采用S2MP并行體系結(jié)構(gòu) S2MP實(shí)際上是NUMA多處理機(jī)系統(tǒng)，采用分布存儲(chǔ)器，并通過(guò)cache對(duì)系統(tǒng)的共享和局部數(shù)據(jù)都進(jìn)行緩存。從用戶編程角度看，S2MP是一種共享存儲(chǔ)的多處理機(jī)系統(tǒng)。 S2MP的主要特點(diǎn)的主要特點(diǎn)：(1)編程容易編程容易，使用方便。(

54、2)可擴(kuò)展性好可擴(kuò)展性好，增加處理器數(shù)目容易。(3)通信開(kāi)銷小，可開(kāi)發(fā)程序的細(xì)粒度并行性4. S2MP結(jié)構(gòu)結(jié)構(gòu) S2MP的關(guān)鍵技術(shù)的關(guān)鍵技術(shù)：(1)高速無(wú)阻塞互連網(wǎng)絡(luò)高速無(wú)阻塞互連網(wǎng)絡(luò)，增加多處理機(jī)系統(tǒng)的通信帶寬。(2)分布式存儲(chǔ)器分布式存儲(chǔ)器，隨處理器數(shù)目的增加自動(dòng)增加存儲(chǔ)器帶寬。(3)引入引入cache，降低訪存時(shí)延。(4)所有存儲(chǔ)器統(tǒng)一編址所有存儲(chǔ)器統(tǒng)一編址，提供單一的大容量地址空間。(5)每個(gè)處理器結(jié)點(diǎn)上有一個(gè)目錄存儲(chǔ)器，維護(hù)cache一致性。 P ： 處 理 機(jī) ， C ： Cache， M ： 主 存 儲(chǔ) 器 ， D ： 目 錄 存 儲(chǔ) 器S2M P 體體 系系 結(jié)結(jié) 構(gòu)構(gòu) 示示

55、意意 圖圖高高 速速 互互 連連 網(wǎng)網(wǎng) 絡(luò)絡(luò)M 1C 1 1D 1M 2C 2 2D 2M nC n nD n2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)825. SGI Origin2000系列服務(wù)器系列服務(wù)器Origin 2000將將SMP、MPP、Cluster的優(yōu)點(diǎn)結(jié)合起來(lái)的優(yōu)點(diǎn)結(jié)合起來(lái)SMP易編程，MPP可擴(kuò)展性，Cluster可用性好。有4種機(jī)型：Origin 2000，塔式系統(tǒng)，最多4個(gè)處理器。Origin 2000 Deskside，桌邊服務(wù)器，最多8個(gè)處理器Origin 2000 Rack，機(jī)柜服務(wù)器，最多為16個(gè)處理器Cray Origin 2000，支持128個(gè)處

56、理器。Origin 2000是S2MP結(jié)構(gòu)的典型實(shí)現(xiàn)，地址空間成指數(shù)增長(zhǎng)，連續(xù)可擴(kuò)展，地址空間成指數(shù)增長(zhǎng)，連續(xù)可擴(kuò)展，最多可擴(kuò)展至1024個(gè)處理器，具有高帶寬和低時(shí)延2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)83關(guān)鍵技術(shù)：Cray LinkCray Link多重交叉開(kāi)關(guān)互連技術(shù)多重交叉開(kāi)關(guān)互連技術(shù)Cellular IRIXCellular IRIX蜂窩式操作系統(tǒng)蜂窩式操作系統(tǒng)Origin 2000Origin 2000系列服務(wù)器結(jié)構(gòu)：系列服務(wù)器結(jié)構(gòu)：(1) 結(jié)點(diǎn)板結(jié)點(diǎn)板每個(gè)結(jié)點(diǎn)板（主板）有一到兩個(gè)R10000處理器、二級(jí)cache、主存儲(chǔ)器、錄存儲(chǔ)器、HUB、I/O接口、互連網(wǎng)絡(luò)路由

57、器接口。2022年6月25日計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第九章 多處理機(jī)84R10000Secondarycache1MB/4MBR10000Secondarycache1MB/4MB780MB/S peakMain MemoryDirectoryMemoryBX ASICHUB ASICAddress/ControlDirectory dataDirectory address/control780MB/S peak780MB/S780MB/SRouter780MB/SXIO780MB/S(1) 結(jié)點(diǎn)板結(jié)點(diǎn)板(2) HUB結(jié)構(gòu)結(jié)構(gòu)四個(gè)雙向端口，每個(gè)端口的雙工帶寬1.6GB/S分別與處理器、主存、XIO和

58、互連網(wǎng)絡(luò)連接在內(nèi)部以交叉開(kāi)關(guān)互連。Processor InterfaceMemory/DirectoryInterfaceI/O InterfaceInterconnection FabricOutputFIFOInputFIFOInputFIFOOutputFIFOOutputFIFOInputFIFOInputFIFOOutputFIFOAsynch/SynchInterfaceAsynchInterface(3) 存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)有一個(gè)統(tǒng)一的共享地址空間，存儲(chǔ)系統(tǒng)共分為四個(gè)層次：第一層：寄存器堆，訪問(wèn)延遲時(shí)間最短；第二層：cache,主cache在CPU芯片上,二級(jí)cache在結(jié)點(diǎn)板上；

59、第三層：本地存儲(chǔ)器，包括主存儲(chǔ)器和目錄存儲(chǔ)器；第四層：遠(yuǎn)程cache，用于減少訪問(wèn)共享存儲(chǔ)器所需的時(shí)間。(4)(4)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)是一組開(kāi)關(guān)組成，稱為路由器；允許多個(gè)傳輸同時(shí)發(fā)生；速度極高，每條鏈路帶寬達(dá)到1.6GB/S；互連網(wǎng)絡(luò)不需要仲裁，也不存在競(jìng)爭(zhēng)；路由器的核心是6路全交叉開(kāi)關(guān)。峰值通信帶寬9.6GB/S。CrossbarReceiverSenderLLPSSD/SSRReceiverSenderLLPSSD/SSRReceiverSenderLLPSSD/SSRReceiverSenderLLPSSD/SSRReceiverSenderLLPSSD/SSRReceiverSe

60、nderLLPSSD/SSR(5) 擴(kuò)展連接方式：擴(kuò)展連接方式：可構(gòu)成 4, 16, 32, 64, 128個(gè)處理器的互連拓?fù)浣Y(jié)構(gòu)。兩個(gè)結(jié)點(diǎn)板通過(guò)HUB直接連接得到4個(gè)處理器。由于路由器提供了兩條連接結(jié)點(diǎn)板的鏈路，由一個(gè)路由器和兩個(gè)結(jié)點(diǎn)板構(gòu)成一個(gè)模塊，利用路由器的其他4個(gè)接口可以擴(kuò)展到不同的規(guī)模。使用其中的2條鏈路，可以連接16個(gè)處理器。使用其中的3條鏈路，形成一個(gè)立方體，可以連接32個(gè)處理器。使用4條鏈路，構(gòu)成一個(gè)4維超立方體，可以連接64個(gè)處理器。采用Cray Router，最大配置可以達(dá)到128個(gè)處理器。HPP4個(gè)處理器HPP16個(gè)處理器= NRNNRNNRNNRNN32個(gè)處理器RNNR