計(jì)算機(jī)體系結(jié)構(gòu)-第7章

7.1互連網(wǎng)絡(luò)7.2

SIMD計(jì)算機(jī)

7.3MIMD計(jì)算機(jī)7.4本章小結(jié)第7章并行處理機(jī)技術(shù)?本章重點(diǎn)：常見(jiàn)的靜態(tài)互連網(wǎng)絡(luò)和動(dòng)態(tài)互連網(wǎng)絡(luò)的結(jié)構(gòu)和特點(diǎn);Omega網(wǎng)絡(luò)構(gòu)成和尋徑方式、SIMD處理機(jī)的基本結(jié)構(gòu)和特點(diǎn)、MIMD處理機(jī)的基本結(jié)構(gòu)和特點(diǎn)以及多處理機(jī)的Cache一致性問(wèn)題。?本章難點(diǎn)：

Omega網(wǎng)絡(luò)的尋徑、SIMD處理機(jī)和MIMD處理機(jī)的工作方式，以及多處理機(jī)的Cache一致性問(wèn)題的解決。7.1互連網(wǎng)絡(luò)7.1.1互連函數(shù)

互連網(wǎng)絡(luò):是一種由高速開(kāi)關(guān)按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用來(lái)實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或功能部件之間的相互連接。

在輸入結(jié)點(diǎn)與輸出結(jié)點(diǎn)之間建立對(duì)應(yīng)關(guān)系，來(lái)反映不同互連網(wǎng)絡(luò)的連接特性

常用的表示方法有兩種：第二種方法是互連函數(shù)表示法，又稱(chēng)排列函數(shù)。第一種是圖形表示法。1.方體置換其表達(dá)式為：例：節(jié)點(diǎn)數(shù)N=8時(shí)，n=3，則方體互連函數(shù)為：方體置換函數(shù)共有n=，其中N為節(jié)點(diǎn)數(shù)。

方體置換主要用于超立方體互連網(wǎng)絡(luò)中，其互連函數(shù)的圖形表示法如圖7-1所示。（a）C0方體交換函數(shù)（b）C1方體交換函數(shù)（c）C2方體交換函數(shù)圖7-1N=8的立方體交換函數(shù)2.PM2I函數(shù)表達(dá)式為：其中：N為節(jié)點(diǎn)數(shù)，n=，0≤x≤N-1，0≤i≤n-1。

PM2I互連函數(shù)有2n個(gè)互連函數(shù)例：結(jié)點(diǎn)數(shù)N=8的PM2I函數(shù)的圖形表示法如圖7-2所示（a）i=0（b）i=+1（c）i+2圖7-2N=8的PM2I函數(shù)3.蝶式函數(shù)

表達(dá)式為：其中：N為節(jié)點(diǎn)數(shù)，n=例：結(jié)點(diǎn)數(shù)N=8的蝶式函數(shù)的圖形表示法如圖7-3所示。

圖7-3N=8的蝶式函數(shù)4.均勻洗牌函數(shù)

表達(dá)式為：其中：N為節(jié)點(diǎn)數(shù)，n=例：結(jié)點(diǎn)數(shù)N=8的均勻洗牌函數(shù)的圖形表示法如圖7-4所示。

圖7-4N=8的均勻洗牌函數(shù)

均勻洗牌是一種非常有用的互連函數(shù)，以其為代表的鏈路與以交換置換為代表的開(kāi)關(guān)多級(jí)組合起來(lái)可構(gòu)成Omega（Ω）網(wǎng)絡(luò)?！纠?-1】IlliacIV陣列計(jì)算機(jī)采用PM±0和PM±2四個(gè)互連函數(shù)構(gòu)成的移數(shù)網(wǎng)絡(luò)進(jìn)行16個(gè)處理器的連接，如圖7-5所示。圖7-5用移數(shù)函數(shù)構(gòu)成IlliacIV陣列互連函數(shù)PM+0

：（012...15）PM-0

：（151413…0）PM±2

