互聯網絡培訓教程[1]

?學習目標：

??? 掌握互連網絡的定義、性能參數。

??? 掌握互連函數的概念。

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

??? 掌握靜態網絡的拓撲結構及特點。(線性陣列、環和帶弦環、全連接網絡、循環移數網絡、樹形和星形、胖樹形、網格形和環網、超立方體、k元n-立方體網絡)

??? 掌握動態網絡的分類方法和動態網絡的拓撲結構。 (總線系統、交叉開關網絡 、多端口存儲器、多級網絡)

??? 正文：

??? 6.3互聯網絡

??? 互連網絡是將集中式系統或分布式系統中的結點連接起來所構成的網絡，這些結點可能是處理器、存儲模塊或者其他設備，它們通過互連網絡進行信息交換。在拓撲上，互連網絡為輸入和輸出兩組結點之間提供一組互連或映象（mapping）。

??? 本節介紹構造多處理機的互連網絡。首先討論互連網絡的通信特性和拓撲結構，然后再來分析并行結構的可擴展性。我們希望得到的是數據傳送速率高、延遲低、通信頻帶寬的網絡。
6.3.1互聯網絡的性能參數

??? 互連網絡的拓撲可以采用靜態或動態的結構。

??? 1. 靜態網絡由點和點直接相連而成，這種連接方式在程序執行過程中不會改變。靜態網絡常用來實現一個系統中子系統或計算結點之間的固定連接。

??? 2. 動態網絡是用開關通道實現的，它可動態地改變結構，使其與用戶程序中的通信要求匹配。

??? 動態網絡常用于集中式共享存儲器多處理系統中。

??? 下面定義幾個常用于估算網絡復雜性、通信效率和價格的參數。

??? (1) 網絡規模

??? 一般說來，網絡用圖來表示。這種圖由用有向邊或無向邊連接的有限個結點構成。其結點數稱為網絡規模(network size)。

??? (2) 結點度

??? 與結點相連接的邊的數目稱為結點度(node degree)。這里的邊表示鏈路或通道。鏈路或通道是指網絡中連接兩個結點并傳送數字信號的通路。在單向通道的情況下，進入結點的通道數叫做入度(in degree)，而從結點出來的通道數則稱為出度(out degree),結點度是這兩者之和。結點度應盡可能地小并保持恒定。

??? (3) 網絡直徑

??? 網絡中任意兩個結點間最短路徑長度的最大值稱為網絡直徑。網絡直徑應當盡可能地小。

??? (4) 等分寬度

??? 在將某一網絡切成相等兩半的各種切法中，沿切口的最小通道邊數稱為通道等分寬度(channel bisection width)。等分寬度是能很好地說明將網絡等分的交界處最大通信帶寬的一個參數另一個量化參數是結點間的線長(或通道長度)。它會影響信號的延遲、時鐘扭斜和對功率的需要。對于一個網絡，如果從其中的任何一個結點看，拓撲結構都是一樣的話，則稱此網絡為對稱網絡。對稱網絡較易實現，編制程序也較容易。

(5) 路由（routing）

??? 在網絡通信中對路徑的選擇與指定。互連網絡中路由功能較強將有利于減少數據交換所需的時間，因而能顯著地改善系統的性能。通常見到的處理單元之間的數據路由功能有移數、循環、置換(一對一)、廣播(一對全體)、選播(多對多)、個人通信(一對多)、混洗、交換等。這些路由功能可在環形、網絡形、超立方體以及多級網絡上實現。

??? 為了反映不同互連網絡的連接特性，每一種互連網絡可用一組互連函數來定義。如果把互連網絡的N個入端和N個出端各自用整數0，1，…，N-1代表，則互連函數表示互連的出端號和入端號的一一對應關系。令互連函數為f,則它的作用是：對于所有的0≤j≤N-1, 同時存在入端j連至出端f(j)的對應關系。

??? 下面介紹幾種數據路由功能：

??? 1. 循環（rotation）

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

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

??? 則代表對應關系為：

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

??? j+1稱為該循環的周期。

??? 2. 置換（permutation）

??? 指對象的重新排序。對于n個對象來說，有n!種置換。n個對象可照此重新排序，全部的置換形成一個與復合運算有關的置換集合。例如，置換π=(a,b,c)(d,e)表示了置換映射：f(a)=b,f(b)=c,f(c)=a,f(d)=e和f(e)=d。這里循環(a,b,c)周期為3，循環(d,e)周期為2。可以用交叉開關來實現置換，也可以用一次或多次通過多級網絡來實現某些置換，還可用移數或廣播操作實現置換。

?

3. 均勻混洗（shuffle）

??? n=8（對象個數）的均勻混洗所對應的映射如圖6.3.1所示，圖6.3.2為其逆過程。

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

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

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

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

?