計算機(jī)系統(tǒng)結(jié)構(gòu)第7章

第8章并行處理機(jī) 8.1并行處理機(jī)模型 8.2并行處理機(jī)結(jié)構(gòu) 8.3并行處理機(jī)實例 8.4并行處理機(jī)算法舉例2/2/20231計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)兩種并行性概念：(1)同時性并行Simultaneity：兩個或兩個以上事件在同一時刻發(fā)生。(2)并發(fā)性并行Concurrency：兩個或兩個以上事件在同一時間間隔內(nèi)發(fā)生。三條技術(shù)途徑：(1)資源重復(fù)：重復(fù)設(shè)置多個部件來提高速度。(2)時間重疊：流水線(3)資源共享：分時系統(tǒng)，分布式系統(tǒng)8.1并行處理機(jī)模型2/2/20232計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)1.并行處理機(jī)的定義：

多個處理部件PU按照一定方式互連，在同一個控制部件CU控制下，對各自的數(shù)據(jù)完成同一條指令規(guī)定的操作。從CU看，指令是串行執(zhí)行的，從PU看，數(shù)據(jù)是并行處理的。并行處理機(jī)也稱為陣列處理機(jī)，按照按照佛林分類法，它屬于SIMD處理機(jī)。2.并行處理機(jī)的主要應(yīng)用領(lǐng)域：用于高速向量或矩陣運算。2/2/20233計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)3.并行處理機(jī)的操作模型可用五元組來表示：

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

其中：N為PE個數(shù)。如IlliacIV有64個PE。C為控制部件CU執(zhí)行的指令集，包括標(biāo)量指令和程序控制指令。I為所有PE并行執(zhí)行的指令集，包括ALU、數(shù)據(jù)傳送等操作M為屏蔽操作集，將PE劃分為允許操作和禁止操作兩個子集R是數(shù)據(jù)尋徑集，互連網(wǎng)絡(luò)中PE間通信所需要的各種模式2/2/20234計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)4.H.J.Siegel提出的并行處理機(jī)模型

2/2/20235計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.2并行處理機(jī)結(jié)構(gòu)8.2.1并行處理機(jī)的基本結(jié)構(gòu)8.2.2分布存儲器并行處理機(jī)8.2.3共享存儲器并行處理機(jī)8.2.4并行處理機(jī)的特點2/2/20236計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.2.1并行處理機(jī)的基本結(jié)構(gòu)一臺并行處理機(jī)由五個部分組成：

多個處理單元PE， 多個存儲器模塊M， 一個控制器CU， 一個互連網(wǎng)絡(luò)ICN， 一臺輸入輸出處理機(jī)IOP。并行處理機(jī)有兩種典型結(jié)構(gòu)：

分布存儲器并行處理機(jī)， 共享存儲器并行處理機(jī)。

2/2/20237計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.2.2分布存儲器并行處理機(jī)目前的大部分并行處理機(jī)屬于基于分布式存儲器模型。分布式存儲器并行處理機(jī)比較容易構(gòu)成MPP(MassivelyParallelProcessor)，可以有幾十萬個處理部件PE。CU是控制部件。對于標(biāo)量指令，在CU中直接執(zhí)行；對于向量指令，CU把它廣播到各個PE中去執(zhí)行。在CU中通常有一個較大容量的存儲器，用來存放程序和共享數(shù)據(jù)。2/2/20238計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)IOP是輸入輸出處理機(jī)，或稱為主機(jī)。在IOP上安裝操作系統(tǒng)，它除了負(fù)擔(dān)輸入輸出工作外，還負(fù)責(zé)程序的編輯、編譯和調(diào)試等工作。IOP可以是一臺通用計算機(jī)。分布式存儲器并行處理機(jī)必須依靠并行算法來提高PE的利用率。因此，應(yīng)用領(lǐng)域有限，可以認(rèn)為是一種專用計算機(jī)。數(shù)據(jù)在局部存儲器中的分布是一個很關(guān)鍵的問題。標(biāo)量指令與向量指令可以并發(fā)執(zhí)行。2/2/20239計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)分布式存儲器并行處理機(jī)的結(jié)構(gòu)框圖2/2/202310計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.2.3共享存儲器并行處理機(jī)共享多體并行存儲器SM通過互連網(wǎng)絡(luò)與各處理單元PE相連。存儲模塊的數(shù)目等于或略大于處理單元的數(shù)目。為了實現(xiàn)無沖突訪問，存儲模塊的個數(shù)為質(zhì)數(shù)。在存儲模塊之間合理分配數(shù)據(jù)，通過靈活、高速的互連網(wǎng)絡(luò)，使存儲器與處理單元之間的數(shù)據(jù)傳送在大多數(shù)向量運算中都能以存儲器的最高頻率進(jìn)行，而最少受存儲器沖突的影響。2/2/202311計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)共享存儲器模型的處理單元數(shù)目一般不多，幾個至幾十個。BurroughsScientificProcessor(BSP)采用了這種結(jié)構(gòu)。16個PE通過一個16×17的對準(zhǔn)互連網(wǎng)絡(luò)訪問17個共享存儲器模塊。存儲器模塊數(shù)與PE數(shù)互質(zhì)可以實現(xiàn)無沖突并行訪問存儲器。對互連網(wǎng)絡(luò)的要求很高。2/2/202312計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)共享存儲器并行處理機(jī)的結(jié)構(gòu)框圖2/2/202313計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.2.4并行處理機(jī)的特點

