第8章SIMD處理機PPT課件

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

2、多個處理部件PU按照一定方式互連，在同一個控按照一定方式互連，在同一個控制部件制部件CU控制下，對各自的數(shù)據(jù)完成同一條指令控制下，對各自的數(shù)據(jù)完成同一條指令規(guī)定的操作。從規(guī)定的操作。從CU看，指令是串行執(zhí)行的，從看，指令是串行執(zhí)行的，從PU看，數(shù)據(jù)是并行處理的。看，數(shù)據(jù)是并行處理的。按照按照佛林分類法，它屬于SIMD處理機。SIMD處理機又稱SIMD處理機，也稱為陣列處理機。2. SIMD處理機的主要應用領域：處理機的主要應用領域：用于高速向量或矩陣運算。3. SIMD處理機的操作模型可用五元組來表示：處理機的操作模型可用五元組來表示： M(N，C，I，M，R), 其中：N為為PE個數(shù)個數(shù)。如

3、IlliacIV有64個PE。C為控制部件為控制部件CU執(zhí)行的指令集執(zhí)行的指令集，包括標量指令和程序控制指令。I為所有為所有PE并行執(zhí)行的指令集并行執(zhí)行的指令集，包括ALU、數(shù)據(jù)傳送等操作M為屏蔽操作集為屏蔽操作集，將PE劃分為允許操作和禁止操作兩個子集R是數(shù)據(jù)尋徑集是數(shù)據(jù)尋徑集，互連網(wǎng)絡中PE間通信所需要的各種模式 PE0 PE1 PE2 PE2 控制器 P0 M0 P1 P1 P2 P2 PN-1 PN-1 互連網(wǎng)絡 4. H.J.Siegel提出的提出的SIMD處理機模型處理機模型 8.2 SIMD處理機結構處理機結構8.2.1 SIMD處理機的基本結構處理機的基本結構8.2.2 分布存

4、儲器分布存儲器SIMD處理機處理機8.2.3 共享存儲器共享存儲器SIMD處理機處理機8.2.4 SIMD處理機的特點處理機的特點8.2.1 SIMD處理機的基本結構處理機的基本結構一臺一臺SIMDSIMD處理機由五個部分組成：處理機由五個部分組成：多個處理單元多個處理單元PEPE，多個存儲器模塊多個存儲器模塊M M，一個控制器一個控制器CUCU，一個互連網(wǎng)絡一個互連網(wǎng)絡ICNICN，一臺輸入輸出處理機一臺輸入輸出處理機IOPIOP。SIMDSIMD處理機有兩種典型結構：處理機有兩種典型結構：分布存儲器分布存儲器SIMDSIMD處理機，處理機，共享存儲器共享存儲器SIMDSIMD處理機。處理機

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

6、的利用率。因此，應用領域有限，可以認為是一種專用計算機。數(shù)據(jù)在局部存儲器中的分布是一個很關鍵的問題。標量指令與向量指令可以并發(fā)執(zhí)行。 CUIOPLM0LM1LMn-1PE0PE1PEn-1互連網(wǎng)絡 分布式存儲器分布式存儲器SIMD處理機的結構框圖處理機的結構框圖8.2.3 共享存儲器共享存儲器SIMD處理機處理機共享多體并行存儲器SM通過互連網(wǎng)絡與各處理單元PE相連。存儲模塊的數(shù)目等于或略大于處理單元的數(shù)目。為了實現(xiàn)無沖突訪問，存儲模塊的個數(shù)為質數(shù)。在存儲模塊之間合理分配數(shù)據(jù)，通過靈活、高速的互連網(wǎng)絡，使存儲器與處理單元之間的數(shù)據(jù)傳送在大多數(shù)向量運算中都能以存儲器的最高頻率進行，而最少受存儲器

7、沖突的影響。共享存儲器模型的處理單元數(shù)目一般不多，幾個至幾十個。Burroughs Scientific Processor(BSP)采用了這種結構。16個PE通過一個1617的對準互連網(wǎng)絡訪問17個共享存儲器模塊。存儲器模塊數(shù)與PE數(shù)互質可以實現(xiàn)無沖突并行訪問存儲器。對互連網(wǎng)絡的要求很高。C UIO PP E0P E1P EnS M0S M1S Mk互 連 網(wǎng) 絡 共享存儲器共享存儲器SIMD處理機的結構框圖處理機的結構框圖8.2.4 SIMD處理機的特點處理機的特點 SIMD處理機的主要特點如下：處理機的主要特點如下：1. 速度快，而且潛力大速度快，而且潛力大2. 模塊性好，生產(chǎn)和維護方便

