第13章 陣列處理機(jī)

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

2、條指令，但它們所操作的對(duì)象卻是不同的數(shù)據(jù)。13.1 陣列處理機(jī)的操作模型和特點(diǎn)5 5/50/5013.1 陣列處理機(jī)的操作模型和特點(diǎn) 控制部件（控制部件（CUCU） 處理處理 單元單元 1 1 PEPE1 1 互連網(wǎng)絡(luò)互連網(wǎng)絡(luò) 處理處理 單元單元 2 2 PEPE2 2 處理處理 單元單元 3 3 PEPE3 3 處理處理 單元單元 n n PEPEn n 陣列處理機(jī)的操作模型陣列處理機(jī)的操作模型 6 6/50/5013.1 陣列處理機(jī)的操作模型和特點(diǎn) 陣列處理機(jī)的操作模型可用五元組表示 陣列處理機(jī)（N，C，I，M，R）其中：N：機(jī)器的處理單元（PE）數(shù)。例如：例如：Illiac 計(jì)算機(jī)有計(jì)算

3、機(jī)有64個(gè)個(gè)PE MP-1計(jì)算機(jī)有計(jì)算機(jī)有16384個(gè)個(gè)PEC：控制部件CU直接執(zhí)行的指令集，包括標(biāo)量指令和程序流控制指令。I：由CU廣播至所有PE進(jìn)行并行執(zhí)行的指令集。q包括算術(shù)運(yùn)算、邏輯運(yùn)算、數(shù)據(jù)尋徑、屏蔽以及其他包括算術(shù)運(yùn)算、邏輯運(yùn)算、數(shù)據(jù)尋徑、屏蔽以及其他由每個(gè)由每個(gè)PEPE對(duì)它的數(shù)據(jù)所執(zhí)行的局部操作。對(duì)它的數(shù)據(jù)所執(zhí)行的局部操作。7 7/50/5013.1 陣列處理機(jī)的操作模型和特點(diǎn)M：屏蔽方案集q每種屏蔽將所有每種屏蔽將所有PE劃分成允許操作和禁止操作兩種劃分成允許操作和禁止操作兩種工作模式。工作模式。R：數(shù)據(jù)尋徑功能集q說(shuō)明互連網(wǎng)絡(luò)中說(shuō)明互連網(wǎng)絡(luò)中PE間通信所需要的各種設(shè)置模式。間

4、通信所需要的各種設(shè)置模式。例如例如：MasPar MP-1MasPar MP-1計(jì)算機(jī)的操作特性如下：計(jì)算機(jī)的操作特性如下： （1 1）MP-1MP-1是一種是一種SIMDSIMD機(jī)器，其機(jī)器，其PEPE數(shù)數(shù)N N102410241638416384。 （2 2）CUCU執(zhí)行標(biāo)量指令，將譯碼后的向量指令廣播到執(zhí)行標(biāo)量指令，將譯碼后的向量指令廣播到PEPE陣列，陣列，并控制并控制PEPE間通信。間通信。 （3 3）每個(gè)）每個(gè)PEPE都是都是RISCRISC處理機(jī)，能執(zhí)行不同數(shù)據(jù)的整數(shù)運(yùn)算和處理機(jī)，能執(zhí)行不同數(shù)據(jù)的整數(shù)運(yùn)算和標(biāo)準(zhǔn)浮點(diǎn)運(yùn)算。標(biāo)準(zhǔn)浮點(diǎn)運(yùn)算。PEPE從從CUCU接收指令接收指令。 8 8

5、/50/5013.1 陣列處理機(jī)的操作模型和特點(diǎn) （4）屏蔽方案設(shè)在每個(gè)）屏蔽方案設(shè)在每個(gè)PE中，并由中，并由CU連續(xù)監(jiān)控，它能在運(yùn)行連續(xù)監(jiān)控，它能在運(yùn)行時(shí)動(dòng)態(tài)地使每個(gè)時(shí)動(dòng)態(tài)地使每個(gè)PE處于工作或禁止?fàn)顟B(tài)。處于工作或禁止?fàn)顟B(tài)。 （5）MP-1有一個(gè)有一個(gè)X-Net網(wǎng)格網(wǎng)絡(luò)和一個(gè)全局多級(jí)交叉開關(guān)尋徑網(wǎng)格網(wǎng)絡(luò)和一個(gè)全局多級(jí)交叉開關(guān)尋徑器，以實(shí)現(xiàn)器，以實(shí)現(xiàn)CU-PE之間、之間、X-Net的的8個(gè)近鄰和全局尋徑器的通信。個(gè)近鄰和全局尋徑器的通信。 陣列處理機(jī)的特點(diǎn) 以單指令流多數(shù)據(jù)流方式工作。通過(guò)設(shè)置多個(gè)相同的處理單元來(lái)開發(fā)并行性。q利用并行性中的利用并行性中的同時(shí)性同時(shí)性，而不是并發(fā)性。所有處理單，

