第13章陣列處理機(jī)13.1 陣列處理機(jī)的操作模型和特點(diǎn)13.2 陣列處理機(jī)的基本結(jié)構(gòu)13.3 陣列處理機(jī)實(shí)例13.4 陣列處理機(jī)的并行算法舉例陣列處理機(jī)核心：一個(gè)由多個(gè)處理單元構(gòu)成的陣列采用資源重復(fù)的方法，設(shè)置較多的處理單元來提高并行性。用單一的控制部件來控制多個(gè)處理單元對(duì)各自的數(shù)據(jù)進(jìn)行相同的運(yùn)算和操作。又稱為SIMD計(jì)算機(jī)。有時(shí)還被稱為并行處理機(jī)。陣列處理機(jī)的操作模型用一個(gè)控制部件CU同時(shí)管理多個(gè)處理單元PE。CU對(duì)指令進(jìn)行譯碼，并把指令播送到各處理單元。所有處理單元均被動(dòng)地接收并執(zhí)行從控制部件廣播來的同一條指令，但它們所操作的對(duì)象卻是不同的數(shù)據(jù)。13.1陣列處理機(jī)的操作模型和特點(diǎn)13.1陣列處理機(jī)的操作模型和特點(diǎn)陣列處理機(jī)的操作模型

13.1陣列處理機(jī)的操作模型和特點(diǎn)陣列處理機(jī)的操作模型可用五元組表示陣列處理機(jī)＝（N，C，I，M，R）其中：N：機(jī)器的處理單元（PE）數(shù)。例如：IlliacⅣ計(jì)算機(jī)有64個(gè)PEMP-1計(jì)算機(jī)有16384個(gè)PEC：控制部件CU直接執(zhí)行的指令集，包括標(biāo)量指令和程序流控制指令。I：由CU廣播至所有PE進(jìn)行并行執(zhí)行的指令集。包括算術(shù)運(yùn)算、邏輯運(yùn)算、數(shù)據(jù)尋徑、屏蔽以及其他由每個(gè)PE對(duì)它的數(shù)據(jù)所執(zhí)行的局部操作。13.1陣列處理機(jī)的操作模型和特點(diǎn)M：屏蔽方案集每種屏蔽將所有PE劃分成允許操作和禁止操作兩種工作模式。R：數(shù)據(jù)尋徑功能集說明互連網(wǎng)絡(luò)中PE間通信所需要的各種設(shè)置模式。例如：MasParMP-1計(jì)算機(jī)的操作特性如下：（1）MP-1是一種SIMD機(jī)器，其PE數(shù)N＝1024～16384。（2）CU執(zhí)行標(biāo)量指令，將譯碼后的向量指令廣播到PE陣列，并控制PE間通信。（3）每個(gè)PE都是RISC處理機(jī)，能執(zhí)行不同數(shù)據(jù)的整數(shù)運(yùn)算和標(biāo)準(zhǔn)浮點(diǎn)運(yùn)算。PE從CU接收指令。

13.1陣列處理機(jī)的操作模型和特點(diǎn)

