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

計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)（第二版）華中科技大學(xué)出版社尹朝慶、王瑩目錄第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ī)的算法及性能分析

第6章

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

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

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

單指令流多數(shù)據(jù)流（SIMD）計(jì)算機(jī)的關(guān)鍵特征是它的并行處理機(jī)。它的并行處理機(jī)是由單一控制部件控制多個(gè)處理單元同時(shí)進(jìn)行運(yùn)算操作，多個(gè)處理單元通常通過互連網(wǎng)絡(luò)連接成陣列結(jié)構(gòu)，故也稱為陣列處理機(jī)。

并行處理機(jī)的所有處理單元同時(shí)執(zhí)行從控制部件廣播來(lái)的同一條指令，但指令使用不同的數(shù)據(jù)，因此，并行處理機(jī)是指令操作級(jí)并行的單指令流多數(shù)據(jù)流處理機(jī)。6.1.1單指令流多數(shù)據(jù)流計(jì)算機(jī)的兩種基本結(jié)構(gòu)

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

1.分布式存儲(chǔ)器SIMD計(jì)算機(jī)基本結(jié)構(gòu)

采用分布式存儲(chǔ)器構(gòu)型的SIMD計(jì)算機(jī)的基本結(jié)構(gòu)如圖6.1所示。并行處理機(jī)的每個(gè)處理單元都有自己的局部存儲(chǔ)器，存放可直接訪問的數(shù)據(jù)。所有的處理單元通過互連網(wǎng)絡(luò)互聯(lián)。陣列控制部件CU是一臺(tái)功能專用的處理機(jī)，它執(zhí)行程序流控制指令和程序中的標(biāo)量運(yùn)算。管理處理機(jī)SC運(yùn)行操作系統(tǒng)，管理系統(tǒng)資源。

圖6.1分布式存儲(chǔ)器的SIMD計(jì)算機(jī)基本結(jié)構(gòu)

2.集中式共享存儲(chǔ)器SIMD計(jì)算機(jī)基本結(jié)構(gòu)

采用集中式共享存儲(chǔ)器構(gòu)型的SIMD計(jì)算機(jī)的基本結(jié)構(gòu)如圖6.2所示。并行處理機(jī)的所有處理單元共享由個(gè)存儲(chǔ)體組成的并行存儲(chǔ)器，個(gè)處理單元與個(gè)存儲(chǔ)體之間通過互連網(wǎng)絡(luò)互連。CU和SC的功能與采用分布式存儲(chǔ)器構(gòu)型的SIMD計(jì)算機(jī)沒有什么差別。圖6.2集中式共享存儲(chǔ)器的SIMD計(jì)算機(jī)基本結(jié)構(gòu)

6.1.2單指令流多數(shù)據(jù)流計(jì)算機(jī)的主要特點(diǎn)

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

6.2分布式存儲(chǔ)器SIMD計(jì)算機(jī)實(shí)例分析

兩種典型的SIMD計(jì)算機(jī)采用分布式存儲(chǔ)器結(jié)構(gòu)的并行處理機(jī)的ILLIACⅣ計(jì)算機(jī)。采用集中式共享存儲(chǔ)器結(jié)構(gòu)的并行處理機(jī)的BSP計(jì)算機(jī)。1.ILLIACⅣ陣列ILLIACⅣ系統(tǒng)框圖如圖6.3所示。它是由3種類型處理機(jī)組成的一個(gè)異構(gòu)多處理機(jī)系統(tǒng)。一是專門用于數(shù)組運(yùn)算的處理單元陣列；二是陣列控制器，它既是處理單元陣列的控制部分，又是一臺(tái)相對(duì)獨(dú)立的小型標(biāo)量處理機(jī)；三是一臺(tái)標(biāo)準(zhǔn)的BurroughsB6700計(jì)算機(jī)，由它擔(dān)負(fù)ILLIACⅣ輸入輸出系統(tǒng)和操作系統(tǒng)管理功能。

圖6.3ILLIACⅣ系統(tǒng)框圖1.BSP計(jì)算機(jī)BSP計(jì)算機(jī)系統(tǒng)框圖如圖6.6所示。它由系統(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ī)，三是容量為4~64M字的文件存儲(chǔ)器。6.3集中式共享存儲(chǔ)器SIMD計(jì)算機(jī)實(shí)例分析

圖6.6BSP計(jì)算機(jī)系統(tǒng)框圖操作系統(tǒng)和維護(hù)信息文件存儲(chǔ)器CCD4～64M字文件存儲(chǔ)器控制器文件存儲(chǔ)器系統(tǒng)指令/控制存儲(chǔ)器256K字控制維護(hù)單元標(biāo)量處理單元并行處理機(jī)控制器控制處理機(jī)并行存儲(chǔ)器0.5～8M字入口和出口對(duì)準(zhǔn)網(wǎng)絡(luò)16個(gè)算術(shù)單元并行處理機(jī)100M字/s100M字/s12.5M字/s系統(tǒng)管理機(jī)B7700/B7800程序和數(shù)據(jù)250K字/s●●6.4陣列處理機(jī)的算法及性能分析

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