8、模塊性好，生產(chǎn)和維護方便3. 可靠性高，容易實現(xiàn)容錯和重構可靠性高，容易實現(xiàn)容錯和重構4. 效率低效率低與流水線處理機、向量處理機等比較。依靠的是資源重復，而不是時間重疊，它的每個處理單元要擔負多種處理功能，其效率要低一些。5. 潛力大潛力大 主要依靠增加PE個數(shù)，與流水線處理機主要依靠縮短時鐘周期相比，其提高速度的潛力要大得多。6. 依賴于互連網(wǎng)絡和并行算法依賴于互連網(wǎng)絡和并行算法 互連網(wǎng)絡決定了PE之間的連接模式，也決定了SIMD處理機能夠適應的算法。7. 需要有一臺高性能的標量處理機需要有一臺高性能的標量處理機 如果一臺機器的向量處理速度極高，但標量處理速度只是每秒一百萬次，那么對于標量

9、運算占10的題目來說，總的有效速度就不過是每秒一千萬次。8.3 SIMD處理機實例處理機實例IlliacIV 是最先采用SIMD結構的SIMD處理機。隨后一個方向是用位片PE制造的SIMD處理機，如Goodyear MPP、AMT/DAP610和TMC/CM-2CM-5是以SIMD模式運行的同步MIMD計算機另一方向是字寬運算PE的中粒度SIMD計算機SIMD處理機的兩個發(fā)展方向：保留陣列結構，但每個處理單元的規(guī)模減小保留陣列結構，但每個處理單元的規(guī)模減小，如一個bit。去掉陣列結構和分布存儲器去掉陣列結構和分布存儲器。Burroughs公司的BSP是代表。8.3.1 IlliacIV SIM

10、D處理機處理機1963年，美國西屋電器公司提出“Slotnick，The SOLOMON Computer，Simultaneous Operation linked Ordinal Modular Network”。1966年美國國防遠景研究規(guī)劃局ARPR與伊利諾依大學簽定合同。原計劃：256個PE，運算速度為1GFLOPS。Burroughs公司和伊利諾依大學于1972年共同設計和生產(chǎn)，1975年實際投入運行。用了4倍的經(jīng)費，只達到1/20的速度。只實現(xiàn)了8864個PE，只達到50MFLOPS。IlliacIV的影響非常大。它是SIMD處理機的典型代表，也是分布存儲器SIMD處理機的典型代

11、表。PEM63PEM0PEM1CUCDCBIOMB6700CPUB6700內(nèi)存B6700多路開關B6700外圍設備IOS激光存儲器6464 X 8CU總 線控 制 線模 式 位 線APPA網(wǎng) 接 口1282561024I/O 總 線CDBPE63PE01024 實 時 裝 置48484848256PE0PE1PE63.DFSIlliacIV由三大部分組成由三大部分組成IlliacIV處理機陣列：包括88 PE、PEM和互連網(wǎng)絡。陣列控制器CU。輸入輸出處理機：一臺標準的Burroughs B6700計算機。1. 陣列控制器陣列控制器陣列控制器CU實際上是一臺小型計算機。對陣列處理單元實行控制和

12、完成標量操作。對陣列處理單元實行控制和完成標量操作。標量操作與各標量操作與各PE的數(shù)組操作可以重疊執(zhí)行。的數(shù)組操作可以重疊執(zhí)行?？刂破鞯墓δ苡幸韵挛鍌€方面：(1)對指令進行譯碼，并執(zhí)行標量指令；(2)向各PE發(fā)出執(zhí)行數(shù)組操作指令的控制信號；(3)產(chǎn)生并向所有處理單元廣播公共的地址；(4)產(chǎn)生并向所有處理單元廣播公共的數(shù)據(jù)；(5)接收和處理PE、I/O操作以及B6700產(chǎn)生的陷阱中斷信號。2. 輸入輸出系統(tǒng)輸入輸出系統(tǒng)IlliacIV的輸入輸出系統(tǒng)包括：磁盤文件系統(tǒng)DFS，I/O分系統(tǒng)，一臺B6700處理機組成。I/O分系統(tǒng)由三個部分組成：輸入輸出開關IOS，控制描述字控制器CDC，輸入輸出緩沖

13、存儲器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直接連接。南北方向同一列PU連成一個環(huán)，東西方向構成一個閉合螺線。閉合螺線網(wǎng)絡直徑為閉合螺線網(wǎng)絡直徑為7步，步，環(huán)形網(wǎng)格的直徑為環(huán)形網(wǎng)格的直徑為8步。步。 PU56 PU57 PU63 PU63 2 3 4 5 6 PU8 PU8 10 11 12 13 14 PU16 16 17 18 19 20 21

