并行处理机和多处理机课件

並行處理機和多處理機並行處理機又叫SIMD電腦。它是單一控制部件控制下的多個處理單元構成的陣列，所以又稱為陣列處理機。多處理機是由多台獨立的處理機組成的系統。並行處理機結構和實例多處理機結構和實例並行處理電腦模型並行處理機定義：

多個PU按照一定方式互連，在同一個CU控制下，對各自的數據完成同一條指令規定的操作。

從CU看，指令是串行執行的，從PU看，數據是並行處理的。

並行處理機也稱為陣列處理機。按照佛林分類法，它屬於SIMD電腦。並行處理機的應用領域：

主要用於高速向量或矩陣運算中。8.1並行處理機結構和實例P0M0PE0P1M1PE1P2M2PE2Pn-1Mn-1Pen-1互連網絡控制器……H·J·Siegel提出的並行處理機模型下圖是H.J.Siegel提出的SIMD電腦的操作模型並行處理機的操作模型可用五元組來表示：

M＝(N，C，I，M，R),

其中：

N為PE個數。如IlliacIV有64個PE。

C為由控制部件CU直接執行的指令集，包括標量指令和程式控制指令。

I為所有PE並行執行的指令集，包括算術運算、邏輯運算、數據尋徑、遮罩以及其他由每個活動的PE對它的數據所執行的局部操作。

M為遮罩操作集，每種遮罩將PE劃分為允許操作和禁止操作兩個子集。

R是數據尋徑集，說明互連網絡中PE間通信所需要的各種設置模式。系統型號SIMD計算系統

結構和性能語言、編譯器和軟體支持MasPar

MP-1系列1024~16384個PE,26GIPS或1.3Gflops;每個PE帶16KB本地記憶體,X-Net網格加一個多級交叉開關互連網Fortran77,MasParFortran(MPF)和MasPar並行應用語言;X窗口UNIX/OS,符號調試程式,可視化和動畫製作程式典型並行處理機ActiveMemoryTechnologyDAP600

系列1K位/PE方形網格互連成4096PE的細粒、位片SIMD陣列，正交4-鄰位鏈接，20GIPS和560Mflops峰值性能由主機VAX/VMS或UNIXFortran-plus或DAP上APAL提供，主機的Fortran77或C;與Fortran90標準有關的Fortran-plusThinkingMachines公司CM-265536個PE排成10維超立方體,每個PE可有1M位記憶體,32個PE共用FPU選件,峰值速度28Gflops和持續速度5.6Gflops由VAX,Sun或Symbolics360主機驅動,PARIS支持的Lisp編譯器、Fortran90、C*和*Lisp並行處理機的基本結構兩種SIMD電腦的基本結構：分佈記憶體並行處理機共用記憶體並行處理機一臺並行處理機由五個部分組成：

多個處理單元PE

多個記憶體模組M

一個控制器CU

一個互連網絡ICN

一臺輸入輸出處理機IOP目前的大部分並行處理機是基於分佈式記憶體模型的系統。比較容易構成MPP（MassivelyParallelProcessor）,幾十萬個PE。必須依靠並行演算法來提高PE的利用率。因此，應用領域很有限。CU是控制部件，執行標量指令，並把向量指令廣播到各個PE中。在CU中通常有一個較大容量的記憶體。IOP是輸入輸出處理機，或稱為主機。在IOP上安裝操作系統，它除了負擔輸入輸出工作外，還負責程式的編輯、編譯和調試等工作。數據在局部記憶體中的分佈是一個很關鍵的問題。標量指令與向量指令可以併發執行。1、分佈記憶體結構LM0互連網絡……PE0CULM1PE1LMn-1PEn-1IOP……共用的多體並行記憶體SM通過互連網絡與各處理單元PE相連。存儲模組的數目等於或略大於處理單元的數目。同時在存儲模組之間合理分配數據，通過靈活、高速的互連網絡，使記憶體與處理單元之間的數據傳送在大多數向量運算中都能以記憶體的最高頻率進行，而最少受存儲衝突的影響。共用記憶體模型的處理單元數目一般不多，幾個至幾十個。BurroughsScientificProcessor(BSP)採用了這種結構。16個PE通過一個16×17的對準互連網絡訪問17個共用記憶體模組。記憶體模組數與PE數互質可以實現無衝突並行訪問記憶體。2.共用記憶體並行處理機PE0互連網絡……CUPE1PEn-1IOPSM0……SM1SMk-1並行處理機的主要特點如下：速度快，特別適於高速數值計算。SIMD依靠的是資源重複，而不是時間重疊。它依靠增加PE個數，與流水線處理機主要依靠縮短時鐘週期相比，其提高速度的潛力要大得多。依賴於互連網絡和並行演算法。互連網絡決定了PE之間的連接模式，也決定了並行處理機能夠適應的演算法。需要有一臺高性能的標量處理機。如果一臺機器的向量處理速度極高，但標量處理速度只是每秒一百萬次，那麼對於標量運算占10％的題目來說，總的有效速度就不過是每秒一千萬次。SIMD基本上是一臺向量處理專用電腦。儘管它有一個功能很強的控制部件實際上起作標量處理機的作用，但仍然必須和一臺高性能單處理機配合工作，使後者擔負系統的全部管理功能。並行處理機的特點IlliacIV是最先採用SIMD結構的並行機隨後一個方向是用位片PE製造的並行機，如GoodyearMPP、AMT/DAP610和TMC/CM-2。CM-5是以SIMD模式運行的同步MIMD電腦。另一方向是用字寬運算PE的中粒度SIMD電腦。並行處理機的兩個發展方向：保留陣列結構，但每個處理單元的規模減小，如一個bit。去掉陣列結構和分佈記憶體。Burroughs公司的BSP是典型代表。

