計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第八章并行處理機(jī)_第1頁(yè)
已閱讀1頁(yè),還剩43頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

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

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

4、D處理機(jī)的基本結(jié)構(gòu)8.2.2 分布存儲(chǔ)器SIMD處理機(jī)8.2.3 共享存儲(chǔ)器SIMD處理機(jī)8.2.4 SIMD處理機(jī)的特點(diǎn),8.2.1 SIMD處理機(jī)的基本結(jié)構(gòu),一臺(tái)SIMD處理機(jī)由五個(gè)部分組成:多個(gè)處理單元PE,多個(gè)存儲(chǔ)器模塊M,一個(gè)控制器CU,一個(gè)互連網(wǎng)絡(luò)ICN,一臺(tái)輸入輸出處理機(jī)IOP。SIMD處理機(jī)有兩種典型結(jié)構(gòu):分布存儲(chǔ)器SIMD處理機(jī),共享存儲(chǔ)器SIMD處理機(jī)。,8.2.2 分布存儲(chǔ)器SI

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

6、作外,還負(fù)責(zé)程序的編輯、編譯和調(diào)試等工作。 IOP可以是一臺(tái)通用計(jì)算機(jī)。分布式存儲(chǔ)器SIMD處理機(jī)必須依靠并行算法來(lái)提高PE的利用率。因此,應(yīng)用領(lǐng)域有限,可以認(rèn)為是一種專用計(jì)算機(jī)。數(shù)據(jù)在局部存儲(chǔ)器中的分布是一個(gè)很關(guān)鍵的問(wèn)題。標(biāo)量指令與向量指令可以并發(fā)執(zhí)行。,分布式存儲(chǔ)器SIMD處理機(jī)的結(jié)構(gòu)框圖,8.2.3 共享存儲(chǔ)器SIMD處理機(jī),共享多體并行存儲(chǔ)器SM通過(guò)互連網(wǎng)絡(luò)與各處理單元PE相連。存儲(chǔ)模塊的數(shù)目等于或略大于處理單元的數(shù)目。

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

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

9、,與流水線處理機(jī)主要依靠縮短時(shí)鐘周期相比,其提高速度的潛力要大得多。6. 依賴于互連網(wǎng)絡(luò)和并行算法 互連網(wǎng)絡(luò)決定了PE之間的連接模式,也決定了SIMD處理機(jī)能夠適應(yīng)的算法。7. 需要有一臺(tái)高性能的標(biāo)量處理機(jī) 如果一臺(tái)機(jī)器的向量處理速度極高,但標(biāo)量處理速度只是每秒一百萬(wàn)次,那么對(duì)于標(biāo)量運(yùn)算占10%的題目來(lái)說(shuō),總的有效速度就不過(guò)是每秒一千萬(wàn)次。,8.3 SIMD處理機(jī)實(shí)例,IlliacIV 是最先采用SIMD結(jié)構(gòu)的SIM

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

11、年,美國(guó)西屋電器公司提出“Slotnick,The SOLOMON Computer,Simultaneous Operation linked Ordinal Modular Network”。1966年美國(guó)國(guó)防遠(yuǎn)景研究規(guī)劃局ARPR與伊利諾依大學(xué)簽定合同。原計(jì)劃:256個(gè)PE,運(yùn)算速度為1GFLOPS。Burroughs公司和伊利諾依大學(xué)于1972年共同設(shè)計(jì)和生產(chǎn),1975年實(shí)際投入運(yùn)行。用了4倍的經(jīng)費(fèi),只達(dá)到1/20的速度。只

12、實(shí)現(xiàn)了8?8=64個(gè)PE,只達(dá)到50MFLOPS。IlliacIV的影響非常大。它是SIMD處理機(jī)的典型代表,也是分布存儲(chǔ)器SIMD處理機(jī)的典型代表。,IlliacIV由三大部分組成IlliacIV處理機(jī)陣列:包括8×8 PE、PEM和互連網(wǎng)絡(luò)。陣列控制器CU。輸入輸出處理機(jī):一臺(tái)標(biāo)準(zhǔn)的Burroughs B6700計(jì)算機(jī)。,1. 陣列控制器陣列控制器CU實(shí)際上是一臺(tái)小型計(jì)算機(jī)。對(duì)陣列處理單元實(shí)行控制和完成標(biāo)量

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

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

15、方向同一列PU連成一個(gè)環(huán),東西方向構(gòu)成一個(gè)閉合螺線。閉合螺線網(wǎng)絡(luò)直徑為7步,環(huán)形網(wǎng)格的直徑為8步。,例如:從PU0到PU36,采用環(huán)行網(wǎng)格必須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 或 ……對(duì)于n×n個(gè)單元的陣列,網(wǎng)絡(luò)直徑為n-1。,二維閉合螺旋線網(wǎng)格網(wǎng) 結(jié)點(diǎn)度為4,網(wǎng)絡(luò)直徑為n-1。,8.3.2 BSP處理機(jī),BSP(Buroughs Scientific Processor)計(jì)算機(jī)是由美國(guó)寶來(lái)公司和伊利諾依大學(xué)于1979年制造的。BSP是共享存儲(chǔ)器SIMD處理機(jī)的典型代

17、表。BSP由5個(gè)部分組成:控制處理機(jī)、SIMD處理機(jī)、文件存儲(chǔ)器、并行存儲(chǔ)器模塊、對(duì)準(zhǔn)網(wǎng)絡(luò)。,1. SIMD處理機(jī)17個(gè)存儲(chǔ)模塊,每個(gè)模塊512K字,周期160ns5級(jí)流水線:(1)從17個(gè)存儲(chǔ)模塊中讀出數(shù)據(jù)(2)通過(guò)輸出對(duì)準(zhǔn)網(wǎng)絡(luò)把數(shù)據(jù)送入16個(gè)并行處理部件(3)16個(gè)并行處理部件SIMD處理機(jī)數(shù)據(jù)(4)通過(guò)輸入對(duì)準(zhǔn)網(wǎng)絡(luò)把數(shù)據(jù)從并行處理部件送到并行存儲(chǔ)器(5)把接收到的數(shù)據(jù)寫入并行存儲(chǔ)器時(shí)

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

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

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

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

22、:(x, y)為平面直角坐標(biāo), h為網(wǎng)格間距。IlliacIV的陣列結(jié)構(gòu)特別適合計(jì)算這種在網(wǎng)格上定義的有限差分函數(shù)。把內(nèi)部網(wǎng)格點(diǎn)分配給各個(gè)處理單元,計(jì)算過(guò)程可以并行完成。運(yùn)算速度的提高可以與處理機(jī)數(shù)目成正比。,8.4.2 矩陣乘,矩陣乘是典型的并行程序,非常適合在SIMDSIMD處理機(jī)上運(yùn)行。例如:A、B、C均為8×8的二維矩陣,則C=A×B的計(jì)算公式為:在串行機(jī)上要用

23、一個(gè)三重循環(huán)程序,乘法和加法分別為512次。,如果在SIMD處理機(jī)上求解,F(xiàn)ORTRAN語(yǔ)言程序如下: 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個(gè)PE的SIMD處理機(jī)運(yùn)行,運(yùn)算速度可提高8倍。也可在64個(gè)PE的SIMD處理機(jī)上

24、運(yùn)行數(shù)據(jù)如何分布到各個(gè)局部存儲(chǔ)器中?,在SIMD處理機(jī)上,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個(gè)數(shù)的順序相加變?yōu)椴⑿邢嗉?。串行求和?FORTRAN 程序如下: C(-1)=0 DO 10 I=0, N10 C(I)=C(I-

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論