并行處理機(jī)和多處理機(jī)

1、第八章 并行處理機(jī)和多處理機(jī)并行處理機(jī)又叫SIMD計(jì)算機(jī)。它是單一控制部件控制下的多個(gè)處理單元構(gòu)成的陣列，所以又稱為陣列處理機(jī)。多處理機(jī)是由多臺(tái)獨(dú)立的處理機(jī)組成的系統(tǒng)。并行處理機(jī)結(jié)構(gòu)和實(shí)例多處理機(jī)結(jié)構(gòu)和實(shí)例1并行處理計(jì)算機(jī)模型并行處理機(jī)定義：多個(gè)PU按照一定方式互連，在同一個(gè)CU控制下，對(duì)各自的數(shù)據(jù)完成同一條指令規(guī)定的操作。從CU看，指令是串行執(zhí)行的，從PU看，數(shù)據(jù)是并行處理的。并行處理機(jī)也稱為陣列處理機(jī)。按照佛林分類法，它屬于SIMD計(jì)算機(jī)。并行處理機(jī)的應(yīng)用領(lǐng)域：主要用于高速向量或矩陣運(yùn)算中。8.1 并行處理機(jī)結(jié)構(gòu)和實(shí)例2P0M0PE0P1M1PE1P2M2PE2Pn-1Mn-1Pen-1互

2、連網(wǎng)絡(luò)控制器HJSiegel提出的并行處理機(jī)模型下圖是H.J.Siegel提出的SIMD計(jì)算機(jī)的操作模型3并行處理機(jī)的操作模型可用五元組來(lái)表示：M(N，C，I，M，R), 其中： N為PE個(gè)數(shù)。如IlliacIV有64個(gè)PE。 C為由控制部件CU直接執(zhí)行的指令集，包括標(biāo)量指令和程序控制指令。I為所有PE并行執(zhí)行的指令集，包括算術(shù)運(yùn)算、邏輯運(yùn)算、數(shù)據(jù)尋徑、屏蔽以及其它由每個(gè)活動(dòng)的PE對(duì)它的數(shù)據(jù)所執(zhí)行的局部操作。M為屏蔽操作集，每種屏蔽將PE劃分為允許操作和禁止操作兩個(gè)子集。 R是數(shù)據(jù)尋徑集，說(shuō)明互連網(wǎng)絡(luò)中PE間通信所需要的各種設(shè)置模式。4系統(tǒng)型號(hào)SIMD計(jì)算系統(tǒng)結(jié)構(gòu)和性能語(yǔ)言、編譯器和軟件支持M

3、asParMP-1系列102416384個(gè)PE, 26 GIPS或1.3 Gflops; 每個(gè)PE帶16KB本地存儲(chǔ)器, X-Net網(wǎng)格加一個(gè)多級(jí)交叉開(kāi)關(guān)互連網(wǎng)Fortran77, MasPar Fortran (MPF)和MasPar并行應(yīng)用語(yǔ)言; X窗口UNIX/OS, 符號(hào)調(diào)試程序, 可視化和動(dòng)畫制作程序典型并行處理機(jī)5Active Memory Technology DAP600系列1K位/PE方形網(wǎng)格互連成4096PE的細(xì)粒、位片SIMD陣列，正交4-鄰位鏈接，20GIPS和560Mflops峰值性能由主機(jī)VAX/VMS或UNIX Fortran-plus 或DAP上APAL提供，主

4、機(jī)的Fortran77或C; 與Fortran90標(biāo)準(zhǔn)有關(guān)的Fortran-plusThinking Machines公司CM-265536個(gè)PE排成10維超立方體, 每個(gè)PE可有1M位存儲(chǔ)器, 32個(gè)PE共享FPU選件, 峰值速度28 Gflops和持續(xù)速度5.6 Gflops由VAX, Sun或Symbolics 360主機(jī)驅(qū)動(dòng), PARIS支持的Lisp編譯器、Fortran90、C*和*Lisp6并行處理機(jī)的基本結(jié)構(gòu)兩種SIMD計(jì)算機(jī)的基本結(jié)構(gòu)：分布存儲(chǔ)器并行處理機(jī)共享存儲(chǔ)器并行處理機(jī)一臺(tái)并行處理機(jī)由五個(gè)部分組成：多個(gè)處理單元PE多個(gè)存儲(chǔ)器模塊M一個(gè)控制器CU一個(gè)互連網(wǎng)絡(luò)ICN一臺(tái)輸入