6、而不是并發(fā)性。所有處理單元必須同時(shí)進(jìn)行相同的操作。元必須同時(shí)進(jìn)行相同的操作。2.以某一類算法為背景的專用計(jì)算機(jī)。 9 9/50/5013.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)。1010/50/501. 分布式存儲(chǔ)器的陣列機(jī)結(jié)構(gòu)含有多個(gè)相同的處理單元PE，每個(gè)PE有各自的本地存儲(chǔ)器LM。PE之間通過(guò)數(shù)據(jù)尋徑網(wǎng)絡(luò)以一定方式互相連接。它們?cè)陉嚵锌刂撇考慕y(tǒng)一指揮下，實(shí)現(xiàn)并行操作。指令的執(zhí)行

7、順序基本上是串行進(jìn)行的。程序和數(shù)據(jù)是通過(guò)主機(jī)裝入控制存儲(chǔ)器。13.2 陣列處理機(jī)的基本結(jié)構(gòu)13.2.1 分布式存儲(chǔ)器的陣列機(jī)1111/50/5013.2 陣列處理機(jī)的基本結(jié)構(gòu) 標(biāo)量處理機(jī)標(biāo)量處理機(jī) 大容量存儲(chǔ)器大容量存儲(chǔ)器 標(biāo)量指令標(biāo)量指令 網(wǎng)絡(luò)控制網(wǎng)絡(luò)控制 陣列控制陣列控制 部件部件 向量指令向量指令 PE1 LM1 PE2 LM2 PE3 LM3 PEn LMn 廣播總線廣播總線 控制存儲(chǔ)器控制存儲(chǔ)器 （程序和數(shù)據(jù)）（程序和數(shù)據(jù)） 指令指令 主機(jī)主機(jī) I/OI/O（用戶）（用戶） 數(shù)據(jù)總線數(shù)據(jù)總線 數(shù)據(jù)尋徑網(wǎng)絡(luò)數(shù)據(jù)尋徑網(wǎng)絡(luò) PEPE：處理單元：處理單元 LMLM：本地存儲(chǔ)器：本地存儲(chǔ)器 分

8、布式存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu)分布式存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu) 1212/50/5013.2 陣列處理機(jī)的基本結(jié)構(gòu) 指令送到控制部件進(jìn)行譯碼。標(biāo)量指令：直接由標(biāo)量處理機(jī)執(zhí)行。向量指令：陣列控制部件通過(guò)廣播總線將它廣播到所有PE中去并行地執(zhí)行。 執(zhí)行程序所需的數(shù)據(jù)集經(jīng)劃分后通過(guò)數(shù)據(jù)總線分布存放到各PE的本地存儲(chǔ)器LM。 各PE之間通過(guò)數(shù)據(jù)尋徑網(wǎng)絡(luò)互連，實(shí)現(xiàn)PE間的通信，控制部件通過(guò)執(zhí)行程序來(lái)控制數(shù)據(jù)尋徑網(wǎng)絡(luò)。 PE的同步是在控制部件的控制下由硬件實(shí)現(xiàn)?？梢宰屗蠵E在同一個(gè)周期執(zhí)行同一條指令1313/50/5013.2 陣列處理機(jī)的基本結(jié)構(gòu)也可以通過(guò)采用屏蔽邏輯來(lái)控制某些PE在指定的指令周期是否參與執(zhí)行

9、 各種陣列處理機(jī)的主要差別 在于數(shù)據(jù)尋徑網(wǎng)絡(luò)的不同。Illiac ： 4-鄰連接網(wǎng)絡(luò)結(jié)構(gòu) （在過(guò)去是最常用的一種）（在過(guò)去是最常用的一種）CM-2：嵌在網(wǎng)格中的超立方體6.MasPar MP-1：X-Net加多級(jí)交叉開關(guān)尋徑器1414/50/5013.2 陣列處理機(jī)的基本結(jié)構(gòu)共享存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu) 集中設(shè)置存儲(chǔ)器 q共享的多體并行存儲(chǔ)器共享的多體并行存儲(chǔ)器SM通過(guò)對(duì)準(zhǔn)網(wǎng)絡(luò)與各處理單通過(guò)對(duì)準(zhǔn)網(wǎng)絡(luò)與各處理單元元PE相連。相連。q存儲(chǔ)模塊的數(shù)目等于或略大于處理單元的數(shù)目。存儲(chǔ)模塊的數(shù)目等于或略大于處理單元的數(shù)目。必須減少存儲(chǔ)器訪問(wèn)沖突 （將數(shù)據(jù)合理地分配到各存儲(chǔ)器模塊中（將數(shù)據(jù)合理地分配到各存儲(chǔ)

