1、第第8章章 并行處理機(jī)并行處理機(jī)8.1 并行處理機(jī)模型并行處理機(jī)模型8.2 并行處理機(jī)結(jié)構(gòu)并行處理機(jī)結(jié)構(gòu)8.3 并行處理機(jī)實(shí)例并行處理機(jī)實(shí)例8.4 并行處理機(jī)算法舉例并行處理機(jī)算法舉例兩種并行性概念：兩種并行性概念：(1)同時(shí)性并行Simultaneity：兩個(gè)或兩個(gè)以上事件在同一時(shí)刻發(fā)生。(2)并發(fā)性并行Concurrency：兩個(gè)或兩個(gè)以上事件在同一時(shí)間間隔內(nèi)發(fā)生。三條技術(shù)途徑：三條技術(shù)途徑：(1)資源重復(fù)：重復(fù)設(shè)置多個(gè)部件來(lái)提高速度。(2)時(shí)間重疊：流水線(3)資源共享：分時(shí)系統(tǒng)，分布式系統(tǒng)8.1 并行處理機(jī)模型并行處理機(jī)模型1. 并行處理機(jī)的定義：并行處理機(jī)的定義： 多個(gè)處理部件多個(gè)處

2、理部件PU按照一定方式互連，在同按照一定方式互連，在同一個(gè)控制部件一個(gè)控制部件CU控制下，對(duì)各自的數(shù)據(jù)完成控制下，對(duì)各自的數(shù)據(jù)完成同一條指令規(guī)定的操作。從同一條指令規(guī)定的操作。從CU看，指令是串看，指令是串行執(zhí)行的，從行執(zhí)行的，從PU看，數(shù)據(jù)是并行處理的?？?，數(shù)據(jù)是并行處理的。 并行處理機(jī)也稱為陣列處理機(jī)，按照按照佛林分類法，它屬于SIMD處理機(jī)。2. 并行處理機(jī)的主要應(yīng)用領(lǐng)域：并行處理機(jī)的主要應(yīng)用領(lǐng)域：用于高速向量或矩陣運(yùn)算。3. 并行處理機(jī)的操作模型可用五元組來(lái)表示：并行處理機(jī)的操作模型可用五元組來(lái)表示： M(N，C，I，M，R), 其中：N為為PE個(gè)數(shù)個(gè)數(shù)。如IlliacIV有64個(gè)PE

3、。C為控制部件為控制部件CU執(zhí)行的指令集執(zhí)行的指令集，包括標(biāo)量指令和程序控制指令。I為所有為所有PE并行執(zhí)行的指令集并行執(zhí)行的指令集，包括ALU、數(shù)據(jù)傳送等操作M為屏蔽操作集為屏蔽操作集，將PE劃分為允許操作和禁止操作兩個(gè)子集R是數(shù)據(jù)尋徑集是數(shù)據(jù)尋徑集，互連網(wǎng)絡(luò)中PE間通信所需要的各種模式 PE0 PE1 PE2 PE2 控制器 P0 M0 P1 P1 P2 P2 PN-1 PN-1 互連網(wǎng)絡(luò) 4. H.J.Siegel提出的并行處理機(jī)模型提出的并行處理機(jī)模型 8.2 并行處理機(jī)結(jié)構(gòu)并行處理機(jī)結(jié)構(gòu)8.2.1 并行處理機(jī)的基本結(jié)構(gòu)并行處理機(jī)的基本結(jié)構(gòu)8.2.2 分布存儲(chǔ)器并行處理機(jī)分布存儲(chǔ)器并行