：（04）（115）（26）（37）（48）（59）（610）（711）（812）（913）（1014）（1115）（120）（131）（142）（153）解：該網(wǎng)絡(luò)可用4個(gè)PM2I函數(shù)表示如下：7.1.2互連網(wǎng)絡(luò)的性能和特征

⑴網(wǎng)絡(luò)規(guī)模指網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)，它體現(xiàn)網(wǎng)絡(luò)所能連接的部件數(shù)。1．互連網(wǎng)絡(luò)的性能參數(shù)⑵結(jié)點(diǎn)度進(jìn)入結(jié)點(diǎn)的邊數(shù)叫入度，從結(jié)點(diǎn)出來(lái)的邊數(shù)叫出度。⑶結(jié)點(diǎn)距離從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過(guò)的最少邊數(shù)。⑷網(wǎng)絡(luò)直徑指網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間距離的最大值，常用D表示。從數(shù)據(jù)傳送的角度來(lái)看，網(wǎng)絡(luò)直徑應(yīng)盡可能的小。⑸等分寬度指某一網(wǎng)絡(luò)被切成相等的兩半時(shí)，沿切口的最小邊數(shù)稱(chēng)為通道等分寬度，用b表示。用w表示通道寬度，則線(xiàn)等分寬度可表示為B=b×w。主要反映網(wǎng)絡(luò)的最大流量。⑹結(jié)點(diǎn)間線(xiàn)長(zhǎng)指兩結(jié)點(diǎn)之間的線(xiàn)路長(zhǎng)度，它影響信號(hào)傳輸中的延時(shí)、扭曲和需要的功率。⑺對(duì)稱(chēng)性指從任何結(jié)點(diǎn)看，網(wǎng)絡(luò)互連拓?fù)浣Y(jié)構(gòu)都是相同的網(wǎng)絡(luò)。2.互連網(wǎng)絡(luò)的特征參數(shù)⑴傳送方式傳送方式一般分為同步和異步兩種：同步方式：在數(shù)據(jù)傳送的過(guò)程中采用統(tǒng)一時(shí)鐘信號(hào)。

異步方式：不需要統(tǒng)一的時(shí)鐘信號(hào)在各處理機(jī)或單元之間進(jìn)行同步，各處理機(jī)或處理單元根據(jù)自身需要獨(dú)立工作。⑵控制策略控制策略：指控制互連開(kāi)關(guān)構(gòu)成信息通路的方式，可以分為集中控制和分散控制兩種。集中控制：由統(tǒng)一的控制器對(duì)各個(gè)互連開(kāi)關(guān)實(shí)施控制。分散控制：由各個(gè)開(kāi)關(guān)自身實(shí)施控制。⑶交換方法交換方式：指數(shù)據(jù)傳送時(shí)的管理方式，可以分為線(xiàn)路交換和分組交換兩種。線(xiàn)路交換：在整個(gè)傳送過(guò)程中，在源結(jié)點(diǎn)與目的結(jié)點(diǎn)之間建立固定的物理通路，適用于成批數(shù)據(jù)的傳送。分組交換：對(duì)傳送的數(shù)據(jù)進(jìn)行分組，分別送入互連網(wǎng)路，各分組可以通過(guò)不同的路由到達(dá)目標(biāo)結(jié)點(diǎn)，適用于短數(shù)據(jù)報(bào)文傳送。拓?fù)浣Y(jié)構(gòu)：指互連網(wǎng)絡(luò)中各結(jié)點(diǎn)之間的連接關(guān)系。⑷拓?fù)浣Y(jié)構(gòu)按照其控制方式可以分為：靜態(tài)拓?fù)浣Y(jié)構(gòu)和動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)。靜態(tài)拓?fù)浣Y(jié)構(gòu)：指在各結(jié)點(diǎn)間有專(zhuān)用的連接通路，在網(wǎng)絡(luò)運(yùn)行中其結(jié)構(gòu)不能改變。動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)：指在結(jié)構(gòu)中設(shè)有有源開(kāi)關(guān)，在網(wǎng)絡(luò)運(yùn)行中可以借助于控制信號(hào)對(duì)各結(jié)點(diǎn)的鏈路重新組合。7.1.3靜態(tài)互連網(wǎng)絡(luò)

