計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課件：第7章 互連網(wǎng)絡(luò)

1、第7章 互連網(wǎng)絡(luò)7.1 互連網(wǎng)絡(luò)的基本概念7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用來(lái)實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)中結(jié)點(diǎn)之間的相互連接。結(jié)點(diǎn)：處理器、存儲(chǔ)模塊或其他設(shè)備?；ミB網(wǎng)絡(luò)在系統(tǒng)中的位置，如圖所示。在拓?fù)渖?，互連網(wǎng)絡(luò)為輸入結(jié)點(diǎn)到輸出結(jié)點(diǎn)之間的一組互連或映象。 7.1 互連網(wǎng)絡(luò)的基本概念7.1.1 互連網(wǎng)絡(luò)的功能和特性7.1 互連網(wǎng)絡(luò)的基本概念互連網(wǎng)絡(luò)在系統(tǒng)中的位置7.1 互連網(wǎng)絡(luò)的基本概念可以從4個(gè)不同的方面來(lái)描述互連網(wǎng)絡(luò)定時(shí)方式：有同步和異步兩種。同步系統(tǒng)：使用一個(gè)統(tǒng)一的時(shí)鐘。 SIMD陣列處理機(jī)就屬于這一種類型。異步系統(tǒng)：沒有統(tǒng)一的時(shí)鐘，系統(tǒng)中的各個(gè)處

2、理機(jī)都是獨(dú)立地工作。交換方法：有線路交換和分組交換兩種。線路交換：源結(jié)點(diǎn)和目的結(jié)點(diǎn)之間的物理通路在整個(gè)數(shù)據(jù)傳送期間一直保持連接。分組交換：把信息分割成許多組（又稱為包），將它們分別送入互連網(wǎng)絡(luò)。7.1 互連網(wǎng)絡(luò)的基本概念這些數(shù)據(jù)包可以通過(guò)不同的路徑傳送，到達(dá)目的結(jié)點(diǎn)后再拼合成原來(lái)的數(shù)據(jù)。結(jié)點(diǎn)之間不存在固定連接的物理通路?？刂撇呗裕河屑惺胶头稚⑹絻煞N集中控制方式：有一個(gè)全局的控制器接收所有的通信請(qǐng)求，并由它設(shè)置互連網(wǎng)絡(luò)的開關(guān)連接。分散控制方式：不存在全局的控制器，通信請(qǐng)求的處理和開關(guān)的設(shè)置由互連網(wǎng)絡(luò)分散地進(jìn)行。7.1 互連網(wǎng)絡(luò)的基本概念拓?fù)浣Y(jié)構(gòu)：有靜態(tài)和動(dòng)態(tài)兩種。靜態(tài)拓?fù)浣Y(jié)構(gòu)：在各結(jié)點(diǎn)之間有專

3、用的連接通路，且在運(yùn)行過(guò)程中不能改變。動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)：可根據(jù)需要設(shè)置互連網(wǎng)絡(luò)中的開關(guān)，從而對(duì)結(jié)點(diǎn)之間的連接通路進(jìn)行重新組合，實(shí)現(xiàn)所要求的通信模式。7.1 互連網(wǎng)絡(luò)的基本概念 變量x：輸入（設(shè)x=0，1，N1） 函數(shù)f(x)：輸出 通過(guò)數(shù)學(xué)表達(dá)式建立輸入端與輸出端的一一對(duì)應(yīng)關(guān)系。即在互連函數(shù)f的作用下，輸入端x連接到輸出端f(x)?；ミB函數(shù)反映了網(wǎng)絡(luò)輸入數(shù)組和輸出數(shù)組之間對(duì)應(yīng)的置換關(guān)系或排列關(guān)系。（有時(shí)也稱為置換函數(shù)或排列函數(shù)） 7.1.2 互連函數(shù)7.1 互連網(wǎng)絡(luò)的基本概念互連函數(shù)f(x)有時(shí)可以采用循環(huán)表示 即：（x0 x1 x2 xj-1） 表示： f(x0)=x1，f(x1)=x2，f(x

4、j-1)=x0 j稱為該循環(huán)的長(zhǎng)度。幾種常用的基本互連函數(shù)及其主要特征：交換函數(shù) 交換函數(shù)：實(shí)現(xiàn)二進(jìn)制地址編碼中第k位互反的輸入端與輸出端之間的連接。7.1 互連網(wǎng)絡(luò)的基本概念主要用于構(gòu)造立方體互連網(wǎng)絡(luò)和各種超立方體互連網(wǎng)絡(luò)。它共有nlog2N種互連函數(shù)。 （N為結(jié)點(diǎn)個(gè)數(shù)）當(dāng)N8時(shí)，n3，可得到常用的立方體互連函數(shù)： 7.1 互連網(wǎng)絡(luò)的基本概念變換圖形N=8 的立方體交換函數(shù) 7.1 互連網(wǎng)絡(luò)的基本概念立方體網(wǎng)絡(luò)7.1 互連網(wǎng)絡(luò)的基本概念均勻洗牌函數(shù)均勻洗牌函數(shù)：將輸入端分成數(shù)目相等的兩半，前一半和后一半按類似均勻混洗撲克牌的方式交叉地連接到輸出端（輸出端相當(dāng)于混洗的結(jié)果）。 函數(shù)關(guān)系 即把輸

