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

單指令流多數(shù)據(jù)流計算機第1頁，共46頁，2023年，2月20日，星期一目錄第6章單指令流多數(shù)據(jù)流計算機

6.1單指令流多數(shù)據(jù)流計算機的基本結(jié)構(gòu)與特點

6.2分布式存儲器SIMD計算機實例分析

6.3集中式共享存儲器SIMD計算機實例分析

6.4陣列處理機的算法及性能分析第2頁，共46頁，2023年，2月20日，星期一

第6章

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

第3頁，共46頁，2023年，2月20日，星期一6.1單指令流多數(shù)據(jù)流計算機的

基本結(jié)構(gòu)與特點

單指令流多數(shù)據(jù)流（SIMD）計算機的關(guān)鍵特征是它的并行處理機。它的并行處理機是由單一控制部件控制多個處理單元同時進行運算操作，多個處理單元通常通過互連網(wǎng)絡(luò)連接成陣列結(jié)構(gòu)，故也稱為陣列處理機。并行處理機的所有處理單元同時執(zhí)行從控制部件廣播來的同一條指令，但指令使用不同的數(shù)據(jù)，因此，并行處理機是指令操作級并行的單指令流多數(shù)據(jù)流處理機。第4頁，共46頁，2023年，2月20日，星期一6.1.1單指令流多數(shù)據(jù)流計算機的兩種基本結(jié)構(gòu)

根據(jù)存儲器的組織方式不同，單指令流多數(shù)據(jù)流計算機的基本結(jié)構(gòu)分為兩種： 集中式共享存儲器型 分布式存儲器型

第5頁，共46頁，2023年，2月20日，星期一1.分布式存儲器SIMD計算機基本結(jié)構(gòu)

并行處理機的每個處理單元都有自己的局部存儲器，存放可直接訪問的數(shù)據(jù)。所有的處理單元通過互連網(wǎng)絡(luò)互聯(lián)。陣列控制部件CU是一臺功能專用的處理機，它執(zhí)行程序流控制指令和程序中的標量運算。管理處理機SC運行操作系統(tǒng)，管理系統(tǒng)資源。

第6頁，共46頁，2023年，2月20日，星期一圖6.1分布式存儲器的SIMD計算機基本結(jié)構(gòu)第7頁，共46頁，2023年，2月20日，星期一2.集中式共享存儲器SIMD計算機基本結(jié)構(gòu)

并行處理機的所有處理單元共享由個存儲體組成的并行存儲器，處理單元與存儲體之間通過互連網(wǎng)絡(luò)互連。CU和SC的功能與采用分布式存儲器構(gòu)型的SIMD計算機沒有什么差別。第8頁，共46頁，2023年，2月20日，星期一圖6.2集中式共享存儲器的SIMD計算機基本結(jié)構(gòu)第9頁，共46頁，2023年，2月20日，星期一6.1.2單指令流多數(shù)據(jù)流計算機的主要特點

SIMD的效率取決于計算程序向量化的程度。SIMD計算機依靠的并行措施是資源重復(fù)。SIMD計算機的互連網(wǎng)絡(luò)決定了SIMD計算機能適應(yīng)的算法類別，SIMD計算機的實際有效速度取決于另外兩個因素。一是標量運算速度，二是編譯過程的時間開銷。SIMD計算機是根據(jù)功能專用化的原則組成的一種異構(gòu)型多計算機系統(tǒng)。

第10頁，共46頁，2023年，2月20日，星期一6.2分布式存儲器SIMD計算機實例分析

兩種典型的SIMD計算機采用分布式存儲器結(jié)構(gòu)的并行處理機的ILLIACⅣ計算機。采用集中式共享存儲器結(jié)構(gòu)的并行處理機的BSP計算機。第11頁，共46頁，2023年，2月20日，星期一1.ILLIACⅣ陣列ILLIACⅣ系統(tǒng)由3種類型處理機組成的一個異構(gòu)多處理機系統(tǒng)。一是專門用于數(shù)組運算的處理單元陣列；二是陣列控制器，它既是處理單元陣列的控制部分，又是一臺相對獨立的小型標量處理機；三是一臺標準的BurroughsB6700計算機，由它擔(dān)負ILLIACⅣ輸入輸出系統(tǒng)和操作系統(tǒng)管理功能。第12頁，共46頁，2023年，2月20日，星期一

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