靜態(tài)互連網(wǎng)絡(luò)：指處理單元間有著固定連接的網(wǎng)絡(luò)，在程序執(zhí)行期間，點(diǎn)到點(diǎn)的連接保持不變。

下面介紹幾種常見(jiàn)的靜態(tài)互連網(wǎng)絡(luò)1.線(xiàn)型網(wǎng)和星型網(wǎng)圖7-6線(xiàn)性陣列網(wǎng)圖7-7星型網(wǎng)內(nèi)部結(jié)點(diǎn)的連接度d=2，兩端結(jié)點(diǎn)的連接度d=1。網(wǎng)絡(luò)直徑D=N-1，等分寬度為1。星型網(wǎng)中心結(jié)點(diǎn)的連接度d=N-1，外層結(jié)點(diǎn)的連接度d=1，網(wǎng)絡(luò)直徑D=2。2.環(huán)網(wǎng)和帶弦環(huán)網(wǎng)圖7-8環(huán)網(wǎng)圖7-9帶弦環(huán)網(wǎng)環(huán)網(wǎng)的結(jié)點(diǎn)度均為d=2，單向環(huán)網(wǎng)的直徑D=N-1，雙向環(huán)網(wǎng)的直徑D=N/2。3.循環(huán)移數(shù)網(wǎng)和全連接網(wǎng)圖7-10循環(huán)移數(shù)網(wǎng)圖7-11全連接網(wǎng)網(wǎng)絡(luò)規(guī)模為N=2n，網(wǎng)絡(luò)結(jié)點(diǎn)度d=2n-1，網(wǎng)絡(luò)直徑D=n/2。該網(wǎng)絡(luò)的結(jié)點(diǎn)度為d=N-1，全連接網(wǎng)直徑為1

4.二叉樹(shù)型網(wǎng)和二叉胖樹(shù)型網(wǎng)（a）二叉樹(shù)型網(wǎng)（b）二叉胖樹(shù)型網(wǎng)5.網(wǎng)格型網(wǎng)絡(luò)（a）網(wǎng)格型網(wǎng)（b）Illiac網(wǎng)（c）環(huán)型網(wǎng)圖7-13網(wǎng)格型與環(huán)網(wǎng)型結(jié)構(gòu)6.超立方體網(wǎng)絡(luò)（a）3-立方體（b）2個(gè)3-立方體構(gòu)成的4-立方體

圖7-14超立方體結(jié)構(gòu)7.靜態(tài)互連網(wǎng)絡(luò)比較表7-1靜態(tài)互連網(wǎng)絡(luò)特性匯總r×r網(wǎng)絡(luò)，r=

與r=的帶弦環(huán)等效網(wǎng)絡(luò)類(lèi)型結(jié)點(diǎn)度（d）網(wǎng)絡(luò)直徑（D）鏈路數(shù)l等分寬度B對(duì)稱(chēng)性網(wǎng)絡(luò)規(guī)格說(shuō)明線(xiàn)形陣列2N-1N-11否N個(gè)結(jié)點(diǎn)環(huán)形2[N/2]N2是N個(gè)結(jié)點(diǎn)全連接N-11N（N-1）/2是N個(gè)結(jié)點(diǎn)二維網(wǎng)絡(luò)42（r-1）2N-2rR否Illiac網(wǎng)4r-12N2r否二維環(huán)網(wǎng)42[r/2]2N2r是r×r網(wǎng)絡(luò)，r=

超立方體NnnN/2N/2是N個(gè)結(jié)點(diǎn)，n=