4、處理機(jī)8.2.3 共享存儲(chǔ)器并行處理機(jī)共享存儲(chǔ)器并行處理機(jī)8.2.4 并行處理機(jī)的特點(diǎn)并行處理機(jī)的特點(diǎn)8.2.1 并行處理機(jī)的基本結(jié)構(gòu)并行處理機(jī)的基本結(jié)構(gòu)一臺(tái)并行處理機(jī)由五個(gè)部分組成：一臺(tái)并行處理機(jī)由五個(gè)部分組成：多個(gè)處理單元多個(gè)處理單元PEPE，多個(gè)存儲(chǔ)器模塊多個(gè)存儲(chǔ)器模塊M M，一個(gè)控制器一個(gè)控制器CUCU，一個(gè)互連網(wǎng)絡(luò)一個(gè)互連網(wǎng)絡(luò)ICNICN，一臺(tái)輸入輸出處理機(jī)一臺(tái)輸入輸出處理機(jī)IOPIOP。并行處理機(jī)有兩種典型結(jié)構(gòu)：并行處理機(jī)有兩種典型結(jié)構(gòu)：分布存儲(chǔ)器并行處理機(jī)，分布存儲(chǔ)器并行處理機(jī)，共享存儲(chǔ)器并行處理機(jī)。共享存儲(chǔ)器并行處理機(jī)。 8.2.2 分布存儲(chǔ)器并行處理機(jī)分布存儲(chǔ)器并行處理機(jī)目前

5、的大部分并行處理機(jī)屬于基于分布式存儲(chǔ)器模型。分布式存儲(chǔ)器并行處理機(jī)比較容易構(gòu)成MPP(Massively Parallel Processor)，可以有幾十萬(wàn)個(gè)處理部件PE。CU是控制部件。對(duì)于標(biāo)量指令，在CU中直接執(zhí)行；對(duì)于向量指令，CU把它廣播到各個(gè)PE中去執(zhí)行。在CU中通常有一個(gè)較大容量的存儲(chǔ)器，用來(lái)存放程序和共享數(shù)據(jù)。IOP是輸入輸出處理機(jī)，或稱為主機(jī)。在IOP上安裝操作系統(tǒng)，它除了負(fù)擔(dān)輸入輸出工作外，還負(fù)責(zé)程序的編輯、編譯和調(diào)試等工作。 IOP可以是一臺(tái)通用計(jì)算機(jī)。分布式存儲(chǔ)器并行處理機(jī)必須依靠并行算法來(lái)提高PE的利用率。因此，應(yīng)用領(lǐng)域有限，可以認(rèn)為是一種專用計(jì)算機(jī)。數(shù)據(jù)在局部存儲(chǔ)器

6、中的分布是一個(gè)很關(guān)鍵的問題。標(biāo)量指令與向量指令可以并發(fā)執(zhí)行。 CUIOPLM0LM1LMn-1PE0PE1PEn-1互連網(wǎng)絡(luò) 分布式存儲(chǔ)器并行處理機(jī)的結(jié)構(gòu)框圖分布式存儲(chǔ)器并行處理機(jī)的結(jié)構(gòu)框圖8.2.3 共享存儲(chǔ)器并行處理機(jī)共享存儲(chǔ)器并行處理機(jī)共享多體并行存儲(chǔ)器SM通過(guò)互連網(wǎng)絡(luò)與各處理單元PE相連。存儲(chǔ)模塊的數(shù)目等于或略大于處理單元的數(shù)目。為了實(shí)現(xiàn)無(wú)沖突訪問，存儲(chǔ)模塊的個(gè)數(shù)為質(zhì)數(shù)。在存儲(chǔ)模塊之間合理分配數(shù)據(jù)，通過(guò)靈活、高速的互連網(wǎng)絡(luò)，使存儲(chǔ)器與處理單元之間的數(shù)據(jù)傳送在大多數(shù)向量運(yùn)算中都能以存儲(chǔ)器的最高頻率進(jìn)行，而最少受存儲(chǔ)器沖突的影響。共享存儲(chǔ)器模型的處理單元數(shù)目一般不多，幾個(gè)至幾十個(gè)。Burr