14、22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 PU55 58 59 60 61 62 PU0 PU0 PU1 PU7 PU0 PU1 PU8 PU9 PU56 PU57 PU7 PU15 PU63 例如：從PU0到PU36，采用環(huán)行網(wǎng)格必須8步： PUPU0 0PUPU1 1PUPU2 2PUPU3 3PUPU4 4PUPU1212PUPU2020PUPU2828PUPU3636或 PUPU0 0PUPU8 8PUPU1616PUPU24

15、24PUPU3232PUPU3333PUPU3434PUPU3535PUPU3636 或 如果采用閉合螺旋線，只需要如果采用閉合螺旋線，只需要7 7步：步： PUPU0 0PUPU6363PUPU6262PUPU6161PUPU6060PUPU5252PUPU4444PUPU3636或PUPU0 0PUPU6363PUPU5555PUPU4747PUPU3939PUPU3838PUPU3737PUPU3636 或 對于nn個單元的陣列，網(wǎng)絡直徑為n-1n-1。二維閉合螺旋線網(wǎng)格網(wǎng)二維閉合螺旋線網(wǎng)格網(wǎng) 結點度為4，網(wǎng)絡直徑為n-1。8.3.2 BSP處理機處理機BSP（Buroughs Scie

16、ntific Processor）計算機是由美國寶來公司和伊利諾依大學于1979年制造的。BSP是共享存儲器SIMD處理機的典型代表。BSP由5個部分組成：控制處理機、SIMD處理機、文件存儲器、并行存儲器模塊、對準網(wǎng)絡。1. SIMD處理機處理機17個存儲模塊，每個模塊512K字，周期160ns5級流水線：級流水線：(1)從17個存儲模塊中讀出數(shù)據(jù)(2)通過輸出對準網(wǎng)絡把數(shù)據(jù)送入16個并行處理部件(3)16個并行處理部件SIMD處理機數(shù)據(jù)(4)通過輸入對準網(wǎng)絡把數(shù)據(jù)從并行處理部件送到并行存儲器(5)把接收到的數(shù)據(jù)寫入并行存儲器時鐘周期160ns，向量運算速度向量運算速度50MFLOPS。1