5、入端的二進(jìn)制編號(hào)循環(huán)左移一位。7.1 互連網(wǎng)絡(luò)的基本概念N=8 的均勻洗牌和逆均勻洗牌函數(shù) N=8 的均勻洗牌和逆均勻洗牌函數(shù)7.1 互連網(wǎng)絡(luò)的基本概念逆均勻洗牌函數(shù)：將輸入端的二進(jìn)制編號(hào)循環(huán)右移一位而得到所連接的輸出端編號(hào)。互連函數(shù) 逆均勻洗牌是均勻洗牌的逆函數(shù) 碟式函數(shù) 蝶式互連函數(shù)：把輸入端的二進(jìn)制編號(hào)的最高位與最低位互換位置，便得到了輸出端的編號(hào)。 7.1 互連網(wǎng)絡(luò)的基本概念反位序函數(shù) 反位序函數(shù)：將輸入端二進(jìn)制編號(hào)的位序顛倒過(guò)來(lái)求得相應(yīng)輸出端的編號(hào)?；ミB函數(shù) 對(duì)于N8的情況，B(x)函數(shù)等于R(x)函數(shù)。7.1 互連網(wǎng)絡(luò)的基本概念N8的蝶式函數(shù)的變換圖形 N=8 的碟式函數(shù)和反位序函

6、數(shù)7.1 互連網(wǎng)絡(luò)的基本概念PM2I函數(shù) PM2I函數(shù)：一種移數(shù)函數(shù)，它是將各輸入端都循環(huán)移動(dòng)一定的位置連到輸出端?；ミB函數(shù) PM2+i(x) x2i mod N PM2-i(x) x2i mod N 其中： 0 xN1，0in1，nlog2N，N為結(jié)點(diǎn)數(shù)。PM2I互連網(wǎng)絡(luò)共有2n個(gè)互連函數(shù)。7.1 互連網(wǎng)絡(luò)的基本概念當(dāng)N8時(shí)，有6個(gè)PM2I函數(shù)：PM2+0 ：（0 1 2 3 4 5 6 7）PM2-0 ：（7 6 5 4 3 2 1 0）PM2+1 ：（0 2 4 6 ）（1 3 5 7）PM2-1 ：（6 4 2 0）（7 5 3 1）PM22：（0 4）（1 5）（2 6）（3 7）

7、7.1 互連網(wǎng)絡(luò)的基本概念N=8 的PM2I函數(shù)陣列計(jì)算機(jī)ILLIAC 采用PM20和PM2n/2構(gòu)成其互連網(wǎng)絡(luò)，實(shí)現(xiàn)各處理單元之間的上下左右互連 。用移數(shù)函數(shù)構(gòu)成ILLIAC 陣列機(jī)的互連網(wǎng)絡(luò)7.1 互連網(wǎng)絡(luò)的基本概念網(wǎng)絡(luò)通常是用有向邊或無(wú)向邊連接有限個(gè)結(jié)點(diǎn)的圖來(lái)表示。互連網(wǎng)絡(luò)的主要特性參數(shù)有：網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(shù)。 表示該網(wǎng)絡(luò)所能連接的部件的數(shù)量。結(jié)點(diǎn)度：與結(jié)點(diǎn)相連接的邊數(shù)（通道數(shù)），包括入度和出度。進(jìn)入結(jié)點(diǎn)的邊數(shù)稱為入度。從結(jié)點(diǎn)出來(lái)的邊數(shù)稱為出度。7.1.3 互連網(wǎng)絡(luò)的特性參數(shù)7.1 互連網(wǎng)絡(luò)的基本概念距離：對(duì)于網(wǎng)絡(luò)中的任意兩個(gè)結(jié)點(diǎn)，從一個(gè)結(jié)點(diǎn)出發(fā)到另一個(gè)結(jié)點(diǎn)終止所需要跨越的邊數(shù)的