7、oughs Scientific Processor(BSP)采用了這種結(jié)構(gòu)。16個(gè)PE通過(guò)一個(gè)1617的對(duì)準(zhǔn)互連網(wǎng)絡(luò)訪問17個(gè)共享存儲(chǔ)器模塊。存儲(chǔ)器模塊數(shù)與PE數(shù)互質(zhì)可以實(shí)現(xiàn)無(wú)沖突并行訪問存儲(chǔ)器。對(duì)互連網(wǎng)絡(luò)的要求很高。C UIO PP E0P E1P EnS M0S M1S Mk互 連 網(wǎng) 絡(luò) 共享存儲(chǔ)器并行處理機(jī)的結(jié)構(gòu)框圖共享存儲(chǔ)器并行處理機(jī)的結(jié)構(gòu)框圖8.2.4 并行處理機(jī)的特點(diǎn)并行處理機(jī)的特點(diǎn) 并行處理機(jī)的主要特點(diǎn)如下：并行處理機(jī)的主要特點(diǎn)如下：1. 速度快，而且潛力大速度快，而且潛力大2. 模塊性好，生產(chǎn)和維護(hù)方便模塊性好，生產(chǎn)和維護(hù)方便3. 可靠性高，容易實(shí)現(xiàn)容錯(cuò)和重構(gòu)可靠性高，容易

8、實(shí)現(xiàn)容錯(cuò)和重構(gòu)4. 效率低效率低與流水線處理機(jī)、向量處理機(jī)等比較。依靠的是資源重復(fù)，而不是時(shí)間重疊，它的每個(gè)處理單元要擔(dān)負(fù)多種處理功能，其效率要低一些。5. 潛力大潛力大 主要依靠增加PE個(gè)數(shù)，與流水線處理機(jī)主要依靠縮短時(shí)鐘周期相比，其提高速度的潛力要大得多。6. 依賴于互連網(wǎng)絡(luò)和并行算法依賴于互連網(wǎng)絡(luò)和并行算法 互連網(wǎng)絡(luò)決定了PE之間的連接模式，也決定了并行處理機(jī)能夠適應(yīng)的算法。7. 需要有一臺(tái)高性能的標(biāo)量處理機(jī)需要有一臺(tái)高性能的標(biāo)量處理機(jī) 如果一臺(tái)機(jī)器的向量處理速度極高，但標(biāo)量處理速度只是每秒一百萬(wàn)次，那么對(duì)于標(biāo)量運(yùn)算占10的題目來(lái)說(shuō)，總的有效速度就不過(guò)是每秒一千萬(wàn)次。8.3 并行處理機(jī)實(shí)

9、例并行處理機(jī)實(shí)例IlliacIV 是最先采用SIMD結(jié)構(gòu)的并行處理機(jī)。隨后一個(gè)方向是用位片PE制造的并行處理機(jī)，如Goodyear MPP、AMT/DAP610和TMC/CM-2CM-5是以SIMD模式運(yùn)行的同步MIMD計(jì)算機(jī)另一方向是字寬運(yùn)算PE的中粒度SIMD計(jì)算機(jī)并行處理機(jī)的兩個(gè)發(fā)展方向：保留陣列結(jié)構(gòu)，但每個(gè)處理單元的規(guī)模減小保留陣列結(jié)構(gòu)，但每個(gè)處理單元的規(guī)模減小，如一個(gè)bit。去掉陣列結(jié)構(gòu)和分布存儲(chǔ)器去掉陣列結(jié)構(gòu)和分布存儲(chǔ)器。Burroughs公司的BSP是代表。8.3.1 IlliavIV 并行處理機(jī)并行處理機(jī)1963年，美國(guó)西屋電器公司提出“Slotnick，The SOLOMON

10、 Computer，Simultaneous Operation linked Ordinal Modular Network”。1966年美國(guó)國(guó)防遠(yuǎn)景研究規(guī)劃局ARPR與伊利諾依大學(xué)簽定合同。原計(jì)劃：256個(gè)PE，運(yùn)算速度為1GFLOPS。Burroughs公司和伊利諾依大學(xué)于1972年共同設(shè)計(jì)和生產(chǎn)，1975年實(shí)際投入運(yùn)行。用了4倍的經(jīng)費(fèi)，只達(dá)到1/20的速度。只實(shí)現(xiàn)了8864個(gè)PE，只達(dá)到50MFLOPS。IlliacIV的影響非常大。它是并行處理機(jī)的典型代表，也是分布存儲(chǔ)器并行處理機(jī)的典型代表。PEM63PEM0PEM1CUCDCBIOMB6700CPUB6700內(nèi)存B6700多路開關(guān)

