計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第6章(rev 1)

6.1互連網(wǎng)絡(luò)6.2

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

6.3MIMD計(jì)算機(jī)6.4本章小結(jié)第6章陣列機(jī)?本章重點(diǎ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一致性問題。6.1SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò)6.1.1互連函數(shù)

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

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

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

方體置換主要用于超立方體互連網(wǎng)絡(luò)中，其互連函數(shù)的圖形表示法如圖6-1所示。（a）C0方體交換函數(shù)（b）C1方體交換函數(shù)（c）C2方體交換函數(shù)圖6-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ù)的圖形表示法如圖6-2所示（a）i=0（b）i=+1（c）i+2圖6-2N=8的PM2I函數(shù)3.均勻洗牌函數(shù)

表達(dá)式為：Shuffle(Xn-1Xn-2…X1X0)=Xn-2…X1X0Xn-1

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

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

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

：（012...15）PM-0

：（151413…0）PM±2

：（04）（15）（26）（36）（48）（59）（610）（611）（812）（913）（1014）（1115）（120）（131）（142）（153）解：該網(wǎng)絡(luò)可用4個(gè)PM2I函數(shù)表示如下：6.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)距離從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過的最少邊數(shù)。⑷網(wǎng)絡(luò)直徑指網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間距離的最大值，常用D表示。從數(shù)據(jù)傳送的角度來看，網(wǎng)絡(luò)直徑應(yīng)盡可能的小。2.互連網(wǎng)絡(luò)的特征參數(shù)⑴傳送方式傳送方式一般分為同步和異步兩種：同步方式：在數(shù)據(jù)傳送的過程中采用統(tǒng)一時(shí)鐘信號(hào)。異步方式：不需要統(tǒng)一的時(shí)鐘信號(hào)在各處理機(jī)或單元之間進(jìn)行同步，各處理機(jī)或處理單元根據(jù)自身需要獨(dú)立工作。⑵控制策略控制策略：指控制互連開關(guān)構(gòu)成信息通路的方式，可以分為集中控制和分散控制兩種。集中控制：由統(tǒng)一的控制器對(duì)各個(gè)互連開關(guān)實(shí)施控制。分散控制：由各個(gè)開關(guān)自身實(shí)施控制。⑶交換方法交換方式：指數(shù)據(jù)傳送時(shí)的管理方式，可以分為線路交換和分組交換兩種。線路交換：在整個(gè)傳送過程中，在源結(jié)點(diǎn)與目的結(jié)點(diǎn)之間建立固定的物理通路，適用于成批數(shù)據(jù)的傳送。分組交換：對(duì)傳送的數(shù)據(jù)進(jìn)行分組，分別送入互連網(wǎng)路，各分組可以通過不同的路由到達(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)間有專用的連接通路，在網(wǎng)絡(luò)運(yùn)行中其結(jié)構(gòu)不能改變。動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)：指在結(jié)構(gòu)中設(shè)有有源開關(guān)，在網(wǎng)絡(luò)運(yùn)行中可以借助于控制信號(hào)對(duì)各結(jié)點(diǎn)的鏈路重新組合。6.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)圖6-6線性陣列網(wǎng)圖6-6星型網(wǎng)內(nèi)部結(jié)點(diǎn)的連接度d=2，兩端結(jié)點(diǎn)的連接度d=1。網(wǎng)絡(luò)直徑D=N-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)圖6-8環(huán)網(wǎng)圖6-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.二叉樹型網(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)圖6-13網(wǎng)格型與環(huán)網(wǎng)型結(jié)構(gòu)6.超立方體網(wǎng)絡(luò)（a）3-立方體（b）2個(gè)3-立方體構(gòu)成的4-立方體

圖6-14超立方體結(jié)構(gòu)6.靜態(tài)互連網(wǎng)絡(luò)比較表6-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對(duì)稱性網(wǎng)絡(luò)規(guī)格說明線形陣列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=

6.1.4動(dòng)態(tài)互連網(wǎng)絡(luò)

在動(dòng)態(tài)互連網(wǎng)絡(luò)中，各結(jié)點(diǎn)之間的連接是不固定的，而是在控制信號(hào)的作用下，通過網(wǎng)絡(luò)開關(guān)的設(shè)置來建立結(jié)點(diǎn)之間的間接、可變的連接通路。1.總線互連網(wǎng)絡(luò)圖6-15一種總線連接的多處理機(jī)系統(tǒng)2.交叉開關(guān)網(wǎng)絡(luò)圖6-16多處理機(jī)中處理機(jī)-存儲(chǔ)器之間的交叉開關(guān)網(wǎng)絡(luò)Fujitsu公司在1992年制造的向量并行處理機(jī)VPP500采用224×224的大型交叉開關(guān)網(wǎng)絡(luò)。如圖6-16所示。圖6-16VPP500向量并行處理機(jī)中處理機(jī)間的交叉開關(guān)網(wǎng)絡(luò)3.多級(jí)互連網(wǎng)絡(luò)在多級(jí)互連網(wǎng)絡(luò)結(jié)構(gòu)中，由交換開關(guān)、拓?fù)浣Y(jié)構(gòu)和控制方式三個(gè)參數(shù)描述。⑴交換開關(guān)（a）直送（b）交叉（c）下播（d）上播圖6-182×2交換開關(guān)的四種工作狀態(tài)⑵拓?fù)浣Y(jié)構(gòu)