5、輸出處理機(jī)IOP7目前的大部分并行處理機(jī)是基于分布式存儲(chǔ)器模型的系統(tǒng)。比較容易構(gòu)成MPP（Massively Parallel Processor）,幾十萬(wàn)個(gè)PE。必須依靠并行算法來(lái)提高PE的利用率。因此，應(yīng)用領(lǐng)域很有限。CU是控制部件，執(zhí)行標(biāo)量指令，并把向量指令廣播到各個(gè)PE中。在CU中通常有一個(gè)較大容量的存儲(chǔ)器。IOP是輸入輸出處理機(jī)，或稱為主機(jī)。在IOP上安裝操作系統(tǒng)，它除了負(fù)擔(dān)輸入輸出工作外，還負(fù)責(zé)程序的編輯、編譯和調(diào)試等工作。數(shù)據(jù)在局部存儲(chǔ)器中的分布是一個(gè)很關(guān)鍵的問(wèn)題。標(biāo)量指令與向量指令可以并發(fā)執(zhí)行。1、分布存儲(chǔ)器結(jié)構(gòu)8LM0互連網(wǎng)絡(luò)PE0CULM1PE1LMn-1PEn-1IOP9

6、共享的多體并行存儲(chǔ)器 SM 通過(guò)互連網(wǎng)絡(luò)與各處理單元PE相連。存儲(chǔ)模塊的數(shù)目等于或略大于處理單元的數(shù)目。同時(shí)在存儲(chǔ)模塊之間合理分配數(shù)據(jù)，通過(guò)靈活、高速的互連網(wǎng)絡(luò)，使存儲(chǔ)器與處理單元之間的數(shù)據(jù)傳送在大多數(shù)向量運(yùn)算中都能以存儲(chǔ)器的最高頻率進(jìn)行，而最少受存儲(chǔ)沖突的影響。共享存儲(chǔ)器模型的處理單元數(shù)目一般不多，幾個(gè)至幾十個(gè)。Burroughs Scientific Processor (BSP)采用了這種結(jié)構(gòu)。16個(gè)PE通過(guò)一個(gè)1617的對(duì)準(zhǔn)互連網(wǎng)絡(luò)訪問(wèn)17個(gè)共享存儲(chǔ)器模塊。存儲(chǔ)器模塊數(shù)與PE數(shù)互質(zhì)可以實(shí)現(xiàn)無(wú)沖突并行訪問(wèn)存儲(chǔ)器。2. 共享存儲(chǔ)器并行處理機(jī)10PE0互連網(wǎng)絡(luò)CUPE1PEn-1IOPSM0

7、SM1SMk-111并行處理機(jī)的主要特點(diǎn)如下：速度快，特別適于高速數(shù)值計(jì)算。SIMD依靠的是資源重復(fù)，而不是時(shí)間重疊。它依靠增加PE個(gè)數(shù)，與流水線處理機(jī)主要依靠縮短時(shí)鐘周期相比，其提高速度的潛力要大得多。依賴于互連網(wǎng)絡(luò)和并行算法?；ミB網(wǎng)絡(luò)決定了PE之間的連接模式，也決定了并行處理機(jī)能夠適應(yīng)的算法。需要有一臺(tái)高性能的標(biāo)量處理機(jī)。如果一臺(tái)機(jī)器的向量處理速度極高，但標(biāo)量處理速度只是每秒一百萬(wàn)次，那么對(duì)于標(biāo)量運(yùn)算占10的題目來(lái)說(shuō)，總的有效速度就不過(guò)是每秒一千萬(wàn)次。SIMD基本上是一臺(tái)向量處理專用計(jì)算機(jī)。盡管它有一個(gè)功能很強(qiáng)的控制部件實(shí)際上起作標(biāo)量處理機(jī)的作用，但仍然必須和一臺(tái)高性能單處理機(jī)配合工作，使