17、16 6算算術術單單元元( (A AE E5 5) )輸輸 出出對對準準輸輸 入入對對準準1 17 7并并行行存存儲儲器器模模塊塊（5 5- -8 8兆兆字字）(PPS)并并行行處處理理機機控控制制控控制制維維護護單單元元標標量量處處理理機機控控制制存存儲儲器器( (2 25 56 6K K字字）系系統(tǒng)統(tǒng)管管理理機機B B 7 77 70 00 0/ /B B 7 78 80 00 0文文件件存存儲儲 器器 系系統(tǒng)統(tǒng)（F FM M）并并行行處處理理機機（5 50 0M MF FL LO OP PS S）BSP外圍設備與終端75兆字節(jié)/秒控制通信(PMs)2. 控制處理機控制處理機控制處理機主要

18、用來控制控制處理機主要用來控制SIMD處理機。處理機。提供與系統(tǒng)管理機相連的接口。執(zhí)行存放在控制存儲器中的操作系統(tǒng)和用戶程執(zhí)行存放在控制存儲器中的操作系統(tǒng)和用戶程序的標量部分。序的標量部分。把全部的向量指令及成組的標量指令送給SIMD處理機?？刂凭S護單元是系統(tǒng)管理機與控制處理機之間的接口，用來進行初始化、監(jiān)控命令通信和維護。3. 文件存儲器文件存儲器計算任務文件從系統(tǒng)管理機加載到文件存儲器，由控制處理機執(zhí)行。文件存儲器是在BSP直接控制下的唯一外圍設備。程序執(zhí)行過程中所產(chǎn)生的暫存文件和輸出文件，在將它們送給系統(tǒng)管理機輸出給用戶之前是存在文件存儲器中的。文件存儲器的數(shù)據(jù)傳輸率較高，大大地緩解了I

19、/O受限問題。4. 對準網(wǎng)絡對準網(wǎng)絡對準網(wǎng)絡采用全交叉開關實現(xiàn)對準網(wǎng)絡采用全交叉開關實現(xiàn)。數(shù)據(jù)從一個源廣播至幾個目的地，幾個源尋找數(shù)據(jù)從一個源廣播至幾個目的地，幾個源尋找一個目的地時能分解沖突。一個目的地時能分解沖突。存儲器模塊和對準網(wǎng)絡的組合實現(xiàn)了無沖突訪存儲器模塊和對準網(wǎng)絡的組合實現(xiàn)了無沖突訪問并行存儲器問并行存儲器。對準網(wǎng)絡還可以實現(xiàn)快速傅里葉變換、數(shù)據(jù)壓縮和擴展操作。5. 無訪問沖突存儲系統(tǒng)無訪問沖突存儲系統(tǒng)只有數(shù)組存取和I/O訪問并行存儲器。等效存儲等效存儲周期為周期為10ns。兩次算術運算中需要用到三個變量，產(chǎn)生一個結果，共訪問存儲器4次，并行存儲器和浮點運算之間的頻帶保持完全平衡

20、頻帶保持完全平衡。對于長向量來，中間結果存在寄存器中，每次運算只需要一個操作數(shù)。因此并行存儲器有足夠的頻寬留給輸入和輸出信息用。實現(xiàn)一維向量和二維矩陣的行、列、對角線和實現(xiàn)一維向量和二維矩陣的行、列、對角線和反對角線的無沖突訪問。反對角線的無沖突訪問。8.4 SIMD處理機算法舉例處理機算法舉例8.4.1 有限差分問題有限差分問題8.4.2 矩陣乘矩陣乘8.4.3 求累加和求累加和SIMD處理機特別處理機特別依賴于并行算法。依賴于并行算法。并行算法的一個關鍵是并行算法的一個關鍵是提高向量化的程度。提高向量化的程度。在設計并行算法時，要特別注意：在設計并行算法時，要特別注意：數(shù)據(jù)在多個存儲模塊之

21、間的分布。數(shù)據(jù)在多個存儲模塊之間的分布。要解決好訪問存儲器的沖突問題。要解決好訪問存儲器的沖突問題?；ミB網(wǎng)絡并不能提供所有處理單元之間的互連網(wǎng)絡并不能提供所有處理單元之間的連接，因此，并行算法要連接，因此，并行算法要充分利用互連充分利用互連網(wǎng)絡的結構網(wǎng)絡的結構。8.4.1 有限差分問題有限差分問題有限差分方法是一種通用和有效方法：把連續(xù)方程變換成離散形式。二階偏導數(shù)表示為差分形式：22220UxUy22222222UxU xhU xU xhhUyU xhU xU xhh(,)( ,)(,)( ,)( ,)( ,) y y y y y y并代入原方程，則可得有限差分計算公式：其中：(x, y)為

22、平面直角坐標， h為網(wǎng)格間距。IlliacIV的陣列結構特別適合計算這種在網(wǎng)格上定義的有限差分函數(shù)。把內(nèi)部網(wǎng)格點分配給各個處理單元，計算過程可以并行完成。運算速度的提高可以與處理機數(shù)目成正比。U xU x hU xhU x hU xh()()()()(), y, y, y, y, y48.4.2 矩陣乘矩陣乘矩陣乘是典型的并行程序，非常適合在SIMDSIMD處理機上運行。例如：A、B、C均為88的二維矩陣，則CAB的計算公式為：在串行機上要用一個三重循環(huán)程序，乘法和加法分別為512次。ca bijikkjk, 0i, j707如果在SIMD處理機上求解，F(xiàn)ORTRAN語言程序如下： DO 10

23、 I0，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處理機上運行數(shù)據(jù)如何分布到各個局部存儲器中？在SIMD處理機上，J循環(huán)只需一次。 PE0PE0：c c0000a a0000b b0000a a0101b b1010a a0202b b2020a a0707b b7070 PE1 PE1：c c0101a a0000b b0101a a0101b b1111a a0202b b2121a a0707b b717

24、1 PE7 PE7：c c0707a a0000b b0707a a0101b b1717a a0202b b2727a a0707b b7777 PE0PE0：c c1010a a1010b b0000a a1111b b1010a a1212b b2020a a1717b b7070 PE1PE1：c c1111a a1010b b0101a a1111b b1111a a1212b b2121a a1717b b7171 PE7 PE7：c c1717a a1010b b0707a a1111b b1717a a1212b b2727a a1717b b7777PE7PE7：c c777

25、7a a7070b b0707a a7171b b1717a a7272b b2727a a7777b b7777局局部部存存儲儲器器中中的的數(shù)數(shù)據(jù)據(jù)分分布布如如下下： PEM0 PEM1 PEM2 PEM3 PEM4 PEM5 PEM6 PEM7 b00 b10 b70 c00 c10 c70 a00 a10 a70 b01 b11 b71 c01 c11 c71 a01 a11 a71 b02 b12 b72 c02 c12 c72 a02 a12 a72 b03 b13 b73 c03 c13 c73 a03 a13 a73 b04 b14 b74 c04 c14 c74 a04 a14 a74 b05 b15 b75 c05 c15 c75 a05 a15 a75 b06 b16 b76 c06 c16 c76 a06 a16 a76 b07 b17 b77 c07 c17 c77 a07 a17 a77 開 始i = 0C i , j = 0 , k = 0 讀讀 L L O O A A D D A A i i , , k k 播播送送 B B C C A A S S T T A A i i , , k k 乘乘 M M U U L L Y Y B B k k , , j j 加加 A A D