指多級(jí)互連網(wǎng)絡(luò)的各級(jí)開關(guān)之間鏈路的互連模式。⑶控制方式控制方式：指對(duì)各級(jí)交換開關(guān)的控制方式。級(jí)控：同一級(jí)的所有開關(guān)用一個(gè)信號(hào)來控制，所有開關(guān)都處于同一種工作狀態(tài)，n級(jí)開關(guān)需要n個(gè)控制信號(hào)。單元控制：每一個(gè)開關(guān)單獨(dú)有一個(gè)控制信號(hào)，同一級(jí)的開關(guān)可以處于相同的工作狀態(tài)，也可以處于不同的工作狀態(tài)。N級(jí)網(wǎng)絡(luò)的輸入端和輸出端的總數(shù)N=2n，所以每一級(jí)有N/2個(gè)開關(guān)，這種方式下共需要nN/2個(gè)控制信號(hào)。部分級(jí)控：對(duì)于同一級(jí)開關(guān)分組，在不同級(jí)使用不同數(shù)量的控制信號(hào)。圖6-19所示是一種通用的多級(jí)互連網(wǎng)絡(luò)。接下來以O(shè)mega網(wǎng)絡(luò)為例，介紹多級(jí)互連網(wǎng)絡(luò)的構(gòu)成和尋徑算法。圖6-20N=8個(gè)結(jié)點(diǎn)的Omega網(wǎng)絡(luò)⑴Omega網(wǎng)絡(luò)的構(gòu)成6.2SIMD計(jì)算機(jī)按照Flynn分類法，將單指令流多數(shù)據(jù)流結(jié)構(gòu)的計(jì)算機(jī)稱為SIMD計(jì)算機(jī)。它主要通過硬件資源的重復(fù)設(shè)置來實(shí)現(xiàn)并行性，適用于大量高速的向量或矩陣運(yùn)算，所以又稱為并行處理機(jī)和陣列處理機(jī)。6.2.1SIMD計(jì)算機(jī)模型與特點(diǎn)1.SIMD計(jì)算機(jī)模型圖6-23SIMD計(jì)算機(jī)的操作模型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)向量處理專用計(jì)算機(jī)。6.2.2SIMD計(jì)算機(jī)結(jié)構(gòu)

根據(jù)存儲(chǔ)器的分布方式不同，陣列處理機(jī)有分布式存儲(chǔ)器和共享式存儲(chǔ)器兩種基本結(jié)構(gòu)，1.分布式存儲(chǔ)器陣列處理機(jī)的基本結(jié)構(gòu)圖6-24分布式存儲(chǔ)器陣列處理機(jī)的基本結(jié)構(gòu)2.共享存儲(chǔ)器陣列處理機(jī)的基本結(jié)構(gòu)圖6-25共享存儲(chǔ)器的SIMD計(jì)算機(jī)6.2.3SIMD計(jì)算機(jī)實(shí)例

接下來分別介紹兩種典型的SIMD計(jì)算機(jī)：IlliacIV陣列處理機(jī)和BSP計(jì)算機(jī)。1.IlliacIV陣列處理機(jī)圖6-26IlliacIV陣列處理機(jī)總體框架⑴IlliacIV陣列IlliacIV陣列PU是由64個(gè)處理單元（PE）、64個(gè)局部存儲(chǔ)器（PEM）和存儲(chǔ)邏輯部件（MLU）組成。（a）處理單元之間的連接關(guān)系（b）IlliacIV處理部件的連接圖6-26IlliacIV陣列處理機(jī)的陣列連接概括起來，控制器的功能有以下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操作以及B6600所產(chǎn)生的陷阱中斷信號(hào)。6.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單元中。圖6-29矩陣相加存儲(chǔ)器分配⑵矩陣乘

設(shè)A、B和C為3個(gè)8×8的二維矩陣。若給定A和B，則C＝A×B的64個(gè)分量可利用下列公式計(jì)算。，0≤i≤6，0≤j≤6。

如果在SIMD計(jì)算機(jī)上求解這個(gè)問題，可執(zhí)行下列FORTRAN程序：DO

10

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

20

K=0,620

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

CONTINUE圖6-30矩陣乘程序執(zhí)行流程圖圖6-31矩陣乘存儲(chǔ)器分配⑶累加和

假設(shè)累加的數(shù)為A(I)，其中I的取值范圍為0≤I≤7，即共有8個(gè)數(shù)進(jìn)行順序累加。在SIMD計(jì)算機(jī)上可寫成下列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≤6；第3步令K＝0；第4步全部PEi的(RGAi)轉(zhuǎn)送到傳送寄存器RGRi，0≤I≤6；第5步全部PEi的(RGAi）經(jīng)過互連網(wǎng)絡(luò)向右傳送2k步距，0≤I≤6；第6步令j=2k-1；第6步置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≤6；第12步全部PEi的(RGAi)存入相應(yīng)PEMi的a+1單元中。上面描述的計(jì)算過程如圖6-32所示。圖6-32陣列處理機(jī)上累加和的計(jì)算過程6.3MIMD計(jì)算機(jī)MIMD計(jì)算機(jī)按照Flynn分類法是指多指令流多數(shù)據(jù)流計(jì)算機(jī)，它由多臺(tái)獨(dú)立的計(jì)算機(jī)組成，每臺(tái)計(jì)算機(jī)能夠獨(dú)立執(zhí)行自己的程序。6.3.1MIMD計(jì)算機(jī)結(jié)構(gòu)MIMD計(jì)算機(jī)根據(jù)存儲(chǔ)器組織方式的不同，將MIMD計(jì)算機(jī)結(jié)構(gòu)分成兩類：共享存儲(chǔ)器多處理機(jī)結(jié)構(gòu)和分布式存儲(chǔ)器多處理機(jī)結(jié)構(gòu)。（a）共享存儲(chǔ)器多處理機(jī)結(jié)構(gòu)（b）分布式存儲(chǔ)器多處理機(jī)結(jié)果6-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)用，