并行處理機(jī)精品課件

1、并行處理機(jī)第1頁，共28頁，2022年，5月20日，7點41分，星期三M1M2MN-1M08.1 并行處理機(jī)模型 五道口生活網(wǎng) 五道論壇第2頁，共28頁，2022年，5月20日，7點41分，星期三并行處理機(jī)的定義：多個PU按照一定方式互連，在同一個CU控制下，對各自的數(shù)據(jù)完成同一條指令規(guī)定的操作。從CU看，指令是串行執(zhí)行的，從PU看，數(shù)據(jù)是并行處理的。并行處理機(jī)也稱為陣列處理機(jī)、SIMD處理機(jī)等并行處理機(jī)的應(yīng)用領(lǐng)域：主要用于高速向量或矩陣運算并行處理機(jī)的操作模型可用五元組來表示：M(N，C，I，M，R), 其中：N為PE個數(shù)。如IlliacIV有64個PE。C為控制部件CU執(zhí)行的指令集，包括標(biāo)

2、量指令和程序控制指令。I為所有PE并行執(zhí)行的指令集，包括ALU、數(shù)據(jù)傳送等操作M為屏蔽操作集，將PE劃分為允許操作和禁止操作兩個子集R是數(shù)據(jù)尋徑集，互連網(wǎng)絡(luò)中PE間通信所需要的各種模式 五道口生活網(wǎng) 五道論壇第3頁，共28頁，2022年，5月20日，7點41分，星期三 五道口生活網(wǎng) 五道論壇第4頁，共28頁，2022年，5月20日，7點41分，星期三8.2 并行處理機(jī)的基本結(jié)構(gòu)并行處理機(jī)有兩種典型結(jié)構(gòu)：分布存儲器并行處理機(jī)、共享存儲器并行處理機(jī)一臺并行處理機(jī)由五個部分組成：多個處理單元PE，多個存儲器模塊M，一個控制器CU，一個互連網(wǎng)絡(luò)ICN，一臺輸入輸出處理機(jī)IOP。 8.2.1 分布存儲器

3、并行處理機(jī) 8.2.2 共享存儲器并行處理機(jī) 8.2.3 并行處理機(jī)的特點 五道口生活網(wǎng) 五道論壇第5頁，共28頁，2022年，5月20日，7點41分，星期三8.2.1 分布存儲器并行處理機(jī) 五道口生活網(wǎng) 五道論壇第6頁，共28頁，2022年，5月20日，7點41分，星期三目前的大部分并行處理機(jī)是基于分布式存儲器模型的比較容易構(gòu)成MPP(Massively Parallel Processor),幾十萬個PE。必須依靠并行算法來提高PE的利用率。因此，應(yīng)用領(lǐng)域有限。CU是控制部件，執(zhí)行標(biāo)量指令，并把向量指令廣播到各個PE中。在CU中通常有一個較大容量的存儲器。IOP是輸入輸出處理機(jī)，或稱為主機(jī)

4、。在IOP上安裝操作系統(tǒng)，它除了負(fù)擔(dān)輸入輸出工作外，還負(fù)責(zé)程序的編輯、編譯和調(diào)試等工作。數(shù)據(jù)在局部存儲器中的分布是一個很關(guān)鍵的問題。標(biāo)量指令與向量指令可以并發(fā)執(zhí)行。 五道口生活網(wǎng) 五道論壇第7頁，共28頁，2022年，5月20日，7點41分，星期三8.2.2 共享存儲器并行處理機(jī)共享多體并行存儲器SM通過互連網(wǎng)絡(luò)與各處理單元PE相連。存儲模塊的數(shù)目等于或略大于處理單元的數(shù)目。同時在存儲模塊之間合理分配數(shù)據(jù)，通過靈活、高速的互連網(wǎng)絡(luò)，使存儲器與處理單元之間的數(shù)據(jù)傳送在大多數(shù)向量運算中都能以存儲器的最高頻率進(jìn)行，而最少受存儲器沖突的影響。共享存儲器模型的處理單元數(shù)目一般不多，幾個至幾十個。Burr

5、oughs Scientific Processor(BSP)采用了這種結(jié)構(gòu)。16個PE通過一個1617的對準(zhǔn)互連網(wǎng)絡(luò)訪問17個共享存儲器模塊。存儲器模塊數(shù)與PE數(shù)互質(zhì)可以實現(xiàn)無沖突并行訪問存儲器。 五道口生活網(wǎng) 五道論壇第8頁，共28頁，2022年，5月20日，7點41分，星期三第9頁，共28頁，2022年，5月20日，7點41分，星期三8.2.3 并行處理機(jī)的特點速度高，依靠增加PE個數(shù)來提高速度，與流水線處理機(jī)主要依靠縮短時鐘周期相比，其提高速度的潛力要大得多。模塊性好，生產(chǎn)和維護(hù)方便。可靠性高，容易實現(xiàn)容錯和重構(gòu)。效率低，通常作為專用計算機(jī)，在很大程度上依賴于并行算法。它依靠的是資源重