8、后者擔(dān)負(fù)系統(tǒng)的全部管理功能。并行處理機(jī)的特點(diǎn)12IlliacIV 是最先采用SIMD結(jié)構(gòu)的并行機(jī)隨后一個(gè)方向是用位片PE制造的并行機(jī)，如Goodyear MPP、AMT/DAP 610和TMC/CM-2。CM-5是以SIMD模式運(yùn)行的同步MIMD計(jì)算機(jī)。另一方向是用字寬運(yùn)算PE的中粒度SIMD計(jì)算機(jī)。并行處理機(jī)的兩個(gè)發(fā)展方向：保留陣列結(jié)構(gòu)，但每個(gè)處理單元的規(guī)模減小，如一個(gè)bit。去掉陣列結(jié)構(gòu)和分布存儲(chǔ)器。Burroughs公司的BSP是典型代表。 GF-11是由IBM Watson實(shí)驗(yàn)室研制、作科學(xué)模擬研究用的。MasPar MP1是中粒度并行處理機(jī)的典型代表。下面介紹并行處理機(jī)的兩種典型代表

9、：采用陣列結(jié)構(gòu)分布存儲(chǔ)器的IlliacIV并行處理機(jī)去掉陣列結(jié)構(gòu)和分布存儲(chǔ)器BSP并行處理機(jī)。并行處理機(jī)實(shí)例13Illiac IV(Barnes等，1968）Goodyear MPP(Batcher,1980）BSP(kuck和Stokes，1982）DAP 610(AMT，Inc.1987)CM-2(TMC,1990)CM-5(TMC,1991)MasPar MPI(Nickolls,1990)IBM GF-11(Beetem等，1985）SIMD計(jì)算機(jī)發(fā)展過(guò)程141963年，美國(guó)西屋電器公司提出“Slotnick，The SOLOMON Computer，Simultaneous Oper

10、ation linked Ordinal Modular Network”。1966年美國(guó)國(guó)防遠(yuǎn)景研究規(guī)劃局ARPR與伊利諾依大學(xué)簽定合同。原計(jì)劃：256個(gè)PE，每個(gè)PE每240ns處理一個(gè)64位的浮點(diǎn)數(shù)，每個(gè)局部存儲(chǔ)器PEM為2K?64位，總的運(yùn)算速度為1GFLOPS。美國(guó)Burroughs公司和伊利諾依大學(xué)于1972年共同設(shè)計(jì)和生產(chǎn)，1975年實(shí)際投入運(yùn)行。用了4倍的經(jīng)費(fèi)，只達(dá)到1/20的速度。只實(shí)現(xiàn)了8?864個(gè)PE，只達(dá)到50MFLOPS。IlliacIV系統(tǒng)的影響非常大。它是并行處理機(jī)的典型代表，也是分布存儲(chǔ)器并行處理機(jī)的典型代表。IlliacIV系統(tǒng)由三大部分組成。IlliacIV

11、處理機(jī)陣列，陣列控制器，一臺(tái)標(biāo)準(zhǔn)的Burroughs B6700計(jì)算機(jī)。1 IlliacIV 陣列處理機(jī)151、IlliacIV處理陣列IlliacIV處理陣列由8864個(gè)PU組成。每個(gè)PU由處理部件PE和它的局部存儲(chǔ)器PEM組成。每一個(gè)PUi只和它的東、西、南、北四個(gè)近鄰直接連接。PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64南北方向上同一列的PU連成一個(gè)環(huán)，東西方向上構(gòu)成一個(gè)閉合螺線。采用閉合螺線最短距離不超過(guò)7步。而普通網(wǎng)格最短距離不超過(guò)8步。例如：從PU0到PU36的距離：采用普通網(wǎng)格必須8步：PU0 PU1 PU2 PU3 PU

12、4 PU12 PU20 PU28 PU36或 PU0 PU8 PU16 PU24 PU32 PU33 PU34 PU35 PU36或 （等于8步的很多，大于8步的更多）如果采用閉合螺旋線，只需要7步：PU0 PU63 PU62 PU61 PU60 PU52 PU44 PU3616普通網(wǎng)格必須8步：PU0 PU1 PU2 PU3 PU4 PU12 PU20 PU28 PU36或 PU0 PU8 PU16 PU24 PU32 PU33 PU34 PU35 PU36或 閉合螺旋線只要7步：PU0 PU63 PU62 PU61 PU60 PU52 PU44 PU36或 PU0 PU63 PU55 PU

13、47 PU39 PU38 PU37 PU36或 172、陣列控制器陣列控制器CU實(shí)際上是一臺(tái)小型控制計(jì)算機(jī)。對(duì)陣列處理單元實(shí)行控制和完成標(biāo)量操作。標(biāo)量操作與各PE的數(shù)組操作可以重疊執(zhí)行?？刂破鞯墓δ苡幸韵挛鍌€(gè)方面：(1) 對(duì)指令進(jìn)行譯碼，并執(zhí)行標(biāo)量指令；(2) 向各處理單元發(fā)出執(zhí)行數(shù)組操作指令所需的控制信號(hào)；(3) 產(chǎn)生和向所有處理單元廣播公共的地址；18(4) 產(chǎn)生和向所有處理單元廣播公共的數(shù)據(jù)；(5) 接收和處理PE、I/O操作以及B6700產(chǎn)生的陷阱中斷信號(hào)。2、輸入輸出系統(tǒng)IlliacIV的輸入輸出系統(tǒng)由磁盤文件系統(tǒng)DFS、I/O分系統(tǒng)和一臺(tái)B6700處理機(jī)組成。I/O分系統(tǒng)又由輸入輸

14、出開(kāi)關(guān)IOS、控制描述字控制器CDC和輸入輸出緩沖存儲(chǔ)器BIOM三個(gè)部分組成。19試在含一個(gè)PE的SISD機(jī)和在含m個(gè)PE的且連接成一線性環(huán)的SIMD機(jī)上計(jì)算下列求內(nèi)積的表達(dá)式。假定完成每次ADD操作需2個(gè)單元時(shí)間，完成每次MULTIPLY操作需4個(gè)單位時(shí)間，沿雙向環(huán)在相鄰PE間移數(shù)需1個(gè)單位時(shí)間。（1）SISD計(jì)算機(jī)上計(jì)算s需多少時(shí)間？（2）SIMD計(jì)算機(jī)上計(jì)算s需多少時(shí)間？（3）用SIMD機(jī)計(jì)算s相對(duì)于用SISD機(jī)計(jì)算的加速比是多少？習(xí)題8.620（1）在SISD計(jì)算機(jī)中計(jì)算s需要串行計(jì)算n次乘法和n-1次加法。共需要時(shí)間： 算法如下： S=A1*B1 For i=2 to n DoS=S

15、+Ai*Bi Enddo（2）在SIMD計(jì)算機(jī)上計(jì)算采用如下的算法：（假設(shè)mn）首先，把向量中的n對(duì)元素盡量平均地分配到m個(gè)處理器中，每個(gè)處理器最多分配n/m+1對(duì)，最少分配n/m對(duì)，最多經(jīng)過(guò)4（n/m+1）+2n/m 時(shí)間，所有n個(gè)處理器上都得到了一個(gè)局部和，對(duì)這m個(gè)處理器 解答21構(gòu)成的線性環(huán)做累加運(yùn)算。若采用兩路7線性累加的方法共用做加法m/2次,數(shù)據(jù)傳遞m/2次，共用時(shí)間4（n/m+1）+2n/m+3m/2 = 6n/m+ 3m/2+4。若用遞歸累加的方法，假設(shè)m 是2的p次冪。做p次并行的加法，移位1+2+4+ + m/2 = m-1 次。用時(shí)2p+（m-1）?？偣灿脮r(shí)為 4（n/m

16、+1）+2n/m+2log m +（m-1） = 6n/m+ m+2log m +3進(jìn)一步分析：當(dāng)2logm 16時(shí) 并行累加比兩路線性累加更優(yōu)。反之，當(dāng)m 16 時(shí)，兩路線性累加更快。其根本原因就是并行累加算法節(jié)省了加法時(shí)間，但是花費(fèi)更多的數(shù)據(jù)傳送時(shí)間。22算法描述如下:Par：For j=1 to m DoS(j)=A1j*B1jFor 2 to n/m DoS(j)=S(j)+Aij*BijEnddoS(j)=S(j)+S(j+1)S(j)=S(j)+S(j+2)S(j)=S(j)+S(j+4) S(j)=S(j)+S(j+n/m)Enddo23（3）加速比當(dāng)采用兩路線性累加的方法時(shí)加速

17、比為：若m = n，做乘法的時(shí)間變?yōu)?，則加速比簡(jiǎn)化為當(dāng)采用遞歸并行累加時(shí)加速比為：當(dāng)m = n 時(shí)，做乘法的時(shí)間變?yōu)?，則加速比簡(jiǎn)化為24分析其原因，可以看出，線性互連網(wǎng)絡(luò)的傳輸開(kāi)銷在這里是制約加速比增長(zhǎng)的最大障礙，無(wú)論采用何種并行算法，一個(gè)數(shù)據(jù)從線性環(huán)形網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)傳遞到最遠(yuǎn)的節(jié)點(diǎn)的最短時(shí)間為m/2，這個(gè)時(shí)間是無(wú)法改進(jìn)的，并且隨著處理節(jié)點(diǎn)的增多成為最主要的時(shí)間開(kāi)銷。相對(duì)而言，加法和乘法隨著處理單元的增多，所占的時(shí)間比例越來(lái)越小。258.2多處理機(jī)結(jié)構(gòu)和實(shí)例兩個(gè)或兩個(gè)以上處理機(jī)(包括PU和CU)，通過(guò)高速互連網(wǎng)絡(luò)連接起來(lái)，在統(tǒng)一的操作系統(tǒng)管理下，實(shí)現(xiàn)指令以上級(jí)（任務(wù)級(jí)、作業(yè)級(jí)）并行。按照

18、Flynn分類法，多處理機(jī)系統(tǒng)屬于MIMD計(jì)算機(jī)。多處理機(jī)系統(tǒng)由多個(gè)獨(dú)立的處理機(jī)組成，每個(gè)處理機(jī)都能夠獨(dú)立執(zhí)行自己的程序。26多處理機(jī)結(jié)構(gòu)由若干臺(tái)獨(dú)立的計(jì)算機(jī)組成，每臺(tái)計(jì)算機(jī)能夠獨(dú)立執(zhí)行自己的程序。Flynn稱這種結(jié)構(gòu)為多指令流多數(shù)據(jù)流（MIMD）結(jié)構(gòu)。多處理機(jī)系統(tǒng)中的處理機(jī)之間按某種形式互連，從而實(shí)現(xiàn)程序之間的數(shù)據(jù)交換和同步。多處理機(jī)系統(tǒng)中每臺(tái)處理機(jī)都有寄存器、運(yùn)算器、邏輯部件、訪問(wèn)存儲(chǔ)器和I/O的通道。還有一種多處理機(jī)系統(tǒng)中每臺(tái)處理機(jī)有自己的存儲(chǔ)器和I/O設(shè)備。多處理機(jī)結(jié)構(gòu)27互連網(wǎng)絡(luò)處理機(jī)1處理機(jī)2處理機(jī)N存儲(chǔ)器存儲(chǔ)器存儲(chǔ)器I/OI/O具有通過(guò)互連網(wǎng)絡(luò)共享存儲(chǔ)器和I/O的多處理機(jī)系統(tǒng)28

19、處理機(jī)1存儲(chǔ)器I/O處理機(jī)2存儲(chǔ)器I/O處理機(jī)N存儲(chǔ)器I/O互連網(wǎng)每個(gè)處理機(jī)都擁有自己的存儲(chǔ)器和I/O的多處理機(jī)系統(tǒng)29 1、結(jié)構(gòu)靈活性并行處理機(jī)：專用，PE數(shù)很多（幾千個(gè)），固定有限的通信多處理機(jī)： 通用，幾十個(gè)，高速靈活的通信2、程序并行性并行處理機(jī)的并行性存在于指令內(nèi)部，識(shí)別比較容易。多處理機(jī)的并行性存在于指令外部，在多個(gè)任務(wù)之間，識(shí)別難度較大。一個(gè)簡(jiǎn)單的例子：Y = A+B*C*D/E+F用兩個(gè)處理機(jī)：CPU1： CPU2： B*C， D/E， A+F， B*C*D/E A+B*C*D/E+F多處理機(jī)系統(tǒng)的特點(diǎn)303、并行任務(wù)派生并行處理機(jī)把同種操作集中在一起，由指令直接啟動(dòng)各PE同時(shí)

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

21、效率有很大的影響。31引起峰值性能下降的原因是：(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)銷研究多處理機(jī)的目的：提前5年得到速度高10倍的機(jī)器。 或用1/10的價(jià)格獲得一臺(tái)高性能的機(jī)器。如果設(shè)計(jì)得好，在某些適合進(jìn)行并行處理得應(yīng)用領(lǐng)域，可以達(dá)到：提前10年得到速度高100倍的機(jī)器 或用1/100的價(jià)格獲得一臺(tái)高性能的機(jī)器。多處理機(jī)性能模型32并行性在很大程度上依賴于R/C比值，其中：R代表程序執(zhí)行時(shí)間，C代表通信開(kāi)銷。通常：R/C比

22、值小，并行性低。R/C比值大，并行性高如果把作業(yè)分解成較大的塊，就能得到較大的R/C值，但是所得到的并行性比最大可能的并行性要小得多。R/C比值是衡量任務(wù)粒度(Granularity)大小的尺度在粗粒度（Coarsegrain）并行情況下，R/C比值比較大，通信開(kāi)銷小在細(xì)粒度（Finegrain）并行情況下，R/C比值比較小，通信開(kāi)銷大細(xì)粒度并行性需要的處理機(jī)多，粗粒度并行性需要的處理機(jī)少。細(xì)粒度并行性的基本原理是把一個(gè)程序盡可能地分解成能并行執(zhí)行的小任務(wù)。在極端情況下，一個(gè)小任務(wù)只完成一個(gè)操作。331.基本模型在兩臺(tái)處理機(jī)情況每個(gè)任務(wù)的執(zhí)行時(shí)間為R個(gè)單位時(shí)間兩個(gè)任務(wù)不在同一臺(tái)處理機(jī)上時(shí)，通信

23、開(kāi)銷為C個(gè)單位時(shí)間K個(gè)任務(wù)給一臺(tái)處理機(jī)M-K個(gè)任務(wù)給另一臺(tái)處理機(jī)總處理時(shí)間=Rmax(M-K，K)+C(M-K)K結(jié)論：當(dāng)R/CM/2時(shí)，把任務(wù)平均分給兩臺(tái)處理機(jī)能使總處理時(shí)間最小。342.N臺(tái)處理機(jī)系統(tǒng)的基本模型將Ki個(gè)任務(wù)分配給第i臺(tái)處理機(jī)。推廣前面的式子：35分析任務(wù)均分給N臺(tái)處理機(jī)和任務(wù)集中在一臺(tái)處理機(jī)的總處理時(shí)間差，有：如果R/C比臨界值M/2大，將任務(wù)平均分配給盡可能多的處理機(jī)進(jìn)行處理，能獲得最短處理時(shí)間。如果R/C比臨界值M/2小，即使有很多臺(tái)處理機(jī)可供使用，也不可能比用一臺(tái)處理機(jī)處理全部任務(wù)快。36并行系統(tǒng)的加速比是一個(gè)計(jì)算問(wèn)題在一臺(tái)處理機(jī)上的運(yùn)行時(shí)間與在并行系統(tǒng)上的運(yùn)行時(shí)間的

24、比值，可近似如下：多處理機(jī)的Cache一致性（自己看）37多處理機(jī)系統(tǒng)主要有四大類：(1) 多向量處理機(jī)系統(tǒng)：如CRAY YMP-90, NEC SX-3和FUJITSU VP-2000(2) SMP (Symmetry MultiProcessors)對(duì)稱多處理機(jī);SMP (Shared Memory MulptiProcessors)共享存儲(chǔ)多處理機(jī) 如SGI Challenge，Sun SparcCenter 2000(3) MPP (massively parallel processing)大規(guī)模并行處理機(jī)如Intel Paragon, CM-5, Cray T3D(4) Clust

25、er 機(jī)群系統(tǒng)（NOW或COM） 多處理機(jī)實(shí)例38科學(xué)計(jì)算中的重大課題要求提供3T性能：(1) 1 Teraflops計(jì)算能力(2) 1 Terabyte主存儲(chǔ)器(3) 1 Terabyte/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é)采用的關(guān)鍵技術(shù)：VLSI, 可擴(kuò)展技術(shù), 共享虛擬存儲(chǔ)技術(shù) 大規(guī)模并行處理機(jī)(MPP)39虛擬共享存儲(chǔ)器(Shared Virtual Memory)也稱為共享分布存儲(chǔ)器(Distribut

26、ed Shared Memory)；物理上分布存儲(chǔ)器，邏輯上共享存儲(chǔ)器。虛擬共享存儲(chǔ)器的優(yōu)點(diǎn)：編程容易, 系統(tǒng)結(jié)構(gòu)靈活可擴(kuò)充性好, 有較好的軟件移植性與消息傳遞方式相比，程序運(yùn)行效率高，主要原因：(1) 數(shù)據(jù)塊緩存在本地 (內(nèi)存或Cache中), 可以多次使用(2) 通信時(shí)間分散，提高了并行性(3) 擴(kuò)大存儲(chǔ)空間，減少換頁(yè)操作虛擬共享存儲(chǔ)器實(shí)現(xiàn)途徑：(1) 硬件實(shí)現(xiàn), 利用Cache技術(shù)。需要增加專用硬件(2) 操作系統(tǒng)和庫(kù)實(shí)現(xiàn)，通過(guò)虛擬存儲(chǔ)機(jī)制取得共享和一致性。在松耦合的分布存儲(chǔ)多處理機(jī)上，不需要增加任何硬件(3) 編譯實(shí)現(xiàn)，自動(dòng)將共享訪問(wèn)轉(zhuǎn)換成同步和一致原語(yǔ)。大多數(shù)系統(tǒng)采用途徑(1)和(2

27、)，或這兩種途徑結(jié)合實(shí)現(xiàn)40SMP稱為共享存儲(chǔ)多處理機(jī) (Shared Memory mulptiProcessors),也稱為對(duì)稱多處理機(jī) (Symmetry MultiProcessors)有三種模型：(1) UMA多處理機(jī)均勻存儲(chǔ)器存取模型 (Uniform Memory Access)存儲(chǔ)器被所有處理機(jī)均勻共享所有處理機(jī)對(duì)所有存儲(chǔ)單元具有相同的存取時(shí)間每臺(tái)處理機(jī)有局部Cache外圍設(shè)備可以共享(2) NUMA多處理機(jī)非均勻存儲(chǔ)器存取 (Nonuniform Memory Access)模型存儲(chǔ)器訪問(wèn)時(shí)間隨存儲(chǔ)單元的位置不同而變化。共享存儲(chǔ)器在物理上是分布在所有處理機(jī)中的本地存儲(chǔ)器。所有