7.1.4動(dòng)態(tài)互連網(wǎng)絡(luò)在動(dòng)態(tài)互連網(wǎng)絡(luò)中，各結(jié)點(diǎn)之間的連接是不固定的，而是在控制信號(hào)的作用下，通過(guò)網(wǎng)絡(luò)開(kāi)關(guān)的設(shè)置來(lái)建立結(jié)點(diǎn)之間的間接、可變的連接通路。1.總線(xiàn)互連網(wǎng)絡(luò)圖7-15一種總線(xiàn)連接的多處理機(jī)系統(tǒng)2.交叉開(kāi)關(guān)網(wǎng)絡(luò)圖7-16多處理機(jī)中處理機(jī)-存儲(chǔ)器之間的交叉開(kāi)關(guān)網(wǎng)絡(luò)Fujitsu公司在1992年制造的向量并行處理機(jī)VPP500采用224×224的大型交叉開(kāi)關(guān)網(wǎng)絡(luò)。如圖7-17所示。圖7-17VPP500向量并行處理機(jī)中處理機(jī)間的交叉開(kāi)關(guān)網(wǎng)絡(luò)3.多級(jí)互連網(wǎng)絡(luò)在多級(jí)互連網(wǎng)絡(luò)結(jié)構(gòu)中，由交換開(kāi)關(guān)、拓?fù)浣Y(jié)構(gòu)和控制方式三個(gè)參數(shù)描述。⑴交換開(kāi)關(guān)（a）直送（b）交叉（c）下播（d）上播圖7-182×2交換開(kāi)關(guān)的四種工作狀態(tài)⑵拓?fù)浣Y(jié)構(gòu)指多級(jí)互連網(wǎng)絡(luò)的各級(jí)開(kāi)關(guān)之間鏈路的互連模式。⑶控制方式控制方式：指對(duì)各級(jí)交換開(kāi)關(guān)的控制方式。級(jí)控：同一級(jí)的所有開(kāi)關(guān)用一個(gè)信號(hào)來(lái)控制，所有開(kāi)關(guān)都處于同一種工作狀態(tài)，n級(jí)開(kāi)關(guān)需要n個(gè)控制信號(hào)。單元控制：每一個(gè)開(kāi)關(guān)單獨(dú)有一個(gè)控制信號(hào)，同一級(jí)的開(kāi)關(guān)可以處于相同的工作狀態(tài)，也可以處于不同的工作狀態(tài)。N級(jí)網(wǎng)絡(luò)的輸入端和輸出端的總數(shù)N=2n，所以每一級(jí)有N/2個(gè)開(kāi)關(guān)，這種方式下共需要nN/2個(gè)控制信號(hào)。部分級(jí)控：對(duì)于同一級(jí)開(kāi)關(guān)分組，在不同級(jí)使用不同數(shù)量的控制信號(hào)。圖7-19所示是一種通用的多級(jí)互連網(wǎng)絡(luò)。接下來(lái)以O(shè)mega網(wǎng)絡(luò)為例，介紹多級(jí)互連網(wǎng)絡(luò)的構(gòu)成和尋徑算法。圖7-20N=8個(gè)結(jié)點(diǎn)的Omega網(wǎng)絡(luò)⑴Omega網(wǎng)絡(luò)的構(gòu)成⑵Omega網(wǎng)絡(luò)尋徑尋徑算法：通過(guò)檢查目的地址二進(jìn)制編碼來(lái)控制數(shù)據(jù)路徑的，目的地址編碼從高位開(kāi)始的第i位為0時(shí)，第i級(jí)的2×2開(kāi)關(guān)的輸入端與上輸出端連接，否則輸入端與下輸入端連接。1（0，7，6，4，2）（1，3）（5）

（a）Omega網(wǎng)絡(luò)無(wú)阻塞地實(shí)現(xiàn)置換1（0，7，6，4，2）（1，3）（5）

（b）Omega網(wǎng)絡(luò)實(shí)現(xiàn)置換2（0，6，4，7，3）（1，5）（2）