6、復(fù)，而不是時間重疊，它的每個處理單元要擔(dān)負(fù)多種處理功能，其效率要低一些。依賴于互連網(wǎng)絡(luò)?；ミB網(wǎng)絡(luò)決定了PE之間的連接模式，也決定了并行處理機(jī)能夠適應(yīng)的算法。需要有一臺高性能的標(biāo)量處理機(jī)。如果一臺機(jī)器的向量處理速度極高，但標(biāo)量處理速度只是每秒一百萬次，則對于標(biāo)量運算占10的題目，總的有效速度就不超過每秒一千萬次。 五道口生活網(wǎng) 五道論壇第10頁，共28頁，2022年，5月20日，7點41分，星期三8.3 并行處理機(jī)實例并行處理機(jī)的兩種典型代表：采用陣列結(jié)構(gòu)分布存儲器的IlliacIV并行處理機(jī)共享存儲器結(jié)構(gòu)BSP并行處理機(jī)。 五道口生活網(wǎng) 五道論壇第11頁，共28頁，2022年，5月20日，7點

7、41分，星期三8.3.1 IlliavIV 并行處理機(jī)1963年，美國西屋電器公司提出“Slotnick，The SOLOMON Computer，Simultaneous Operation linked Ordinal Modular Network”。1966年美國國防遠(yuǎn)景研究規(guī)劃局ARPR與伊利諾依大學(xué)簽定合同。原計劃：256個PE，每個PE每240ns處理一個64位浮點數(shù)，每個局部存儲器PEM為2K64位，總的原算速度為1GFLOPS。美國Burroughs公司和伊利諾依大學(xué)于1972年共同設(shè)計和生產(chǎn)，1975年實際投入運行。用了4倍的經(jīng)費，只達(dá)到1/20的速度。只實現(xiàn)了8864個P

8、E，只達(dá)到50MFLOPS。IlliacIV系統(tǒng)的影響非常大。它是并行處理機(jī)的典型代表，也是分布存儲器并行處理機(jī)的典型代表。IlliacIV系統(tǒng)由三大部分組成。IlliacIV處理機(jī)陣列，陣列控制器，一臺標(biāo)準(zhǔn)的Burroughs B6700計算機(jī)。 五道口生活網(wǎng) 五道論壇第12頁，共28頁，2022年，5月20日，7點41分，星期三IlliacIV系統(tǒng)由三大部分組成IlliacIV處理機(jī)陣列：8 X 8，包括PE、PEM和互連網(wǎng)絡(luò)。陣列控制器CU，輸入輸出處理機(jī)：一臺標(biāo)準(zhǔn)的Burroughs B6700計算機(jī)。 五道口生活網(wǎng) 五道論壇第13頁，共28頁，2022年，5月20日，7點41分，星期

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

10、器BIOM三個部分組成。 五道口生活網(wǎng) 五道論壇第14頁，共28頁，2022年，5月20日，7點41分，星期三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)，東西方向構(gòu)成一個閉合螺線。閉合螺線最短距離不超過7步。普通網(wǎng)格最短距離不超過8步。例如：從PU0到PU36的距離：采用普通網(wǎng)格必須8步： PU0PU1PU2PU3PU4PU12PU20P

11、U28PU36 或 PU0PU8PU16PU24PU32PU33PU34PU35PU36 或 如果采用閉合螺旋線，只需要7步： PU0PU63PU62PU61PU60PU52PU44PU36或 PU0PU63PU55PU47PU39PU38PU37PU36 或 對于nn個單元的陣列，任意兩個單元之間的最短距離不超過n-1步。 五道口生活網(wǎng) 五道論壇第15頁，共28頁，2022年，5月20日，7點41分，星期三普通網(wǎng)格必須8步：PU0PU1PU2PU3PU4PU12PU20PU28PU36或 PU0PU8PU16PU24PU32PU33PU34PU35PU36 或 閉合螺旋線只要7步：PU0PU

12、63PU62PU61PU60PU52PU44PU36 或 PU0PU63PU55PU47PU39PU38PU37PU36 或 五道口生活網(wǎng) 五道論壇第16頁，共28頁，2022年，5月20日，7點41分，星期三8.3.2 BSP處理機(jī)BSP（Buroughs Scientific Processor）計算機(jī)是由美國寶來公司和伊利諾依大學(xué)于1979年制造的。BSP是共享存儲器結(jié)構(gòu)的并行處理機(jī)的典型代表。BSP由控制處理機(jī)、并行處理機(jī)、文件存儲器、并行存儲器模塊以及對準(zhǔn)網(wǎng)絡(luò)等5個部分組成。1、并行處理機(jī)時鐘周期160ns，向量運算速度最高可達(dá)50MFLOPS。17個并行存儲器模塊，每個模塊512K

