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

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

SIMD計算機(jī)

7.3MIMD計算機(jī)7.4本章小結(jié)第7章并行處理機(jī)技術(shù)?本章重點(diǎn)：常見的靜態(tài)互連網(wǎng)絡(luò)和動態(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一致性問題。?本章難點(diǎn)：

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

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

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

常用的表示方法有兩種：第二種方法是互連函數(shù)表示法，又稱排列函數(shù)。第一種是圖形表示法。1.方體置換其表達(dá)式為：例：節(jié)點(diǎn)數(shù)N=8時，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個互連函數(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ù)，以其為代表的鏈路與以交換置換為代表的開關(guān)多級組合起來可構(gòu)成Omega（Ω）網(wǎng)絡(luò)。【例7-1】IlliacIV陣列計算機(jī)采用PM±0和PM±2四個互連函數(shù)構(gòu)成的移數(shù)網(wǎng)絡(luò)進(jìn)行16個處理器的連接，如圖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個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)出來的邊數(shù)叫出度。⑶結(jié)點(diǎn)距離從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)所經(jīng)過的最少邊數(shù)。⑷網(wǎng)絡(luò)直徑指網(wǎng)絡(luò)中任意兩個結(jié)點(diǎn)之間距離的最大值，常用D表示。從數(shù)據(jù)傳送的角度來看，網(wǎng)絡(luò)直徑應(yīng)盡可能的小。⑸等分寬度指某一網(wǎng)絡(luò)被切成相等的兩半時，沿切口的最小邊數(shù)稱為通道等分寬度，用b表示。用w表示通道寬度，則線等分寬度可表示為B=b×w。主要反映網(wǎng)絡(luò)的最大流量。⑹結(jié)點(diǎn)間線長指兩結(jié)點(diǎn)之間的線路長度，它影響信號傳輸中的延時、扭曲和需要的功率。⑺對稱性指從任何結(jié)點(diǎn)看，網(wǎng)絡(luò)互連拓?fù)浣Y(jié)構(gòu)都是相同的網(wǎng)絡(luò)。2.互連網(wǎng)絡(luò)的特征參數(shù)⑴傳送方式傳送方式一般分為同步和異步兩種：同步方式：在數(shù)據(jù)傳送的過程中采用統(tǒng)一時鐘信號。

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

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