10、器模塊中 ）在處理單元數(shù)目不太多的情況下是很理想的所有陣列指令都必須使用長(zhǎng)度為n的向量操作數(shù) （n為PE的個(gè)數(shù))13.2.2 共享存儲(chǔ)器的陣列機(jī)1515/50/5013.2 陣列處理機(jī)的基本結(jié)構(gòu)共享存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu)共享存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu) 互連網(wǎng)絡(luò)是共享存儲(chǔ)器SM和處理單元PE之間的必由之路。 I/OI/O（用戶）（用戶） 大容量大容量 存儲(chǔ)器存儲(chǔ)器 主機(jī) 控制存儲(chǔ)器控制存儲(chǔ)器 陣列控制部件陣列控制部件 網(wǎng)絡(luò)控制網(wǎng)絡(luò)控制 標(biāo)量指令標(biāo)量指令 標(biāo)量處理機(jī)標(biāo)量處理機(jī) PE1 PE2 PEn 廣播總線（向量指令）廣播總線（向量指令） 對(duì)準(zhǔn)網(wǎng)絡(luò)對(duì)準(zhǔn)網(wǎng)絡(luò) SM1 SM2 SMm 數(shù)據(jù)總線數(shù)據(jù)總線

11、1616/50/50美國(guó)寶來(lái)公司和伊利諾大學(xué)合作研制 1972年最早的陣列處理機(jī)一個(gè)由3種類型處理機(jī)聯(lián)合組成的多機(jī)系統(tǒng)q處理單元陣列：專門用于數(shù)組運(yùn)算處理單元陣列：專門用于數(shù)組運(yùn)算q陣列控制器（陣列控制器（CU）：既是處理單元陣列的控制部分，）：既是處理單元陣列的控制部分，又可以看作是一臺(tái)相對(duì)獨(dú)立的小型標(biāo)量處理機(jī)。又可以看作是一臺(tái)相對(duì)獨(dú)立的小型標(biāo)量處理機(jī)。q一臺(tái)標(biāo)準(zhǔn)的一臺(tái)標(biāo)準(zhǔn)的B6700計(jì)算機(jī)：擔(dān)負(fù)計(jì)算機(jī)：擔(dān)負(fù)Illiac 輸入輸出系輸入輸出系統(tǒng)和操作系統(tǒng)管理功能統(tǒng)和操作系統(tǒng)管理功能 13.3 陣列處理機(jī)實(shí)例13.3.1 實(shí)例1：Illiac 陣列處理機(jī) 1717/50/5013.3 陣列處理

12、機(jī)實(shí)例 Illiac 系統(tǒng)總框圖系統(tǒng)總框圖 B6700 計(jì)算機(jī)計(jì)算機(jī) PE63 CU 模式位線模式位線 PE0 控制線控制線 CDBCDB 64 PE1 PE63 PEM0 PEM1 PEM63 CDC 48 BIOM I/OI/O緩沖存儲(chǔ)器緩沖存儲(chǔ)器 PE0 CUCU 總線總線 I/OI/O 總線總線 DFS 128 磁盤文件系統(tǒng)磁盤文件系統(tǒng) IOS 1024 I/O 開關(guān) 256 256 實(shí)實(shí)時(shí) 裝置裝置 1024 48 控制描述字控制描述字 控制器控制器 1818/50/5013.3 陣列處理機(jī)實(shí)例1. Illiac 陣列由64個(gè)處理單元（PE）、64個(gè)本地存儲(chǔ)器（PEM）和存儲(chǔ)器邏輯部

13、件（MLU）組成； 把每個(gè)PE和PEM對(duì)看成是一個(gè)處理部件PU；q64個(gè)處理部件個(gè)處理部件PU0PU63排列成一個(gè)排列成一個(gè)88方陣方陣 Illiac 的陣列結(jié)構(gòu)又稱為閉合螺線陣列；既便于一維長(zhǎng)向量（多至64個(gè)元素）的處理，又便于二維數(shù)組運(yùn)算，以縮短處理單元之間的路徑距離。q步距不等于步距不等于1或或8的任意處理單元間通信可用軟件的任意處理單元間通信可用軟件方法尋找最短路徑，其最短距離都不會(huì)超過(guò)方法尋找最短路徑，其最短距離都不會(huì)超過(guò)7步。步。 Illiac 處理部件的連接處理部件的連接 例如：例如：從從PU10到到PU46 的距離以下列路徑為最短的距離以下列路徑為最短 PU10 PU9 PU8

14、 PU0 PU63 PU62 PU54 PU46 PU63 PU56 PU0 PU57 PU1 PU63 PU7 PU8 PU7 PU8 PU9 PU15 PU16 PU55 PU56 PU57 PU63 PU0 PU0 PU1 PU7 （a） i+1 i-1 i+8 i-8 i （b） 2020/50/5013.3 陣列處理機(jī)實(shí)例q一般情況，一般情況，nn個(gè)單元組成的陣列中，任意兩個(gè)處個(gè)單元組成的陣列中，任意兩個(gè)處理單元之間的理單元之間的最短距離最短距離不會(huì)超過(guò)不會(huì)超過(guò)（n1）步。步。 每個(gè)處理單元有6個(gè)可編程序寄存器q64位字長(zhǎng)的累加器位字長(zhǎng)的累加器RGAq64位字長(zhǎng)的操作數(shù)寄存器位字長(zhǎng)的