Omega網(wǎng)絡(luò)通過(guò)采用上播或下播的開(kāi)關(guān)設(shè)置，可以實(shí)現(xiàn)從一個(gè)源將數(shù)據(jù)廣播到多個(gè)目的地址。圖7-22所示中，將輸入端011的消息廣播到所有8個(gè)輸出端。圖7-222×2開(kāi)關(guān)的廣播連接7.2SIMD計(jì)算機(jī)按照Flynn分類(lèi)法，將單指令流多數(shù)據(jù)流結(jié)構(gòu)的計(jì)算機(jī)稱(chēng)為SIMD計(jì)算機(jī)。它主要通過(guò)硬件資源的重復(fù)設(shè)置來(lái)實(shí)現(xiàn)并行性，適用于大量高速的向量或矩陣運(yùn)算，所以又稱(chēng)為并行處理機(jī)和陣列處理機(jī)。7.2.1SIMD計(jì)算機(jī)模型與特點(diǎn)1.SIMD計(jì)算機(jī)模型圖7-23SIMD計(jì)算機(jī)的操作模型SIMD計(jì)算機(jī)的操作模型可用五元組表示：M=（N，C，I，M，R）其中，N：表示機(jī)器的處理單元數(shù)；C：表示控制部件CU直接執(zhí)行的指令集；I：表示由控制部件CU廣播到所有PE進(jìn)行并行執(zhí)行的指令集；M：表示屏蔽方案集，每種屏蔽將所有PE劃分為允許操作和禁止操作兩種子集；R：表示數(shù)據(jù)尋徑功能集，即互連網(wǎng)絡(luò)中PE間通信所需要的各種設(shè)置模式。2.SIMD計(jì)算機(jī)的特點(diǎn)⑴SIMD計(jì)算機(jī)的工作方式是單指令流多數(shù)據(jù)流。⑵SIMD計(jì)算機(jī)依靠的并行措施是資源重復(fù)，⑶SIMD計(jì)算機(jī)采用的互連網(wǎng)絡(luò)將處理單元進(jìn)行連接，⑷SIMD計(jì)算機(jī)以向量處理為主，在SIMD計(jì)算機(jī)處理短向量時(shí)，短向量對(duì)其速度的影響雖較小，但會(huì)降低處理效率。⑸SIMD計(jì)算機(jī)是一臺(tái)向量處理專(zhuān)用計(jì)算機(jī)。7.2.2SIMD計(jì)算機(jī)結(jié)構(gòu)根據(jù)存儲(chǔ)器的分布方式不同，陣列處理機(jī)有分布式存儲(chǔ)器和共享式存儲(chǔ)器兩種基本結(jié)構(gòu)，1.分布式存儲(chǔ)器陣列處理機(jī)的基本結(jié)構(gòu)圖7-24分布式存儲(chǔ)器陣列處理機(jī)的基本結(jié)構(gòu)2.共享存儲(chǔ)器陣列處理機(jī)的基本結(jié)構(gòu)圖7-25共享存儲(chǔ)器的SIMD計(jì)算機(jī)7.2.3SIMD計(jì)算機(jī)實(shí)例接下來(lái)分別介紹兩種典型的SIMD計(jì)算機(jī)：IlliacIV陣列處理機(jī)和BSP計(jì)算機(jī)。1.IlliacIV陣列處理機(jī)圖7-26IlliacIV陣列處理機(jī)總體框架⑴IlliacIV陣列IlliacIV陣列PU是由64個(gè)處理單元（PE）、64個(gè)局部存儲(chǔ)器（PEM）和存儲(chǔ)邏輯部件（MLU）組成。（a）處理單元之間的連接關(guān)系（b）IlliacIV處理部件的連接圖7-27IlliacIV陣列處理機(jī)的陣列連接※⑵陣列控制器陣列控制器CU實(shí)際上是一臺(tái)小型控制計(jì)算機(jī)。除對(duì)陣列處理單元實(shí)行控制以外，還能利用本身的內(nèi)部資源執(zhí)行一整套指令，用以完成標(biāo)量操作，在時(shí)間上與各PE的數(shù)組操作重疊起來(lái)。概括起來(lái)，控制器的功能有以下5個(gè)方面：對(duì)指令流進(jìn)行控制和譯碼，包括執(zhí)行一整套標(biāo)量操作指令；向各處理單元發(fā)出執(zhí)行數(shù)組操作指令所需的控制信號(hào)；產(chǎn)生和向所有處理單元廣播公共的地址部分；產(chǎn)生和向所有處理單元廣播公共的數(shù)據(jù)；接收和處理由各PE（計(jì)算出錯(cuò)時(shí)）、系統(tǒng)I/O操作以及B6700所產(chǎn)生的陷阱中斷信號(hào)。

