單指令流多數(shù)據(jù)流計(jì)算機(jī)

1、單指令流多數(shù)據(jù)流計(jì)算機(jī)第1頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二目 錄第6章 單指令流多數(shù)據(jù)流計(jì)算機(jī) 6.1 單指令流多數(shù)據(jù)流計(jì)算機(jī)的基本結(jié)構(gòu)與特點(diǎn) 6.2 分布式存儲(chǔ)器SIMD計(jì)算機(jī)實(shí)例分析 6.3 集中式共享存儲(chǔ)器SIMD計(jì)算機(jī)實(shí)例分析 6.4 陣列處理機(jī)的算法及性能分析第2頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二 第6章 單指令流多數(shù)據(jù)流計(jì)算機(jī) 第3頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二6.1 單指令流多數(shù)據(jù)流計(jì)算機(jī)的基本結(jié)構(gòu)與特點(diǎn) 單指令流多數(shù)據(jù)流（SIMD）計(jì)算機(jī)的關(guān)鍵特征是它的并行處理機(jī)。它的并行處理機(jī)是由單一控制部件控制多個(gè)處理

2、單元同時(shí)進(jìn)行運(yùn)算操作，多個(gè)處理單元通常通過(guò)互連網(wǎng)絡(luò)連接成陣列結(jié)構(gòu)，故也稱(chēng)為陣列處理機(jī)。 并行處理機(jī)的所有處理單元同時(shí)執(zhí)行從控制部件廣播來(lái)的同一條指令，但指令使用不同的數(shù)據(jù)，因此，并行處理機(jī)是指令操作級(jí)并行的單指令流多數(shù)據(jù)流處理機(jī)。第4頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二6.1.1 單指令流多數(shù)據(jù)流計(jì)算機(jī)的兩種基本結(jié)構(gòu) 根據(jù)存儲(chǔ)器的組織方式不同，單指令流多數(shù)據(jù)流計(jì)算機(jī)的基本結(jié)構(gòu)分為兩種：集中式共享存儲(chǔ)器型分布式存儲(chǔ)器型 第5頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二1. 分布式存儲(chǔ)器SIMD計(jì)算機(jī)基本結(jié)構(gòu) 并行處理機(jī)的每個(gè)處理單元都有自己的局部存儲(chǔ)器，存放可直接

3、訪(fǎng)問(wèn)的數(shù)據(jù)。所有的處理單元通過(guò)互連網(wǎng)絡(luò)互聯(lián)。 陣列控制部件CU是一臺(tái)功能專(zhuān)用的處理機(jī)，它執(zhí)行程序流控制指令和程序中的標(biāo)量運(yùn)算。 管理處理機(jī)SC運(yùn)行操作系統(tǒng)，管理系統(tǒng)資源。 第6頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二 圖6.1 分布式存儲(chǔ)器的SIMD計(jì)算機(jī)基本結(jié)構(gòu)第7頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二 2.集中式共享存儲(chǔ)器SIMD計(jì)算機(jī)基本結(jié)構(gòu) 并行處理機(jī)的所有處理單元共享由個(gè)存儲(chǔ)體組成的并行存儲(chǔ)器，處理單元與存儲(chǔ)體之間通過(guò)互連網(wǎng)絡(luò)互連。CU和SC的功能與采用分布式存儲(chǔ)器構(gòu)型的SIMD計(jì)算機(jī)沒(méi)有什么差別。第8頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分

