第09章 互連網(wǎng)絡(luò)

張晨曦編著華中科技大學(xué)計算機學(xué)院2013年5月作業(yè)：P294頁9.139.1引言9.2對稱式共享存儲器體系結(jié)構(gòu)9.3分布式共享存儲器體系結(jié)構(gòu)9.4互連網(wǎng)絡(luò)9.5同步9.6同時多線程9.7多處理機實例第9章互連網(wǎng)絡(luò)9.4互連網(wǎng)絡(luò)

互連網(wǎng)絡(luò)是將集中式系統(tǒng)或分布式系統(tǒng)中的結(jié)點連

接起來所構(gòu)成的網(wǎng)絡(luò)。在拓?fù)渖?，互連網(wǎng)絡(luò)為輸入和輸出兩組結(jié)點之間提

供一組互連或映象。本節(jié)介紹：構(gòu)造多處理機的互連網(wǎng)絡(luò)第九章互連網(wǎng)絡(luò)9.4.1互連網(wǎng)絡(luò)的性能參數(shù)1.互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)(1)靜態(tài)網(wǎng)絡(luò)

由點和點直接相連而成，這種連接方式在

程序執(zhí)行過程中不會改變。

(2)動態(tài)網(wǎng)絡(luò)用開關(guān)通道實現(xiàn)，可動態(tài)地改變結(jié)構(gòu)，使其與用戶程序中通信要求匹配。9.4互連網(wǎng)絡(luò)2.性能參數(shù)(1)網(wǎng)絡(luò)規(guī)模：結(jié)點數(shù)

(2)結(jié)點度：與結(jié)點相連接的邊的數(shù)目。

入度：進入結(jié)點的通道數(shù)出度：從結(jié)點出來的通道數(shù)(3)網(wǎng)絡(luò)直徑

網(wǎng)絡(luò)中任意兩個結(jié)點間最短路徑長度的最大值。(4)等分寬度

在將某一網(wǎng)絡(luò)切成相等兩半的各種切法中，沿切口的最小通道邊數(shù)。9.4互連網(wǎng)絡(luò)

對稱網(wǎng)絡(luò)

從其中的任何一個結(jié)點看，拓?fù)浣Y(jié)構(gòu)都是一樣的。(5)路由

在網(wǎng)絡(luò)通信中對路徑的選擇與指定。3.互連函數(shù)

如果把互連網(wǎng)絡(luò)的N個入端和N個出端各自用整數(shù)0，1，…，N-1代表，則互連函數(shù)表示互連的出端號和入端號的一一對應(yīng)關(guān)系。

9.4互連網(wǎng)絡(luò)4.幾種數(shù)據(jù)路由功能

(1)循環(huán)

若把互連函數(shù)f(x)表示為：(x0,x1,x2,……,xj)則代表對應(yīng)關(guān)系為：f(x0)=x1,f(x1)=x2,……,f(xj)=x0

j+1稱為該循環(huán)的周期。(2)置換

指對象的重新排序。對于n個對象來說，有n!種置換。9.4互連網(wǎng)絡(luò)例如置換π=(a,b,c)(d,e)表示了置換映射：f(a)=b,f(b)=c,f(c)=a,f(d)=e和f(e)=d。這里循環(huán)(a,b,c)周期為3，循環(huán)(d,e)周期為2。(3)均勻混洗n=8（對象個數(shù)）的均勻混洗所對應(yīng)的映射與其逆過程

對n=2k個對象均勻混洗，可用k位二進制數(shù)x=(xk-1,…,x1,x0)表示定義域中的每個對象均勻混洗將x映射到f(x)，得到：f(x)=(xk-2,…,x1,x0,xk-1)（將x循環(huán)左移1位）

若x=(0,0,0)，則f(x)=(0,0,0)；若x=(1,1,1)，則f(x)=(1,1,1)9.4互連網(wǎng)絡(luò)(4)超立方體路由功能

例一個三維二進制立方體網(wǎng)絡(luò)

9.4互連網(wǎng)絡(luò)根據(jù)最低位C0路由根據(jù)中間位C1路由根據(jù)最高位C2路由一個n維超立方體共有n種路由功能，分別由n位地址中的每一位求反位值來確定。將x=(xk-1,…,x1,x0)映射到f(x)，得到有三種路由功能:

分別根據(jù)結(jié)點的二進制地址（C2C1C0）中的某一位來確定9.4互連網(wǎng)絡(luò)

(5)廣播和選播

廣播

一對全體的映射。選播