（4）屏蔽方案設(shè)在每個(gè)PE中，并由CU連續(xù)監(jiān)控，它能在運(yùn)行時(shí)動(dòng)態(tài)地使每個(gè)PE處于工作或禁止?fàn)顟B(tài)。（5）MP-1有一個(gè)X-Net網(wǎng)格網(wǎng)絡(luò)和一個(gè)全局多級(jí)交叉開關(guān)尋徑器，以實(shí)現(xiàn)CU-PE之間、X-Net的8個(gè)近鄰和全局尋徑器的通信。陣列處理機(jī)的特點(diǎn)以單指令流多數(shù)據(jù)流方式工作。通過設(shè)置多個(gè)相同的處理單元來開發(fā)并行性。利用并行性中的同時(shí)性，而不是并發(fā)性。所有處理單元必須同時(shí)進(jìn)行相同的操作。以某一類算法為背景的專用計(jì)算機(jī)。13.1陣列處理機(jī)的操作模型和特點(diǎn)陣列機(jī)的研究必須與并行算法的研究密切結(jié)合，以便能充分發(fā)揮它的處理能力。陣列機(jī)的控制器實(shí)質(zhì)上是一臺(tái)標(biāo)量處理機(jī)，而為了完成I/O操作以及操作系統(tǒng)的管理，尚需一個(gè)前端機(jī)。實(shí)際的陣列機(jī)系統(tǒng)是由3部分構(gòu)成的一個(gè)異構(gòu)型多處理機(jī)系統(tǒng)。分布式存儲(chǔ)器的陣列機(jī)結(jié)構(gòu)含有多個(gè)相同的處理單元PE，每個(gè)PE有各自的本地存儲(chǔ)器LM。PE之間通過數(shù)據(jù)尋徑網(wǎng)絡(luò)以一定方式互相連接。它們?cè)陉嚵锌刂撇考慕y(tǒng)一指揮下，實(shí)現(xiàn)并行操作。指令的執(zhí)行順序基本上是串行進(jìn)行的。程序和數(shù)據(jù)是通過主機(jī)裝入控制存儲(chǔ)器。13.2陣列處理機(jī)的基本結(jié)構(gòu)13.2.1分布式存儲(chǔ)器的陣列機(jī)13.2陣列處理機(jī)的基本結(jié)構(gòu)分布式存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu)

13.2陣列處理機(jī)的基本結(jié)構(gòu)指令送到控制部件進(jìn)行譯碼。標(biāo)量指令：直接由標(biāo)量處理機(jī)執(zhí)行。向量指令：陣列控制部件通過廣播總線將它廣播到所有PE中去并行地執(zhí)行。執(zhí)行程序所需的數(shù)據(jù)集經(jīng)劃分后通過數(shù)據(jù)總線分布存放到各PE的本地存儲(chǔ)器LM。各PE之間通過數(shù)據(jù)尋徑網(wǎng)絡(luò)互連，實(shí)現(xiàn)PE間的通信，控制部件通過執(zhí)行程序來控制數(shù)據(jù)尋徑網(wǎng)絡(luò)。PE的同步是在控制部件的控制下由硬件實(shí)現(xiàn)?？梢宰屗蠵E在同一個(gè)周期執(zhí)行同一條指令13.2陣列處理機(jī)的基本結(jié)構(gòu)也可以通過采用屏蔽邏輯來控制某些PE在指定的指令周期是否參與執(zhí)行各種陣列處理機(jī)的主要差別在于數(shù)據(jù)尋徑網(wǎng)絡(luò)的不同。IlliacⅣ：4-鄰連接網(wǎng)絡(luò)結(jié)構(gòu)（在過去是最常用的一種）CM-2：嵌在網(wǎng)格中的超立方體MasParMP-1：X-Net加多級(jí)交叉開關(guān)尋徑器13.2陣列處理機(jī)的基本結(jié)構(gòu)共享存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu)集中設(shè)置存儲(chǔ)器共享的多體并行存儲(chǔ)器SM通過對(duì)準(zhǔn)網(wǎng)絡(luò)與各處理單元PE相連。存儲(chǔ)模塊的數(shù)目等于或略大于處理單元的數(shù)目。必須減少存儲(chǔ)器訪問沖突（將數(shù)據(jù)合理地分配到各存儲(chǔ)器模塊中）在處理單元數(shù)目不太多的情況下是很理想的所有陣列指令都必須使用長度為n的向量操作數(shù)（n為PE的個(gè)數(shù))13.2.2共享存儲(chǔ)器的陣列機(jī)13.2陣列處理機(jī)的基本結(jié)構(gòu)共享存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu)互連網(wǎng)絡(luò)是共享存儲(chǔ)器SM和處理單元PE之間的必由之路。美國寶來公司和伊利諾大學(xué)合作研制1972年最早的陣列處理機(jī)一個(gè)由3種類型處理機(jī)聯(lián)合組成的多機(jī)系統(tǒng)處理單元陣列：專門用于數(shù)組運(yùn)算陣列控制器（CU）：既是處理單元陣列的控制部分，又可以看作是一臺(tái)相對(duì)獨(dú)立的小型標(biāo)量處理機(jī)。一臺(tái)標(biāo)準(zhǔn)的B6700計(jì)算機(jī)：擔(dān)負(fù)IlliacⅣ輸入輸出系統(tǒng)和操作系統(tǒng)管理功能13.3陣列處理機(jī)實(shí)例13.3.1實(shí)例1：IlliacⅣ陣列處理機(jī)

