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

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

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

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

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

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

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

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

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

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

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

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

對稱網(wǎng)絡

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

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

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

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

(1)循環(huán)

若把互連函數(shù)f(x)表示為：(x0,x1,x2,……,xj)則代表對應關系為：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ù)結點的二進制地址（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)硬件復雜性諸如導線、開關、連接器、仲裁和接口邏輯等的造價。(5)可擴展性

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

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

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

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

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

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

通過在環(huán)上每個結點到所有與其距離為2的整數(shù)冪的結點之間都增加一條附加鏈而構成的。結點數(shù):16結點度:7直徑:29.4互連網(wǎng)絡如果｜j-i｜=2r，r=0,1,2,…,n-1，網(wǎng)絡規(guī)模N=2n，則結點i與結點j連接。這種循環(huán)移數(shù)網(wǎng)絡的結點度為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個結點的二叉樹

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

(2)星形一種2層樹結點度較高，為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個結點的k維網(wǎng)絡的內部結點度為2k，網(wǎng)絡直徑為k(n-1)。邊結點和角結點的結點度分別為3或2。例如，N=nk=32，則內部節(jié)點度為4，直徑為4(2)環(huán)形網(wǎng)可看做是直徑更短的另一種網(wǎng)格環(huán)形網(wǎng)沿陣列每行和每列都有環(huán)形連接一個n×n二元環(huán)網(wǎng)結點度為4直徑為2×n/2例如，N=nk=32，則節(jié)點度為4，直徑為29.4互連網(wǎng)絡9.4互連網(wǎng)絡7.超立方體一種二元n-立方體結構一般說來，一個n-立方體由N=2n個結點組成，它們分布在n維上，每維有兩個結點。

例8個結點的3-立方體4-立方體一個n-立方體的結點度等于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)的拓撲同構體。

參數(shù)n:立方體的維數(shù)k:基數(shù)或者說是沿每個方向的結點數(shù)(多重性)。N=kn,(n=logkN)K元n-立方體的結點可用基數(shù)為k的n位地址A=a0a1a2…an-1來表示，其中ai代表第i維結點的位置。按照慣例，低維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)絡的三個主要操作特征定時開關控制2.根據(jù)級間連結方式，動態(tài)互連網(wǎng)絡分為

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

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

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

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

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

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

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

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