一個子集到另一子集(多對多)的映射。5.影響互連網(wǎng)絡(luò)性能的因素(1)功能特性

網(wǎng)絡(luò)如何支持路由、中斷處理、同步、請求／消息組合和一致性。9.4互連網(wǎng)絡(luò)(2)網(wǎng)絡(luò)時延

單位消息通過網(wǎng)絡(luò)傳送時最壞情況下的時間延遲。(3)帶寬

通過網(wǎng)絡(luò)的最大數(shù)據(jù)傳輸率，用MB／s表示。(4)硬件復(fù)雜性諸如導(dǎo)線、開關(guān)、連接器、仲裁和接口邏輯等的造價。(5)可擴展性

在增加機器資源使性能可擴展的情況下，網(wǎng)絡(luò)具備模塊化可擴展的能力。

9.4互連網(wǎng)絡(luò)9.4.2靜態(tài)連接網(wǎng)絡(luò)1.線性陣列

一種一維的線性網(wǎng)絡(luò)，其中N個結(jié)點用N-1個鏈路連成一行。

內(nèi)部結(jié)點度：2端結(jié)點度：1直徑：N-1等分寬度b=19.4互連網(wǎng)絡(luò)2.環(huán)和帶弦環(huán)(1)環(huán)用一條附加鏈路將線性陣列的兩個端點連接起來而構(gòu)成的?？梢詥蜗蚬ぷ鳎部梢噪p向工作。結(jié)點度：2雙向環(huán)的直徑：N／2單向環(huán)的直徑：N等分寬度b=2?9.4互連網(wǎng)絡(luò)(2)帶弦環(huán)

增加的鏈路愈多，結(jié)點度愈高，網(wǎng)絡(luò)直徑就愈小。

9.4互連網(wǎng)絡(luò)全連接網(wǎng)絡(luò)結(jié)點度:N-1直徑最短，為19.4互連網(wǎng)絡(luò)3.循環(huán)移數(shù)網(wǎng)絡(luò)

通過在環(huán)上每個結(jié)點到所有與其距離為2的整數(shù)冪的結(jié)點之間都增加一條附加鏈而構(gòu)成的。結(jié)點數(shù):16結(jié)點度:7直徑:29.4互連網(wǎng)絡(luò)如果｜j-i｜=2r，r=0,1,2,…,n-1，網(wǎng)絡(luò)規(guī)模N=2n，則結(jié)點i與結(jié)點j連接。這種循環(huán)移數(shù)網(wǎng)絡(luò)的結(jié)點度為d=2n-1，直徑D=n／2。如：N=16，n=4，r=0,1,2,3，|j-i|=1,2,4,8則：d=7,D=2

9.4互連網(wǎng)絡(luò)4.樹形和星形

(1)一棵5層31個結(jié)點的二叉樹

一般說來，一棵k層完全平衡的二叉樹有N=2k-1個結(jié)點。最大結(jié)點度是3，直徑是2(k-1)。

(2)星形一種2層樹結(jié)點度較高，為d=N-1直徑較小，是一常數(shù)29.4互連網(wǎng)絡(luò)9.4互連網(wǎng)絡(luò)5.胖樹形(解決瓶頸問題)9.4互連網(wǎng)絡(luò)6.網(wǎng)格形和環(huán)網(wǎng)形(1)一個3×3網(wǎng)格形網(wǎng)絡(luò)一般說來，N=nk個結(jié)點的k維網(wǎng)絡(luò)的內(nèi)部結(jié)點度為2k，網(wǎng)絡(luò)直徑為k(n-1)。邊結(jié)點和角結(jié)點的結(jié)點度分別為3或2。例如，N=nk=32，則內(nèi)部節(jié)點度為4，直徑為4(2)環(huán)形網(wǎng)可看做是直徑更短的另一種網(wǎng)格環(huán)形網(wǎng)沿陣列每行和每列都有環(huán)形連接一個n×n二元環(huán)網(wǎng)結(jié)點度為4直徑為2×n/2例如，N=nk=32，則節(jié)點度為4，直徑為29.4互連網(wǎng)絡(luò)9.4互連網(wǎng)絡(luò)7.超立方體一種二元n-立方體結(jié)構(gòu)一般說來，一個n-立方體由N=2n個結(jié)點組成，它們分布在n維上，每維有兩個結(jié)點。

例8個結(jié)點的3-立方體4-立方體一個n-立方體的結(jié)點度等于n，也就是網(wǎng)絡(luò)的直徑。9.4互連網(wǎng)絡(luò)9.4互連網(wǎng)絡(luò)8.k元n-立方體網(wǎng)絡(luò)