15、操作數(shù)寄存器RGBq64位字長(zhǎng)的數(shù)據(jù)路由寄存器位字長(zhǎng)的數(shù)據(jù)路由寄存器RGRq64位字長(zhǎng)的通用寄存器位字長(zhǎng)的通用寄存器RGS （可被程序用來(lái)暫存中間結(jié)果）（可被程序用來(lái)暫存中間結(jié)果）q16位的變址寄存器位的變址寄存器q8位的模式寄存器位的模式寄存器 （存放（存放PE屏蔽信息以及狀態(tài)位）屏蔽信息以及狀態(tài)位）2121/50/5013.3 陣列處理機(jī)實(shí)例運(yùn)算部件q加加/乘算術(shù)單元乘算術(shù)單元q邏輯單元邏輯單元q移位單元移位單元q地址加法器等地址加法器等操作數(shù)來(lái)源qPE本身的寄存器本身的寄存器qPEMqCU的公共數(shù)據(jù)總線的公共數(shù)據(jù)總線qPE的的4個(gè)近鄰個(gè)近鄰2222/50/5013.3 陣列處理機(jī)實(shí)例并行

16、的加法速度每秒每秒1010次次8位定點(diǎn)加法或位定點(diǎn)加法或150106次次64位浮點(diǎn)加法位浮點(diǎn)加法 每一個(gè)處理單元有一個(gè)自己的本地存儲(chǔ)器PEM PE和PEM之間經(jīng)過(guò)存儲(chǔ)器邏輯部件MLU相連 陣列控制器CU 一臺(tái)小型計(jì)算機(jī) q對(duì)陣列的處理單元進(jìn)行控制對(duì)陣列的處理單元進(jìn)行控制q利用本身的內(nèi)部資源執(zhí)行一整套指令，用以完成標(biāo)量利用本身的內(nèi)部資源執(zhí)行一整套指令，用以完成標(biāo)量操作。操作。2.功能 2323/50/5013.3 陣列處理機(jī)實(shí)例q對(duì)指令流進(jìn)行控制和譯碼，包括執(zhí)行一整套標(biāo)量指令；對(duì)指令流進(jìn)行控制和譯碼，包括執(zhí)行一整套標(biāo)量指令；q向各處理單元發(fā)出執(zhí)行數(shù)組操作指令所需的控制信號(hào)；向各處理單元發(fā)出執(zhí)行數(shù)

17、組操作指令所需的控制信號(hào)；q產(chǎn)生并向所有處理單元廣播公共的地址部分；產(chǎn)生并向所有處理單元廣播公共的地址部分；q產(chǎn)生并向所有處理單元廣播公共的數(shù)據(jù)；產(chǎn)生并向所有處理單元廣播公共的數(shù)據(jù)；q接收和處理由各接收和處理由各PE計(jì)算出錯(cuò)、系統(tǒng)計(jì)算出錯(cuò)、系統(tǒng)I/O操作以及操作以及B6700所產(chǎn)生的陷阱中斷信號(hào)。所產(chǎn)生的陷阱中斷信號(hào)。陣列控制器CU與處理單元之間有4條信息通路 qCU總線總線 q公共數(shù)據(jù)總線公共數(shù)據(jù)總線CDB q模式位線模式位線 q指令控制指令控制線線 （大約有（大約有200根根 ）2424/50/5013.3 陣列處理機(jī)實(shí)例 輸入輸出系統(tǒng) 由磁盤文件系統(tǒng)DFS、I/O分系統(tǒng)和B6700管理計(jì)

18、算機(jī)組成。磁盤文件系統(tǒng)DFSq兩套大容量并行讀寫磁盤系統(tǒng)及其相應(yīng)的控制器；兩套大容量并行讀寫磁盤系統(tǒng)及其相應(yīng)的控制器；q每套有每套有13臺(tái)磁盤機(jī)，總?cè)萘繛榕_(tái)磁盤機(jī)，總?cè)萘繛?09位；位；q每臺(tái)磁盤機(jī)有每臺(tái)磁盤機(jī)有128道，每道一個(gè)磁頭，并行讀寫，數(shù)道，每道一個(gè)磁頭，并行讀寫，數(shù)據(jù)寬度為據(jù)寬度為256位，最大傳輸率為位，最大傳輸率為502106b/s；平均等；平均等待時(shí)間為待時(shí)間為19.6ms；q如果兩個(gè)通道同時(shí)發(fā)送或接收數(shù)據(jù)，則數(shù)據(jù)寬度為如果兩個(gè)通道同時(shí)發(fā)送或接收數(shù)據(jù)，則數(shù)據(jù)寬度為512位，最大傳輸率為位，最大傳輸率為109b/s。 2525/50/5013.3 陣列處理機(jī)實(shí)例I/O系統(tǒng)包括3