4、，星期二圖6.2 集中式共享存儲(chǔ)器的SIMD計(jì)算機(jī)基本結(jié)構(gòu)第9頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二 6.1.2 單指令流多數(shù)據(jù)流計(jì)算機(jī)的主要特點(diǎn) SIMD的效率取決于計(jì)算程序向量化的程度。SIMD計(jì)算機(jī)依靠的并行措施是資源重復(fù)。SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò)決定了SIMD計(jì)算機(jī)能適應(yīng)的算法類(lèi)別，SIMD計(jì)算機(jī)的實(shí)際有效速度取決于另外兩個(gè)因素。一是標(biāo)量運(yùn)算速度，二是編譯過(guò)程的時(shí)間開(kāi)銷(xiāo)。SIMD計(jì)算機(jī)是根據(jù)功能專(zhuān)用化的原則組成的一種異構(gòu)型多計(jì)算機(jī)系統(tǒng)。 第10頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二6.2 分布式存儲(chǔ)器SIMD計(jì)算機(jī)實(shí)例分析 兩種典型的SIMD計(jì)算機(jī)采

5、用分布式存儲(chǔ)器結(jié)構(gòu)的并行處理機(jī)的ILLIAC 計(jì)算機(jī)。采用集中式共享存儲(chǔ)器結(jié)構(gòu)的并行處理機(jī)的BSP計(jì)算機(jī)。第11頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二1. ILLIAC 陣列ILLIAC 系統(tǒng)由3種類(lèi)型處理機(jī)組成的一個(gè)異構(gòu)多處理機(jī)系統(tǒng)。一是專(zhuān)門(mén)用于數(shù)組運(yùn)算的處理單元陣列；二是陣列控制器，它既是處理單元陣列的控制部分，又是一臺(tái)相對(duì)獨(dú)立的小型標(biāo)量處理機(jī)；三是一臺(tái)標(biāo)準(zhǔn)的Burroughs B6700計(jì)算機(jī)，由它擔(dān)負(fù)ILLIAC 輸入輸出系統(tǒng)和操作系統(tǒng)管理功能。第12頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二 圖6.3 ILLIAC 系統(tǒng)框圖第13頁(yè)，共46頁(yè)，2022

6、年，5月20日，2點(diǎn)22分，星期二1. BSP計(jì)算機(jī)它由系統(tǒng)管理計(jì)算機(jī)B7700/B7800和BSP處理機(jī)兩大部分組成，前者可視為后者的前端機(jī)。系統(tǒng)管理機(jī)負(fù)責(zé)BSP程序編譯、與遠(yuǎn)程終端及網(wǎng)絡(luò)的數(shù)據(jù)通信、外圍設(shè)備管理等，大多數(shù)BSP作業(yè)調(diào)度和操作系統(tǒng)活動(dòng)也是在系統(tǒng)管理機(jī)上完成的。BSP處理機(jī)又可分為3部分，一是并行處理機(jī)，二是控制處理機(jī)，三是容量為464M字的文件存儲(chǔ)器。6.3 集中式共享存儲(chǔ)器SIMD計(jì)算機(jī)實(shí)例 第14頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二圖6.6 BSP計(jì)算機(jī)系統(tǒng)框圖操作系統(tǒng)和維護(hù)信息文件存儲(chǔ)器CCD464M字文件存儲(chǔ)器控制器文件存儲(chǔ)器系統(tǒng)指令/控制存儲(chǔ)器2

7、56K字控制維護(hù)單元標(biāo)量處理單元并行處理機(jī)控制器控制處理機(jī)并行存儲(chǔ)器0.58M字入口和出口對(duì)準(zhǔn)網(wǎng)絡(luò)16個(gè)算術(shù)單元并行處理機(jī)100M字/s100M字/s12.5M字/s系統(tǒng)管理機(jī)B7700/B7800程序和數(shù)據(jù)250K字/s第15頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二系統(tǒng)管理機(jī)文件存儲(chǔ)器控制處理機(jī)(指令存儲(chǔ)器，標(biāo)量運(yùn)算器)17個(gè)存儲(chǔ)體16算術(shù)單元BSP科學(xué)處理機(jī)系統(tǒng)組成第16頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二為了說(shuō)明BSP并行存儲(chǔ)器的地址變換和無(wú)沖突訪(fǎng)問(wèn)，下面先看一個(gè)較簡(jiǎn)單的例子。設(shè)并行存儲(chǔ)器的存儲(chǔ)體數(shù)m=7(質(zhì)數(shù))，運(yùn)算單元數(shù)n=6。若有一個(gè)45的數(shù)組。