13、字，存儲周期160ns。5級流水線：(1)從17個存儲模塊中讀出數(shù)據(jù)(2)通過輸出對準(zhǔn)網(wǎng)絡(luò)把數(shù)據(jù)送入16個并行處理部件(3)16個并行處理部件并行處理數(shù)據(jù)(4)通過輸入對準(zhǔn)網(wǎng)絡(luò)把數(shù)據(jù)從并行處理部件送到并行存儲器(5)把接收到的數(shù)據(jù)寫入并行存儲器 五道口生活網(wǎng) 五道論壇第17頁，共28頁，2022年，5月20日，7點41分，星期三 五道口生活網(wǎng) 五道論壇第18頁，共28頁，2022年，5月20日，7點41分，星期三2、控制處理機(jī)控制處理機(jī)主要用來控制并行處理機(jī)。提供與系統(tǒng)管理機(jī)相連的接口。執(zhí)行存放在控制存儲器中的操作系統(tǒng)和用戶程序的標(biāo)量部分。全部向量指令及成組的標(biāo)量指令被送給并行處理機(jī)?？刂凭S護(hù)

14、單元是系統(tǒng)管理機(jī)與控制處理機(jī)之間的接口，用來進(jìn)行初始化、監(jiān)控命令通信和維護(hù)。3、文件存儲器計算任務(wù)文件從系統(tǒng)管理機(jī)加載到文件存儲器，由控制處理機(jī)執(zhí)行。文件存儲器是BSP直接控制下唯一的外圍設(shè)備。程序執(zhí)行過程中所產(chǎn)生的暫存文件和輸出文件，在將它們送給系統(tǒng)管理機(jī)輸出給用戶之前是存在文件存儲器中的。文件存儲器的數(shù)據(jù)傳輸率較高，大大地緩解了I/O受限問題。 五道口生活網(wǎng) 五道論壇第19頁，共28頁，2022年，5月20日，7點41分，星期三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)

15、絡(luò)還可以實現(xiàn)快速傅里葉變換、數(shù)據(jù)壓縮和擴(kuò)展操作。5、無訪問沖突存儲系統(tǒng)只有數(shù)組存取和I/O訪問并行存儲器。等效存儲周期為10ns。兩次算術(shù)運算中需要用到三個變量，產(chǎn)生一個結(jié)果，共訪問存儲器4次，并行存儲器和浮點運算之間的頻帶保持完全平衡。對于長向量來，中間結(jié)果存在寄存器中，每次運算只需要一個操作數(shù)。因此并行存儲器有足夠的頻寬留給輸入和輸出信息用。實現(xiàn)一維向量和二維矩陣的行、列、對角線和反對角線的無沖突訪問。 五道口生活網(wǎng) 五道論壇第20頁，共28頁，2022年，5月20日，7點41分，星期三8.4 并行處理機(jī)算法舉例要發(fā)揮并行處理機(jī)的效率，特別依賴于并行算法。并行算法的一個關(guān)鍵問題是要提高向量

16、化的程度。在設(shè)計并行算法時，要特別注意數(shù)據(jù)在多個存儲模塊之間的分布，要解決好訪問存儲器的沖突問題?；ミB網(wǎng)絡(luò)并不能提供所有處理單元之間的連接，因此，并行算法要充分利用互連網(wǎng)絡(luò)的結(jié)構(gòu)。8.4.1矩陣乘8.4.2求累加和 五道口生活網(wǎng) 五道論壇第21頁，共28頁，2022年，5月20日，7點41分，星期三8.4.1 矩陣乘A、B、C均為88的二維矩陣，則CAB的計算公式為：在串行機(jī)上要用一個三重循環(huán)程序，乘和加分別為512次(除循環(huán)控制外)。在并行處理機(jī)上求解，F(xiàn)ORTRAN程序如下： DO 10 I0，7 C(I, J)=0 DO 20 K=0, 720C(I, J)=C (I, J )+A(I,

17、 K) * B(K, J)10 CONTINUE 五道口生活網(wǎng) 五道論壇第22頁，共28頁，2022年，5月20日，7點41分，星期三在并行處理機(jī)上，J循環(huán)只需一次。速度提高到8倍。 PE0：c00a00b00a01b10a02b20a07b70 PE1：c01a00b01a01b11a02b21a07b71 PE7：c07a00b07a01b17a02b27a07b77 PE0：c10a10b00a11b10a12b20a17b70 PE1：c11a10b01a11b11a12b21a17b71 PE7：c17a10b07a11b17a12b27a17b77PE7：c77a70b07a71b

18、17a72b27a77b77行向量跨PEM存放列向量在同一個PEM初始時Cij0CU廣播同一個乘數(shù)aij給所有PE;與B的第i個行向量的所有n個元素同時相乘 五道口生活網(wǎng) 五道論壇第23頁，共28頁，2022年，5月20日，7點41分，星期三 五道口生活網(wǎng) 五道論壇第24頁，共28頁，2022年，5月20日，7點41分，星期三PE0：c00a00b00a01b10a02b20a07b70PE1：c01a00b01a01b11a02b21a07b71 PE7：c07a00b07a01b17a02b27a07b77PE0：c10a10b00a11b10a12b20a17b70PE1：c11a10b01a11b11a12b21a17b71 PE7：c17a10b07a11b17a12b2