并行處理機(jī)的主要特點如下：1.速度快，而且潛力大2.模塊性好，生產(chǎn)和維護(hù)方便3.可靠性高，容易實現(xiàn)容錯和重構(gòu)4.效率低與流水線處理機(jī)、向量處理機(jī)等比較。依靠的是資源重復(fù)，而不是時間重疊，它的每個處理單元要擔(dān)負(fù)多種處理功能，其效率要低一些。2/2/202314計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)5.潛力大主要依靠增加PE個數(shù)，與流水線處理機(jī)主要依靠縮短時鐘周期相比，其提高速度的潛力要大得多。6.依賴于互連網(wǎng)絡(luò)和并行算法互連網(wǎng)絡(luò)決定了PE之間的連接模式，也決定了并行處理機(jī)能夠適應(yīng)的算法。7.需要有一臺高性能的標(biāo)量處理機(jī)如果一臺機(jī)器的向量處理速度極高，但標(biāo)量處理速度只是每秒一百萬次，那么對于標(biāo)量運算占10％的題目來說，總的有效速度就不過是每秒一千萬次。2/2/202315計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.3并行處理機(jī)實例IlliacIV是最先采用SIMD結(jié)構(gòu)的并行處理機(jī)。隨后一個方向是用位片PE制造的并行處理機(jī)， 如GoodyearMPP、AMT/DAP610和TMC/CM-2 CM-5是以SIMD模式運行的同步MIMD計算機(jī)另一方向是字寬運算PE的中粒度SIMD計算機(jī)并行處理機(jī)的兩個發(fā)展方向：

保留陣列結(jié)構(gòu)，但每個處理單元的規(guī)模減小，如一個bit。

去掉陣列結(jié)構(gòu)和分布存儲器。Burroughs公司的BSP是代表。2/2/202316計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.3.1IlliavIV并行處理機(jī)1963年，美國西屋電器公司提出“Slotnick，TheSOLOMONComputer，SimultaneousOperationlinkedOrdinalModularNetwork”。1966年美國國防遠(yuǎn)景研究規(guī)劃局ARPR與伊利諾依大學(xué)簽定合同。原計劃：256個PE，運算速度為1GFLOPS。Burroughs公司和伊利諾依大學(xué)于1972年共同設(shè)計和生產(chǎn)，1975年實際投入運行。用了4倍的經(jīng)費，只達(dá)到1/20的速度。只實現(xiàn)了88＝64個PE，只達(dá)到50MFLOPS。IlliacIV的影響非常大。它是并行處理機(jī)的典型代表，也是分布存儲器并行處理機(jī)的典型代表。2/2/202317計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)

IlliacIV由三大部分組成IlliacIV處理機(jī)陣列： 包括8×8PE、PEM和互連網(wǎng)絡(luò)。陣列控制器CU。輸入輸出處理機(jī)：一臺標(biāo)準(zhǔn)的BurroughsB6700計算機(jī)。2/2/202318計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)1.陣列控制器陣列控制器CU實際上是一臺小型計算機(jī)。