8、 a00 a01 a02 a03 a04 a10 a11 a12 a13 a14 a20 a21 a22 a23 a24 a30 a31 a32 a33 a34第17頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二 BSP的地址映象關(guān)系為：先將二維數(shù)組按列或者按行的順序變換為一維數(shù)組，以形成一個(gè)一維線(xiàn)性地址空間，地址用a表示。然后將地址a變換成并行存儲(chǔ)器地址(j，i)，其中j是存儲(chǔ)體體號(hào)，i是體內(nèi)地址： j=a mod m i=an下整存儲(chǔ)體數(shù)m為一質(zhì)數(shù)，n為無(wú)沖突訪(fǎng)問(wèn)的最大存儲(chǔ)體數(shù)。第18頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二3. BSP的數(shù)據(jù)流水線(xiàn)結(jié)構(gòu) BSP的1

9、6個(gè)AE組成的算術(shù)單元陣列、17個(gè)存儲(chǔ)體組成的并行存儲(chǔ)器和2套互連網(wǎng)絡(luò)(對(duì)準(zhǔn)網(wǎng)絡(luò))形成了一條5級(jí)數(shù)據(jù)流水線(xiàn)，使連續(xù)幾條向量指令能在時(shí)間上重疊起來(lái)執(zhí)行。由17個(gè)存儲(chǔ)器輸出端口并行讀出16個(gè)操作數(shù)。經(jīng)對(duì)準(zhǔn)網(wǎng)絡(luò)NWl將16個(gè)操作數(shù)重排列成16個(gè)算術(shù)單元需要的次序。將排列好的16個(gè)操作數(shù)送到16個(gè)算術(shù)單元完成操作。所得的16個(gè)結(jié)果經(jīng)對(duì)準(zhǔn)網(wǎng)絡(luò)NW2重新排列成在17個(gè)存儲(chǔ)體中存儲(chǔ)所需要的次序。寫(xiě)入并行存儲(chǔ)器。存儲(chǔ)器處理器對(duì)準(zhǔn)網(wǎng)絡(luò)2對(duì)準(zhǔn)網(wǎng)絡(luò)1第19頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二6.4 陣列處理機(jī)的算法及性能分析 陣列處理機(jī)的處理器陣列有固定的結(jié)構(gòu)，因此，陣列處理機(jī)的性能與算法有很大

10、關(guān)系。若問(wèn)題求解的算法能與陣列處理機(jī)的結(jié)構(gòu)相適應(yīng)，就能獲得較高的性能；否則，陣列處理機(jī)的實(shí)際性能就很低，處理單元的利用率也很低。 第20頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二6.4.1 陣列處理機(jī)的差分計(jì)算 描述平面場(chǎng)的拉普拉斯方程： 將二階偏導(dǎo)數(shù)表示為差分形式 :代入原方程，則可得有限差分計(jì)算公式： 第21頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二迭代計(jì)算開(kāi)始時(shí)，除由邊界條件給定的某些邊緣點(diǎn)之外，其余網(wǎng)格點(diǎn)的函數(shù)值初值均可設(shè)為零。若取網(wǎng)格間距為單位1，迭代計(jì)算的表達(dá)式為： 式中的上標(biāo) t 表示迭代次數(shù)。迭代計(jì)算直至連續(xù)二次迭代所求值的差小于規(guī)定誤差為止。 第2