11、B6700外圍設(shè)備IOS激光存儲(chǔ)器6464 X 8CU總 線控 制 線模 式 位 線APPA網(wǎng) 接 口1282561024I/O 總 線CDBPE63PE01024 實(shí) 時(shí) 裝 置48484848256PE0PE1PE63.DFSIlliacIV由三大部分組成由三大部分組成IlliacIV處理機(jī)陣列：包括88 PE、PEM和互連網(wǎng)絡(luò)。陣列控制器CU。輸入輸出處理機(jī)：一臺(tái)標(biāo)準(zhǔn)的Burroughs B6700計(jì)算機(jī)。1. 陣列控制器陣列控制器陣列控制器CU實(shí)際上是一臺(tái)小型計(jì)算機(jī)。對(duì)陣列處理單元實(shí)行控制和完成標(biāo)量操作。對(duì)陣列處理單元實(shí)行控制和完成標(biāo)量操作。標(biāo)量操作與各標(biāo)量操作與各PE的數(shù)組操作可以重

12、疊執(zhí)行。的數(shù)組操作可以重疊執(zhí)行?？刂破鞯墓δ苡幸韵挛鍌€(gè)方面：(1)對(duì)指令進(jìn)行譯碼，并執(zhí)行標(biāo)量指令；(2)向各PE發(fā)出執(zhí)行數(shù)組操作指令的控制信號(hào)；(3)產(chǎn)生并向所有處理單元廣播公共的地址；(4)產(chǎn)生并向所有處理單元廣播公共的數(shù)據(jù)；(5)接收和處理PE、I/O操作以及B6700產(chǎn)生的陷阱中斷信號(hào)。2. 輸入輸出系統(tǒng)輸入輸出系統(tǒng)IlliacIV的輸入輸出系統(tǒng)包括：磁盤文件系統(tǒng)DFS，I/O分系統(tǒng)，一臺(tái)B6700處理機(jī)組成。I/O分系統(tǒng)由三個(gè)部分組成：輸入輸出開關(guān)IOS，控制描述字控制器CDC，輸入輸出緩沖存儲(chǔ)器BIOM。3. IlliacIV處理陣列處理陣列IlliacIV處理陣列由64個(gè)PU組成。

13、每個(gè)PU由處理部件PE和它的局部存儲(chǔ)器PEM組成。每一個(gè)PUi只和它的東、西、南、北四個(gè)近鄰：PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64直接連接。南北方向同一列PU連成一個(gè)環(huán)，東西方向構(gòu)成一個(gè)閉合螺線。閉合螺線網(wǎng)絡(luò)直徑為閉合螺線網(wǎng)絡(luò)直徑為7步，步，環(huán)形網(wǎng)格的直徑為環(huán)形網(wǎng)格的直徑為8步。步。 PU56 PU57 PU63 PU63 2 3 4 5 6 PU8 PU8 10 11 12 13 14 PU16 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

14、38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 PU55 58 59 60 61 62 PU0 PU0 PU1 PU7 PU0 PU1 PU8 PU9 PU56 PU57 PU7 PU15 PU63 例如：從PU0到PU36，采用環(huán)行網(wǎng)格必須8步： PUPU0 0PUPU1 1PUPU2 2PUPU3 3PUPU4 4PUPU1212PUPU2020PUPU2828PUPU3636或 PUPU0 0PUPU8 8PUPU1616PUPU2424PUPU3232PUPU3333PUPU3434PUPU3535PUPU3636 或 如果采

