【文章內(nèi)容簡介】 T5執(zhí)行完后， T6繼續(xù)執(zhí)行。這樣， T5， T6， T7僅在 1 .5個時間單元中完成。 P1和 P2得到充分利用 動態(tài)隨機(jī)性調(diào)度又稱為非確定性調(diào)度，在運行過程中對資源進(jìn)行動態(tài)分配，即把等待處理的任務(wù)分配給空閑的處理機(jī)。常用分配算法有隨機(jī)數(shù)法和巡回分配法。動態(tài)調(diào)度可以較充分地利用處理機(jī)資源，使所有處理機(jī)最大限度地發(fā)揮作用。但是由于任務(wù)的執(zhí)行時間不能事先知道，因此要求系統(tǒng)隨時監(jiān)視所有處理機(jī)的狀態(tài)。無疑，系統(tǒng)開銷大，算法復(fù)雜。 并行多處理機(jī)的發(fā)展趨勢 大規(guī)模并行處理機(jī) MPP機(jī)舉例 共享存儲器型多處理機(jī) 并行向量處理機(jī) 機(jī)群 并行多處理機(jī)除了上述介紹的同構(gòu)對稱型緊耦合多處理機(jī)、異構(gòu)非對稱型緊耦合多處理機(jī)以及各種松耦合多處理機(jī)之外，發(fā)展較快的還有大規(guī)模并行處理機(jī)、并行向量處理機(jī)以及工作站機(jī)群等。 大規(guī)模并行處理機(jī) 大規(guī)模并行處理機(jī) MPP（ Massively Parallel Processor） 是指規(guī)?？缮炜s，常擁有百計、千計甚至萬計的處理機(jī)的系統(tǒng)。在早期多屬于SIMD計算機(jī)，以后逐步成為 MIMD計算機(jī)。 1. MPP主要特點 ① MPP系統(tǒng)最突出的特點就是進(jìn)行大型并行處理，即并行處理能力強(qiáng)，在結(jié)構(gòu)上表現(xiàn)為很強(qiáng)的規(guī)?？缮炜s性。 ② 其中每一臺處理機(jī)的功能都很強(qiáng)，相對獨立，且有較大容量的存儲器，有利于系統(tǒng)的伸縮性。這在結(jié)構(gòu)上，擬采用分布式存儲器系統(tǒng)。 ③ 采用分布式存儲器系統(tǒng)，每一臺處理機(jī)不能直接訪問非本地存儲器，因此在各處理機(jī)之間常采用消息傳送方式。故此可在分布式存儲器系統(tǒng)的基礎(chǔ)上構(gòu)建共享虛擬存儲器 SVM， 系統(tǒng)結(jié)構(gòu)靈活，易于編程，易于擴(kuò)展，使軟件有較好的可移植性。 2. SVM構(gòu)成方式 SVM（ Shared virtual memory） 的構(gòu)成方式可以用軟件來實現(xiàn)，也可以用硬件來實現(xiàn)。 （ 1）軟件構(gòu)成 軟件構(gòu)成方式是用程序把分配在各處理機(jī)上的存儲器連接起來，統(tǒng)一編址。采用純軟件方式進(jìn)行管理，若發(fā)生缺頁，置換頁可能來自外存，也可能來自其它處理機(jī)的局部存儲器。為保證頁的一致性，軟件開銷較大。 （ 2）硬件構(gòu)成硬件構(gòu)成有兩種形式，一種是部分 Cache形式，另一種是全 Cache形式。部分 Cache是將傳統(tǒng)的 Cache技術(shù)應(yīng)用到松耦合分布式存儲器系統(tǒng)中，即在每一個處理機(jī)中設(shè)置一個大容量的 Cache和有關(guān)保證一致性的部件。 圖 全 Cache存儲器結(jié)構(gòu) 全 Cache結(jié)構(gòu)是指所有處理機(jī)的局部存儲器本身就是一個 Cache， 其集合構(gòu)成共享存儲器。這樣，相當(dāng)于每一個處理機(jī)都有一個很大的 Cache，消除了傳統(tǒng)意義上的局部存儲器與主存儲器，這在邏輯上也就消除了對物理存儲器的尋址。這樣既保持了共享主存多處理機(jī)的優(yōu)點，又具備分布式存儲器多處理機(jī)易擴(kuò)展的長處。KSR公司推出的 MPP處理機(jī)KSR1/2采取的就是這種存儲器體系結(jié)構(gòu)，如圖 。 目前，構(gòu)成 MPP機(jī)的基礎(chǔ)是功能很強(qiáng)的 RISC芯片，比如CRAYT3D， 采用主頻 150MHz的 DEC Alpha芯片， TMC公司的 CM5采用 40MHz的 SPARC芯片?；ミB網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)多采用二維、三維網(wǎng)格、環(huán)（ Torus） 或胖樹結(jié)構(gòu)。在整個系統(tǒng)中，與數(shù)據(jù)處理時間相比，網(wǎng)絡(luò)傳輸所需要的時間小得多。因此，無論采用哪種網(wǎng)絡(luò)結(jié)構(gòu)，對系統(tǒng)的影響都不很大。 MPP機(jī)舉例 CM5的系統(tǒng)組成如圖 ，可包含 32～ 16384個處理機(jī)結(jié)點，圖 CM5系統(tǒng)組成 每個結(jié)點包括一個32MHz的 SPARC處理器、 32MB的本地存儲器和一個速度為128MFLOPS的 64位向量處理部件。系統(tǒng)控制計算機(jī) CP使用的是 SUN公司的工作站計算機(jī)，可配置一臺到幾十臺，每一臺可根據(jù)需要配置存儲器和磁盤。 整個系統(tǒng)配置有 3個互連網(wǎng)絡(luò)，其中數(shù)據(jù)網(wǎng)絡(luò)為各結(jié)點提供高速點對點數(shù)據(jù)通信；控制網(wǎng)絡(luò)為處理機(jī)結(jié)點與控制計算機(jī)之間提供互連，實現(xiàn)廣播、同步、掃描等協(xié)同操作，并完成相關(guān)的管理功能；診斷網(wǎng)絡(luò)用以訪問所有的硬件設(shè)備，測試系統(tǒng)的完整性，檢查并隔離錯誤。處理結(jié)點、控制處理機(jī)、 I/O通道都采用統(tǒng)一網(wǎng)絡(luò)接口 NI與數(shù)據(jù)網(wǎng)絡(luò)和控制網(wǎng)絡(luò)連接，這樣可實現(xiàn)網(wǎng)絡(luò)與設(shè)備的型號無關(guān)性。 CM5的峰值速度可超過 1TFLOPS。 圖 4元胖樹結(jié)構(gòu) （ 1） 數(shù)據(jù)網(wǎng)絡(luò) CM5的數(shù)據(jù)網(wǎng)絡(luò)是以胖樹概念為基礎(chǔ)設(shè)計的。各處理機(jī)結(jié)點、控制處理機(jī)、 I/O通道都位于胖樹的葉結(jié)點上，樹的內(nèi)部結(jié)點都是開關(guān)。其結(jié)構(gòu)如圖 ，用 4元胖樹來實現(xiàn)。每一個內(nèi)部開關(guān)結(jié)點是由 n個尋徑器芯片組成，每個尋徑器芯片同與 4個開關(guān)結(jié)點中的尋徑器芯片連接，并與 2個或 4個父開關(guān)結(jié)點中的尋徑器芯片連接，可調(diào)節(jié)胖樹結(jié)點間的帶寬。 （ 2）控制網(wǎng)絡(luò) 控制網(wǎng)絡(luò)是一個完全的二叉樹結(jié)構(gòu)，處理機(jī)結(jié)點、控制處理機(jī)、I/O通道位于葉結(jié)點上。該控制網(wǎng)絡(luò)可為每一個分區(qū)分配一棵子樹，且整體結(jié)構(gòu)比數(shù)據(jù)網(wǎng)絡(luò)的胖樹結(jié)構(gòu)簡單，具有切換能力，數(shù)據(jù)包長 64位，實現(xiàn)的操作有廣播、組合與全局操作。整體分工是控制處理機(jī)執(zhí)行操作代碼中的標(biāo)量部分，處理機(jī)結(jié)點執(zhí)行操作代碼中的并行數(shù)據(jù)處理部件。 （ 3）診斷網(wǎng)絡(luò)診斷網(wǎng)絡(luò)也是一棵二叉樹結(jié)構(gòu)，根結(jié)點可以是一個或多個診斷處理機(jī)，每個葉結(jié)點是一塊插板或在底板上構(gòu)成的物理系統(tǒng)盒。診斷處理機(jī)通過一個專門診斷接口來對內(nèi)部所有支持 JTAG（ Join test action group） 標(biāo)準(zhǔn)的 CM5芯片及網(wǎng)絡(luò)進(jìn)行測試，從中發(fā)現(xiàn)錯誤，排除故障或掉電部分。 圖 控制處理機(jī)組成 （ 4）控制處理機(jī) 如圖 ，由 RISC微處理器、存儲器、帶有本地磁盤的 I/O子系統(tǒng)及網(wǎng)絡(luò)接口 NI組成。該網(wǎng)絡(luò)接口向內(nèi)連接 CM5的控制網(wǎng)絡(luò)及數(shù)據(jù)網(wǎng)絡(luò)，向外連接本地以太網(wǎng)。每個控制處理機(jī)運行 COMST程序，即一個基于 UNIX的操作系統(tǒng)，負(fù)責(zé) CM5并行處理資源的管理工作。包括用戶分區(qū)的計算資源和 I/O資源。 （ 5）處理機(jī)結(jié)點 處理機(jī)結(jié)點是由 SPARC微處理器、向量部件、存儲器和網(wǎng)絡(luò)接口 NI組成，如圖 。內(nèi)部數(shù)據(jù)總線 64位，每個向量部件有一條專用通路與8MB存儲器連接，專用通路 72位，附加了 8位錯誤校正碼（ ECC）。 圖 帶向量部件的處理機(jī)結(jié)點 每個向量部件包含一個流水線式的 ALU、 一個向量指令譯碼器和 64個 64位的寄存器，執(zhí)行標(biāo)量處理器發(fā)來的向量指令，完成存儲器訪問，并生成校正碼（ ECC）。 標(biāo)量處理器可把向量指令發(fā)送給指定的向量部件，也可發(fā)送給一對或廣播給 4個向量部件。每個向量部件訪問存儲器的峰值帶寬為128MBps， 所有向量部件訪問存儲器的總帶寬位 512MB/s。 處理機(jī)結(jié)點的峰值速度為 128MFLOPS， CM5的最大配置為 214=16384個處理機(jī)結(jié)點，總峰值速度為 27214=2TFLOPS。 T3E T3E的體系結(jié)構(gòu)如圖 ，是 Cray公司 1995年推出的又一種MPP機(jī)，如今已有三種型號，即 T3E、 T3E90、 T3E1200。圖 T3E體系結(jié)構(gòu) （ 1） 處理機(jī)結(jié)點 處理機(jī)結(jié)點由 DEC Alpha 21164和一個外部 Shell組成。在 Shell中包含有一個本地主存、通信處理器、 512個 64位 E寄存器及讀 /寫控制部件。其中 21164是一個超標(biāo)量 64位 RISC微處理器，內(nèi)部寄存器也是 64位，每一個時鐘周期能發(fā)射 4條指令。虛擬地址限定為 43位，物理地址限定為 40位，為每個結(jié)點配置的本地主存可達(dá) 2GB。 整個系統(tǒng)若有 2048個結(jié)點處理機(jī)，整個系統(tǒng)的全局物理存儲器可達(dá) 4096GB。 在 Alpha 21164中設(shè)有兩級片內(nèi) Cache， L1指令 Cache和數(shù)據(jù) Cache各 8KB， L2 Cache是有 96KB的 3路組相聯(lián) Cache， 統(tǒng)一用于指令和數(shù)據(jù)的高速緩存。 片內(nèi)兩級 Cache緩存本地存儲器中的內(nèi)容，處理器則使用虛擬地址訪問遠(yuǎn)程存儲器，虛擬地址經(jīng)由 E寄存器被通信處理器轉(zhuǎn)換成物理地址，即結(jié)點號 +結(jié)點內(nèi)存偏移地址。 （ 2）互連網(wǎng)絡(luò) T3E機(jī)采用兩種網(wǎng)絡(luò)，主機(jī)連接采用雙向三維環(huán)網(wǎng)，帶寬為480MB/s， 且為處理機(jī)結(jié)點提供預(yù)取和非阻塞寫能力，對于存儲器提供 4字或 8字的塊傳輸能力，且實現(xiàn)自適應(yīng)最短距離的尋徑算法，允許消息繞過擁擠的鏈路和結(jié)點。 所有結(jié)點通過一個或者多個 GigaRing相連。 GigaRing由一對循環(huán)計數(shù)的 32位環(huán)組成，用以連接用戶結(jié)點和 I/O結(jié)點。在 I/O結(jié)點上設(shè)有插槽，可插入以太、 FDDI、 HiPPI、 ATM等網(wǎng)卡，或者插入磁盤、磁帶機(jī)等設(shè)備的接口卡。這多個 GigaRing構(gòu)成包交換、高帶寬的 I/O子系統(tǒng)，包的大小可達(dá) 256B， 峰值帶寬為 1GB/s。 在 T3E中，除了用戶結(jié)點、 I/O結(jié)點之外，還有操作系統(tǒng)服務(wù)結(jié)點和預(yù)備結(jié)點。操作系統(tǒng)使用的是 Cray 64位 UNIX的一個變種 UNIDOS/mk， 是一個全分布式操作系統(tǒng)。 除了提高 Cache及其一致性管理、通信網(wǎng)與處理器接口性能以及 I/O處理能力之外，人們已經(jīng)在研究利用多線程（ Multithread） 技術(shù)開發(fā)細(xì)粒度的并行性，研究新的并行算法和計算模型，開發(fā)并行編譯與并行編程環(huán)境等。 而且，數(shù)字通信網(wǎng)的速率很高（ Gbps）， 使網(wǎng)絡(luò)中的計算資源聯(lián)系非常緊密，因而分布式系統(tǒng)與并行計算機(jī)系統(tǒng)之間的界限逐漸模糊起來。通過計算機(jī)網(wǎng)絡(luò)也可構(gòu)成大型并行計算機(jī)環(huán)境。且有利于開發(fā)異構(gòu)型并行處理機(jī)環(huán)境，如圖 ，有利于系統(tǒng)的容錯能力。圖 異構(gòu)型并行處理機(jī) 共享存儲器型多處理機(jī) 共享存儲器型多處理機(jī) SMP（ Shared Memory MultiProcessors）， 也稱為對稱型多處理機(jī)，有三種模型，即均勻存儲器存取 UMA（Uniform Memory Access） 模型、非均勻存儲器存取 NUMA（Nonuniform Uniform Memory Access） 模型和只用高速緩存的存儲器結(jié)構(gòu) COMA（ Cache Only Memory Architecture）。 其區(qū)別在于存儲器和外部資源如何共享或分布。圖 UMA多處理機(jī)模型 （ 1） UMA模型 UMA結(jié)構(gòu)如圖 ，通過互連網(wǎng)絡(luò)把各處理機(jī)及存儲器模塊均勻地連接起來。存儲器為所有處理機(jī)均勻共享，且具有相同的訪問時間。每臺處理機(jī)有自己的 Cache和外圍設(shè)備，這些設(shè)備也可以某種方式為其它處理機(jī)所共享。圖 NUMA多處理機(jī)模型 （ 2） NUMA模型 非均勻存儲器存取多處理機(jī)的體系結(jié)構(gòu)如圖 ，共享存儲分布在各處理機(jī)的本地存儲器上，處理機(jī)訪問存儲器的時間因與存儲單元所在的位置而有所不同，主要因為網(wǎng)絡(luò)傳送而引起的附加時間。所有本地存儲器的集合構(gòu)成全局存儲空間，可被所有的處理機(jī)訪問。 圖 COMA多處理機(jī)模型 （ 3） COMA模型 如圖 ，是一種只用高速緩沖存儲器的多處理機(jī)，可以說是NUMA的特例，它把 NUMA中的分布式主存用高速緩存來取代。在每一個處理機(jī)結(jié)點上沒有存儲器的層次結(jié)構(gòu)，而是將全部高速緩存組成全局存儲器空間。對于遠(yuǎn)程高速緩存的訪問，可借助分布高速緩存目錄來進(jìn)行。圖 ， P表示處理機(jī)， C表示高速緩沖存儲器， D表示高速緩存目錄。2. S2MP體系結(jié)構(gòu) S2MP（ Scalable SharedMemory MultiProcessing） 可稱為新一代的共享存儲器并行多處理機(jī)，其示意如圖 （ a） 所示，有效地解決了共享主存的并行多處理機(jī)的可擴(kuò)展性。 圖中可以看出，每一個結(jié)點都由兩個部分組成，即微處理器和存儲器。而存儲器又由 Ca