13.3陣列處理機(jī)實(shí)例

IlliacⅣ系統(tǒng)總框圖

13.3陣列處理機(jī)實(shí)例

IlliacⅣ陣列由64個(gè)處理單元（PE）、64個(gè)本地存儲(chǔ)器（PEM）和存儲(chǔ)器邏輯部件（MLU）組成；把每個(gè)PE和PEM對(duì)看成是一個(gè)處理部件PU；64個(gè)處理部件PU0～PU63排列成一個(gè)8×8方陣

IlliacⅣ的陣列結(jié)構(gòu)又稱為閉合螺線陣列；既便于一維長向量（多至64個(gè)元素）的處理，又便于二維數(shù)組運(yùn)算，以縮短處理單元之間的路徑距離。步距不等于±1或±8的任意處理單元間通信可用軟件方法尋找最短路徑，其最短距離都不會(huì)超過7步。

IlliacⅣ處理部件的連接

例如：從PU10到PU46的距離以下列路徑為最短

PU10→PU9→PU8→PU0→PU63→PU62→PU54→PU46

13.3陣列處理機(jī)實(shí)例一般情況，n×n個(gè)單元組成的陣列中，任意兩個(gè)處理單元之間的最短距離不會(huì)超過（n－1）步。

每個(gè)處理單元有6個(gè)可編程序寄存器64位字長的累加器RGA64位字長的操作數(shù)寄存器RGB64位字長的數(shù)據(jù)路由寄存器RGR64位字長的通用寄存器RGS

（可被程序用來暫存中間結(jié)果）16位的變址寄存器8位的模式寄存器

（存放PE屏蔽信息以及狀態(tài)位）13.3陣列處理機(jī)實(shí)例運(yùn)算部件加/乘算術(shù)單元邏輯單元移位單元地址加法器等操作數(shù)來源PE本身的寄存器PEMCU的公共數(shù)據(jù)總線PE的4個(gè)近鄰13.3陣列處理機(jī)實(shí)例并行的加法速度每秒1010次8位定點(diǎn)加法或150×106次64位浮點(diǎn)加法每一個(gè)處理單元有一個(gè)自己的本地存儲(chǔ)器PEM

PE和PEM之間經(jīng)過存儲(chǔ)器邏輯部件MLU相連陣列控制器CU一臺(tái)小型計(jì)算機(jī)對(duì)陣列的處理單元進(jìn)行控制利用本身的內(nèi)部資源執(zhí)行一整套指令，用以完成標(biāo)量操作。功能13.3陣列處理機(jī)實(shí)例對(duì)指令流進(jìn)行控制和譯碼，包括執(zhí)行一整套標(biāo)量指令；向各處理單元發(fā)出執(zhí)行數(shù)組操作指令所需的控制信號(hào)；產(chǎn)生并向所有處理單元廣播公共的地址部分；產(chǎn)生并向所有處理單元廣播公共的數(shù)據(jù)；接收和處理由各PE計(jì)算出錯(cuò)、系統(tǒng)I/O操作以及B6700所產(chǎn)生的陷阱中斷信號(hào)。陣列控制器CU與處理單元之間有4條信息通路

CU總線公共數(shù)據(jù)總線CDB模式位線指令控制線（大約有200根）13.3陣列處理機(jī)實(shí)例輸入輸出系統(tǒng)