15、用閉合螺旋線，只需要如果采用閉合螺旋線，只需要7 7步：步： PUPU0 0PUPU6363PUPU6262PUPU6161PUPU6060PUPU5252PUPU4444PUPU3636或PUPU0 0PUPU6363PUPU5555PUPU4747PUPU3939PUPU3838PUPU3737PUPU3636 或 對(duì)于nn個(gè)單元的陣列，網(wǎng)絡(luò)直徑為n-1n-1。二維閉合螺旋線網(wǎng)格網(wǎng)二維閉合螺旋線網(wǎng)格網(wǎng) 結(jié)點(diǎn)度為4，網(wǎng)絡(luò)直徑為n-1。8.3.2 BSP處理機(jī)處理機(jī)BSP（Buroughs Scientific Processor）計(jì)算機(jī)是由美國(guó)寶來(lái)公司和伊利諾依大學(xué)于1979年制造的。BSP

16、是共享存儲(chǔ)器并行處理機(jī)的典型代表。BSP由5個(gè)部分組成：控制處理機(jī)、并行處理機(jī)、文件存儲(chǔ)器、并行存儲(chǔ)器模塊、對(duì)準(zhǔn)網(wǎng)絡(luò)。1. 并行處理機(jī)并行處理機(jī)17個(gè)存儲(chǔ)模塊，每個(gè)模塊512K字，周期160ns5級(jí)流水線：級(jí)流水線：(1)從17個(gè)存儲(chǔ)模塊中讀出數(shù)據(jù)(2)通過(guò)輸出對(duì)準(zhǔn)網(wǎng)絡(luò)把數(shù)據(jù)送入16個(gè)并行處理部件(3)16個(gè)并行處理部件并行處理機(jī)數(shù)據(jù)(4)通過(guò)輸入對(duì)準(zhǔn)網(wǎng)絡(luò)把數(shù)據(jù)從并行處理部件送到并行存儲(chǔ)器(5)把接收到的數(shù)據(jù)寫入并行存儲(chǔ)器時(shí)鐘周期160ns，向量運(yùn)算速度向量運(yùn)算速度50MFLOPS。1 16 6算算術(shù)術(shù)單單元元( (A AE E5 5) )輸輸 出出對(duì)對(duì)準(zhǔn)準(zhǔn)輸輸 入入對(duì)對(duì)準(zhǔn)準(zhǔn)1 17 7并并行