19、部分： q輸入輸入/ /輸出開關(guān)輸出開關(guān)IOS IOS n作為一個(gè)開關(guān)，把作為一個(gè)開關(guān)，把DFSDFS或可能連上的實(shí)時(shí)裝置轉(zhuǎn)或可能連上的實(shí)時(shí)裝置轉(zhuǎn)接到陣列存儲(chǔ)器，進(jìn)行大批數(shù)據(jù)的接到陣列存儲(chǔ)器，進(jìn)行大批數(shù)據(jù)的I/OI/O傳送；傳送；n作為作為DFSDFS和和PEMPEM之間的緩沖，以平衡兩邊不同的之間的緩沖，以平衡兩邊不同的數(shù)據(jù)寬度。數(shù)據(jù)寬度。q控制描述字控制器控制描述字控制器CDC CDC n對(duì)陣列控制器對(duì)陣列控制器CU的的I/O請(qǐng)求進(jìn)行管理請(qǐng)求進(jìn)行管理 qBIOMn在在DFS和和B6700之間，是為了取得二者之間傳送之間，是為了取得二者之間傳送帶寬上的匹配。帶寬上的匹配。2626/50/50

20、13.3 陣列處理機(jī)實(shí)例B6700管理計(jì)算機(jī)q管理全部系統(tǒng)資源，完成用戶程序的編譯或匯編，管理全部系統(tǒng)資源，完成用戶程序的編譯或匯編，q為為Illiac 進(jìn)行作業(yè)調(diào)度、存儲(chǔ)分配、產(chǎn)生進(jìn)行作業(yè)調(diào)度、存儲(chǔ)分配、產(chǎn)生I/O控制描控制描述字送至述字送至CDC、處理中斷、提供操作系統(tǒng)所具備的、處理中斷、提供操作系統(tǒng)所具備的其他服務(wù)等。其他服務(wù)等。13.3.2 實(shí)例2：BSP計(jì)算機(jī)美國(guó)寶來(lái)公司和伊利諾依大學(xué) 1979年共享存儲(chǔ)器結(jié)構(gòu)的SIMD計(jì)算機(jī)的典型代表最高處理性能：每秒5千萬(wàn)次浮點(diǎn)運(yùn)算 依靠并行性來(lái)提高性能 BSP計(jì)算機(jī)系統(tǒng)的框圖計(jì)算機(jī)系統(tǒng)的框圖 文件存儲(chǔ)器系統(tǒng)文件存儲(chǔ)器系統(tǒng) 系統(tǒng)管理機(jī)系統(tǒng)管理機(jī)

21、B7700/B7800 操作系統(tǒng)和操作系統(tǒng)和 維護(hù)信息維護(hù)信息 控制控制 維護(hù)單元維護(hù)單元 并行處理機(jī)并行處理機(jī) 控制器控制器 標(biāo)量標(biāo)量 處理單元處理單元 指令指令/ /控制存儲(chǔ)器控制存儲(chǔ)器 256K 字 控制處理機(jī)控制處理機(jī) 文件存儲(chǔ)器文件存儲(chǔ)器 CCDCCD 464M 字 文件存儲(chǔ)器控制器文件存儲(chǔ)器控制器 程序和數(shù)據(jù)程序和數(shù)據(jù) 250K 字/s 12.5M 字/s 并行處理機(jī)并行處理機(jī) 并行存儲(chǔ)器并行存儲(chǔ)器 0.58M 字 100M 字/s 入口和出口入口和出口 對(duì)準(zhǔn)網(wǎng)絡(luò)對(duì)準(zhǔn)網(wǎng)絡(luò) 100M 字/s 1616 個(gè)算術(shù)單元個(gè)算術(shù)單元 2828/50/5013.3 陣列處理機(jī)實(shí)例BSP處理機(jī)由3

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

23、網(wǎng)絡(luò)對(duì)準(zhǔn)網(wǎng)絡(luò) 17 個(gè)存儲(chǔ)體個(gè)存儲(chǔ)體 16 個(gè)處理單元個(gè)處理單元 對(duì)準(zhǔn)網(wǎng)絡(luò)對(duì)準(zhǔn)網(wǎng)絡(luò) NW1 NW2 指令譯碼指令譯碼 控制部件控制部件 存儲(chǔ)器存儲(chǔ)器 處理器處理器 BSP的的5級(jí)數(shù)據(jù)流水線結(jié)構(gòu)示意圖級(jí)數(shù)據(jù)流水線結(jié)構(gòu)示意圖 3030/50/5013.3 陣列處理機(jī)實(shí)例n將排列好的將排列好的16個(gè)操作數(shù)送到個(gè)操作數(shù)送到16個(gè)算術(shù)單元進(jìn)行處理；個(gè)算術(shù)單元進(jìn)行處理；n所得的所得的16個(gè)結(jié)果經(jīng)對(duì)準(zhǔn)網(wǎng)絡(luò)個(gè)結(jié)果經(jīng)對(duì)準(zhǔn)網(wǎng)絡(luò)NW2重新排列成在重新排列成在17個(gè)存?zhèn)€存儲(chǔ)體中存儲(chǔ)所需要的次序；儲(chǔ)體中存儲(chǔ)所需要的次序；n 寫入并行存儲(chǔ)器。寫入并行存儲(chǔ)器。q兩套對(duì)準(zhǔn)網(wǎng)絡(luò)的兩套對(duì)準(zhǔn)網(wǎng)絡(luò)的作用作用：在讀或?qū)懖⑿写鎯?chǔ)器時(shí)，使