由磁盤文件系統(tǒng)DFS、I/O分系統(tǒng)和B6700管理計(jì)算機(jī)組成。磁盤文件系統(tǒng)DFS兩套大容量并行讀寫磁盤系統(tǒng)及其相應(yīng)的控制器；每套有13臺(tái)磁盤機(jī)，總?cè)萘繛?09位；每臺(tái)磁盤機(jī)有128道，每道一個(gè)磁頭，并行讀寫，數(shù)據(jù)寬度為256位，最大傳輸率為502×106b/s；平均等待時(shí)間為19.6ms；如果兩個(gè)通道同時(shí)發(fā)送或接收數(shù)據(jù)，則數(shù)據(jù)寬度為512位，最大傳輸率為109b/s。

13.3陣列處理機(jī)實(shí)例I/O系統(tǒng)包括3部分：輸入/輸出開關(guān)IOS作為一個(gè)開關(guān)，把DFS或可能連上的實(shí)時(shí)裝置轉(zhuǎn)接到陣列存儲(chǔ)器，進(jìn)行大批數(shù)據(jù)的I/O傳送；作為DFS和PEM之間的緩沖，以平衡兩邊不同的數(shù)據(jù)寬度。控制描述字控制器CDC對(duì)陣列控制器CU的I/O請(qǐng)求進(jìn)行管理BIOM在DFS和B6700之間，是為了取得二者之間傳送帶寬上的匹配。13.3陣列處理機(jī)實(shí)例B6700管理計(jì)算機(jī)管理全部系統(tǒng)資源，完成用戶程序的編譯或匯編，為IlliacⅣ進(jìn)行作業(yè)調(diào)度、存儲(chǔ)分配、產(chǎn)生I/O控制描述字送至CDC、處理中斷、提供操作系統(tǒng)所具備的其他服務(wù)等。13.3.2實(shí)例2：BSP計(jì)算機(jī)美國寶來公司和伊利諾依大學(xué)1979年共享存儲(chǔ)器結(jié)構(gòu)的SIMD計(jì)算機(jī)的典型代表最高處理性能：每秒5千萬次浮點(diǎn)運(yùn)算

依靠并行性來提高性能

BSP計(jì)算機(jī)系統(tǒng)的框圖13.3陣列處理機(jī)實(shí)例BSP處理機(jī)由3部分構(gòu)成：控制處理機(jī)，并行處理機(jī)，文件存儲(chǔ)器。BSP處理機(jī)并行處理機(jī)包含16個(gè)算術(shù)單元AE、由17個(gè)存儲(chǔ)體組成的一個(gè)無沖突訪問的并行存儲(chǔ)器和兩套對(duì)準(zhǔn)網(wǎng)絡(luò)（分別為入口和出口對(duì)準(zhǔn)網(wǎng)絡(luò)）一條5級(jí)的數(shù)據(jù)流水線從17個(gè)存儲(chǔ)器輸出端口并行讀出16個(gè)操作數(shù)；經(jīng)對(duì)準(zhǔn)網(wǎng)絡(luò)NW1將16個(gè)操作數(shù)重新排列，形成16個(gè)算術(shù)單元所需要的順序；

13.3陣列處理機(jī)實(shí)例BSP的5級(jí)數(shù)據(jù)流水線結(jié)構(gòu)示意圖