28、局部存儲(chǔ)器地址空間的集合就組成了全局地址空間。對(duì)稱多處理機(jī) (SMP)41系統(tǒng)互連網(wǎng)絡(luò)NUMA多處理機(jī)模型P1LM1P2LM2PnLMn系統(tǒng)互連網(wǎng)絡(luò)（總線、交叉開(kāi)關(guān)、多級(jí)網(wǎng)絡(luò)）UMA多處理機(jī)模型P1P2PnSM1SM2SM2I/O42處理機(jī)訪問(wèn)本地存儲(chǔ)器比較快，訪問(wèn)屬于另一臺(tái)處理機(jī)的遠(yuǎn)程存儲(chǔ)器則比較慢，因?yàn)橥ㄟ^(guò)互連網(wǎng)絡(luò)會(huì)產(chǎn)生附加的時(shí)間延遲。(3) COMA多處理機(jī)只有Cache的存儲(chǔ)器結(jié)構(gòu) (Cache-Only Memory Architecture) 模型；COMA是一種只用Cache的多處理機(jī)系統(tǒng)實(shí)際上，COMA模型是NUMA模型的一種特例，后者分布存儲(chǔ)器換成了Cache在每個(gè)處理機(jī)結(jié)點(diǎn)

29、上沒(méi)有主存儲(chǔ)器，全部Cache組成了全局虛擬地址空間遠(yuǎn)程Cache訪問(wèn)通過(guò)分布Cache目錄進(jìn)行共享存儲(chǔ)系統(tǒng)擁有統(tǒng)一的尋址空間，程序員不必參與數(shù)據(jù)分配和傳輸。43互連網(wǎng)絡(luò)COMA多處理機(jī)模型D1Cache1P1D2Cache2P2DnCachenPn441、機(jī)群系統(tǒng)的組成機(jī)群系統(tǒng)是利用高速網(wǎng)絡(luò)將一組高性能工作站或高檔PC機(jī)連接起來(lái)，在并行程序設(shè)計(jì)以及可視化人機(jī)交互集成開(kāi)發(fā)環(huán)境支持下，統(tǒng)一調(diào)度，協(xié)調(diào)處理，實(shí)現(xiàn)高效并行處理的系統(tǒng)。Cluster、NOW、COW從結(jié)構(gòu)和結(jié)點(diǎn)間的通信方式來(lái)看，屬于分布存儲(chǔ)系統(tǒng)。機(jī)群系統(tǒng)中的主機(jī)和網(wǎng)絡(luò)可以是同構(gòu)的，也可以是異構(gòu)的。微處理機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)和并行編程環(huán)境的發(fā)

