計算機系統(tǒng)結構第八章并行處理機

1、第8章 SIMD 處理機,8.1 SIMD處理機模型8.2 SIMD處理機的結構8.3 SIMD處理機實例8.4 SIMD處理機算法舉例,兩種并行性概念：(1)同時性并行Simultaneity：兩個或兩個以上事件在同一時刻發(fā)生。(2)并發(fā)性并行Concurrency：兩個或兩個以上事件在同一時間間隔內發(fā)生。三條技術途徑：(1)資源重復：重復設置多個部件來提高速度。(2)時間重疊：流水線(3)資源共

2、享：分時系統(tǒng)，分布式系統(tǒng),8.1 SIMD處理機模型,1. SIMD處理機的定義： 多個處理部件PU按照一定方式互連，在同一個控制部件CU控制下，對各自的數據完成同一條指令規(guī)定的操作。從CU看，指令是串行執(zhí)行的，從PU看，數據是并行處理的。按照按照佛林分類法，它屬于SIMD處理機。SIMD處理機又稱SIMD處理機，也稱為陣列處理機。2. SIMD處理機的主要應用領域：用于高速向量或矩陣運算。,3. SIMD處理機的操作模型

3、可用五元組來表示： M＝(N，C，I，M，R), 其中：N為PE個數。如IlliacIV有64個PE。C為控制部件CU執(zhí)行的指令集，包括標量指令和程序控制指令。I為所有PE并行執(zhí)行的指令集，包括ALU、數據傳送等操作M為屏蔽操作集，將PE劃分為允許操作和禁止操作兩個子集R是數據尋徑集，互連網絡中PE間通信所需要的各種模式,4. H.J.Siegel提出的SIMD處理機模型,8.2 SIMD處理機結構,8.2.1 SIM

4、D處理機的基本結構8.2.2 分布存儲器SIMD處理機8.2.3 共享存儲器SIMD處理機8.2.4 SIMD處理機的特點,8.2.1 SIMD處理機的基本結構,一臺SIMD處理機由五個部分組成：多個處理單元PE，多個存儲器模塊M，一個控制器CU，一個互連網絡ICN，一臺輸入輸出處理機IOP。SIMD處理機有兩種典型結構：分布存儲器SIMD處理機，共享存儲器SIMD處理機。,8.2.2 分布存儲器SI

5、MD處理機,目前的大部分SIMD處理機屬于基于分布式存儲器模型。分布式存儲器SIMD處理機比較容易構成MPP(Massively Parallel Processor)，可以有幾十萬個處理部件PE。CU是控制部件。對于標量指令，在CU中直接執(zhí)行；對于向量指令，CU把它廣播到各個PE中去執(zhí)行。在CU中通常有一個較大容量的存儲器，用來存放程序和共享數據。,IOP是輸入輸出處理機，或稱為主機。在IOP上安裝操作系統(tǒng)，它除了負擔輸入輸出工

6、作外，還負責程序的編輯、編譯和調試等工作。 IOP可以是一臺通用計算機。分布式存儲器SIMD處理機必須依靠并行算法來提高PE的利用率。因此，應用領域有限，可以認為是一種專用計算機。數據在局部存儲器中的分布是一個很關鍵的問題。標量指令與向量指令可以并發(fā)執(zhí)行。,分布式存儲器SIMD處理機的結構框圖,8.2.3 共享存儲器SIMD處理機,共享多體并行存儲器SM通過互連網絡與各處理單元PE相連。存儲模塊的數目等于或略大于處理單元的數目。

7、為了實現(xiàn)無沖突訪問，存儲模塊的個數為質數。在存儲模塊之間合理分配數據，通過靈活、高速的互連網絡，使存儲器與處理單元之間的數據傳送在大多數向量運算中都能以存儲器的最高頻率進行，而最少受存儲器沖突的影響。,共享存儲器模型的處理單元數目一般不多，幾個至幾十個。Burroughs Scientific Processor(BSP)采用了這種結構。16個PE通過一個16×17的對準互連網絡訪問17個共享存儲器模塊。存儲器模塊數與P

8、E數互質可以實現(xiàn)無沖突并行訪問存儲器。對互連網絡的要求很高。,共享存儲器SIMD處理機的結構框圖,8.2.4 SIMD處理機的特點,SIMD處理機的主要特點如下：1. 速度快，而且潛力大2. 模塊性好，生產和維護方便3. 可靠性高，容易實現(xiàn)容錯和重構4. 效率低與流水線處理機、向量處理機等比較。依靠的是資源重復，而不是時間重疊，它的每個處理單元要擔負多種處理功能，其效率要低一些。,5. 潛力大 主要依靠增加PE個數