13.3陣列處理機(jī)實(shí)例將排列好的16個(gè)操作數(shù)送到16個(gè)算術(shù)單元進(jìn)行處理；所得的16個(gè)結(jié)果經(jīng)對(duì)準(zhǔn)網(wǎng)絡(luò)NW2重新排列成在17個(gè)存儲(chǔ)體中存儲(chǔ)所需要的次序；寫入并行存儲(chǔ)器。兩套對(duì)準(zhǔn)網(wǎng)絡(luò)的作用：在讀或?qū)懖⑿写鎯?chǔ)器時(shí)，使并行存儲(chǔ)器中為保證無沖突訪問而錯(cuò)開存放的操作數(shù)順序能夠與算術(shù)單元并行處理所要求的正常順序協(xié)調(diào)一致。這種流水線對(duì)提高系統(tǒng)處理效率有很大作用。有效地實(shí)現(xiàn)了處理單元、存儲(chǔ)器和互連網(wǎng)絡(luò)在時(shí)間上重疊工作，在理想情況下能取得帶寬的完全匹配。13.3陣列處理機(jī)實(shí)例可把大于16的任意長度的向量按16個(gè)分量的標(biāo)準(zhǔn)長度分為若干段，依次在時(shí)間上重疊起來進(jìn)行處理。實(shí)現(xiàn)不同向量指令的重疊執(zhí)行。數(shù)據(jù)保存在由17個(gè)存儲(chǔ)體組成的并行存儲(chǔ)器中，每個(gè)存儲(chǔ)體的容量可達(dá)512K字，存儲(chǔ)周期為160ns。

（一個(gè)無沖突訪問存儲(chǔ)器）控制處理機(jī)控制并行處理機(jī)，提供與系統(tǒng)管理機(jī)相連的接口。標(biāo)量處理單元：處理存儲(chǔ)在指令/控制存儲(chǔ)器中的全部操作系統(tǒng)和用戶程序的指令。13.3陣列處理機(jī)實(shí)例全部的向量指令以及某些成組運(yùn)算的標(biāo)量指令被送給并行處理機(jī)控制器。在經(jīng)過合格性檢查之后，并行處理機(jī)控制器將指令轉(zhuǎn)換為微操作序列去控制16個(gè)AE操作。指令/控制存儲(chǔ)器的容量為256K字，存儲(chǔ)周期為160ns，字長為56位，其中8位是校驗(yàn)位，提供單錯(cuò)校正和雙錯(cuò)檢測的能力?？刂凭S護(hù)單元：系統(tǒng)管理機(jī)與控制處理機(jī)的接口，用來對(duì)控制處理機(jī)進(jìn)行初始化以及監(jiān)控命令的通信和維護(hù)。

13.3陣列處理機(jī)實(shí)例文件存儲(chǔ)器BSP直接控制下的唯一外圍設(shè)備。BSP程序執(zhí)行過程中所產(chǎn)生的暫存文件和輸出文件都是先存放在文件存儲(chǔ)器中，然后才被送給系統(tǒng)管理機(jī)，輸出給用戶。文件存儲(chǔ)器的數(shù)據(jù)傳輸率較高，大大緩解了I/O受限問題。

BSP并行存儲(chǔ)器由17個(gè)存儲(chǔ)體組成可以實(shí)現(xiàn)無沖突訪問13.3陣列處理機(jī)實(shí)例實(shí)現(xiàn)無沖突訪問的硬件支持：質(zhì)數(shù)個(gè)存儲(chǔ)器端口（存儲(chǔ)體數(shù)是質(zhì)數(shù)17）存儲(chǔ)端口和AE之間的交叉開關(guān)（對(duì)準(zhǔn)網(wǎng)絡(luò)）特殊的存儲(chǔ)器地址生成機(jī)構(gòu)

討論一臺(tái)含N個(gè)AE和M個(gè)存儲(chǔ)體的類BSP機(jī)的情況。地址映像規(guī)則先將二維數(shù)組按列優(yōu)先或者按行優(yōu)先的順序變換為一維數(shù)組，以形成一個(gè)一維線性地址空間，地址用A表示。然后將地址A變換成并行存儲(chǔ)器地址（i，j）。

其中：j是存儲(chǔ)體體號(hào)，

j＝A(modM)13.3陣列處理機(jī)實(shí)例i：在相應(yīng)存儲(chǔ)體內(nèi)的地址，i=。存儲(chǔ)體的個(gè)數(shù)M是一個(gè)質(zhì)數(shù)。一個(gè)比較簡單的例子設(shè)并行存儲(chǔ)器的體數(shù)M＝7（質(zhì)數(shù)），運(yùn)算單元數(shù)N＝6?？紤]下述4×5的數(shù)組：13.3陣列處理機(jī)實(shí)例