6.4.1陣列處理機(jī)的差分計(jì)算

描述平面場(chǎng)的拉普拉斯方程：

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

迭代計(jì)算開始時(shí)，除由邊界條件給定的某些邊緣點(diǎn)之外，其余網(wǎng)格點(diǎn)的函數(shù)值初值均可設(shè)為零。若取網(wǎng)格間距為單位1，迭代計(jì)算的表達(dá)式為：式中的上標(biāo)t表示迭代次數(shù)。迭代計(jì)算直至連續(xù)二次迭代所求值的差小于規(guī)定誤差為止。

由于陣列處理機(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)6.4.2陣列處理機(jī)的常用算法及性能分析

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

2.矩陣乘：若A和B為兩個(gè)8×8的矩陣，并行地一次完成8個(gè)中間積的運(yùn)算。最后對(duì)8個(gè)中間積做7次加法。3.累加和

【例6.1】

A和B都是元素為浮點(diǎn)表示的64×64的二維數(shù)組，一次浮點(diǎn)加法的計(jì)算過程可由取數(shù)、求階差、對(duì)階、尾數(shù)加、規(guī)格化和存數(shù)共6個(gè)段組成，若每個(gè)段的執(zhí)行時(shí)間均為，請(qǐng)分別求出在下列結(jié)構(gòu)不同的處理機(jī)上完成C=A+B所需時(shí)間及相對(duì)于順序處理方式的加速比。

（1）順序處理方式的處理機(jī)。（2）具有浮點(diǎn)加法流水線的流水處理機(jī)，且浮點(diǎn)加法流水線分為6個(gè)段，各段執(zhí)行時(shí)間均為。（3）8×8的陣列處理機(jī)，且處理陣列上的每個(gè)處理器只能順序處理浮點(diǎn)加運(yùn)算。（4）8×8的陣列處理機(jī)，且處理陣列上的每個(gè)處理器均能流水處理浮點(diǎn)加運(yùn)算。（5）64×64的陣列處理機(jī)。

解

（1）需要順序執(zhí)行的浮點(diǎn)加法次數(shù)為，每次浮點(diǎn)加運(yùn)算所需時(shí)間為，則全部運(yùn)算所需時(shí)間為（2）需要流水執(zhí)行的浮點(diǎn)加法次數(shù)為，則一個(gè)段的浮點(diǎn)加法流水線處理全部運(yùn)算所需時(shí)間和加速比為（3）對(duì)于8×8的處理陣列，每個(gè)處理器需要處理64×64二維數(shù)組中的一個(gè)的子數(shù)組，因此，每個(gè)處理器需要執(zhí)行的浮點(diǎn)加法次數(shù)為8×8=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í)間和加速比為（4）對(duì)于8×8的處理陣列，每個(gè)處理器需要流水處理64×64二維數(shù)組中的一個(gè)8×8的子數(shù)組，因此，每個(gè)處理器的浮點(diǎn)加法次數(shù)為n=8×8=64，k=6段的浮點(diǎn)加法流水線處理64次浮點(diǎn)加運(yùn)算所需時(shí)間為。64個(gè)處理器并行處理，同時(shí)完成各自的64次浮點(diǎn)加運(yùn)算，所以，全部運(yùn)算所需時(shí)間和加速比為（5）對(duì)于64×64的處理陣列，每個(gè)處理器只需執(zhí)行一次浮點(diǎn)加法運(yùn)算，所需時(shí)間為，所以，全部運(yùn)算所需時(shí)間和加速比為【例6.2】

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

計(jì)算點(diǎn)積需要做8次乘法和7次加法。（1）順序執(zhí)行8次乘法所需時(shí)間為再順序執(zhí)行7次加法所需時(shí)間為故共需時(shí)間為（2）在流水處理機(jī)上，8次乘運(yùn)算分別用1~8表示，7次加運(yùn)算分別用9~15表示，時(shí)空?qǐng)D如圖6.10所示圖6.10計(jì)算S的時(shí)空?qǐng)D

（3）由8個(gè)PE組成的雙向環(huán)，每個(gè)PE有自己的局部存儲(chǔ)器PEM，向量A和B的元素對(duì)和存儲(chǔ)在相應(yīng)的中。雙向環(huán)上的累加和計(jì)算過程可以用樹形流程圖直觀地表示，結(jié)點(diǎn)表示PE，有向弧箭頭表示相應(yīng)PE之間沿雙向環(huán)的數(shù)據(jù)傳送，需要特別指出的是：由于SIMD計(jì)算機(jī)的并行處理機(jī)的所有處理單元（PE）只能同時(shí)執(zhí)行同一條指令，因此，SIMD的樹形流程圖中同一層的所有結(jié)點(diǎn)只能執(zhí)行同一種運(yùn)算。有向弧的值為數(shù)據(jù)傳送時(shí)間，如果兩層之間的有向弧的值不等，那么，應(yīng)取最大值作為層間PE的數(shù)據(jù)傳送時(shí)間。

在雙向環(huán)上完成累加和計(jì)算3次傳送所需時(shí)間:3次加法所需時(shí)