9、，與流水線處理機主要依靠縮短時鐘周期相比，其提高速度的潛力要大得多。6. 依賴于互連網絡和并行算法 互連網絡決定了PE之間的連接模式，也決定了SIMD處理機能夠適應的算法。7. 需要有一臺高性能的標量處理機 如果一臺機器的向量處理速度極高，但標量處理速度只是每秒一百萬次，那么對于標量運算占10％的題目來說，總的有效速度就不過是每秒一千萬次。,8.3 SIMD處理機實例,IlliacIV 是最先采用SIMD結構的SIM

10、D處理機。隨后一個方向是用位片PE制造的SIMD處理機，如Goodyear MPP、AMT/DAP610和TMC/CM-2CM-5是以SIMD模式運行的同步MIMD計算機另一方向是字寬運算PE的中粒度SIMD計算機SIMD處理機的兩個發(fā)展方向：保留陣列結構，但每個處理單元的規(guī)模減小，如一個bit。去掉陣列結構和分布存儲器。Burroughs公司的BSP是代表。,8.3.1 IlliacIV SIMD處理機,1963

11、年，美國西屋電器公司提出“Slotnick，The SOLOMON Computer，Simultaneous Operation linked Ordinal Modular Network”。1966年美國國防遠景研究規(guī)劃局ARPR與伊利諾依大學簽定合同。原計劃：256個PE，運算速度為1GFLOPS。Burroughs公司和伊利諾依大學于1972年共同設計和生產，1975年實際投入運行。用了4倍的經費，只達到1/20的速度。只

12、實現(xiàn)了8?8＝64個PE，只達到50MFLOPS。IlliacIV的影響非常大。它是SIMD處理機的典型代表，也是分布存儲器SIMD處理機的典型代表。,IlliacIV由三大部分組成IlliacIV處理機陣列：包括8×8 PE、PEM和互連網絡。陣列控制器CU。輸入輸出處理機：一臺標準的Burroughs B6700計算機。,1. 陣列控制器陣列控制器CU實際上是一臺小型計算機。對陣列處理單元實行控制和完成標量

13、操作。標量操作與各PE的數組操作可以重疊執(zhí)行?？刂破鞯墓δ苡幸韵挛鍌€方面：(1)對指令進行譯碼，并執(zhí)行標量指令；(2)向各PE發(fā)出執(zhí)行數組操作指令的控制信號；(3)產生并向所有處理單元廣播公共的地址；(4)產生并向所有處理單元廣播公共的數據；(5)接收和處理PE、I/O操作以及B6700產生的陷阱中斷信號。,2. 輸入輸出系統(tǒng)IlliacIV的輸入輸出系統(tǒng)包括：磁盤文件系統(tǒng)DFS，I/O分系統(tǒng)，一

14、臺B6700處理機組成。I/O分系統(tǒng)由三個部分組成：輸入輸出開關IOS，控制描述字控制器CDC，輸入輸出緩沖存儲器BIOM。,3. IlliacIV處理陣列IlliacIV處理陣列由８?８＝64個PU組成。每個PU由處理部件PE和它的局部存儲器PEM組成。每一個PUi只和它的東、西、南、北四個近鄰：PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64直接連接。南北

15、方向同一列PU連成一個環(huán)，東西方向構成一個閉合螺線。閉合螺線網絡直徑為7步，環(huán)形網格的直徑為8步。,例如：從PU0到PU36，采用環(huán)行網格必須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?

16、PU52?PU44?PU36或PU0?PU63?PU55?PU47?PU39?PU38?PU37?PU36 或 ……對于n×n個單元的陣列，網絡直徑為n-1。,二維閉合螺旋線網格網 結點度為4，網絡直徑為n-1。,8.3.2 BSP處理機,BSP（Buroughs Scientific Processor）計算機是由美國寶來公司和伊利諾依大學于1979年制造的。BSP是共享存儲器SIMD處理機的典型代

17、表。BSP由5個部分組成：控制處理機、SIMD處理機、文件存儲器、并行存儲器模塊、對準網絡。,1. SIMD處理機17個存儲模塊，每個模塊512K字，周期160ns5級流水線：(1)從17個存儲模塊中讀出數據(2)通過輸出對準網絡把數據送入16個并行處理部件(3)16個并行處理部件SIMD處理機數據(4)通過輸入對準網絡把數據從并行處理部件送到并行存儲器(5)把接收到的數據寫入并行存儲器時