30、展使得機(jī)群系統(tǒng)這一新的并行處理系統(tǒng)形式正成為當(dāng)前研究的熱點(diǎn)。(1)微處理器的性能不斷提高。(2)網(wǎng)絡(luò)技術(shù)的進(jìn)步使得松散耦合系統(tǒng)的通信瓶頸逐步得到緩解。機(jī)群系統(tǒng) (Cluster)45(3)并行編程環(huán)境的開(kāi)發(fā)使得新編并行程序或改寫串行程序更為容易。2、機(jī)群系統(tǒng)的特點(diǎn)(1)系統(tǒng)開(kāi)發(fā)周期短。(2)用戶投資風(fēng)險(xiǎn)小。(3)系統(tǒng)價(jià)格低。(4)節(jié)約系統(tǒng)資源。UC Berkeley計(jì)算機(jī)系100多臺(tái)工作站的使用情況調(diào)查表明，一般單機(jī)系統(tǒng)的使用率不到10%，而機(jī)群系統(tǒng)中的資源利用率可達(dá)到80%左右。(5)系統(tǒng)擴(kuò)展性好。(6)用戶編程方便。463、機(jī)群系統(tǒng)的關(guān)鍵技術(shù)(1)高效的通信系統(tǒng)在用戶空間實(shí)現(xiàn)通信協(xié)議精簡(jiǎn)通信協(xié)議Active Message通信機(jī)制(2) 并行程序設(shè)計(jì)環(huán)境PVM(Parallel Virtual Machine)開(kāi)始于1989年夏天,美國(guó)橡樹(shù)嶺國(guó)家實(shí)驗(yàn)室(ORNL)；是一套并行計(jì)算工具軟件，支持多用戶及多任務(wù)運(yùn)行；支持多種結(jié)構(gòu)的計(jì)算機(jī)，工作站、并行機(jī)以及向量機(jī)等；支持C、C+和Fortran語(yǔ)言；自由軟件，使用非常廣泛；編程模型可以是SPMD或MPMD；具有容錯(cuò)功能，當(dāng)發(fā)現(xiàn)一個(gè)結(jié)點(diǎn)出故障時(shí)，自動(dòng)將之刪除MPI(Message Passing Interface)在1992年11月至1994年元月產(chǎn)生。47能用于大多數(shù)并行計(jì)算