8、最小值。網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間距離的最大值。網(wǎng)絡(luò)直徑應(yīng)當(dāng)盡可能地小。結(jié)點(diǎn)之間的線長(zhǎng)：兩個(gè)結(jié)點(diǎn)之間連線的長(zhǎng)度，用米、千米等表示。等分寬度：當(dāng)某一網(wǎng)絡(luò)被切成相等的兩半時(shí)，沿切口的邊數(shù)（通道數(shù)）的最小值稱為通道等分寬度，用b表示。7.1 互連網(wǎng)絡(luò)的基本概念線等分寬度：Bbw其中：w為通道寬度（用位表示）。該參數(shù)主要反映了網(wǎng)絡(luò)最大流量。對(duì)稱性：從任何結(jié)點(diǎn)看到的拓?fù)浣Y(jié)構(gòu)都是相同的網(wǎng)絡(luò)稱為對(duì)稱網(wǎng)絡(luò)。 對(duì)稱網(wǎng)絡(luò)比較容易實(shí)現(xiàn)，編程也比較容易。互連網(wǎng)絡(luò)通?？梢苑譃閮纱箢悾红o態(tài)互連網(wǎng)絡(luò) 各結(jié)點(diǎn)之間有固定的連接通路且在運(yùn)行中不能改變的網(wǎng)絡(luò)。動(dòng)態(tài)互連網(wǎng)絡(luò) 由交換開關(guān)構(gòu)成、可按運(yùn)行程序的要求動(dòng)態(tài)地改變連接狀態(tài)

9、的網(wǎng)絡(luò)。下面介紹幾種靜態(tài)互連網(wǎng)絡(luò)。 （其中：N表示結(jié)點(diǎn)的個(gè)數(shù)） 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)7.2.1 靜態(tài)互連網(wǎng)絡(luò)7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)線性陣列 一種一維的線性網(wǎng)絡(luò)，其中N個(gè)結(jié)點(diǎn)用N-1個(gè)鏈路連成一行。端結(jié)點(diǎn)的度：1其余結(jié)點(diǎn)的度：2直徑：N1等分寬度b=1 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)對(duì)稱結(jié)點(diǎn)的度：2雙向環(huán)的直徑：N/2單向環(huán)的直徑：N 環(huán)和帶弦環(huán) 環(huán) 用一條附加鏈路將線性陣列的兩個(gè)端點(diǎn)連接起來(lái)而構(gòu)成?？梢詥蜗蚬ぷ鳎部梢噪p向工作。7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)帶弦環(huán) 增加的鏈路愈多，結(jié)點(diǎn)度愈高，網(wǎng)絡(luò)直徑就愈小。7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)全連接網(wǎng)絡(luò) 結(jié)點(diǎn)度：15直徑最短，為1。 循環(huán)移數(shù)網(wǎng)絡(luò)通

10、過(guò)在環(huán)上每個(gè)結(jié)點(diǎn)到所有與其距離為2的整數(shù)冪的結(jié)點(diǎn)之間都增加一條附加鏈而構(gòu)成。N=16結(jié)點(diǎn)度：7直徑：2 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)一般地，如果j-i=2r（r=0,1,2,n-1，n=log2N），則結(jié)點(diǎn)i與結(jié)點(diǎn)j連接。結(jié)點(diǎn)度：2n1直徑：n/27.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)樹形和星形 一棵5層31個(gè)結(jié)點(diǎn)的二叉樹 一般說(shuō)來(lái)，一棵k層完全平衡的二叉樹有N=2k-1個(gè)結(jié)點(diǎn)。最大結(jié)點(diǎn)度：3直徑：2(k-1) 星形 結(jié)點(diǎn)度較高，為N1。直徑較小，是一常數(shù)2?？煽啃员容^差，只要中心結(jié)點(diǎn)出故障，整個(gè)系統(tǒng)就會(huì)癱瘓。 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)胖樹形 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)網(wǎng)格形和環(huán)網(wǎng)形 網(wǎng)格形一個(gè)33

