陣列處理機(jī)曹強(qiáng)計(jì)算機(jī)學(xué)院武漢光電國(guó)家實(shí)驗(yàn)室信息.ppt

第12章 陣列處理機(jī) 曹強(qiáng) 計(jì)算機(jī)學(xué)院 武漢光電國(guó)家實(shí)驗(yàn)室信息存儲(chǔ)部 張晨曦 劉依（版）,12.1 陣列處理機(jī)的操作模型和特點(diǎn) 12.2 陣列處理機(jī)的基本結(jié)構(gòu) 12.3 陣列處理機(jī)實(shí)例 12.4 陣列處理機(jī)的并行算法舉例,陣列處理機(jī) 核心：一個(gè)由多個(gè)處理單元構(gòu)成的陣列 采用資源重復(fù)的方法，設(shè)置較多的處理單元來(lái)提高并行性。 用單一的控制部件來(lái)控制多個(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í)行從控制部件廣播來(lái)的同一條指令，但它們所操作的對(duì)象卻是不同的數(shù)據(jù)。,12.1 陣列處理機(jī)的操作模型和特點(diǎn),12.1 陣列處理機(jī)的操作模型和特點(diǎn),陣列處理機(jī)的操作模型,12.1 陣列處理機(jī)的操作模型和特點(diǎn),陣列處理機(jī)的操作模型可用五元組表示 陣列處理機(jī)（N，C，I，M，R） 其中： N：機(jī)器的處理單元（PE）數(shù)。 例如：Illiac 計(jì)算機(jī)有64個(gè)PE MP-1計(jì)算機(jī)有16384個(gè)PE C：控制部件CU直接執(zhí)行的指令集，包括標(biāo)量指令和程序流控制指令。 I：由CU廣播至所有PE進(jìn)行并行執(zhí)行的指令集。 包括算術(shù)運(yùn)算、邏輯運(yùn)算、數(shù)據(jù)尋徑、屏蔽以及其他由每個(gè)PE對(duì)它的數(shù)據(jù)所執(zhí)行的局部操作。,12.1 陣列處理機(jī)的操作模型和特點(diǎn),M：屏蔽方案集 每種屏蔽將所有PE劃分成允許操作和禁止操作兩種工作模式。 R：數(shù)據(jù)尋徑功能集 說(shuō)明互連網(wǎng)絡(luò)中PE間通信所需要的各種設(shè)置模式。 例如：MasPar MP-1計(jì)算機(jī)的操作特性如下： （1）MP-1是一種SIMD機(jī)器，其PE數(shù)N102416384。 （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接收指令。,12.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í)交叉開(kāi)關(guān)尋徑 器，以實(shí)現(xiàn)CU-PE之間、X-Net的8個(gè)近鄰和全局尋徑器的通信。 陣列處理機(jī)的特點(diǎn) 以單指令流多數(shù)據(jù)流方式工作。 通過(guò)設(shè)置多個(gè)相同的處理單元來(lái)開(kāi)發(fā)并行性。 利用并行性中的同時(shí)性，而不是并發(fā)性。所有處理單元必須同時(shí)進(jìn)行相同的操作。 以某一類(lèi)算法為背景的專用計(jì)算機(jī)。,12.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之間通過(guò)數(shù)據(jù)尋徑網(wǎng)絡(luò)以一定方式互相連接。它們?cè)陉嚵锌刂撇考慕y(tǒng)一指揮下，實(shí)現(xiàn)并行操作。 指令的執(zhí)行順序基本上是串行進(jìn)行的。 程序和數(shù)據(jù)是通過(guò)主機(jī)裝入控制存儲(chǔ)器。,12.2 陣列處理機(jī)的基本結(jié)構(gòu),12.2.1 分布式存儲(chǔ)器的陣列機(jī),12.2 陣列處理機(jī)的基本結(jié)構(gòu),分布式存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu),12.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)。 可以讓所有PE在同一個(gè)周期執(zhí)行同一條指令,12.2 陣列處理機(jī)的基本結(jié)構(gòu),也可以通過(guò)采用屏蔽邏輯來(lái)控制某些PE在指定的指令周期是否參與執(zhí)行 各種陣列處理機(jī)的主要差別 在于數(shù)據(jù)尋徑網(wǎng)絡(luò)的不同。 Illiac ： 4-鄰連接網(wǎng)絡(luò)結(jié)構(gòu) （在過(guò)去是最常用的一種） CM-2：嵌在網(wǎng)格中的超立方體 MasPar MP-1：X-Net加多級(jí)交叉開(kāi)關(guān)尋徑器,12.2 陣列處理機(jī)的基本結(jié)構(gòu),共享存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu) 集中設(shè)置存儲(chǔ)器 共享的多體并行存儲(chǔ)器SM通過(guò)對(duì)準(zhǔn)網(wǎng)絡(luò)與各處理單元PE相連。 存儲(chǔ)模塊的數(shù)目等于或略大于處理單元的數(shù)目。 必須減少存儲(chǔ)器訪問(wèn)沖突 （將數(shù)據(jù)合理地分配到各存儲(chǔ)器模塊中 ） 在處理單元數(shù)目不太多的情況下是很理想的 所有陣列指令都必須使用長(zhǎng)度為n的向量操作數(shù) （n為PE的個(gè)數(shù)),12.2.2 共享存儲(chǔ)器的陣列機(jī),12.2 陣列處理機(jī)的基本結(jié)構(gòu),共享存儲(chǔ)器的陣列處理機(jī)結(jié)構(gòu),互連網(wǎng)絡(luò)是共享存儲(chǔ)器SM和處理單元PE之間的必由之路。,美國(guó)寶來(lái)公司和伊利諾大學(xué)合作研制 1972年 最早的陣列處理機(jī) 一個(gè)由3種類(lèi)型處理機(jī)聯(lián)合組成的多機(jī)系統(tǒng) 處理單元陣列：專門(mén)用于數(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)管理功能,12.3 陣列處理機(jī)實(shí)例,12.3.1 實(shí)例1：Illiac 陣列處理機(jī),12.3 陣列處理機(jī)實(shí)例,Illiac 系統(tǒng)總框圖,12.3 陣列處理機(jī)實(shí)例,Illiac 陣列 由64個(gè)處理單元（PE）、64個(gè)本地存儲(chǔ)器（PEM）和存儲(chǔ)器邏輯部件（MLU）組成； 把每個(gè)PE和PEM對(duì)看成是一個(gè)處理部件PU； 64個(gè)處理部件PU0PU63排列成一個(gè)88方陣 Illiac 的陣列結(jié)構(gòu)又稱為閉合螺線陣列； 既便于一維長(zhǎng)向量（多至64個(gè)元素）的處理，又便于二維數(shù)組運(yùn)算，以縮短處理單元之間的路徑距離。 步距不等于1或8的任意處理單元間通信可用軟件方法尋找最短路徑，其最短距離都不會(huì)超過(guò)7步。,Illiac 處理部件的連接,例如：從PU10到PU46 的距離以下列路徑為最短 PU10 PU9 PU8 PU0 PU63 PU62 PU54 PU46,12.3 陣列處理機(jī)實(shí)例,一般情況，nn個(gè)單元組成的陣列中，任意兩個(gè)處理單元之間的最短距離不會(huì)超過(guò)（n1）步。 每個(gè)處理單元有6個(gè)可編程序寄存器 64位字長(zhǎng)的累加器RGA 64位字長(zhǎng)的操作數(shù)寄存器RGB 64位字長(zhǎng)的數(shù)據(jù)路由寄存器RGR 64位字長(zhǎng)的通用寄存器RGS （可被程序用來(lái)暫存中間結(jié)果） 16位的變址寄存器 8位的模式寄存器 （存放PE屏蔽信息以及狀態(tài)位）,12.3 陣列處理機(jī)實(shí)例,運(yùn)算部件 加/乘算術(shù)單元 邏輯單元 移位單元 地址加法器等 操作數(shù)來(lái)源 PE本身的寄存器 PEM CU的公共數(shù)據(jù)總線 PE的4個(gè)近鄰,12.3 陣列處理機(jī)實(shí)例,并行的加法速度 每秒1010次8位定點(diǎn)加法或150106次64位浮點(diǎn)加法 每一個(gè)處理單元有一個(gè)自己的本地存儲(chǔ)器PEM PE和PEM之間經(jīng)過(guò)存儲(chǔ)器邏輯部件MLU相連 陣列控制器CU 一臺(tái)小型計(jì)算機(jī) 對(duì)陣列的處理單元進(jìn)行控制 利用本身的內(nèi)部資源執(zhí)行一整套指令，用以完成標(biāo)量操作。 功能,12.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根 ）,12.3 陣列處理機(jī)實(shí)例,輸入輸出系統(tǒng) 由磁盤(pán)文件系統(tǒng)DFS、I/O分系統(tǒng)和B6700管理計(jì)算機(jī)組成。 磁盤(pán)文件系統(tǒng)DFS 兩套大容量并行讀寫(xiě)磁盤(pán)系統(tǒng)及其相應(yīng)的控制器； 每套有13臺(tái)磁盤(pán)機(jī)，總?cè)萘繛?09位； 每臺(tái)磁盤(pán)機(jī)有128道，每道一個(gè)磁頭，并行讀寫(xiě)，數(shù)據(jù)寬度為256位，最大傳輸率為502106b/s；平均等待時(shí)間為19.6ms； 如果兩個(gè)通道同時(shí)發(fā)送或接收數(shù)據(jù)，則數(shù)據(jù)寬度為512位，最大傳輸率為109b/s。,12.3 陣列處理機(jī)實(shí)例,I/O系統(tǒng) 包括3部分： 輸入/輸出開(kāi)關(guān)IOS 作為一個(gè)開(kāi)關(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之間，是為了取得二者之間傳送帶寬上的匹配。,12.3 陣列處理機(jī)實(shí)例,B6700管理計(jì)算機(jī) 管理全部系統(tǒng)資源，完成用戶程序的編譯或匯編， 為Illiac 進(jìn)行作業(yè)調(diào)度、存儲(chǔ)分配、產(chǎn)生I/O控制描述字送至CDC、處理中斷、提供操作系統(tǒng)所具備的其他服務(wù)等。,12.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)的框圖,12.3 陣列處理機(jī)實(shí)例,BSP處理機(jī)由3部分構(gòu)成：控制處理機(jī)，并行處理機(jī)，文件存儲(chǔ)器。 BSP處理機(jī) 并行處理機(jī) 包含16個(gè)算術(shù)單元AE、由17個(gè)存儲(chǔ)體組成的一個(gè)無(wú)沖突訪問(wèn)的并行存儲(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ù)單元所需要的順序；,12.3 陣列處理機(jī)實(shí)例,BSP的5級(jí)數(shù)據(jù)流水線結(jié)構(gòu)示意圖,12.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ǔ)所需要的次序； 寫(xiě)入并行存儲(chǔ)器。 兩套對(duì)準(zhǔn)網(wǎng)絡(luò)的作用：在讀或?qū)懖⑿写鎯?chǔ)器時(shí)，使并行存儲(chǔ)器中為保證無(wú)沖突訪問(wèn)而錯(cuò)開(kāi)存放的操作數(shù)順序能夠與算術(shù)單元并行處理所要求的正常順序協(xié)調(diào)一致。 這種流水線對(duì)提高系統(tǒng)處理效率有很大作用 。 有效地實(shí)現(xiàn)了處理單元、存儲(chǔ)器和互連網(wǎng)絡(luò)在時(shí)間上重疊工作，在理想情況下能取得帶寬的完全匹配。,12.3 陣列處理機(jī)實(shí)例,可把大于16的任意長(zhǎng)度的向量按16個(gè)分量的標(biāo)準(zhǔn)長(zhǎng)度分為若干段，依次在時(shí)間上重疊起來(lái)進(jìn)行處理。 實(shí)現(xiàn)不同向量指令的重疊執(zhí)行。 數(shù)據(jù)保存在由17個(gè)存儲(chǔ)體組成的并行存儲(chǔ)器中，每個(gè)存儲(chǔ)體的容量可達(dá)512K字，存儲(chǔ)周期為160ns。 （一個(gè)無(wú)沖突訪問(wèn)存儲(chǔ)器 ） 控制處理機(jī) 控制并行處理機(jī)，提供與系統(tǒng)管理機(jī)相連的接口。 標(biāo)量處理單元：處理存儲(chǔ)在指令/控制存儲(chǔ)器中的全部操作系統(tǒng)和用戶程序的指令。,12.3 陣列處理機(jī)實(shí)例,全部的向量指令以及某些成組運(yùn)算的標(biāo)量指令被送給并行處理機(jī)控制器。在經(jīng)過(guò)合格性檢查之后，并行處理機(jī)控制器將指令轉(zhuǎn)換為微操作序列去控制16個(gè)AE操作。 指令/控制存儲(chǔ)器的容量為256K字，存儲(chǔ)周期為160ns，字長(zhǎng)為56位，其中8位是校驗(yàn)位，提供單錯(cuò)校正和雙錯(cuò)檢測(cè)的能力。 控制維護(hù)單元：系統(tǒng)管理機(jī)與控制處理機(jī)的接口，用來(lái)對(duì)控制處理機(jī)進(jìn)行初始化以及監(jiān)控命令的通信和維護(hù)。,12.3 陣列處理機(jī)實(shí)例,文件存儲(chǔ)器 BSP直接控制下的唯一外圍設(shè)備。 BSP程序執(zhí)行過(guò)程中所產(chǎn)生的暫存文件和輸出文件都是先存放在文件存儲(chǔ)器中，然后才被送給系統(tǒng)管理機(jī)，輸出給用戶。 文件存儲(chǔ)器的數(shù)據(jù)傳輸率較高，大大緩解了I/O受限問(wèn)題 。 BSP并行存儲(chǔ)器 由17個(gè)存儲(chǔ)體組成 可以實(shí)現(xiàn)無(wú)沖突訪問(wèn),12.3 陣列處理機(jī)實(shí)例,實(shí)現(xiàn)無(wú)沖突訪問(wèn)的硬件支持： 質(zhì)數(shù)個(gè)存儲(chǔ)器端口（存儲(chǔ)體數(shù)是質(zhì)數(shù)17） 存儲(chǔ)端口和AE之間的交叉開(kāi)關(guān)（對(duì)準(zhǔn)網(wǎng)絡(luò)） 特殊的存儲(chǔ)器地址生成機(jī)構(gòu) 討論一臺(tái)含N個(gè)AE和M個(gè)存儲(chǔ)體的類(lèi)BSP機(jī)的情況。 地址映像規(guī)則 先將二維數(shù)組按列優(yōu)先或者按行優(yōu)先的順序變換為一維數(shù)組，以形成一個(gè)一維線性地址空間，地址用A表示。 然后將地址A變換成并行存儲(chǔ)器地址（i，j）。 其中：j 是存儲(chǔ)體體號(hào)， jA (mod M),12.3 陣列處理機(jī)實(shí)例,i：在相應(yīng)存儲(chǔ)體內(nèi)的地址，i= 。 存儲(chǔ)體的個(gè)數(shù)M是一個(gè)質(zhì)數(shù)。 一個(gè)比較簡(jiǎn)單的例子 設(shè)并行存儲(chǔ)器的體數(shù)M7（質(zhì)數(shù)），運(yùn)算單元數(shù)N6。 考慮下述45的數(shù)組：,12.3 陣列處理機(jī)實(shí)例,按上述地址映像規(guī)則，將這個(gè)45二維數(shù)組在M7、N6的并 行存儲(chǔ)器中存儲(chǔ)的情況 ：,以Illiac 為例，討論陣列處理機(jī)的算法。 有限差分問(wèn)題 把一個(gè)有規(guī)則的網(wǎng)格覆蓋在整個(gè)場(chǎng)域上，用網(wǎng)格點(diǎn)上的變量值寫(xiě)出差分方程組以代替場(chǎng)方程來(lái)進(jìn)行計(jì)算。 描述平面場(chǎng)的拉普拉斯方程,12.4 陣列處理機(jī)的并行算法舉例,12.4 陣列處理機(jī)的并行算法舉例,將二階偏導(dǎo)數(shù)表示為差分形式 代入原方程，則可得有限差分計(jì)算公式,（x，y）：平面網(wǎng)格點(diǎn)坐標(biāo) h：網(wǎng)格間距,12.4 陣列處理機(jī)的并行算法舉例,差分法求解的精度與網(wǎng)格間距有直接的關(guān)系，網(wǎng)格越小，精度越高，但求解所花費(fèi)的時(shí)空開(kāi)銷(xiāo)越大。 Illiac 在計(jì)算時(shí)，是把內(nèi)部網(wǎng)格點(diǎn)分配給各個(gè)處理單元的。因此，上述計(jì)算過(guò)程可以并行地完成，從而大幅度地提高處理速度。 矩陣加 考慮兩個(gè)88的矩陣A和B的相加，所得結(jié)果矩陣C也 是一個(gè)88的矩陣。,12.4 陣列處理機(jī)的并行算法舉例,把A、B、C中位于相應(yīng)位置的分量存放在同一PEM內(nèi)。 假設(shè)： A的分量在全部64個(gè)PEM中存放的單元地址都是； B的全部分量的地址都是1； C的全部分量的地址都是2。 用3條Illiac 的匯編指令就可以實(shí)現(xiàn)矩陣相加。,12.4 陣列處理機(jī)的并行算法舉例,LDA ALPHA ；全部A的分量由PEMi送PEi的累加器RGAi ADRN ALPHA1 ；全部B的分量與（RGAi）進(jìn)行浮點(diǎn)加， 結(jié)果送RGAi STA ALPHA2 ；全部（RGAi）由PEi送PEMi的2單元,矩陣相加存儲(chǔ)器分配舉例,12.4 陣列處理機(jī)的并行算法舉例,矩陣乘 設(shè)A、B和C為3個(gè)88的二維矩陣。若給定A和B，則 CA*B的64個(gè)分量可利用下列公式計(jì)算。 0 i, j7,12.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) 三重循環(huán)，每重循環(huán)執(zhí)行8次，共需512次乘加的時(shí)間。 在SIMD陣列處理機(jī)上求解這個(gè)問(wèn)題,12.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，