24、并行存：在讀或?qū)懖⑿写鎯?chǔ)器時(shí)，使并行存儲(chǔ)器中為保證無(wú)沖突訪問(wèn)而錯(cuò)開存放的操作數(shù)順序能夠與儲(chǔ)器中為保證無(wú)沖突訪問(wèn)而錯(cuò)開存放的操作數(shù)順序能夠與算術(shù)單元并行處理所要求的正常順序協(xié)調(diào)一致。算術(shù)單元并行處理所要求的正常順序協(xié)調(diào)一致。q這種流水線對(duì)提高系統(tǒng)處理效率有很大作用這種流水線對(duì)提高系統(tǒng)處理效率有很大作用 。n有效地實(shí)現(xiàn)了處理單元、存儲(chǔ)器和互連網(wǎng)絡(luò)在時(shí)間上有效地實(shí)現(xiàn)了處理單元、存儲(chǔ)器和互連網(wǎng)絡(luò)在時(shí)間上重疊工作，在理想情況下能取得帶寬的完全匹配。重疊工作，在理想情況下能取得帶寬的完全匹配。 3131/50/5013.3 陣列處理機(jī)實(shí)例n可把大于可把大于16的任意長(zhǎng)度的向量按的任意長(zhǎng)度的向量按16個(gè)分量

25、的標(biāo)個(gè)分量的標(biāo)準(zhǔn)長(zhǎng)度分為若干段，依次在時(shí)間上重疊起來(lái)進(jìn)準(zhǔn)長(zhǎng)度分為若干段，依次在時(shí)間上重疊起來(lái)進(jìn)行處理。行處理。n實(shí)現(xiàn)不同向量指令的重疊執(zhí)行。實(shí)現(xiàn)不同向量指令的重疊執(zhí)行。q數(shù)據(jù)保存在由數(shù)據(jù)保存在由17個(gè)存儲(chǔ)體組成的并行存儲(chǔ)器中，每個(gè)個(gè)存儲(chǔ)體組成的并行存儲(chǔ)器中，每個(gè)存儲(chǔ)體的容量可達(dá)存儲(chǔ)體的容量可達(dá)512K字，存儲(chǔ)周期為字，存儲(chǔ)周期為160ns。 （一個(gè)無(wú)沖突訪問(wèn)存儲(chǔ)器（一個(gè)無(wú)沖突訪問(wèn)存儲(chǔ)器 ）控制處理機(jī) 控制并行處理機(jī)，提供與系統(tǒng)管理機(jī)相連的接口。q標(biāo)量處理單元：處理存儲(chǔ)在指令標(biāo)量處理單元：處理存儲(chǔ)在指令/控制存儲(chǔ)器中的全控制存儲(chǔ)器中的全部操作系統(tǒng)和用戶程序的指令。部操作系統(tǒng)和用戶程序的指令。 3

26、232/50/5013.3 陣列處理機(jī)實(shí)例q全部的向量指令以及某些成組運(yùn)算的標(biāo)量指令被送給全部的向量指令以及某些成組運(yùn)算的標(biāo)量指令被送給并行處理機(jī)控制器。在經(jīng)過(guò)合格性檢查之后，并行處并行處理機(jī)控制器。在經(jīng)過(guò)合格性檢查之后，并行處理機(jī)控制器將指令轉(zhuǎn)換為微操作序列去控制理機(jī)控制器將指令轉(zhuǎn)換為微操作序列去控制16個(gè)個(gè)AE操作。操作。q指令指令/控制存儲(chǔ)器的容量為控制存儲(chǔ)器的容量為256K字，存儲(chǔ)周期為字，存儲(chǔ)周期為160ns，字長(zhǎng)為字長(zhǎng)為56位，其中位，其中8位是校驗(yàn)位，提供單錯(cuò)校正和雙位是校驗(yàn)位，提供單錯(cuò)校正和雙錯(cuò)檢測(cè)的能力。錯(cuò)檢測(cè)的能力。q控制維護(hù)單元：系統(tǒng)管理機(jī)與控制處理機(jī)的接口，用控制維護(hù)單