11、的網(wǎng)格形網(wǎng)絡(luò)一般來(lái)說(shuō)，N=nk 個(gè)結(jié)點(diǎn)的k維網(wǎng)絡(luò)的內(nèi)部結(jié)點(diǎn)度是2k，網(wǎng)絡(luò)直徑為k(n-1)。 環(huán)形網(wǎng)可看作是直徑更短的另一種網(wǎng)格。 將環(huán)形和網(wǎng)格形組合在一起，并能向高維擴(kuò)展。沿陣列的每行和每列都有環(huán)形連接。一個(gè)nn二元環(huán)網(wǎng)結(jié)點(diǎn)度：4直徑：2n/27.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)超立方體 一種二元n維立方體結(jié)構(gòu)一般來(lái)說(shuō)，一個(gè)二元n維立方體由N=2n 個(gè)結(jié)點(diǎn)組成，它們分布在n維上，每維有兩個(gè)結(jié)點(diǎn)。 例 8個(gè)結(jié)點(diǎn)的3維立方體 4維立方體為實(shí)現(xiàn)一個(gè)n維立方體，只要把兩個(gè)（n1）維立方體中相對(duì)應(yīng)的結(jié)點(diǎn)用鏈路連接起來(lái)即可。共需要2n-1條鏈路。n維立方體中結(jié)點(diǎn)的度都是n，直徑也是n。 7.2

12、互連網(wǎng)絡(luò)的結(jié)構(gòu)靜態(tài)互連網(wǎng)絡(luò)一覽表 網(wǎng)絡(luò)類型 結(jié)點(diǎn)度d 網(wǎng)絡(luò)直徑D 鏈路數(shù)l 等分寬度B 對(duì)稱性 網(wǎng)絡(luò)規(guī)格說(shuō)明 線線陣列 2 N-1 N-1 1非 N個(gè)結(jié)點(diǎn) 環(huán)形 2 N/2 N2是 N個(gè)結(jié)點(diǎn) 全連接 N-1 1N(N-1)/2 (N/2)2 是 N個(gè)結(jié)點(diǎn) 二叉樹 3 2(h-1) N-1 1非 樹高h(yuǎn)=log2N 星形 N-1 2N-1 N/2非 N個(gè)結(jié)點(diǎn) 2D網(wǎng)格 4 2(r-1) 2N-2r r非 rr網(wǎng)格， Illiac網(wǎng) 4 r-12N2r非 與 的帶弦環(huán)等效 2D環(huán)網(wǎng) 4 2r/2 2N2r是 rr網(wǎng)格，超立方體 n n nN/2 N/2是 N個(gè)結(jié)點(diǎn)n=log2NCCC 3 2k-1

13、+k/2 3N/2 N/(2k) 是 N=k2k結(jié)點(diǎn)環(huán)長(zhǎng)k3 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)總線一組導(dǎo)線和插座，用于進(jìn)行與總線相連的處理機(jī)、存儲(chǔ)模塊和外圍設(shè)備等之間的數(shù)據(jù)傳送。每一次總線只能用于一個(gè)源（主部件）到一個(gè)或多個(gè)目的（從部件）之間的數(shù)據(jù)傳送。多個(gè)功能模塊之間的爭(zhēng)用總線或時(shí)分總線。 特點(diǎn)價(jià)格低帶寬較窄7.2.2 動(dòng)態(tài)互連網(wǎng)絡(luò)7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)一種由總線連接的多處理機(jī)系統(tǒng) 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)多級(jí)互連網(wǎng)絡(luò)MIMD和SIMD計(jì)算機(jī)都使用多級(jí)互連網(wǎng)絡(luò)MIN（Multistage Interconnection Network）一種通用的多級(jí)互連網(wǎng)絡(luò) 由ab開關(guān)模塊和級(jí)間連接構(gòu)成的通用多級(jí)互連網(wǎng)