GF-11是由IBMWatson實驗室研製、作科學模擬研究用的。MasParMP1是中粒度並行處理機的典型代表。下麵介紹並行處理機的兩種典型代表： 採用陣列結構分佈記憶體的IlliacIV並行處理機

去掉陣列結構和分佈記憶體BSP並行處理機。並行處理機實例IlliacIV(Barnes等，1968）GoodyearMPP(Batcher,1980）BSP(kuck和Stokes，1982）DAP610(AMT，Inc.1987)CM-2(TMC,1990)CM-5(TMC,1991)MasParMPI(Nickolls,1990)IBMGF-11(Beetem等，1985）SIMD電腦發展過程1963年，美國西屋電器公司提出“Slotnick，TheSOLOMONComputer，SimultaneousOperationlinkedOrdinalModularNetwork”。1966年美國國防遠景研究規劃局ARPR與伊利諾依大學簽定合同。原計畫：256個PE，每個PE每240ns處理一個64位的浮點數，每個局部記憶體PEM為2K?64位，總的運算速度為1GFLOPS。美國Burroughs公司和伊利諾依大學於1972年共同設計和生產，1975年實際投入運行。用了4倍的經費，只達到1/20的速度。只實現了8?8＝64個PE，只達到50MFLOPS。IlliacIV系統的影響非常大。它是並行處理機的典型代表，也是分佈記憶體並行處理機的典型代表。IlliacIV系統由三大部分組成。IlliacIV處理機陣列，陣列控制器，一臺標準的BurroughsB6700電腦。1IlliacIV

陣列處理機1、IlliacIV處理陣列IlliacIV處理陣列由8´8＝64個PU組成。每個PU由處理部件PE和它的局部記憶體PEM組成。每一個PUi只和它的東、西、南、北四個近鄰直接連接。{PUi+1mod64、PUi-1mod64、PUi+8mod64、PUi-8mod64}南北方向上同一列的PU連成一個環，東西方向上構成一個閉合螺線。採用閉合螺線最短距離不超過7步。而普通網格最短距離不超過8步。例如：從PU0到PU36的距離：採用普通網格必須8步：

PU0®PU1

®PU2

®PU3

®PU4

®PU12

®PU20

®PU28

®PU36

或PU0

®PU8

®PU16

®PU24

®PU32

®PU33

®PU34

®PU35

®PU36

或……（等於8步的很多，大於8步的更多）

如果採用閉合螺旋線，只需要7步：

PU0®PU63®PU62®PU61®PU60®PU52®PU44®PU36普通網格必須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®PU47®PU39®PU38®PU37®PU36

或……2、陣列控制器陣列控制器CU實際上是一臺小型控制電腦。對陣列處理單元實行控制和完成標量操作。標量操作與各PE的數組操作可以重疊執行。控制器的功能有以下五個方面：

(1)對指令進行解碼，並執行標量指令；

(2)向各處理單元發出執行數組操作指令所需的控制信號；

(3)產生和向所有處理單元廣播公共的地址；(4)產生和向所有處理單元廣播公共的數據；

(5)接收和處理PE、I/O操作以及B6700產生的陷阱中斷信號。2、輸入輸出系統IlliacIV的輸入輸出系統由磁片檔系統DFS、I/O分系統和一臺B6700處理機組成。I/O分系統又由輸入輸出開關IOS、控制描述字控制器CDC和輸入輸出緩衝記憶體BIOM三個部分組成。試在含一個PE的SISD機和在含m個PE的且連接成一線性環的SIMD機上計算下列求內積的運算式。假定完成每次ADD操作需2個單元時間，完成每次MULTIPLY操作需4個單位時間，沿雙向環在相鄰PE間移數需1個單位時間。（1）SISD電腦上計算s需多少時間？（2）SIMD電腦上計算s需多少時間？（3）用SIMD機計算s相對於用SISD機計算的加速比是多少？[習題8.6]（1）在SISD電腦中計算s需要串行計算n次乘法和n-1次加法。共需要時間：演算法如下：

S=A1*B1Fori=2tonDo S=S+Ai*BiEnddo（2）在SIMD電腦上計算採用如下的演算法：（假設m≤n）首先，把向量中的n對元素儘量平均地分配到m個處理器中，每個處理器最多分配[n/m]+1對，最少分配[n/m]對，最多經過4（[n/m]+1）+2[n/m]時間，所有n個處理器上都得到了一個局部和，對這m個處理器[解答]

構成的線性環做累加運算。若採用兩路7線性累加的方法共用做加法[m/2]次,數據傳遞[m/2]次，共用時間4（[n/m]+1）+2[n/m]+3[m/2]=6[n/m]+3[m/2]+4。若用遞歸累加的方法，假設m是2的p次冪。做p次並行的加法，移位1+2+4+…+m/2=m-1次。用時2p+（m-1）。總共用時為

4（[n/m]+1）+2[n/m]+2logm+（m-1）=6[n/m]+m+2logm+3進一步分析：當2logm<m/2時即m>16時並行累加比兩路線性累加更優。反之，當m<16時，兩路線性累加更快。其根本原因就是並行累加演算法節省了加法時間，但是花費更多的數據傳送時間。演算法描述如下:Par：Forj=1tomDoS(j)=A1j*B1jFor2to[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])Enddo

（3）加速比當採用兩路線性累加的方法時加速比為：若m=n，做乘法的時間變為4，則加速比簡化為當採用遞歸併行累加時加速比為：當m=n時，做乘法的時間變為4，則加速比簡化為分析其原因，可以看出，線性互連網絡的傳輸開銷在這裏是制約加速比增長的最大障礙，無論採用何種並行演算法，一個數據從線性環形網路中的一個節點傳遞到最遠的節點的最短時間為m/2，這個時間是無法改進的，並且隨著處理節點的增多成為最主要的時間開銷。相對而言，加法和乘法隨著處理單元的增多，所占的時間比例越來越小。

8.2多處理機結構和實例兩個或兩個以上處理機(包括PU和CU)，通過高速互連網絡連接起來，在統一的操作系統管理下，實現指令以上級（任務級、作業級）並行。按照Flynn分類法，多處理機系統屬於MIMD電腦。多處理機系統由多個獨立的處理機組成，每個處理機都能夠獨立執行自己的程式。多處理機結構由若干台獨立的電腦組成，每臺電腦能夠獨立執行自己的程式。Flynn稱這種結構為多指令流多數據流（MIMD）結構。多處理機系統中的處理機之間按某種形式互連，從而實現程式之間的數據交換和同步。多處理機系統中每臺處理機都有寄存器、運算器、邏輯部件、訪問記憶體和I/O的通道。還有一種多處理機系統中每臺處理機有自己的記憶體和I/O設備。多處理機結構互連網絡處理機1處理機2處理機N記憶體記憶體記憶體I/OI/O具有通過互連網絡共用記憶體和I/O的多處理機系統處理機1記憶體I/O處理機2記憶體I/O處理機N記憶體I/O互連網每個處理機都擁有自己的記憶體和I/O的多處理機系統

1、結構靈活性並行處理機：專用，PE數很多（幾千個），固定有限的通信

多處理機：通用，幾十個，高速靈活的通信2、程式並行性並行處理機的並行性存在於指令內部，識別比較容易。

多處理機的並行性存在於指令外部，在多個任務之間，識別難度較大。一個簡單的例子：

Y=A+B*C*D/E+F

用兩個處理機：

CPU1：CPU2：B*C，D/E，

A+F，B*C*D/E

A+B*C*D/E+F多處理機系統的特點3、並行任務派生

並行處理機把同種操作集中在一起，由指令直接啟動各PE同時工作。多處理機用專門的指令來表示併發關係，一個任務開始執行時能夠派生出與它並行執行的另一些任務，如果任務數多於處理機數，多餘的任務進入排隊器等待。4、進程同步

並行處理機僅一個CU，自然是同步的

多處理機執行不同的指令，工作進度不會也不必保持相同,先做完的要停下來等待。有數據相關和控制相關也要停下來等待,要採取特殊的同步措施來保持程式所要求的正確順序。5、資源分配和進程調度

並行處理機的PE是固定的，採用遮罩手段改變實際參加操作的PE數目

多處理機執行併發任務，需用處理機的數目不固定，各個處理機進入或退出任務的時刻不相同，所需共用資源的品種、數量又隨時變化提出資源分配和進程調度問題，它對整個系統的效率有很大的影響。引起峰值性能下降的原因是：

(1)因處理機間通信而產生的延遲

(2)一臺處理機與其它處理機同步所需的開銷

(3)當沒有足夠多任務時，一臺或多臺處理機處於空閒狀態

(4)由於一臺或多臺處理機執行無用的工作

(5)系統控制和操作調度所需開銷研究多處理機的目的：

提前5年得到速度高10倍的機器。或用1/10的價格獲得一臺高性能的機器。

如果設計得好，在某些適合進行並行處理得應用領域，可以達到：提前10年得到速度高100倍的機器或用1/100的價格獲得一臺高性能的機器。多處理機性能模型並行性在很大程度上依賴於R/C比值，其中：R代表程式執行時間，C代表通信開銷。通常：R/C比值小，並行性低。R/C比值大，並行性高如果把作業分解成較大的塊，就能得到較大的R/C值，但是所得到的並行性比最大可能的並行性要小得多。R/C比值是衡量任務粒度(Granularity)大小的尺度

在粗粒度（Coarsegrain）並行情況下，R/C比值比較大，通信開銷小

在細粒度（Finegrain）並行情況下，R/C比值比較小，通信開銷大細粒度並行性需要的處理機多，粗粒度並行性需要的處理機少。細粒度並行性的基本原理是把一個程式盡可能地分解成能並行執行的小任務。在極端情況下，一個小任務只完成一個操作。1.基本模型在兩臺處理機情況每個任務的執行時間為R個單位時間兩個任務不在同一臺處理機上時，通信開銷為C個單位時間K個任務給一臺處理機M-K個任務給另一臺處理機總處理時間=Rmax(M-K，K)+C(M-K)K結論：當R/C<M/2時，把所有任務分配給一臺處理機能使總處理時間最小；當R/C>M/2時，把任務平均分給兩臺處理機能使總處理時間最小。2.N臺處理機系統的基本模型將Ki個任務分配給第i臺處理機。推廣前面的式子：分析任務均分給N臺處理機和任務集中在一臺處理機的總處理時間差，有：如果R/C比臨界值M/2大，將任務平均分配給盡可能多的處理機進行處理，能獲得最短處理時間。如果R/C比臨界值M/2小，即使有很多臺處理機可供使用，也不可能比用一臺處理機處理全部任務快。並行系統的加速比是一個計算問題在一臺處理機上的運行時間與在並行系統上的運行時間的比值，可近似如下：多處理機的Cache一致性（自己看）多處理機系統主要有四大類：(1)多向量處理機系統：如CRAYYMP-90,NECSX-3和FUJITSUVP-2000(2)SMP(SymmetryMultiProcessors)對稱多處理機;SMP(SharedMemoryMulptiProcessors)共用存儲多處理機如SGIChallenge，SunSparcCenter2000(3)MPP(massivelyparallelprocessing)大規模並行處理機

如IntelParagon,CM-5,CrayT3D(4)Cluster機群系統（NOW或COM）

多處理機實例科學計算中的重大課題要求提供3T性能：

(1)1Teraflops計算能力

(2)1Terabyte主記憶體

(3)1Terabyte/s輸入輸出頻帶寬度

目前，速度還慢1000倍左右，存儲容量和I/O帶寬差距更大。科學計算中的重大課題：

全球氣候預報,基因工程,飛行動力學,海洋環流,流體動力學,超導建模,半導體建模,量子染色動力學,視覺採用的關鍵技術：

VLSI,可擴展技術,共用虛擬存儲技術

大規模並行處理機(MPP)虛擬共用記憶體(SharedVirtualMemory)

也稱為共用分佈記憶體(DistributedSharedMemory)；物理上分佈記憶體，邏輯上共用記憶體。虛擬共用記憶體的優點：

編程容易,系統結構靈活

可擴充性好,有較好的軟體移植性與消息傳遞方式相比，程式運行效率高，主要原因：(1)數據塊緩存在本地(記憶體或Cache中),可以多次使用

(2)通信時間分散，提高了並行性

(3)擴大存儲空間，減少換頁操作虛擬共用記憶體實現途徑：

(1)硬體實現,利用Cache技術。需要增加專用硬體

(2)操作系統和庫實現，通過虛擬存儲機制取得共用和一致性。在松耦合的分佈存儲多處理機上，不需要增加任何硬體

(3)編譯實現，自動將共用訪問轉換成同步和一致原語。大多數系統採用途徑(1)和(2)，或這兩種途徑結合實現SMP稱為共用存儲多處理機(SharedMemorymulptiProcessors),也稱為對稱多處理機

(SymmetryMultiProcessors)有三種模型：(1)UMA多處理機

均勻記憶體存取模型(UniformMemoryAccess)

記憶體被所有處理機均勻共用

所有處理機對所有存儲單元具有相同的存取時間每臺處理機有局部Cache週邊設備可以共用(2)NUMA多處理機

非均勻記憶體存取(NonuniformMemoryAccess)模型

記憶體訪問時間隨存儲單元的位置不同而變化。

共用記憶體在物理上是分佈在所有處理機中的本地記憶體。所有局部記憶體地址空間的集合就組成了全局地址空間。

對稱多處理機(SMP)系統互連網絡NUMA多處理機模型P1LM1……P2LM2PnLMn系統互連網絡（匯流排、交叉開關、多級網路）UMA多處理機模型P1……P2PnSM1SM2SM2I/O……處理機訪問本地記憶體比較快，訪問屬於另一臺處理機的遠程記憶體則比較慢，因為通過互連網絡會產生附加的時間延遲。(3)COMA多處理機只有Cache的記憶體結構(Cache-OnlyMemoryArchitecture)模型；COMA是一種只用Cache的多處理機系統實際上，COMA模型是NUMA模型的一種特例，後者分佈記憶體換成了Cache在每個處理機結點上沒有主記憶體，全部Cache組成了全局虛擬地址空間遠程Cache訪問通過分佈Cache目錄進行共用存儲系統擁有統一的尋址空間，程式員不必參與數據分配和傳輸。互連網絡COMA多處理機模型D1Cache1……P1D2Cache2P2DnCachenPn1、機群系統的組成機群系統是利用高速網路將一組高性能工作站或高檔PC機連接起來，在並行程式設計以及可視化人機交互集成開發環境支持下，統一調度，協調處理，實現高效並行處理的系統。Cluster、NOW、COW從結構和結點間的通信方式來看，屬於分佈存儲系統。機群系統中的主機和網路可以是同構的，也可以是異構的。微處理機技術、網路技術和並行編程環境的發展使得機群系統這一新的並行處理系統形式正成為當前研究的熱點。

(1)微處理器的性能不斷提高。

(2)網路技術的進步使得鬆散耦合系統的通信瓶頸逐步得到緩解。

機群系統(Cluster)(3)並行編程環境的開發使得新編並行程式或改寫串行程序更為容易。2、機群系統的特點(1)系統開發週期短。(2)用戶投資風險小。(3)系統價格低。(4)節約系統資源。UCBerkeley電腦系100多臺工作站的使用情況調查表明，一般單機系統的使用率不到10%，而機群系統中的資源利用率可達到80%左右。(5)系統擴展性好。(6)用戶編程方便。3、機群系統的關鍵技術(1)高效的通信系統

在用戶空間實現通信協議

精簡通信協議

ActiveMessage通信機制(2)並行程式設計環境

PVM(ParallelVirtualMachine)

開始於1989年夏天,美國橡樹嶺國家實驗室(ORNL)；是一套並行計算工具軟體，支持多用戶及多任務運行；支持多種結構的電腦，工作站、並行機以及向量機等；支持C、C++和Fortran語言；自由軟體