IlliacIV陣列控制器CU與處理單元陣列之間的信息聯(lián)系如圖7-26所示，一共有以下4條信息通路：

CU總線(xiàn)（ControlUnitBus）處理單元存儲(chǔ)器PEM經(jīng)過(guò)CU總線(xiàn)把指令和數(shù)據(jù)送往陣列控制器，以8個(gè)64位字為一信息塊。公共數(shù)據(jù)總線(xiàn)CDB（CommonDataBus）用作向64個(gè)處理單元同時(shí)廣播公共數(shù)據(jù)的通路。模式位線(xiàn)（modebitline）模式寄存器狀態(tài)信息中包括該處理單元的“活動(dòng)”狀態(tài)位。指令控制線(xiàn)處理單元微操作控制信號(hào)和處理單元存儲(chǔ)器地址、讀/寫(xiě)控制信號(hào)。※⑶輸入輸出系統(tǒng)IlliacIV輸入/輸出系統(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)的控制器。I/O系統(tǒng)包括三部分，即輸入/輸出開(kāi)關(guān)IOS、控制描述字控制器CDC和輸入/輸出緩沖存儲(chǔ)器BIOM。B6700管理計(jì)算機(jī)的基本組成部分：?jiǎn)沃醒胩幚砥鳌?2K字內(nèi)存（可擴(kuò)充至512K字）和一大批外圍設(shè)備。※2.BSP計(jì)算機(jī)

BSP計(jì)算機(jī)是由美國(guó)寶來(lái)公司和伊利諾依大學(xué)于1979年制造的，它采用共享存儲(chǔ)器結(jié)構(gòu)，將資源重復(fù)和時(shí)間重復(fù)結(jié)合起來(lái)進(jìn)行并行性處理，依靠并行性來(lái)提高運(yùn)算速度。圖7-28BSP的功能結(jié)構(gòu)與流水線(xiàn)處理⑴并行處理機(jī)16個(gè)算術(shù)單元AE：以SIMD方式在單一微序列控制下同步工作的，即對(duì)不同的數(shù)據(jù)組進(jìn)行同一種指令操作。17個(gè)存儲(chǔ)器模塊的組織形成了一個(gè)無(wú)沖突訪(fǎng)問(wèn)存儲(chǔ)器，它容許對(duì)任意長(zhǎng)度以及跳距不是17倍數(shù)的向量實(shí)現(xiàn)無(wú)沖突存取。BSP可以對(duì)下列4類(lèi)操作進(jìn)行并行計(jì)算：16個(gè)算術(shù)單元實(shí)現(xiàn)并行運(yùn)算；存儲(chǔ)器的讀取和存儲(chǔ)以及存儲(chǔ)器和算術(shù)單元間的數(shù)據(jù)傳輸；并行處理機(jī)控制器中的變址值、向量長(zhǎng)度和循環(huán)控制計(jì)算；線(xiàn)性向量操作描述字在標(biāo)量處理機(jī)中的生成。⑵控制處理機(jī)除控制并行處理機(jī)以外，還提供與系統(tǒng)管理機(jī)相連的接口。⑶文件存儲(chǔ)器文件存儲(chǔ)器是一個(gè)半導(dǎo)體輔助存儲(chǔ)器。BSP的任務(wù)文件從系統(tǒng)管理機(jī)上加載到文件管理器上，然后對(duì)這些任務(wù)進(jìn)行排隊(duì)，由控制處理機(jī)加以執(zhí)行。⑷對(duì)準(zhǔn)網(wǎng)絡(luò)對(duì)準(zhǔn)網(wǎng)絡(luò)包含完全交叉開(kāi)關(guān)以及用來(lái)實(shí)現(xiàn)數(shù)據(jù)從一個(gè)源廣播至幾個(gè)目的地，以及當(dāng)幾個(gè)源尋找一個(gè)目的地時(shí)能分解沖突的硬件。⑸質(zhì)數(shù)存儲(chǔ)系統(tǒng)BSP并行存儲(chǔ)器由17個(gè)周期時(shí)間為160ns的存儲(chǔ)模塊組成。7.2.4SIMD處理機(jī)的算法舉例⑴矩陣加假定兩個(gè)8×8的矩陣A和B相加，所得到的結(jié)果矩陣C也是一個(gè)8×8的矩陣。需用下列3條匯編指令就可一次實(shí)現(xiàn)矩陣相加：LDAALPHA

