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

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

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

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

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

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

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

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

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

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

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

對稱網(wǎng)絡

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

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

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

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

(1)循環(huán)

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

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

指對象的重新排序。對于n個對象來說，有n!種置換。9.4互連網(wǎng)絡例如置換π=(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ù)）的均勻混洗所對應的映射與其逆過程

對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)絡(4)超立方體路由功能

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

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

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

(5)廣播和選播

廣播

一對全體的映射。選播

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

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

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

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

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

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

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

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

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

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

通過在環(huán)上每個結(jié)點到所有與其距離為2的整數(shù)冪的結(jié)點之間都增加一條附加鏈而構(gòu)成的。結(jié)點數(shù):16結(jié)點度:7直徑:29.4互連網(wǎng)絡如果｜j-i｜=2r，r=0,1,2,…,n-1，網(wǎng)絡規(guī)模N=2n，則結(jié)點i與結(jié)點j連接。這種循環(huán)移數(shù)網(wǎng)絡的結(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)絡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)絡9.4互連網(wǎng)絡5.胖樹形(解決瓶頸問題)9.4互連網(wǎng)絡6.網(wǎng)格形和環(huán)網(wǎng)形(1)一個3×3網(wǎng)格形網(wǎng)絡一般說來，N=nk個結(jié)點的k維網(wǎng)絡的內(nèi)部結(jié)點度為2k，網(wǎng)絡直徑為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)絡9.4互連網(wǎng)絡7.超立方體一種二元n-立方體結(jié)構(gòu)一般說來，一個n-立方體由N=2n個結(jié)點組成，它們分布在n維上，每維有兩個結(jié)點。

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

環(huán)形、網(wǎng)絡形、環(huán)網(wǎng)形、二元n-立方體(超立方體)等網(wǎng)絡都是k元n-立方體網(wǎng)絡系統(tǒng)的拓撲同構(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)絡例一種4元3-立方體網(wǎng)絡9.4互連網(wǎng)絡9.4.3動態(tài)連接網(wǎng)絡

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

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

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

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

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

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

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

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

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