按上述地址映像規(guī)則，將這個(gè)4×5二維數(shù)組在M＝7、N＝6的并行存儲(chǔ)器中存儲(chǔ)的情況：以IlliacⅣ為例，討論陣列處理機(jī)的算法。

有限差分問題把一個(gè)有規(guī)則的網(wǎng)格覆蓋在整個(gè)場域上，用網(wǎng)格點(diǎn)上的變量值寫出差分方程組以代替場方程來進(jìn)行計(jì)算。描述平面場的拉普拉斯方程13.4陣列處理機(jī)的并行算法舉例13.4陣列處理機(jī)的并行算法舉例將二階偏導(dǎo)數(shù)表示為差分形式代入原方程，則可得有限差分計(jì)算公式（x，y）：平面網(wǎng)格點(diǎn)坐標(biāo)h：網(wǎng)格間距13.4陣列處理機(jī)的并行算法舉例差分法求解的精度與網(wǎng)格間距有直接的關(guān)系，網(wǎng)格越小，精度越高，但求解所花費(fèi)的時(shí)空開銷越大。IlliacⅣ在計(jì)算時(shí)，是把內(nèi)部網(wǎng)格點(diǎn)分配給各個(gè)處理單元的。因此，上述計(jì)算過程可以并行地完成，從而大幅度地提高處理速度。矩陣加

考慮兩個(gè)8×8的矩陣A和B的相加，所得結(jié)果矩陣C也是一個(gè)8×8的矩陣。

13.4陣列處理機(jī)的并行算法舉例把A、B、C中位于相應(yīng)位置的分量存放在同一PEM內(nèi)。假設(shè)：A的分量在全部64個(gè)PEM中存放的單元地址都是α；B的全部分量的地址都是α＋1；C的全部分量的地址都是α＋2。用3條IlliacⅣ的匯編指令就可以實(shí)現(xiàn)矩陣相加。

13.4陣列處理機(jī)的并行算法舉例LDAALPHA

；全部A的分量由PEMi送PEi的累加器RGAi

ADRNALPHA＋1

；全部B的分量與（RGAi）進(jìn)行浮點(diǎn)加，結(jié)果送RGAiSTAALPHA＋2

；全部（RGAi）由PEi送PEMi的α＋2單元矩陣相加存儲(chǔ)器分配舉例

13.4陣列處理機(jī)的并行算法舉例矩陣乘設(shè)A、B和C為3個(gè)8×8的二維矩陣。若給定A和B，則C＝A*B的64個(gè)分量可利用下列公式計(jì)算。

0≤i,j≤713.4陣列處理機(jī)的并行算法舉例在SISD計(jì)算機(jī)上求解，執(zhí)行下列FORTRAN程序：

DO10I＝0，7DO10J＝0，7C（I，J）＝0DO10K＝0，710C(I，J)＝C(I，J)＋A(I，K)*B(K，J)

三重循環(huán)，每重循環(huán)執(zhí)行8次，共需512次乘加的時(shí)間。在SIMD陣列處理機(jī)上求解這個(gè)問題

13.4陣列處理機(jī)的并行算法舉例執(zhí)行下列FORTRAN程序：

DO10I＝0，7C（I，J）＝0DO10K＝0，710C(I，J)＝C(I，J)＋A(I，K)*B(K，J)

速度提高到原來的8倍，即每個(gè)處理單元的計(jì)算時(shí)間縮短為64次乘加時(shí)間。

程序流程圖：13.4陣列處理機(jī)的并行算法舉例A、B、C向量在處理部件存儲(chǔ)器中的存放13.4陣列處理機(jī)的并行算法舉例累加和一個(gè)將N個(gè)數(shù)的順序相加轉(zhuǎn)變?yōu)椴⑿邢嗉拥膯栴}。只有處于