第14頁，共46頁，2023年，2月20日，星期一圖6.6BSP計算機系統(tǒng)框圖操作系統(tǒng)和維護信息文件存儲器CCD4～64M字文件存儲器控制器文件存儲器系統(tǒng)指令/控制存儲器256K字控制維護單元標量處理單元并行處理機控制器控制處理機并行存儲器0.5～8M字入口和出口對準網(wǎng)絡(luò)16個算術(shù)單元并行處理機100M字/s100M字/s12.5M字/s系統(tǒng)管理機B7700/B7800程序和數(shù)據(jù)250K字/s●●第15頁，共46頁，2023年，2月20日，星期一系統(tǒng)管理機文件存儲器控制處理機(指令存儲器，標量運算器)17個存儲體16算術(shù)單元BSP科學(xué)處理機系統(tǒng)組成第16頁，共46頁，2023年，2月20日，星期一為了說明BSP并行存儲器的地址變換和無沖突訪問，下面先看一個較簡單的例子。設(shè)并行存儲器的存儲體數(shù)m=7(質(zhì)數(shù))，運算單元數(shù)n=6。若有一個45的數(shù)組。

a00a01a02a03a04

a10a11a12a13a14a20a21a22a23a24a30a31a32a33a34第17頁，共46頁，2023年，2月20日，星期一

BSP的地址映象關(guān)系為：先將二維數(shù)組按列或者按行的順序變換為一維數(shù)組，以形成一個一維線性地址空間，地址用a表示。然后將地址a變換成并行存儲器地址(j，i)，其中j是存儲體體號，i是體內(nèi)地址：

j=amodmi=[a／n]下整存儲體數(shù)m為一質(zhì)數(shù)，n為無沖突訪問的最大存儲體數(shù)。第18頁，共46頁，2023年，2月20日，星期一3.BSP的數(shù)據(jù)流水線結(jié)構(gòu)

BSP的16個AE組成的算術(shù)單元陣列、17個存儲體組成的并行存儲器和2套互連網(wǎng)絡(luò)(對準網(wǎng)絡(luò))形成了一條5級數(shù)據(jù)流水線，使連續(xù)幾條向量指令能在時間上重疊起來執(zhí)行。①由17個存儲器輸出端口并行讀出16個操作數(shù)。②經(jīng)對準網(wǎng)絡(luò)NWl將16個操作數(shù)重排列成16個算術(shù)單元需要的次序。③將排列好的16個操作數(shù)送到16個算術(shù)單元完成操作。④所得的16個結(jié)果經(jīng)對準網(wǎng)絡(luò)NW2重新排列成在17個存儲體中存儲所需要的次序。⑤寫入并行存儲器。存儲器處理器對準網(wǎng)絡(luò)2對準網(wǎng)絡(luò)1第19頁，共46頁，2023年，2月20日，星期一6.4陣列處理機的算法及性能分析

陣列處理機的處理器陣列有固定的結(jié)構(gòu)，因此，陣列處理機的性能與算法有很大關(guān)系。若問題求解的算法能與陣列處理機的結(jié)構(gòu)相適應(yīng)，就能獲得較高的性能；否則，陣列處理機的實際性能就很低，處理單元的利用率也很低。

第20頁，共46頁，2023年，2月20日，星期一6.4.1陣列處理機的差分計算

描述平面場的拉普拉斯方程：

將二階偏導(dǎo)數(shù)表示為差分形式:代入原方程，則可得有限差分計算公式：

第21頁，共46頁，2023年，2月20日，星期一迭代計算開始時，除由邊界條件給定的某些邊緣點之外，其余網(wǎng)格點的函數(shù)值初值均可設(shè)為零。若取網(wǎng)格間距為單位1，迭代計算的表達式為：式中的上標t表示迭代次數(shù)。迭代計算直至連續(xù)二次迭代所求值的差小于規(guī)定誤差為止。

第22頁，共46頁，2023年，2月20日，星期一由于陣列處理機中處理器的數(shù)量比網(wǎng)格點數(shù)少得多，需要把離散域劃分為若干個網(wǎng)格塊，一個網(wǎng)格塊上的網(wǎng)格點的迭代計算由一個處理器完成。在劃分網(wǎng)格塊時要注意兩點，一是要使網(wǎng)格塊的大小相等，二是要使網(wǎng)格塊的周長盡可能小，且相鄰網(wǎng)格塊的鄰界邊長相等。迭代實現(xiàn)第23頁，共46頁，2023年，2月20日，星期一6.4.2陣列處理機的常用算法及性能分析

1.矩陣加：把A和B同一位置的一對元素存放在同一個PEM中，那么，64個PE就可以同時并行地完成64對元素的相加。

第24頁，共46頁，2023年，2月20日，星期一6.4.2陣列處理機的常用算法及性能分析

2.矩陣乘：若A和B為兩個8×8的矩陣，并行地一次完成8個中間積的運算。最后對8個中間積做7次加法。

7cij=∑aikbkj0≤i,j≤7

k=0(1)順序執(zhí)行：每個Cij需要8次乘法，7次加法，共需要15*64=960次加/乘法；第25頁，共46頁，2023年，2月20日，星期一A(4*4)B(4*4)C(4*4)第26頁，共46頁，2023年，2月20日，星期一A(4*4)B(4*4)C(4*4)第27頁，共46頁，2023年，2月20日，星期一(2)在Illiac上執(zhí)行：每列或每排Cij需要1次乘法，3次加法，共需要4*8=32次加/乘法；求8×8的矩陣乘法，顯然每列或每排Cij需要1次乘法，7次加法，共需要8*8=64次加/乘法；書中說每個Cij需要1次乘法，7次加法，共需要