11、2頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二由于陣列處理機(jī)中處理器的數(shù)量比網(wǎng)格點(diǎn)數(shù)少得多，需要把離散域劃分為若干個(gè)網(wǎng)格塊，一個(gè)網(wǎng)格塊上的網(wǎng)格點(diǎn)的迭代計(jì)算由一個(gè)處理器完成。在劃分網(wǎng)格塊時(shí)要注意兩點(diǎn)，一是要使網(wǎng)格塊的大小相等，二是要使網(wǎng)格塊的周長(zhǎng)盡可能小，且相鄰網(wǎng)格塊的鄰界邊長(zhǎng)相等。迭代實(shí)現(xiàn)第23頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二6.4.2 陣列處理機(jī)的常用算法及性能分析 1. 矩陣加：把A和B同一位置的一對(duì)元素存放在同一個(gè)PEM中，那么，64個(gè)PE就可以同時(shí)并行地完成64對(duì)元素的相加。 第24頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二6.4.2

12、陣列處理機(jī)的常用算法及性能分析 2. 矩陣乘：若A和B為兩個(gè) 88 的矩陣，并行地一次完成8個(gè)中間積的運(yùn)算。最后對(duì)8個(gè)中間積做7次加法 。 7 cij = aikbkj 0 i , j 7 k=0(1) 順序執(zhí)行：每個(gè)Cij 需要8次乘法，7次加法，共需要 15*64=960 次加/乘法；第25頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二A(4*4)B(4*4)C(4*4)第26頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二A(4*4)B(4*4)C(4*4)第27頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二(2) 在Illiac 上執(zhí)行：每列或每排Cij 需

13、要1次乘法，3次加法，共需要 4*8=32 次加/乘法； 求88的矩陣乘法，顯然每列或每排Cij 需要1次乘法，7次加法，共需要 8*8=64 次加/乘法；書(shū)中說(shuō)每個(gè)Cij需要1次乘法，7次加法，共需要 8*64=512次加、乘法。 顯然有問(wèn)題，沒(méi)有充分利用64個(gè)運(yùn)算器。第28頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二6.4.2 陣列處理機(jī)的常用算法及性能分析 3. 累加和 7 S = ai i=0第29頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二第30頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二 如果在陣列處理機(jī)上采用成對(duì)遞歸相加的算法，則只需log28

14、 = 3次加法時(shí)間。 首先，8個(gè)原始數(shù)據(jù)A(i)，0i7，存放在8個(gè)PEM的a單元中，然后按下述步驟求累加和。第1步 置全部PE為活躍狀態(tài)；第2步 全部A(I)，0I7，從PE的a單元讀到相應(yīng)PE的 RGA中；第3步 令K:=0；第4步 全部PE的(RGA)轉(zhuǎn)送到RGR；第5步 全部PE的(RGR)經(jīng)過(guò)互連網(wǎng)絡(luò)向右傳送2k步距；第6步 令j=2k - 1；第7步 置PE0至PEj為不活躍狀態(tài)；第8步 處于活躍狀態(tài)的PE執(zhí)行(RGA):=(RGA)+(RGR) 的操作；第9步 K:=K+1；第10步 若K3，則轉(zhuǎn)第四步；否則，繼續(xù)往下執(zhí)行；第11步 置全部PE為活躍狀態(tài)；第12步 全部PE的(R

15、GA)存入相應(yīng)PEM的a+1單元中。第31頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二01234567RGA01234567RGRK=00123456RGR700-11-22-33-44-55-66-7RGA00-11-22-33-44-55-66-7RGRK=100-11-22-33-44-55-66-700-10-20-31-42-53-64-7RGARGR00-10-20-31-42-53-64-7RGRK=21-42-53-64-700-10-20-3RGR00-10-20-30-40-50-60-7RGA第32頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二【例6