14、絡(luò)結(jié)構(gòu)每一級(jí)都用了多個(gè)ab開關(guān)a個(gè)輸入和b個(gè)輸出在理論上，a和b不一定相等，然而實(shí)際上a和b經(jīng)常選為2的整數(shù)冪，即ab2k，k1。 相鄰各級(jí)開關(guān)之間都有固定的級(jí)間連接7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)幾種常用的開關(guān)模塊 模塊大小 合法狀態(tài) 置換連接 22 4 244 2562488 16 777 21640 320nn nn n! 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)最簡(jiǎn)單的開關(guān)模塊：22開關(guān) 22開關(guān)的4種連接方式 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)各種多級(jí)互連網(wǎng)絡(luò)的區(qū)別在于所用開關(guān)模塊、控制方式和級(jí)間互連模式的不同?？刂品绞剑簩?duì)各個(gè)開關(guān)模塊進(jìn)行控制的方式。級(jí)控制：每一級(jí)的所有開關(guān)只用一個(gè)控制信號(hào)控制，只能

15、同時(shí)處于同一種狀態(tài)；單元控制：每一個(gè)開關(guān)都有一個(gè)獨(dú)立的控制信號(hào)，可各自處于不同的狀態(tài)；部分級(jí)控制：第i級(jí)的所有開關(guān)分別用i1個(gè)信號(hào)控制，0in1，n為級(jí)數(shù)。 常用的級(jí)間互連模式：均勻洗牌、蝶式、多路洗牌、縱橫交叉、立方體連接等 7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)兩種多級(jí)互連網(wǎng)絡(luò) Omega網(wǎng)絡(luò) 88的Omega網(wǎng)絡(luò)7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)一個(gè)N輸入的Omega網(wǎng)絡(luò)有l(wèi)og2N級(jí)，每級(jí)用N/2個(gè)22開關(guān)模塊，共需要Nlog2N/2個(gè)開關(guān)。每個(gè)開關(guān)模塊均采用單元控制方式。不同的開關(guān)狀態(tài)組合可實(shí)現(xiàn)各種置換、廣播或從輸入到輸出的其他連接。7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)多級(jí)立方體網(wǎng)絡(luò) 采用二功能（直送和交換）的22開關(guān)和交換

16、函數(shù)構(gòu)成級(jí)間互連按從左到右的次序分別是C0、C1、C2互連函數(shù)例如： 當(dāng)所有開關(guān)都直送時(shí)，實(shí)現(xiàn)恒等變換； 當(dāng)A、B、C、D四個(gè)開關(guān)交換、其余直送時(shí)，實(shí)現(xiàn)C0互連函數(shù)； 當(dāng)E、F、G、H四個(gè)開關(guān)交換、其余直送時(shí)，實(shí)現(xiàn)C1互連函數(shù)； 當(dāng)I、J、K、L四個(gè)開關(guān)交換、其余直送時(shí)，實(shí)現(xiàn)C2互連函數(shù)。7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)多級(jí)立方體網(wǎng)絡(luò)7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)通過(guò)選擇不同的控制方式，可以構(gòu)成不同的互連網(wǎng)絡(luò)。 例如：采用以下3種不同的控制方式可以構(gòu)成3種不同的互連網(wǎng)絡(luò)： 級(jí)控制：構(gòu)成交換網(wǎng)； 部分級(jí)控制：構(gòu)成移數(shù)網(wǎng)； 單元控制：構(gòu)成間接二進(jìn)制n方體網(wǎng)。7.2 互連網(wǎng)絡(luò)的結(jié)構(gòu)交叉開關(guān)網(wǎng)絡(luò) 單級(jí)開關(guān)網(wǎng)絡(luò) 交叉點(diǎn)開關(guān)能在對(duì)偶（源、目的）之間形成動(dòng)態(tài)連接，同時(shí)實(shí)現(xiàn)多個(gè)對(duì)偶之間的無(wú)阻塞連接。 帶寬和互連特性最好。 一個(gè)nn的交叉開關(guān)網(wǎng)絡(luò)，可以無(wú)阻塞地實(shí)現(xiàn)n!種置換。 C.mmp多處理機(jī)的互連結(jié)構(gòu)（一種