對陣列處理單元實行控制和完成標(biāo)量操作。 標(biāo)量操作與各PE的數(shù)組操作可以重疊執(zhí)行。控制器的功能有以下五個方面： (1)對指令進(jìn)行譯碼，并執(zhí)行標(biāo)量指令； (2)向各PE發(fā)出執(zhí)行數(shù)組操作指令的控制信號； (3)產(chǎn)生并向所有處理單元廣播公共的地址； (4)產(chǎn)生并向所有處理單元廣播公共的數(shù)據(jù)； (5)接收和處理PE、I/O操作以及B6700產(chǎn)生的陷阱中斷信號。2/2/202319計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)2.輸入輸出系統(tǒng)IlliacIV的輸入輸出系統(tǒng)包括： 磁盤文件系統(tǒng)DFS， I/O分系統(tǒng)， 一臺B6700處理機(jī)組成。I/O分系統(tǒng)由三個部分組成： 輸入輸出開關(guān)IOS， 控制描述字控制器CDC， 輸入輸出緩沖存儲器BIOM。2/2/202320計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)3.IlliacIV處理陣列IlliacIV處理陣列由８８＝64個PU組成。每個PU由處理部件PE和它的局部存儲器PEM組成。每一個PUi只和它的東、西、南、北四個近鄰： PUi+1mod64、PUi-1mod64、PUi+8mod64、PUi-8mod64直接連接。南北方向同一列PU連成一個環(huán)， 東西方向構(gòu)成一個閉合螺線。閉合螺線網(wǎng)絡(luò)直徑為7步， 環(huán)形網(wǎng)格的直徑為8步。2/2/202321計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)2/2/202322計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)例如：從PU0到PU36，采用環(huán)行網(wǎng)格必須8步：

PU0PU1PU2PU3PU4PU12PU20PU28PU36 或PU0PU8PU16PU24PU32PU33PU34PU35PU36

或…

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

PU0PU63PU62PU61PU60PU52PU44PU36 或

PU0PU63PU55PU47PU39PU38PU37PU36