16、.1】 A和B都是元素為浮點(diǎn)表示的6464的二維數(shù)組，一次浮點(diǎn)加法的計(jì)算過(guò)程可由取數(shù)、求階差、對(duì)階、尾數(shù)加、規(guī)格化和存數(shù)共6個(gè)段組成，若每個(gè)段的執(zhí)行時(shí)間均為 ，請(qǐng)分別求出在下列結(jié)構(gòu)不同的處理機(jī)上完成C=A+B所需時(shí)間及相對(duì)于順序處理方式的加速比。 第33頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二（1）順序處理方式的處理機(jī)。（2）具有浮點(diǎn)加法流水線(xiàn)的流水處理機(jī)，且浮點(diǎn)加法流水線(xiàn)分為6個(gè)段，各段執(zhí)行時(shí)間均為 。（3）88的陣列處理機(jī)，且處理陣列上的每個(gè)處理器只能順序處理浮點(diǎn)加運(yùn)算。（4）88的陣列處理機(jī)，且處理陣列上的每個(gè)處理器均能流水處理浮點(diǎn)加運(yùn)算。（5）6464的陣列處理機(jī)。 第

17、34頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二解 （1）需要順序執(zhí)行的浮點(diǎn)加法次數(shù)為 ，每次浮點(diǎn)加運(yùn)算所需時(shí)間為 ，則全部運(yùn)算所需時(shí)間為（2）需要流水執(zhí)行的浮點(diǎn)加法次數(shù)為 ，則一個(gè) 段的浮點(diǎn)加法流水線(xiàn)處理全部運(yùn)算所需時(shí)間和加速比為第35頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二（3）對(duì)于88的處理陣列，每個(gè)處理器需要處理6464二維數(shù)組中的一個(gè)的子數(shù)組，因此，每個(gè)處理器需要執(zhí)行的浮點(diǎn)加法次數(shù)為88=64。每次浮點(diǎn)加運(yùn)算所需時(shí)間為 。每個(gè)處理器順序執(zhí)行64次浮點(diǎn)加運(yùn)算所需時(shí)間為 。64個(gè)處理器并行處理，同時(shí)完成各自的64次浮點(diǎn)加運(yùn)算，所以，全部運(yùn)算所需時(shí)間和加速比為第

18、36頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二（4）對(duì)于88的處理陣列，每個(gè)處理器需要流水處理6464二維數(shù)組中的一個(gè)88的子數(shù)組，因此，每個(gè)處理器的浮點(diǎn)加法次數(shù)為n=88=64，k=6段的浮點(diǎn)加法流水線(xiàn)處理64次浮點(diǎn)加運(yùn)算所需時(shí)間為 64個(gè)處理器并行處理，同時(shí)完成各自的64次浮點(diǎn)加運(yùn)算，所以，全部運(yùn)算所需時(shí)間和加速比為第37頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二（5）對(duì)于6464的處理陣列，每個(gè)處理器只需執(zhí)行一次浮點(diǎn)加法運(yùn)算，所需時(shí)間為 ，所以，全部運(yùn)算所需時(shí)間和加速比為第38頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二【例6.2】 分別計(jì)算在下列

19、各處理機(jī)中，計(jì)算所需的時(shí)間及相對(duì)于順序處理方式的加速比。（1）順序處理方式的處理機(jī)。第39頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二（2）具有一個(gè)流水加法器和一個(gè)流水乘法器的流水處理機(jī)，且加法器和乘法器可以同時(shí)工作。（3）8個(gè)處理單元之間用雙向環(huán)互連的并行處理機(jī)，相鄰PE之間傳送一次數(shù)據(jù)需時(shí) 。（4）88的ILLIAC 陣列處理機(jī)，且相鄰處理單元之間傳送一次數(shù)據(jù)需時(shí) 。假設(shè)各處理機(jī)或處理單元取數(shù)和存數(shù)的時(shí)間忽略不計(jì)，完成一次加法需時(shí)2 ，完成一次乘法需時(shí)4 。第40頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二解 計(jì)算點(diǎn)積 需要做8次乘法和7次加法。（1）順序執(zhí)行8次乘法所需時(shí)間為再順序執(zhí)行7次加法所需時(shí)間為故共需時(shí)間為第41頁(yè)，共46頁(yè)，2022年，5月20日，2點(diǎn)22分，星期二（2）在流水處理機(jī)上，8次乘運(yùn)算分別用18表示，