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