下面介紹幾種常見的靜態(tài)互連網(wǎng)絡(luò)1.線型網(wǎng)和星型網(wǎng)圖7-6線性陣列網(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.二叉樹型網(wǎng)和二叉胖樹型網(wǎng)（a）二叉樹型網(wǎng)（b）二叉胖樹型網(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個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ò)類型結(jié)點(diǎn)度（d）網(wǎng)絡(luò)直徑（D）鏈路數(shù)l等分寬度B對稱性網(wǎng)絡(luò)規(guī)格說明線形陣列2N-1N-11否N個結(jié)點(diǎn)環(huán)形2[N/2]N2是N個結(jié)點(diǎn)全連接N-11N（N-1）/2是N個結(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個結(jié)點(diǎn)，n=

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

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

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

CU總線（ControlUnitBus）處理單元存儲器PEM經(jīng)過CU總線把指令和數(shù)據(jù)送往陣列控制器，以8個64位字為一信息塊。公共數(shù)據(jù)總線CDB（CommonDataBus）用作向64個處理單元同時廣播公共數(shù)據(jù)的通路。模式位線（modebitline）模式寄存器狀態(tài)信息中包括該處理單元的“活動”狀態(tài)位。指令控制線處理單元微操作控制信號和處理單元存儲器地址、讀/寫控制信號?！禽斎胼敵鱿到y(tǒng)IlliacIV輸入/輸出系統(tǒng)由磁盤文件系統(tǒng)DFS、I/O分系統(tǒng)和B6700管理計算機(jī)組成。磁盤文件系統(tǒng)DFS：兩套大容量并行讀寫磁盤系統(tǒng)及其相應(yīng)的控制器。I/O系統(tǒng)包括三部分，即輸入/輸出開關(guān)IOS、控制描述字控制器CDC和輸入/輸出緩沖存儲器BIOM。B6700管理計算機(jī)的基本組成部分：單中央處理器、32K字內(nèi)存（可擴(kuò)充至512K字）和一大批外圍設(shè)備?！?.BSP計算機(jī)

BSP計算機(jī)是由美國寶來公司和伊利諾依大學(xué)于1979年制造的，它采用共享存儲器結(jié)構(gòu)，將資源重復(fù)和時間重復(fù)結(jié)合起來進(jìn)行并行性處理，依靠并行性來提高運(yùn)算速度。圖7-28BSP的功能結(jié)構(gòu)與流水線處理⑴并行處理機(jī)16個算術(shù)單元AE：以SIMD方式在單一微序列控制下同步工作的，即對不同的數(shù)據(jù)組進(jìn)行同一種指令操作。17個存儲器模塊的組織形成了一個無沖突訪問存儲器，它容許對任意長度以及跳距不是17倍數(shù)的向量實(shí)現(xiàn)無沖突存取。BSP可以對下列4類操作進(jìn)行并行計算：16個算術(shù)單元實(shí)現(xiàn)并行運(yùn)算；存儲器的讀取和存儲以及存儲器和算術(shù)單元間的數(shù)據(jù)傳輸；并行處理機(jī)控制器中的變址值、向量長度和循環(huán)控制計算；線性向量操作描述字在標(biāo)量處理機(jī)中的生成。⑵控制處理機(jī)除控制并行處理機(jī)以外，還提供與系統(tǒng)管理機(jī)相連的接口。⑶文件存儲器文件存儲器是一個半導(dǎo)體輔助存儲器。BSP的任務(wù)文件從系統(tǒng)管理機(jī)上加載到文件管理器上，然后對這些任務(wù)進(jìn)行排隊(duì)，由控制處理機(jī)加以執(zhí)行。⑷對準(zhǔn)網(wǎng)絡(luò)對準(zhǔn)網(wǎng)絡(luò)包含完全交叉開關(guān)以及用來實(shí)現(xiàn)數(shù)據(jù)從一個源廣播至幾個目的地，以及當(dāng)幾個源尋找一個目的地時能分解沖突的硬件。⑸質(zhì)數(shù)存儲系統(tǒng)BSP并行存儲器由17個周期時間為160ns的存儲模塊組成。7.2.4SIMD處理機(jī)的算法舉例⑴矩陣加假定兩個8×8的矩陣A和B相加，所得到的結(jié)果矩陣C也是一個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矩陣相加存儲器分配⑵矩陣乘設(shè)A、B和C為3個8×8的二維矩陣。若給定A和B，則C＝A×B的64個分量可利用下列公式計算。，0≤i≤7，0≤j≤7。如果在SIMD計算機(jī)上求解這個問題，可執(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矩陣乘存儲器分配⑶累加和假設(shè)累加的數(shù)為A(I)，其中I的取值范圍為0≤I≤7，即共有8個數(shù)進(jìn)行順序累加。在SIMD計算機(jī)上可寫成下列FORTRAN程序：C(-1)=0DO10I=0,710C(I)=C(I-1)+A(I)在SISD計算機(jī)上，它需要進(jìn)行8次加法循環(huán)的時間。如果在并行處理機(jī)上，采用成對遞歸相加的算法，則只需要=3次的加法時間。將原始數(shù)據(jù)A(I)存放在8個PEM的a單元中，求累加和：第1步將全部PEi置為活動狀態(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)過互連網(wǎng)絡(luò)向右傳送2k步距，0≤I≤7；第6步令j=2k-1；第7步置PE0至PEj為不活動狀態(tài)；第8步處于活動狀態(tài)的PEi執(zhí)行(RGAi):＝(RGAi)＋(RGRi)操作；第9步

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

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

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