互聯(lián)網(wǎng)絡(luò)培訓(xùn)教程[1]

互聯(lián)網(wǎng)絡(luò)培訓(xùn)教程[1]

?學(xué)習(xí)目標(biāo)：

??? 掌握互連網(wǎng)絡(luò)的定義、性能參數(shù)。

??? 掌握互連函數(shù)的概念。

??? 掌握幾種數(shù)據(jù)路由功能的含義和特點(diǎn)。(循環(huán)、置換、均勻混洗 、超立方體路由功能、廣播、選播)

??? 掌握靜態(tài)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)及特點(diǎn)。(線性陣列、環(huán)和帶弦環(huán)、全連接網(wǎng)絡(luò)、循環(huán)移數(shù)網(wǎng)絡(luò)、樹(shù)形和星形、胖樹(shù)形、網(wǎng)格形和環(huán)網(wǎng)、超立方體、k元n-立方體網(wǎng)絡(luò))

??? 掌握動(dòng)態(tài)網(wǎng)絡(luò)的分類(lèi)方法和動(dòng)態(tài)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。 (總線系統(tǒng)、交叉開(kāi)關(guān)網(wǎng)絡(luò) 、多端口存儲(chǔ)器、多級(jí)網(wǎng)絡(luò))

??? 正文：

??? 6.3互聯(lián)網(wǎng)絡(luò)

??? 互連網(wǎng)絡(luò)是將集中式系統(tǒng)或分布式系統(tǒng)中的結(jié)點(diǎn)連接起來(lái)所構(gòu)成的網(wǎng)絡(luò)，這些結(jié)點(diǎn)可能是處理器、存儲(chǔ)模塊或者其他設(shè)備，它們通過(guò)互連網(wǎng)絡(luò)進(jìn)行信息交換。在拓?fù)渖?，互連網(wǎng)絡(luò)為輸入和輸出兩組結(jié)點(diǎn)之間提供一組互連或映象（mapping）。

??? 本節(jié)介紹構(gòu)造多處理機(jī)的互連網(wǎng)絡(luò)。首先討論互連網(wǎng)絡(luò)的通信特性和拓?fù)浣Y(jié)構(gòu)，然后再來(lái)分析并行結(jié)構(gòu)的可擴(kuò)展性。我們希望得到的是數(shù)據(jù)傳送速率高、延遲低、通信頻帶寬的網(wǎng)絡(luò)。
6.3.1互聯(lián)網(wǎng)絡(luò)的性能參數(shù)

??? 互連網(wǎng)絡(luò)的拓?fù)淇梢圆捎渺o態(tài)或動(dòng)態(tài)的結(jié)構(gòu)。

??? 1. 靜態(tài)網(wǎng)絡(luò)由點(diǎn)和點(diǎn)直接相連而成，這種連接方式在程序執(zhí)行過(guò)程中不會(huì)改變。靜態(tài)網(wǎng)絡(luò)常用來(lái)實(shí)現(xiàn)一個(gè)系統(tǒng)中子系統(tǒng)或計(jì)算結(jié)點(diǎn)之間的固定連接。

??? 2. 動(dòng)態(tài)網(wǎng)絡(luò)是用開(kāi)關(guān)通道實(shí)現(xiàn)的，它可動(dòng)態(tài)地改變結(jié)構(gòu)，使其與用戶程序中的通信要求匹配。

??? 動(dòng)態(tài)網(wǎng)絡(luò)常用于集中式共享存儲(chǔ)器多處理系統(tǒng)中。

??? 下面定義幾個(gè)常用于估算網(wǎng)絡(luò)復(fù)雜性、通信效率和價(jià)格的參數(shù)。

??? (1) 網(wǎng)絡(luò)規(guī)模

??? 一般說(shuō)來(lái)，網(wǎng)絡(luò)用圖來(lái)表示。這種圖由用有向邊或無(wú)向邊連接的有限個(gè)結(jié)點(diǎn)構(gòu)成。其結(jié)點(diǎn)數(shù)稱為網(wǎng)絡(luò)規(guī)模(network size)。

??? (2) 結(jié)點(diǎn)度

??? 與結(jié)點(diǎn)相連接的邊的數(shù)目稱為結(jié)點(diǎn)度(node degree)。這里的邊表示鏈路或通道。鏈路或通道是指網(wǎng)絡(luò)中連接兩個(gè)結(jié)點(diǎn)并傳送數(shù)字信號(hào)的通路。在單向通道的情況下，進(jìn)入結(jié)點(diǎn)的通道數(shù)叫做入度(in degree)，而從結(jié)點(diǎn)出來(lái)的通道數(shù)則稱為出度(out degree),結(jié)點(diǎn)度是這兩者之和。結(jié)點(diǎn)度應(yīng)盡可能地小并保持恒定。

??? (3) 網(wǎng)絡(luò)直徑

??? 網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)間最短路徑長(zhǎng)度的最大值稱為網(wǎng)絡(luò)直徑。網(wǎng)絡(luò)直徑應(yīng)當(dāng)盡可能地小。

