第13章 陣列處理機

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

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

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

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

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

6、而不是并發(fā)性。所有處理單元必須同時進行相同的操作。元必須同時進行相同的操作。2.以某一類算法為背景的專用計算機。 9 9/50/5013.1 陣列處理機的操作模型和特點陣列機的研究必須與并行算法的研究密切結(jié)合，以便能充分發(fā)揮它的處理能力。陣列機的控制器實質(zhì)上是一臺標量處理機，而為了完成I/O操作以及操作系統(tǒng)的管理，尚需一個前端機。 實際的陣列機系統(tǒng)是由3部分構(gòu)成的一個異構(gòu)型多處理機系統(tǒng)。1010/50/501. 分布式存儲器的陣列機結(jié)構(gòu)含有多個相同的處理單元PE，每個PE有各自的本地存儲器LM。PE之間通過數(shù)據(jù)尋徑網(wǎng)絡(luò)以一定方式互相連接。它們在陣列控制部件的統(tǒng)一指揮下，實現(xiàn)并行操作。指令的執(zhí)行

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

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

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

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

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

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

13、件（MLU）組成； 把每個PE和PEM對看成是一個處理部件PU；q64個處理部件個處理部件PU0PU63排列成一個排列成一個88方陣方陣 Illiac 的陣列結(jié)構(gòu)又稱為閉合螺線陣列；既便于一維長向量（多至64個元素）的處理，又便于二維數(shù)組運算，以縮短處理單元之間的路徑距離。q步距不等于步距不等于1或或8的任意處理單元間通信可用軟件的任意處理單元間通信可用軟件方法尋找最短路徑，其最短距離都不會超過方法尋找最短路徑，其最短距離都不會超過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 陣列處理機實例q一般情況，一般情況，nn個單元組成的陣列中，任意兩個處個單元組成的陣列中，任意兩個處理單元之間的理單元之間的最短距離最短距離不會超過不會超過（n1）步。步。 每個處理單元有6個可編程序寄存器q64位字長的累加器位字長的累加器RGAq64位字長的操作數(shù)寄存器位字長的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、換成并行存儲器地址（i，j）。 其中：其中：j 是存儲體體號，是存儲體體號， jA (mod M) 3535/50/5013.3 陣列處理機實例qi：在相應(yīng)存儲體內(nèi)的地址，：在相應(yīng)存儲體內(nèi)的地址，i= 。q存儲體的個數(shù)存儲體的個數(shù)M是一個質(zhì)數(shù)。是一個質(zhì)數(shù)。 一個比較簡單的例子 設(shè)并行存儲器的體數(shù)設(shè)并行存儲器的體數(shù)M7（質(zhì)數(shù)），運算單元數(shù)（質(zhì)數(shù)），運算單元數(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、列處理機實例 按上述地址映像規(guī)則，將這個按上述地址映像規(guī)則，將這個45二維數(shù)組在二維數(shù)組在M7、N6的并的并行存儲器中存儲的情況行存儲器中存儲的情況 ： 體內(nèi)地址體內(nèi)地址 i i 存儲體號存儲體號 j j 0 0 a00 數(shù)組元素數(shù)組元素 線性地址線性地址 A 體號體號 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 為例，討論陣列處理機的算法。 1. 有限差分問題 把一個有規(guī)則的網(wǎng)格覆蓋在整個場域上，用網(wǎng)格點

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

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

34、 陣列處理機的并行算法舉例 LDA ALPHA LDA ALPHA ；全部；全部A A的分量由的分量由PEMPEMi i送送PEPEi i的累加器的累加器RGARGAi i ADRN ALPHAADRN ALPHA1 1 ；全部；全部B B的分量與（的分量與（RGARGAi i）進行浮點加，）進行浮點加， 結(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） 矩陣相加存儲器分配舉例矩陣相加存儲器分配舉例 4242/50/5013.4 陣列處理機的并行算法舉例 矩陣乘 設(shè)A、B和C為3個88的二維矩陣。若給定A和B，則CA*B的64個分量可利用下列公式計算。 0 i, j7 0 i, j7 70kkjikijbac4343/50/5013.4 陣列處理機的并行算法舉例在SISD計算機上求解，執(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次乘加的時間。次乘加的時間。在SIMD陣列處理機上求解這個問題 4444/50/5013.4 陣列處理機的并行算法舉例執(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) 速度提高到原來的速度提高到原來的8倍，即每個處理單元的計算時間倍，即每個處理單元的計算時間縮短為縮短為64次乘加時間。次乘加時間。 程序流程圖 ： 向量乘向量乘：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