環(huán)形、網(wǎng)絡(luò)形、環(huán)網(wǎng)形、二元n-立方體(超立方體)等網(wǎng)絡(luò)都是k元n-立方體網(wǎng)絡(luò)系統(tǒng)的拓?fù)渫瑯?gòu)體。

參數(shù)n:立方體的維數(shù)k:基數(shù)或者說是沿每個方向的結(jié)點數(shù)(多重性)。N=kn,(n=logkN)K元n-立方體的結(jié)點可用基數(shù)為k的n位地址A=a0a1a2…an-1來表示，其中ai代表第i維結(jié)點的位置。按照慣例，低維k元n-立方體稱為環(huán)網(wǎng)，而高維二元n-立方體則稱為超立方體。

9.4互連網(wǎng)絡(luò)例一種4元3-立方體網(wǎng)絡(luò)9.4互連網(wǎng)絡(luò)9.4.3動態(tài)連接網(wǎng)絡(luò)

1.動態(tài)互連網(wǎng)絡(luò)的三個主要操作特征定時開關(guān)控制2.根據(jù)級間連結(jié)方式，動態(tài)互連網(wǎng)絡(luò)分為

(1)單級網(wǎng)絡(luò)也稱循環(huán)網(wǎng)絡(luò)

(2)多級網(wǎng)絡(luò)由一級以上的開關(guān)元件構(gòu)成。這類網(wǎng)絡(luò)可以把任一輸入與任一輸出相連。

9.4互連網(wǎng)絡(luò)阻塞網(wǎng)絡(luò)如果同時連接多個輸入輸出對時,可能會引起開關(guān)和通信鏈路使用上的沖突。大多數(shù)多級網(wǎng)絡(luò)都是阻塞網(wǎng)絡(luò)。非阻塞網(wǎng)絡(luò)如果多級網(wǎng)絡(luò)通過重新安排連接方式可以建立所有可能的輸入輸出之間的連接。

9.4互連網(wǎng)絡(luò)總線仲裁中斷處理一致性協(xié)議總線事務(wù)的處理3.幾類主要的開關(guān)網(wǎng)絡(luò)(1)總線系統(tǒng)

優(yōu)點：價格較低帶寬較窄缺點：容易產(chǎn)生故障總線研制中的重要問題9.4互連網(wǎng)絡(luò)一種總線連接的多處理機系統(tǒng)

(2)交叉開關(guān)網(wǎng)絡(luò)單級無阻塞置換網(wǎng)絡(luò)每個交叉點是一個可以打開或關(guān)閉的開關(guān)，提供源(處理器)和目的(存儲器)之間點對點的連接通路。交叉點開關(guān)網(wǎng)絡(luò)中n對處理器可以同時傳送數(shù)據(jù)。交叉開關(guān)網(wǎng)絡(luò)的帶寬和互連特性最好。一種交叉開關(guān)網(wǎng)絡(luò)9.4互連網(wǎng)絡(luò)9.4互連網(wǎng)絡(luò)(3)多端口存儲器

①主要思想將所有交叉點仲裁邏輯和跟每個存儲器模塊有關(guān)的開關(guān)功能移到存儲器控制器中。②多端口存儲器結(jié)構(gòu)是一個折衷方案，它介于低成本低性能的總線系統(tǒng)和高成本高帶寬的交叉開關(guān)系統(tǒng)之間。③缺點十分昂貴不能擴展當(dāng)系統(tǒng)配置很大時，需要大量的互連電纜和連接器。9.4互連網(wǎng)絡(luò)用于多處理機系統(tǒng)的多端口存儲器結(jié)構(gòu)(4)多級網(wǎng)絡(luò)多級網(wǎng)絡(luò)可用于構(gòu)造大型多處理機系統(tǒng)。①一種通用多級網(wǎng)絡(luò)各種多級網(wǎng)絡(luò)的區(qū)別就在于所用開關(guān)模塊和級間連接模式的不同。9.4互連網(wǎng)絡(luò)由a×b開關(guān)模塊和級間構(gòu)成的通用多級互連網(wǎng)絡(luò)結(jié)構(gòu)2×2開關(guān)四種可能的連接方式

②Omega網(wǎng)絡(luò)9.4互連網(wǎng)絡(luò)一個16×16Omega網(wǎng)絡(luò)2012年二學(xué)位A卷用一個級間采用洗牌函數(shù)f(x3x2x1)=x1x3x2連接的N=8的3級Omega