或……對于n×n個單元的陣列，網(wǎng)絡(luò)直徑為n-1。2/2/202323計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)二維閉合螺旋線網(wǎng)格網(wǎng)結(jié)點度為4，網(wǎng)絡(luò)直徑為n-1。2/2/202324計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.3.2BSP處理機(jī)BSP（BuroughsScientificProcessor）計算機(jī)是由美國寶來公司和伊利諾依大學(xué)于1979年制造的。BSP是共享存儲器并行處理機(jī)的典型代表。BSP由5個部分組成： 控制處理機(jī)、 并行處理機(jī)、 文件存儲器、 并行存儲器模塊、 對準(zhǔn)網(wǎng)絡(luò)。2/2/202325計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)1.并行處理機(jī)17個存儲模塊，每個模塊512K字，周期160ns5級流水線： (1)從17個存儲模塊中讀出數(shù)據(jù) (2)通過輸出對準(zhǔn)網(wǎng)絡(luò)把數(shù)據(jù)送入16個并行處理部件 (3)16個并行處理部件并行處理機(jī)數(shù)據(jù) (4)通過輸入對準(zhǔn)網(wǎng)絡(luò)把數(shù)據(jù)從并行處理部件送到并行存儲器 (5)把接收到的數(shù)據(jù)寫入并行存儲器時鐘周期160ns，向量運算速度50MFLOPS。2/2/202326計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)2/2/202327計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)2.控制處理機(jī)控制處理機(jī)主要用來控制并行處理機(jī)。提供與系統(tǒng)管理機(jī)相連的接口。執(zhí)行存放在控制存儲器中的操作系統(tǒng)和用戶程序的標(biāo)量部分。把全部的向量指令及成組的標(biāo)量指令送給并行處理機(jī)。控制維護(hù)單元是系統(tǒng)管理機(jī)與控制處理機(jī)之間的接口，用來進(jìn)行初始化、監(jiān)控命令通信和維護(hù)。2/2/202328計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)3.文件存儲器計算任務(wù)文件從系統(tǒng)管理機(jī)加載到文件存儲器，由控制處理機(jī)執(zhí)行。文件存儲器是在BSP直接控制下的唯一外圍設(shè)備。程序執(zhí)行過程中所產(chǎn)生的暫存文件和輸出文件，在將它們送給系統(tǒng)管理機(jī)輸出給用戶之前是存在文件存儲器中的。文件存儲器的數(shù)據(jù)傳輸率較高，大大地緩解了I/O受限問題。2/2/202329計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)4.對準(zhǔn)網(wǎng)絡(luò)對準(zhǔn)網(wǎng)絡(luò)采用全交叉開關(guān)實現(xiàn)。數(shù)據(jù)從一個源廣播至幾個目的地，幾個源尋找一個目的地時能分解沖突。存儲器模塊和對準(zhǔn)網(wǎng)絡(luò)的組合實現(xiàn)了無沖突訪問并行存儲器。對準(zhǔn)網(wǎng)絡(luò)還可以實現(xiàn)快速傅里葉變換、數(shù)據(jù)壓縮和擴(kuò)展操作。2/2/202330計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)5.無訪問沖突存儲系統(tǒng)只有數(shù)組存取和I/O訪問并行存儲器。等效存儲周期為10ns。兩次算術(shù)運算中需要用到三個變量，產(chǎn)生一個結(jié)果，共訪問存儲器4次，并行存儲器和浮點運算之間的頻帶保持完全平衡。對于長向量來，中間結(jié)果存在寄存器中，每次運算只需要一個操作數(shù)。因此并行存儲器有足夠的頻寬留給輸入和輸出信息用。實現(xiàn)一維向量和二維矩陣的行、列、對角線和反對角線的無沖突訪問。2/2/202331計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.4并行處理機(jī)算法舉例 8.4.1有限差分問題 8.4.2矩陣乘 8.4.3求累加和2/2/202332計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)并行處理機(jī)特別依賴于并行算法。并行算法的一個關(guān)鍵是提高向量化的程度。在設(shè)計并行算法時，要特別注意： 數(shù)據(jù)在多個存儲模塊之間的分布。 要解決好訪問存儲器的沖突問題。互連網(wǎng)絡(luò)并不能提供所有處理單元之間的連接，因此，并行算法要充分利用互連網(wǎng)絡(luò)的結(jié)構(gòu)。2/2/202333計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.4.1有限差分問題有限差分方法是一種通用和有效方法：把連續(xù)方程變換成離散形式。二階偏導(dǎo)數(shù)表示為差分形式：

2/2/202334計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī) 并代入原方程，則可得有限差分計算公式： 其中：(x,y)為平面直角坐標(biāo)，h為網(wǎng)格間距。IlliacIV的陣列結(jié)構(gòu)特別適合計算這種在網(wǎng)格上定義的有限差分函數(shù)。把內(nèi)部網(wǎng)格點分配給各個處理單元，計算過程可以并行完成。運算速度的提高可以與處理機(jī)數(shù)目成正比。2/2/202335計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)8.4.2矩陣乘矩陣乘是典型的并行程序，非常適合在SIMD并行處理機(jī)上運行。例如：A、B、C均為8×8的二維矩陣，則C＝A×B的計算公式為：在串行機(jī)上要用一個三重循環(huán)程序，乘法和加法分別為512次。2/2/202336計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)如果在并行處理機(jī)上求解，F(xiàn)ORTRAN語言程序如下： DO10I＝0，7C(I,J)=0 DO20K=0,7 20 C(I,J)=C(I,J)+A(I,K)*B(K,J) 10CONTINUE可以在8個PE的并行處理機(jī)運行，運算速度可提高8倍。也可在64個PE的并行處理機(jī)上運行數(shù)據(jù)如何分布到各個局部存儲器中？2/2/202337計算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)在并行處理機(jī)上，J循環(huán)只需一次。

PE0：c00＝a00b00＋a01b10＋a02b20……＋a07b70PE1：c01＝a00b01＋a01b11＋a02b21……＋a07b71 ……PE7：c07＝a00b07＋a01b17＋a02b27……＋a07b77

PE0：c10＝a10b00＋a11b10＋a12b20……＋a17b70

PE1：c11＝a10b01＋a11b11＋a12b21……＋a17b71 ……PE7：c17＝a10b07＋a11b17＋a12b27……＋a17b77 …… PE7：c77＝a70b07＋a71b17＋a72b27……＋a77b77