27、元：系統(tǒng)管理機(jī)與控制處理機(jī)的接口，用來(lái)對(duì)控制處理機(jī)進(jìn)行初始化以及監(jiān)控命令的通信和維來(lái)對(duì)控制處理機(jī)進(jìn)行初始化以及監(jiān)控命令的通信和維護(hù)。護(hù)。 3333/50/5013.3 陣列處理機(jī)實(shí)例文件存儲(chǔ)器qBSP直接控制下的唯一外圍設(shè)備。直接控制下的唯一外圍設(shè)備。 qBSP程序執(zhí)行過(guò)程中所產(chǎn)生的暫存文件和輸出文件都程序執(zhí)行過(guò)程中所產(chǎn)生的暫存文件和輸出文件都是先存放在文件存儲(chǔ)器中，然后才被送給系統(tǒng)管理機(jī)，是先存放在文件存儲(chǔ)器中，然后才被送給系統(tǒng)管理機(jī)，輸出給用戶。輸出給用戶。q文件存儲(chǔ)器的數(shù)據(jù)傳輸率較高，大大緩解了文件存儲(chǔ)器的數(shù)據(jù)傳輸率較高，大大緩解了I/O受限受限問(wèn)題問(wèn)題 。 BSP并行存儲(chǔ)器 由17個(gè)存

28、儲(chǔ)體組成可以實(shí)現(xiàn)無(wú)沖突訪問(wèn)3434/50/5013.3 陣列處理機(jī)實(shí)例實(shí)現(xiàn)無(wú)沖突訪問(wèn)的硬件支持：q質(zhì)數(shù)個(gè)存儲(chǔ)器端口（存儲(chǔ)體數(shù)是質(zhì)數(shù)質(zhì)數(shù)個(gè)存儲(chǔ)器端口（存儲(chǔ)體數(shù)是質(zhì)數(shù)17）q存儲(chǔ)端口和存儲(chǔ)端口和AE之間的交叉開關(guān)（對(duì)準(zhǔn)網(wǎng)絡(luò)）之間的交叉開關(guān)（對(duì)準(zhǔn)網(wǎng)絡(luò)）q特殊的存儲(chǔ)器地址生成機(jī)構(gòu)特殊的存儲(chǔ)器地址生成機(jī)構(gòu) 討論一臺(tái)含N個(gè)AE和M個(gè)存儲(chǔ)體的類BSP機(jī)的情況。地址映像規(guī)則q先將二維數(shù)組按列優(yōu)先或者按行優(yōu)先的順序變換為一先將二維數(shù)組按列優(yōu)先或者按行優(yōu)先的順序變換為一維數(shù)組，以形成一個(gè)一維線性地址空間，地址用維數(shù)組，以形成一個(gè)一維線性地址空間，地址用A表表示。示。 q然后將地址然后將地址A變換成并行存儲(chǔ)器地址變

29、換成并行存儲(chǔ)器地址（i，j）。 其中：其中：j 是存儲(chǔ)體體號(hào)，是存儲(chǔ)體體號(hào)， jA (mod M) 3535/50/5013.3 陣列處理機(jī)實(shí)例qi：在相應(yīng)存儲(chǔ)體內(nèi)的地址，：在相應(yīng)存儲(chǔ)體內(nèi)的地址，i= 。q存儲(chǔ)體的個(gè)數(shù)存儲(chǔ)體的個(gè)數(shù)M是一個(gè)質(zhì)數(shù)。是一個(gè)質(zhì)數(shù)。 一個(gè)比較簡(jiǎn)單的例子 設(shè)并行存儲(chǔ)器的體數(shù)設(shè)并行存儲(chǔ)器的體數(shù)M7（質(zhì)數(shù)），運(yùn)算單元數(shù)（質(zhì)數(shù)），運(yùn)算單元數(shù)N6。 考慮下述考慮下述45的數(shù)組：的數(shù)組： a00 a01 a02 a03 a04 a10 a11 a12 a13 a14 a20 a21 a22 a23 a24 a30 a31 a32 a33 a34 NA3636/50/5013.3 陣

30、列處理機(jī)實(shí)例 按上述地址映像規(guī)則，將這個(gè)按上述地址映像規(guī)則，將這個(gè)45二維數(shù)組在二維數(shù)組在M7、N6的并的并行存儲(chǔ)器中存儲(chǔ)的情況行存儲(chǔ)器中存儲(chǔ)的情況 ： 體內(nèi)地址體內(nèi)地址 i i 存儲(chǔ)體號(hào)存儲(chǔ)體號(hào) j j 0 0 a00 數(shù)組元素?cái)?shù)組元素 線性地址線性地址 A 體號(hào)體號(hào) j 體內(nèi)地址體內(nèi)地址 i a10 a20 a30 a01 a11 a21 a31 a02 a12 a22 a32 a03 a13 a23 a33 a04 a14 a24 a34 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 0 1 2 3 4 5

31、 6 0 1 2 3 4 5 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 0 a00 1 a10 2 a20 3 a30 4 a01 5 a11 7 a31 8 a02 9 a12 10 a22 11 a32 6 a21 12 a03 13 a13 19 a34 20 18 a24 14 a23 15 a33 16 a04 17 a14 21 22 23 28 29 25 26 24 27 1 2 3 4 5 6 1 2 3 4 3737/50/50以Illiac 為例，討論陣列處理機(jī)的算法。 1. 有限差分問(wèn)題 把一個(gè)有規(guī)則的網(wǎng)格覆蓋在整個(gè)場(chǎng)域上，用網(wǎng)格點(diǎn)