17、行存存儲(chǔ)儲(chǔ)器器模模塊塊（5 5- -8 8兆兆字字）(PPS)并并行行處處理理機(jī)機(jī)控控制制控控制制維維護(hù)護(hù)單單元元標(biāo)標(biāo)量量處處理理機(jī)機(jī)控控制制存存儲(chǔ)儲(chǔ)器器( (2 25 56 6K K字字）系系統(tǒng)統(tǒng)管管理理機(jī)機(jī)B B 7 77 70 00 0/ /B B 7 78 80 00 0文文件件存存儲(chǔ)儲(chǔ) 器器 系系統(tǒng)統(tǒng)（F FM M）并并行行處處理理機(jī)機(jī)（5 50 0M MF FL LO OP PS S）BSP外圍設(shè)備與終端75兆字節(jié)/秒控制通信(PMs)2. 控制處理機(jī)控制處理機(jī)控制處理機(jī)主要用來(lái)控制并行處理機(jī)?？刂铺幚頇C(jī)主要用來(lái)控制并行處理機(jī)。提供與系統(tǒng)管理機(jī)相連的接口。執(zhí)行存放在控制存儲(chǔ)器中的操

18、作系統(tǒng)和用戶程執(zhí)行存放在控制存儲(chǔ)器中的操作系統(tǒng)和用戶程序的標(biāo)量部分。序的標(biāo)量部分。把全部的向量指令及成組的標(biāo)量指令送給并行處理機(jī)?？刂凭S護(hù)單元是系統(tǒng)管理機(jī)與控制處理機(jī)之間的接口，用來(lái)進(jìn)行初始化、監(jiān)控命令通信和維護(hù)。3. 文件存儲(chǔ)器文件存儲(chǔ)器計(jì)算任務(wù)文件從系統(tǒng)管理機(jī)加載到文件存儲(chǔ)器，由控制處理機(jī)執(zhí)行。文件存儲(chǔ)器是在BSP直接控制下的唯一外圍設(shè)備。程序執(zhí)行過(guò)程中所產(chǎn)生的暫存文件和輸出文件，在將它們送給系統(tǒng)管理機(jī)輸出給用戶之前是存在文件存儲(chǔ)器中的。文件存儲(chǔ)器的數(shù)據(jù)傳輸率較高，大大地緩解了I/O受限問題。4. 對(duì)準(zhǔn)網(wǎng)絡(luò)對(duì)準(zhǔn)網(wǎng)絡(luò)對(duì)準(zhǔn)網(wǎng)絡(luò)采用全交叉開關(guān)實(shí)現(xiàn)對(duì)準(zhǔn)網(wǎng)絡(luò)采用全交叉開關(guān)實(shí)現(xiàn)。數(shù)據(jù)從一個(gè)源廣播至幾個(gè)

19、目的地，幾個(gè)源尋找數(shù)據(jù)從一個(gè)源廣播至幾個(gè)目的地，幾個(gè)源尋找一個(gè)目的地時(shí)能分解沖突。一個(gè)目的地時(shí)能分解沖突。存儲(chǔ)器模塊和對(duì)準(zhǔn)網(wǎng)絡(luò)的組合實(shí)現(xiàn)了無(wú)沖突訪存儲(chǔ)器模塊和對(duì)準(zhǔn)網(wǎng)絡(luò)的組合實(shí)現(xiàn)了無(wú)沖突訪問并行存儲(chǔ)器問并行存儲(chǔ)器。對(duì)準(zhǔn)網(wǎng)絡(luò)還可以實(shí)現(xiàn)快速傅里葉變換、數(shù)據(jù)壓縮和擴(kuò)展操作。5. 無(wú)訪問沖突存儲(chǔ)系統(tǒng)無(wú)訪問沖突存儲(chǔ)系統(tǒng)只有數(shù)組存取和I/O訪問并行存儲(chǔ)器。等效存儲(chǔ)等效存儲(chǔ)周期為周期為10ns。兩次算術(shù)運(yùn)算中需要用到三個(gè)變量，產(chǎn)生一個(gè)結(jié)果，共訪問存儲(chǔ)器4次，并行存儲(chǔ)器和浮點(diǎn)運(yùn)算之間的頻帶保持完全平衡頻帶保持完全平衡。對(duì)于長(zhǎng)向量來(lái)，中間結(jié)果存在寄存器中，每次運(yùn)算只需要一個(gè)操作數(shù)。因此并行存儲(chǔ)器有足夠的頻寬留給輸

20、入和輸出信息用。實(shí)現(xiàn)一維向量和二維矩陣的行、列、對(duì)角線和實(shí)現(xiàn)一維向量和二維矩陣的行、列、對(duì)角線和反對(duì)角線的無(wú)沖突訪問。反對(duì)角線的無(wú)沖突訪問。8.4 并行處理機(jī)算法舉例并行處理機(jī)算法舉例8.4.1 有限差分問題有限差分問題8.4.2 矩陣乘矩陣乘8.4.3 求累加和求累加和并行處理機(jī)特別并行處理機(jī)特別依賴于并行算法。依賴于并行算法。并行算法的一個(gè)關(guān)鍵是并行算法的一個(gè)關(guān)鍵是提高向量化的程度。提高向量化的程度。在設(shè)計(jì)并行算法時(shí)，要特別注意：在設(shè)計(jì)并行算法時(shí)，要特別注意：數(shù)據(jù)在多個(gè)存儲(chǔ)模塊之間的分布。數(shù)據(jù)在多個(gè)存儲(chǔ)模塊之間的分布。要解決好訪問存儲(chǔ)器的沖突問題。要解決好訪問存儲(chǔ)器的沖突問題?；ミB網(wǎng)絡(luò)并不

21、能提供所有處理單元之間的互連網(wǎng)絡(luò)并不能提供所有處理單元之間的連接，因此，并行算法要連接，因此，并行算法要充分利用互連充分利用互連網(wǎng)絡(luò)的結(jié)構(gòu)網(wǎng)絡(luò)的結(jié)構(gòu)。8.4.1 有限差分問題有限差分問題有限差分方法是一種通用和有效方法：把連續(xù)方程變換成離散形式。二階偏導(dǎo)數(shù)表示為差分形式：22220UxUy22222222UxU xhU xU xhhUyU xhU xU xhh(,)( ,)(,)( ,)( ,)( ,) y y y y y y并代入原方程，則可得有限差分計(jì)算公式：其中：(x, y)為平面直角坐標(biāo)， h為網(wǎng)格間距。IlliacIV的陣列結(jié)構(gòu)特別適合計(jì)算這種在網(wǎng)格上定義的有限差分函數(shù)。把內(nèi)部網(wǎng)格點(diǎn)

22、分配給各個(gè)處理單元，計(jì)算過(guò)程可以并行完成。運(yùn)算速度的提高可以與處理機(jī)數(shù)目成正比。U xU x hU xhU x hU xh()()()()(), y, y, y, y, y48.4.2 矩陣乘矩陣乘矩陣乘是典型的并行程序，非常適合在SIMD并行處理機(jī)上運(yùn)行。例如：A、B、C均為88的二維矩陣，則CAB的計(jì)算公式為：在串行機(jī)上要用一個(gè)三重循環(huán)程序，乘法和加法分別為512次。ca bijikkjk, 0i, j707如果在并行處理機(jī)上求解，F(xiàn)ORTRAN語(yǔ)言程序如下： DO 10 I0，7 C(I, J)=0 DO 20 K=0, 720 C(I, J)=C (I, J )+A(I, K) * B

23、(K, J)10 CONTINUE可以在8個(gè)PE的并行處理機(jī)運(yùn)行，運(yùn)算速度可提高8倍。也可在64個(gè)PE的并行處理機(jī)上運(yùn)行數(shù)據(jù)如何分布到各個(gè)局部存儲(chǔ)器中？在并行處理機(jī)上，J循環(huán)只需一次。 PE0PE0：c c0000a a0000b b0000a a0101b b1010a a0202b b2020a a0707b b7070 PE1 PE1：c c0101a a0000b b0101a a0101b b1111a a0202b b2121a a0707b b7171 PE7 PE7：c c0707a a0000b b0707a a0101b b1717a a0202b b2727a a0707

24、b b7777 PE0PE0：c c1010a a1010b b0000a a1111b b1010a a1212b b2020a a1717b b7070 PE1PE1：c c1111a a1010b b0101a a1111b b1111a a1212b b2121a a1717b b7171 PE7 PE7：c c1717a a1010b b0707a a1111b b1717a a1212b b2727a a1717b b7777PE7PE7：c c7777a a7070b b0707a a7171b b1717a a7272b b2727a a7777b b7777局局部部存存儲(chǔ)儲(chǔ)器

25、器中中的的數(shù)數(shù)據(jù)據(jù)分分布布如如下下： PEM0 PEM1 PEM2 PEM3 PEM4 PEM5 PEM6 PEM7 b00 b10 b70 c00 c10 c70 a00 a10 a70 b01 b11 b71 c01 c11 c71 a01 a11 a71 b02 b12 b72 c02 c12 c72 a02 a12 a72 b03 b13 b73 c03 c13 c73 a03 a13 a73 b04 b14 b74 c04 c14 c74 a04 a14 a74 b05 b15 b75 c05 c15 c75 a05 a15 a75 b06 b16 b76 c06 c16 c76 a06 a16 a76 b07 b17 b77 c07 c17 c77 a07 a17 a77 開 始i = 0C i , j = 0 , k = 0 讀讀 L L O O A A D D A A i i , , k k 播播送送 B B C C A A S S T T A A i i , , k k 乘乘 M M U U L L Y Y B B k k , , j j 加加 A A D D