??? (4) 等分寬度

??? 在將某一網(wǎng)絡(luò)切成相等兩半的各種切法中，沿切口的最小通道邊數(shù)稱為通道等分寬度(channel bisection width)。等分寬度是能很好地說(shuō)明將網(wǎng)絡(luò)等分的交界處最大通信帶寬的一個(gè)參數(shù)另一個(gè)量化參數(shù)是結(jié)點(diǎn)間的線長(zhǎng)(或通道長(zhǎng)度)。它會(huì)影響信號(hào)的延遲、時(shí)鐘扭斜和對(duì)功率的需要。對(duì)于一個(gè)網(wǎng)絡(luò)，如果從其中的任何一個(gè)結(jié)點(diǎn)看，拓?fù)浣Y(jié)構(gòu)都是一樣的話，則稱此網(wǎng)絡(luò)為對(duì)稱網(wǎng)絡(luò)。對(duì)稱網(wǎng)絡(luò)較易實(shí)現(xiàn)，編制程序也較容易。

(5) 路由（routing）

??? 在網(wǎng)絡(luò)通信中對(duì)路徑的選擇與指定?；ミB網(wǎng)絡(luò)中路由功能較強(qiáng)將有利于減少數(shù)據(jù)交換所需的時(shí)間，因而能顯著地改善系統(tǒng)的性能。通常見(jiàn)到的處理單元之間的數(shù)據(jù)路由功能有移數(shù)、循環(huán)、置換(一對(duì)一)、廣播(一對(duì)全體)、選播(多對(duì)多)、個(gè)人通信(一對(duì)多)、混洗、交換等。這些路由功能可在環(huán)形、網(wǎng)絡(luò)形、超立方體以及多級(jí)網(wǎng)絡(luò)上實(shí)現(xiàn)。

??? 為了反映不同互連網(wǎng)絡(luò)的連接特性，每一種互連網(wǎng)絡(luò)可用一組互連函數(shù)來(lái)定義。如果把互連網(wǎng)絡(luò)的N個(gè)入端和N個(gè)出端各自用整數(shù)0，1，…，N-1代表，則互連函數(shù)表示互連的出端號(hào)和入端號(hào)的一一對(duì)應(yīng)關(guān)系。令互連函數(shù)為f,則它的作用是：對(duì)于所有的0≤j≤N-1, 同時(shí)存在入端j連至出端f(j)的對(duì)應(yīng)關(guān)系。

??? 下面介紹幾種數(shù)據(jù)路由功能：

??? 1. 循環(huán)（rotation）

??? 若把互連函數(shù)f(x)表示為：

??? (x0,x1,x2,……,xj)

??? 則代表對(duì)應(yīng)關(guān)系為：

??? f(x0)=x1,f(x1)=x2,……,f(xj)=x0

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

??? 2. 置換（permutation）

??? 指對(duì)象的重新排序。對(duì)于n個(gè)對(duì)象來(lái)說(shuō)，有n!種置換。n個(gè)對(duì)象可照此重新排序，全部的置換形成一個(gè)與復(fù)合運(yùn)算有關(guān)的置換集合。例如，置換π=(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。可以用交叉開(kāi)關(guān)來(lái)實(shí)現(xiàn)置換，也可以用一次或多次通過(guò)多級(jí)網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)某些置換，還可用移數(shù)或廣播操作實(shí)現(xiàn)置換。

?

3. 均勻混洗（shuffle）

??? n=8（對(duì)象個(gè)數(shù)）的均勻混洗所對(duì)應(yīng)的映射如圖6.3.1所示，圖6.3.2為其逆過(guò)程。

?一般說(shuō)來(lái)，為了對(duì)n=2k個(gè)對(duì)象均勻混洗，我們可用k位二進(jìn)制數(shù)x=(xk-1,…,x1,x0)來(lái)表示定義域中的每個(gè)對(duì)象。均勻混洗將x映射到f(x)，得到f(x)=( xk-2,…,x1,x0,xk-1)。這是將x循環(huán)左移1位得到。

??? 4．超立方體路由功能

??? 圖6.3.3表示的是一個(gè)三維二進(jìn)制立方體網(wǎng)絡(luò)。它有三種路由功能，可分別根據(jù)結(jié)點(diǎn)的二進(jìn)制地址（C2 C1 C0）中的某一位來(lái)確定。例如，可以根據(jù)最低位C0尋址，即在最低位C0不同的相鄰結(jié)點(diǎn)之間交換數(shù)據(jù)，如圖6.3.4所示。同樣，分別根據(jù)中間位C1 (圖6.3.5)和最高位C2 (圖6.3.6)可得其它兩種路由模式。

??? 一般情況下，一個(gè)n維超立方體共有n種路由功能，分別由n位地址中的每一位求反位值來(lái)確定。將x=(xn-1,…,x1,x0)映射到f(x)，得到f(x)=( xn-1, …, xk,…,x1,x0)。

?