；全部（a）由PEMi送PEi的累加器RGAi中ADRN

ALPHA＋1；全部（a+1）與（RGAi）進(jìn)行浮點(diǎn)加，結(jié)果送

RGAiSTAALPHA＋2；全部（RGA）由PEi送PEMi的a+2單元中。圖7-29矩陣相加存儲(chǔ)器分配⑵矩陣乘設(shè)A、B和C為3個(gè)8×8的二維矩陣。若給定A和B，則C＝A×B的64個(gè)分量可利用下列公式計(jì)算。，0≤i≤7，0≤j≤7。如果在SIMD計(jì)算機(jī)上求解這個(gè)問(wèn)題，可執(zhí)行下列FORTRAN程序：DO

10

I＝0，7C(I,J)=0DO

20

K=0,720

C(I,J)=C(I,J)+A(I,K)*B(K,J)10

CONTINUE圖7-30矩陣乘程序執(zhí)行流程圖圖7-31矩陣乘存儲(chǔ)器分配⑶累加和假設(shè)累加的數(shù)為A(I)，其中I的取值范圍為0≤I≤7，即共有8個(gè)數(shù)進(jìn)行順序累加。在SIMD計(jì)算機(jī)上可寫(xiě)成下列FORTRAN程序：C(-1)=0DO10I=0,710C(I)=C(I-1)+A(I)在SISD計(jì)算機(jī)上，它需要進(jìn)行8次加法循環(huán)的時(shí)間。如果在并行處理機(jī)上，采用成對(duì)遞歸相加的算法，則只需要=3次的加法時(shí)間。將原始數(shù)據(jù)A(I)存放在8個(gè)PEM的a單元中，求累加和：第1步將全部PEi置為活動(dòng)狀態(tài)第2步全部A(I)從PEMi的a單元讀到相應(yīng)PEi的累加寄存器RGAi中，0≤I≤7；第3步令K＝0；第4步全部PEi的(RGAi)轉(zhuǎn)送到傳送寄存器RGRi，0≤I≤7；第5步全部PEi的(RGAi）經(jīng)過(guò)互連網(wǎng)絡(luò)向右傳送2k步距，0≤I≤7；第6步令j=2k-1；第7步置PE0至PEj為不活動(dòng)狀態(tài)；第8步處于活動(dòng)狀態(tài)的PEi執(zhí)行(RGAi):＝(RGAi)＋(RGRi)操作；第9步

k:=k+1；第10步若k<3，則轉(zhuǎn)回第4步，否則繼續(xù)往下執(zhí)行；第11步將全部PEi置為活動(dòng)狀態(tài)，0≤I≤7；第12步全部PEi的(RGAi)存入相應(yīng)PEMi的a+1單元中。上面描述的計(jì)算過(guò)程如圖7-32所示。圖7-32陣列處理機(jī)上累加和的計(jì)算過(guò)程7.3MIMD計(jì)算機(jī)

MIMD計(jì)算機(jī)按照Flynn分類(lèi)法是指多指令流多數(shù)據(jù)流計(jì)算機(jī)，它由多臺(tái)獨(dú)立的計(jì)算機(jī)組成，每臺(tái)計(jì)算機(jī)能夠獨(dú)立執(zhí)行自己的程序。7.3.1MIMD計(jì)算機(jī)結(jié)構(gòu)MIMD計(jì)算機(jī)根據(jù)存儲(chǔ)器組織方式的不同，將MIMD計(jì)算機(jī)結(jié)構(gòu)分成兩類(lèi)：共享存儲(chǔ)器多處理機(jī)結(jié)構(gòu)和分布式存儲(chǔ)器多處理機(jī)結(jié)構(gòu)。（a）共享存儲(chǔ)器多處理機(jī)結(jié)構(gòu)（b）分布式存儲(chǔ)器多處理機(jī)結(jié)果7-33兩種處理機(jī)結(jié)構(gòu)MIMD計(jì)算機(jī)在結(jié)構(gòu)原理上有別于SIMD計(jì)算機(jī)的主要特點(diǎn)：⑴MIMD計(jì)算機(jī)有多個(gè)控制器，有多個(gè)指令部件，可以對(duì)各個(gè)PE實(shí)現(xiàn)單獨(dú)的控制，并使其相互協(xié)調(diào)，相互配合。⑵MIMD計(jì)算機(jī)的外圍設(shè)備能夠被多個(gè)PE分別調(diào)用，因而通過(guò)互連網(wǎng)絡(luò)轉(zhuǎn)接，外圍設(shè)備訪(fǎng)問(wèn)主存儲(chǔ)器進(jìn)行程序和數(shù)組的傳送時(shí)，不像SIMD計(jì)算機(jī)有規(guī)則。⑶SIMD計(jì)算機(jī)主要完成數(shù)組和向量的運(yùn)算，MIMD計(jì)算機(jī)的各個(gè)PE是隨機(jī)地訪(fǎng)問(wèn)主存儲(chǔ)器的，所以互連網(wǎng)絡(luò)的連接模式、頻帶和路徑選擇等問(wèn)題都要復(fù)雜得多。7.3.2MIMD計(jì)算機(jī)的特點(diǎn)1.結(jié)構(gòu)靈活性2.程序并行性3.并行任務(wù)派生4.進(jìn)程同步5.資源分配和進(jìn)程調(diào)度7.3.3多處理機(jī)的Cache一致性1.Cache不一致性問(wèn)題的產(chǎn)生⑴共享可寫(xiě)數(shù)據(jù)引起的不一致性圖7-34共享可寫(xiě)數(shù)據(jù)引起的Cache不一致性⑵進(jìn)程遷移引起的數(shù)據(jù)不一致性圖7-35進(jìn)程遷移引起的Cache不一致性⑶I/O傳輸是造成數(shù)據(jù)的不一致性圖7-36I/O傳輸是造成數(shù)據(jù)的不一致性為了解決Cache不一致性問(wèn)題，提出兩種解決Cache不一致性問(wèn)題的協(xié)議：監(jiān)聽(tīng)協(xié)議和基于目錄的協(xié)議。

2.監(jiān)聽(tīng)協(xié)議圖7-37監(jiān)聽(tīng)協(xié)議基本原理兩種方法來(lái)保持Cache一致性的方法：寫(xiě)無(wú)效（Write-Invalidate）策略和寫(xiě)更新策略（Write-Update）。寫(xiě)無(wú)效策略：在本地Cache的數(shù)據(jù)塊修改時(shí)，使遠(yuǎn)程數(shù)據(jù)塊都無(wú)效。即當(dāng)處理機(jī)P2的本地Cache中有主存的第n個(gè)單元的副本時(shí)，將其數(shù)據(jù)塊設(shè)置為無(wú)效。寫(xiě)更新策略：本地Cache的數(shù)據(jù)塊修改時(shí)，通過(guò)總線(xiàn)把新的數(shù)據(jù)塊廣播給含該數(shù)據(jù)塊的所有其他Cache。即當(dāng)處理機(jī)P2的本地Cache中有主存的第n個(gè)單元的副本時(shí)，將其數(shù)據(jù)塊更新。由于Write-Update策略在本地Cache修改時(shí)，需要通過(guò)總線(xiàn)把修改過(guò)的數(shù)據(jù)塊的內(nèi)容廣播給所有含該數(shù)據(jù)塊的其他Cache，增加了總線(xiàn)的負(fù)擔(dān)，所以在一般的應(yīng)用系統(tǒng)中，極少使用Write-Update策略。大部分系統(tǒng)使用Write-Invalidate策略。⑴用Write-Through策略的Cache狀態(tài)圖7-38采用寫(xiě)通過(guò)策略的Cache狀態(tài)圖⑵采用Write-Back策略的Cache狀態(tài)