8*64=512次加、乘法。顯然有問題，沒有充分利用64個運算器。第28頁，共46頁，2023年，2月20日，星期一6.4.2陣列處理機的常用算法及性能分析

3.累加和

7S

=∑ai

i=0第29頁，共46頁，2023年，2月20日，星期一第30頁，共46頁，2023年，2月20日，星期一

如果在陣列處理機上采用成對遞歸相加的算法，則只需log28=3次加法時間。首先，8個原始數(shù)據(jù)A(i)，0≤i≤7，存放在8個PEM的a單元中，然后按下述步驟求累加和。第1步置全部PE為活躍狀態(tài)；第2步全部A(I)，0≤I≤7，從PE的a單元讀到相應(yīng)PE的

RGA中；第3步令K:=0；第4步全部PE的(RGA)轉(zhuǎn)送到RGR；第5步全部PE的(RGR)經(jīng)過互連網(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步若K<3，則轉(zhuǎn)第四步；否則，繼續(xù)往下執(zhí)行；第11步置全部PE為活躍狀態(tài)；第12步全部PE的(RGA)存入相應(yīng)PEM的a+1單元中。第31頁，共46頁，2023年，2月20日，星期一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頁，共46頁，2023年，2月20日，星期一【例6.1】A和B都是元素為浮點表示的64×64的二維數(shù)組，一次浮點加法的計算過程可由取數(shù)、求階差、對階、尾數(shù)加、規(guī)格化和存數(shù)共6個段組成，若每個段的執(zhí)行時間均為，請分別求出在下列結(jié)構(gòu)不同的處理機上完成C=A+B所需時間及相對于順序處理方式的加速比。

第33頁，共46頁，2023年，2月20日，星期一（1）順序處理方式的處理機。（2）具有浮點加法流水線的流水處理機，且浮點加法流水線分為6個段，各段執(zhí)行時間均為。（3）8×8的陣列處理機，且處理陣列上的每個處理器只能順序處理浮點加運算。（4）8×8的陣列處理機，且處理陣列上的每個處理器均能流水處理浮點加運算。（5）64×64的陣列處理機。

第34頁，共46頁，2023年，2月20日，星期一解（1）需要順序執(zhí)行的浮點加法次數(shù)為，每次浮點加運算所需時間為，則全部運算所需時間為（2）需要流水執(zhí)行的浮點加法次數(shù)為，則一個段的浮點加法流水線處理全部運算所需時間和加速比為第35頁，共46頁，2023年，2月20日，星期一（3）對于8×8的處理陣列，每個處理器需要處理64×64二維數(shù)組中的一個的子數(shù)組，因此，每個處理器需要執(zhí)行的浮點加法次數(shù)為8×8=64。每次浮點加運算所需時間為。每個處理器順序執(zhí)行64次浮點加運算所需時間為。64個處理器并行處理，同時完成各自的64次浮點加運算，所以，全部運算所需時間和加速比為第36頁，共46頁，2023年，2月20日，星期一（4）對于8×8的處理陣列，每個處理器需要流水處理64×64二維數(shù)組中的一個8×8的子數(shù)組，因此，每個處理器的浮點加法次數(shù)為n=8×8=64，k=6段的浮點加法流水線處理64次浮點加運算所需時間為

64個處理器并行處理，同時完成各自的64次浮點加運算，所以，全部運算所需時間和加速比為第37頁，共46頁，2023年，2月20日，星期一（5）對于64×64的處理陣列，每個處理器只需執(zhí)行一次浮點加法運算，所需時間為，所以，全部運算所需時間和加速比為第38頁，共46頁，2023年，2月20日，星期一【例6.2】

分別計算在下列各處理機中，計算所需的時間及相對于順序處理方式的加速比。（1）順序處理方式的處理機。第39頁，共46頁，2023年，2月20日，星期一（2）具有一個流水加法器和一個流水乘法器的流水處理機，且加法器和乘法器可以同時工作。（3）8個處理單元之間用雙向環(huán)互連的并行處理機，相鄰PE之間傳送一次數(shù)據(jù)需時。（4）8×8的ILLIACⅣ陣列處理機，且相鄰處理單元之間傳送一次數(shù)據(jù)需時。假設(shè)各處理機或處理單元取數(shù)和存數(shù)的時間忽略不計，完成一次加法需時2，完成一次乘法需時4。第40頁，共46頁，2023年，2月20日，星期一解

計算點積需要做8次乘法和7次加法。（1）順序執(zhí)行8次乘法所需時間為再順序執(zhí)行7次加法所需時間為故共需時間為第41頁，共46頁，2023年，2月20日，星期一（2）在流水處理