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

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

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

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

供一組互連或映象。本節(jié)介紹：構(gòu)造多處理機(jī)的互連網(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ò)

由點(diǎn)和點(diǎn)直接相連而成，這種連接方式在

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

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

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

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

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

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

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

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

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

如果把互連網(wǎng)絡(luò)的N個(gè)入端和N個(gè)出端各自用整數(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個(gè)對象來說，有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（對象個(gè)數(shù)）的均勻混洗所對應(yīng)的映射與其逆過程

對n=2k個(gè)對象均勻混洗，可用k位二進(jìn)制數(shù)x=(xk-1,…,x1,x0)表示定義域中的每個(gè)對象均勻混洗將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)超立方體路由功能

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

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

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

(5)廣播和選播

廣播

一對全體的映射。選播

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

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

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

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

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

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

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

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

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

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

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

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

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

例8個(gè)結(jié)點(diǎn)的3-立方體4-立方體一個(gè)n-立方體的結(jié)點(diǎn)度等于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ù)或者說是沿每個(gè)方向的結(jié)點(diǎn)數(shù)(多重性)。N=kn,(n=logkN)K元n-立方體的結(jié)點(diǎn)可用基數(shù)為k的n位地址A=a0a1a2…an-1來表示，其中ai代表第i維結(jié)點(diǎn)的位置。按照慣例，低維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動(dòng)態(tài)連接網(wǎng)絡(luò)

1.動(dòng)態(tài)互連網(wǎng)絡(luò)的三個(gè)主要操作特征定時(shí)開關(guān)控制2.根據(jù)級間連結(jié)方式，動(dòng)態(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ò)如果同時(shí)連接多個(gè)輸入輸出對時(shí),可能會(huì)引起開關(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)點(diǎn)：價(jià)格較低帶寬較窄缺點(diǎn)：容易產(chǎn)生故障總線研制中的重要問題9.4互連網(wǎng)絡(luò)一種總線連接的多處理機(jī)系統(tǒng)

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

①主要思想將所有交叉點(diǎn)仲裁邏輯和跟每個(gè)存儲(chǔ)器模塊有關(guān)的開關(guān)功能移到存儲(chǔ)器控制器中。②多端口存儲(chǔ)器結(jié)構(gòu)是一個(gè)折衷方案，它介于低成本低性能的總線系統(tǒng)和高成本高帶寬的交叉開關(guān)系統(tǒng)之間。③缺點(diǎn)十分昂貴不能擴(kuò)展當(dāng)系統(tǒng)配置很大時(shí)，需要大量的互連電纜和連接器。9.4互連網(wǎng)絡(luò)用于多處理機(jī)系統(tǒng)的多端口存儲(chǔ)器結(jié)構(gòu)(4)多級網(wǎng)絡(luò)多級網(wǎng)絡(luò)可用于構(gòu)造大型多處理機(jī)系統(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ò)一個(gè)16×16Omega網(wǎng)絡(luò)2012年二學(xué)位A卷用一個(gè)級間采用洗牌函數(shù)f(x3x2x1)=x1x3x2連接的N=8的3級Omega