32、上的變量值寫出差分方程組以代替場(chǎng)方程來(lái)進(jìn)行計(jì)算。 描述平面場(chǎng)的拉普拉斯方程13.4 陣列處理機(jī)的并行算法舉例02222yUxu3838/50/5013.4 陣列處理機(jī)的并行算法舉例將二階偏導(dǎo)數(shù)表示為差分形式代入原方程，則可得有限差分計(jì)算公式 222),(),(2),(hyhxUyxUyhxUxU222),(),(2),(hhyxUyxUhyxUyU4),(),(),(),(),(hyxUyhxUhyxUyhxUyxU（x，y）：平面網(wǎng)格點(diǎn)坐標(biāo)：平面網(wǎng)格點(diǎn)坐標(biāo) h：網(wǎng)格間距：網(wǎng)格間距 3939/50/5013.4 陣列處理機(jī)的并行算法舉例差分法求解的精度與網(wǎng)格間距有直接的關(guān)系，網(wǎng)格越小，精度越高

33、，但求解所花費(fèi)的時(shí)空開銷越大。Illiac 在計(jì)算時(shí)，是把內(nèi)部網(wǎng)格點(diǎn)分配給各個(gè)處理單元的。因此，上述計(jì)算過(guò)程可以并行地完成，從而大幅度地提高處理速度。 矩陣加 考慮兩個(gè)88的矩陣A和B的相加，所得結(jié)果矩陣C也是一個(gè)88的矩陣。 4040/50/5013.4 陣列處理機(jī)的并行算法舉例把A、B、C中位于相應(yīng)位置的分量存放在同一PEM內(nèi)。假設(shè)：qA的分量在全部的分量在全部64個(gè)個(gè)PEM中存放的單元地址都是中存放的單元地址都是；qB的全部分量的地址都是的全部分量的地址都是1；qC的全部分量的地址都是的全部分量的地址都是2。用3條Illiac 的匯編指令就可以實(shí)現(xiàn)矩陣相加。 4141/50/5013.4

34、 陣列處理機(jī)的并行算法舉例 LDA ALPHA LDA ALPHA ；全部；全部A A的分量由的分量由PEMPEMi i送送PEPEi i的累加器的累加器RGARGAi i ADRN ALPHAADRN ALPHA1 1 ；全部；全部B B的分量與（的分量與（RGARGAi i）進(jìn)行浮點(diǎn)加，）進(jìn)行浮點(diǎn)加， 結(jié)果送結(jié)果送RGARGAi i STA ALPHA STA ALPHA2 2 ；全部（；全部（RGARGAi i）由）由PEPEi i送送PEMPEMi i的的2 2單元單元 A（0，0） 1 1 2 2 PEMPEM0 0 B（0，0） C（0，0） A（0，1） PEMPEM1 1 B（

35、0，1） C（0，1） A（7，7） PEMPEM6363 B（7，7） C（7，7） 矩陣相加存儲(chǔ)器分配舉例矩陣相加存儲(chǔ)器分配舉例 4242/50/5013.4 陣列處理機(jī)的并行算法舉例 矩陣乘 設(shè)A、B和C為3個(gè)88的二維矩陣。若給定A和B，則CA*B的64個(gè)分量可利用下列公式計(jì)算。 0 i, j7 0 i, j7 70kkjikijbac4343/50/5013.4 陣列處理機(jī)的并行算法舉例在SISD計(jì)算機(jī)上求解，執(zhí)行下列FORTRAN程序： DO 10 I0，7 DO 10 J0，7 C（I，J）0 DO 10 K0，7 10 C(I，J) C(I，J)A(I，K)*B(K，J) 三重

36、循環(huán)，每重循環(huán)執(zhí)行三重循環(huán)，每重循環(huán)執(zhí)行8 8次，共需次，共需512512次乘加的時(shí)間。次乘加的時(shí)間。在SIMD陣列處理機(jī)上求解這個(gè)問(wèn)題 4444/50/5013.4 陣列處理機(jī)的并行算法舉例執(zhí)行下列FORTRAN程序： DO 10 I0，7 C（I，J）0 DO 10 K0，7 10 C(I，J) C(I，J)A(I，K)*B(K，J) 速度提高到原來(lái)的速度提高到原來(lái)的8倍，即每個(gè)處理單元的計(jì)算時(shí)間倍，即每個(gè)處理單元的計(jì)算時(shí)間縮短為縮短為64次乘加時(shí)間。次乘加時(shí)間。 程序流程圖 ： 向量乘向量乘：MUL B(K，J) RGA(J) RGA(J)B(K，J) 開始 I0 LIM8 C(I，J)0 0J7 K0 向量取向量取 LOAD A(I，J) RGA(J) A(I，J) 0J7 播送播送：BCAST A(I，K) RGA(J) RGA(K) 0J7 0J7 向量加向量加：ADD C(I，J) RGA(J) RGA(J)C(I，J) 0J7 向量存向量存：STO C(I，J) RGA(J)送 C(I，J) 0J