18、鐘周期160ns，向量運算速度50MFLOPS。,2. 控制處理機控制處理機主要用來控制SIMD處理機。提供與系統(tǒng)管理機相連的接口。執(zhí)行存放在控制存儲器中的操作系統(tǒng)和用戶程序的標量部分。把全部的向量指令及成組的標量指令送給SIMD處理機?？刂凭S護單元是系統(tǒng)管理機與控制處理機之間的接口，用來進行初始化、監(jiān)控命令通信和維護。,3. 文件存儲器計算任務文件從系統(tǒng)管理機加載到文件存儲器，由控制處理機執(zhí)行。文件存儲器是在BSP直接控

19、制下的唯一外圍設備。程序執(zhí)行過程中所產生的暫存文件和輸出文件，在將它們送給系統(tǒng)管理機輸出給用戶之前是存在文件存儲器中的。文件存儲器的數據傳輸率較高，大大地緩解了I/O受限問題。,4. 對準網絡對準網絡采用全交叉開關實現(xiàn)。數據從一個源廣播至幾個目的地，幾個源尋找一個目的地時能分解沖突。存儲器模塊和對準網絡的組合實現(xiàn)了無沖突訪問并行存儲器。對準網絡還可以實現(xiàn)快速傅里葉變換、數據壓縮和擴展操作。,5. 無訪問沖突存儲系統(tǒng)只有數組

20、存取和I/O訪問并行存儲器。等效存儲周期為10ns。兩次算術運算中需要用到三個變量，產生一個結果，共訪問存儲器4次，并行存儲器和浮點運算之間的頻帶保持完全平衡。對于長向量來，中間結果存在寄存器中，每次運算只需要一個操作數。因此并行存儲器有足夠的頻寬留給輸入和輸出信息用。實現(xiàn)一維向量和二維矩陣的行、列、對角線和反對角線的無沖突訪問。,8.4 SIMD處理機算法舉例,8.4.1 有限差分問題8.4.2 矩陣乘8.4.3

21、求累加和,SIMD處理機特別依賴于并行算法。并行算法的一個關鍵是提高向量化的程度。在設計并行算法時，要特別注意：數據在多個存儲模塊之間的分布。要解決好訪問存儲器的沖突問題?；ミB網絡并不能提供所有處理單元之間的連接，因此，并行算法要充分利用互連網絡的結構。,8.4.1 有限差分問題,有限差分方法是一種通用和有效方法：把連續(xù)方程變換成離散形式。二階偏導數表示為差分形式：,并代入原方程，則可得有限差分計算公式：其中

22、：(x, y)為平面直角坐標， h為網格間距。IlliacIV的陣列結構特別適合計算這種在網格上定義的有限差分函數。把內部網格點分配給各個處理單元，計算過程可以并行完成。運算速度的提高可以與處理機數目成正比。,8.4.2 矩陣乘,矩陣乘是典型的并行程序，非常適合在SIMDSIMD處理機上運行。例如：A、B、C均為8×8的二維矩陣，則C＝A×B的計算公式為：在串行機上要用

23、一個三重循環(huán)程序，乘法和加法分別為512次。,如果在SIMD處理機上求解，F(xiàn)ORTRAN語言程序如下： DO 10 I＝0，7 C(I, J)=0 DO 20 K=0, 720 C(I, J)=C (I, J )+A(I, K) * B(K, J)10 CONTINUE可以在8個PE的SIMD處理機運行，運算速度可提高8倍。也可在64個PE的SIMD處理機上

24、運行數據如何分布到各個局部存儲器中？,在SIMD處理機上，J循環(huán)只需一次。 PE0：c00＝a00b00＋a01b10＋a02b20……＋a07b70 PE1：c01＝a00b01＋a01b11＋a02b21……＋a07b71…… PE7：c07＝a00b07＋a01b17＋a02b27……＋a07b77 PE0：c10＝a10b00＋a11b10＋a12b20……＋a17b70 PE1：c11＝a10b

25、01＋a11b11＋a12b21……＋a17b71…… PE7：c17＝a10b07＋a11b17＋a12b27……＋a17b77……PE7：c77＝a70b07＋a71b17＋a72b27……＋a77b77,8.4.3 求累加和,把N個數的順序相加變?yōu)椴⑿邢嗉?。串行求和?FORTRAN 程序如下： C(-1)＝0 DO 10 I＝0, N10 C(I)＝C(I-

26、1)＋A(I)在SIMD處理機上，采用遞歸加法，F(xiàn)ORTRAN 程序如下： DO 10 I=0，log2N－110 A＝A＋SRL(A, 2**I) ;A向量右移2i個PE在SIMD處理機上只需做 log2N 次加法。,遞歸求和算法的性能分析：運算速度提高：加速比為N/log2N倍運算次數增加：從N次增加到N·log2N次效率降低：實際效率為1/log2N如：N＝1024，速度提高1