,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,第六章 互聯(lián)網(wǎng)絡(luò),互連網(wǎng)絡(luò)的作用,用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件之間的相互連接。,互連網(wǎng)絡(luò)已成為并行處理系統(tǒng)的核心組成部分。,互連網(wǎng)絡(luò)對整個(gè)計(jì)算機(jī)系統(tǒng)的性能價(jià)格比有著決定性的影響。,一個(gè)例子：具有本地存儲器、私有高速緩存、共享存儲器和共享外圍設(shè)備的一般處理機(jī)系統(tǒng)的互連結(jié)構(gòu),磁盤,SM,1,SM,2,SM,m,PMN,C,n,P,n,LM,C,1,P,1,LM,PCN,PION,磁帶,打印機(jī),終端,網(wǎng)絡(luò),(共享存儲器),(共享I/O與外設(shè)),互連網(wǎng)絡(luò)通常是用有向邊或無向邊連接有限個(gè)結(jié)點(diǎn)的組成?；ミB網(wǎng)絡(luò)的主要特性有：,(1),網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(shù),(2),結(jié)點(diǎn)度：與結(jié)點(diǎn)相連接的邊數(shù)稱為結(jié)點(diǎn)度,進(jìn)入結(jié)點(diǎn)的邊數(shù)叫入度,從結(jié)點(diǎn)出來的邊數(shù)則叫出度,(3),距離：兩個(gè)結(jié)點(diǎn)之間相連的最少邊數(shù),(4),網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)間距離的最大值。用結(jié)點(diǎn)間的連接邊數(shù)表示,互連網(wǎng)絡(luò)的特性,互連網(wǎng)絡(luò)的性能參數(shù),發(fā)送方的步驟如下：,(1),用戶程序把要發(fā)送的數(shù)據(jù)拷貝到系統(tǒng)緩沖區(qū)。,(2),緩沖區(qū)中的數(shù)據(jù)打包并發(fā)送到網(wǎng)絡(luò)接口部件。,(3),網(wǎng)絡(luò)接口硬件開始發(fā)送消息。,數(shù)據(jù)包的接收步驟如下：,(1),把數(shù)據(jù)包從網(wǎng)絡(luò)接口部件拷貝到系統(tǒng)緩沖區(qū)。,(2),檢查收到的數(shù)據(jù)包，如果正確，發(fā)回答信號。,(3),把接收到的數(shù)據(jù)拷貝到用戶地址空間。,發(fā)送方接收到回答信號后釋放系統(tǒng)緩沖區(qū),互連網(wǎng)絡(luò)的主要性能參數(shù)：,(1),頻帶寬度,(Bandwidth),：傳輸信息的最大速率,(2),傳輸時(shí)間,(Transmission time),：等于消息長度除以頻寬。,(3),飛行時(shí)間,(Time of flight),：第一位信息到達(dá)接收方所花費(fèi)的時(shí)間。,(4),傳輸時(shí)延,(Transport latency),：等于飛行時(shí)間與傳輸時(shí)間之和。,(5),發(fā)送方開銷,(Sender overhead),：處理器把消息放到互連網(wǎng)絡(luò)的時(shí)間。,(6),接收方開銷,(Receiver overhead),：處理器把消息從網(wǎng)絡(luò)取出來的時(shí)間。,一個(gè)消息的總時(shí)延可以用下面公式表示：,總時(shí)延發(fā)送方開銷飛行時(shí)間 消息長度,/,頻寬接收方開銷,例,7.1,：假設(shè)一個(gè)網(wǎng)絡(luò)的頻寬為,10Mb/S,，發(fā)送方開銷為,230us,，接收方開銷分別為,270us,。如果兩臺機(jī)器相距,100,米，現(xiàn)在要發(fā)送一個(gè),1000,字節(jié)的消息給另一臺機(jī)器，試計(jì)算總時(shí)延。如果兩臺機(jī)器相距,1000,公里，那么總時(shí)延為多大？,解：光的速度為,299792.5KM/S,，信號在導(dǎo)體中傳遞速度大約是光速的,50,。,相距,100,米時(shí)總時(shí)延為：,相距,1000,公里時(shí)的總時(shí)延為：,為了在輸入結(jié)點(diǎn)與輸出結(jié)點(diǎn)之間建立對應(yīng)關(guān)系，互連網(wǎng)絡(luò)有三種表示方法：,(1),互連函數(shù)表示法：如：,f(x,n-1,x,1,x,0,)=x,0,x,n-2,x,1,x,n-1,(2),圖形表示法,(3),輸入輸出對應(yīng)表示法,互連網(wǎng)絡(luò),0,0,1,1,n-1,n-1,輸入,:0 1 2 3 4 5 6 7,輸出,:1 0 3 2 5 4 7 6,互連網(wǎng)絡(luò)的表示方法,互連函數(shù),互連函數(shù)也稱為互連置換或互連排列等。,1.,交換函數(shù)（,Exchange,）,當(dāng),n,3,時(shí)，有,3,種函數(shù)，每種能表示,8,個(gè)結(jié)點(diǎn)之間的連接關(guān)系。,由于交換函數(shù)主要用于,超立方體互連網(wǎng),中，因此也稱為超立方體函數(shù)，用,Cube,表示，如：,Cube0,、,Cube1,、,Cube2,等。,2.,全混洗函數(shù)（,Perfect shuffle,）,函數(shù)關(guān)系：把二進(jìn)制結(jié)點(diǎn)號循環(huán)左移一位,子混洗,(subshuffle)S,(k),最低,k,位循環(huán)左移一位,超混洗,(supershuffle)S,(k),最高,k,位循環(huán)左移一位,3.,蝶式函數(shù)（,Butterfly,）,蝶式函數(shù)的名稱來自于,FFT,變換時(shí)的圖形，如蝴蝶式樣。函數(shù)關(guān)系：將輸入端二進(jìn)制結(jié)點(diǎn)號的最高位和最低位互換位置。,子蝶式,(subbutterfly)B,(k),最低,k,位的,高低位互換,超蝶式,(superbutterfly)B,(k),最高,k,位的,高低互換,顯然成立：,4.,反位序函數(shù)（,Bit Reversal,）,函數(shù)關(guān)系：將二進(jìn)制自變量的位序反過來。,子反位序函數(shù)，,最低,k,位的,位序反過來,超反位序函數(shù)，,最高,k,位的,位序反過來,5.,移數(shù)函數(shù),函數(shù)關(guān)系：將輸入端向量循環(huán)移動(dòng)一定的位置,經(jīng)常取,r,2,i,，因此移數(shù)函數(shù)又稱為加減,2,i,函數(shù)、,PM2I,函數(shù)等。,子移數(shù)函數(shù)：,其中：,0,x,N-1,，,0,i,k,n-1,，,n=log,2,N,。,Illiac,函數(shù)包含,PM2,0,和,PM2,n/2,等,4,個(gè)互連函數(shù),每個(gè)接點(diǎn)與它的上下左右,4,個(gè)相鄰接點(diǎn)連接,例,6.2,：假設(shè),16,個(gè)處理機(jī)的編號分別為,0,、,1,、,、,15,，采用單級互連網(wǎng)絡(luò)?；ミB函數(shù)分別為：,(1)Cube3,(2)PM2+3,(3)PM2-0,(4)Shuffle,(5)Butterfly,(6)Reversal,第,12,號處理機(jī)分別與哪一個(gè)處理機(jī)相連？,解：,(12),10,=(1100),2,(1)Cube3,，,(2)PM2+3,，,(3)PM2-0,，,(4)Shuffle,，,(5)Butterfly,，,(6)Reversal,1100,最高位取反得,0100,，,4,號處理機(jī),(12+8)MOD 16=4,，,4,號處理機(jī),12 1=11,，,11,號處理機(jī),1100,循環(huán)左移,1,位得到,1001,9,號處理機(jī),1100,的最高最低位交換,0101,5,號處理機(jī),1100,的位序反過來為,0011,3,號處理機(jī),補(bǔ)充,:,基本的單級互連網(wǎng)絡(luò),1.,立方體單級網(wǎng)絡(luò),立方體的每個(gè)頂點(diǎn)代表一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的編號用二進(jìn)制碼（,C,2,C,1,C,0,）表示。,N,8,的三維立方體結(jié)構(gòu),立方體單級網(wǎng)絡(luò)的互連函數(shù)實(shí)現(xiàn)二進(jìn)制編號中第,k,位值不同的結(jié)點(diǎn)之間的連接。故三維的立方體單級網(wǎng)絡(luò)有三種互連函數(shù)：,Cube,0,、,Cube,1,和,Cube,2,，分別建立結(jié)點(diǎn)編號中,C,0,不同或,C,1,不同或,C,2,不同的結(jié)點(diǎn)之間的連結(jié)。,N,8,的三維立方體三種互連方式,一般情況下，一個(gè),n,維立方體有,N,2,n,個(gè)結(jié)點(diǎn)，共有,n,種互連函數(shù)，分別由,n,位編號中的每一位的位值求反來確定。當(dāng)維數(shù),n,3,時(shí)，稱為超立方體,(Hyper Cube),網(wǎng)絡(luò)。對于,n,維立方體單級網(wǎng)絡(luò)，要實(shí)現(xiàn)任意兩個(gè)結(jié)點(diǎn)之間的連接，最多需使用,n,次不同的互連函數(shù) 因此,n,維立方體單級網(wǎng)絡(luò)的最大距離為,n,。,2,PM2I,（是加減,2,i,的簡稱，,plus,minus2,i,）,PM2I,單級網(wǎng)絡(luò)能實(shí)現(xiàn),j,號結(jié)點(diǎn)與,j,2,i,mod,N,號結(jié)點(diǎn)的直接相連，,N,為處理器的個(gè)數(shù)，,n,log,2,N,。因此，它共有,2,n,個(gè)互連函數(shù)，即,PM2,i,（,j,）,j,2,i,mod,N,PM2,i,（,j,）,j,2,i,mod,N,式中，,0,j,N,1,，,0,i,n,1,。,設(shè),N,8,，則各互連循環(huán)為,PM2,0,：（,01234567,）,PM2,0,：（,76543210,）,PM2,1,：（,0246,）（,1357,）,PM2,1,：（,6420,）（,7531,）,PM2,2,：（,04,）（,15,）（,26,）（,37,）,N,8,的,PM2I,互連網(wǎng)絡(luò)的部分連接圖,網(wǎng)絡(luò)的最大距離為,n/2,=,log2,N,/2,，這里,表示向上取整。由三維,PM2I,互連網(wǎng)絡(luò)可以看出，最多只要兩次使用，即可實(shí)現(xiàn)任意一對入出端號間的連接。,PM2I,互連特性,3.,混洗交換,(shuffle exchange),混洗交換互連網(wǎng)絡(luò)包含全混洗和交換兩種互連函數(shù)。,（,1,）全混洗,全混洗的互連函數(shù)為,Shuffle,（,P,n,1,P,n,2,P,1,P,0,）,P,n,2,P,1,P,0,P,n,1,全混洗互連示意圖,（,2,）交換,由于單一的全混洗互連網(wǎng)絡(luò)不能實(shí)現(xiàn)二進(jìn)制編號為全“,0”,和全“,1”,的結(jié)點(diǎn)與其他任何結(jié)點(diǎn)的連接，所以又增加了,Cube,0,交換互連函數(shù)。同時(shí)采用了全混洗和交換的單級互連網(wǎng)絡(luò)稱為混洗交換單級互連網(wǎng)絡(luò)。,N,8,的全混交換互連網(wǎng)絡(luò)連接圖,在混洗交換網(wǎng)絡(luò)中，最遠(yuǎn)的兩個(gè)入出端號是全“,0”,和全“,1”,，它們的連接需要,n,次交換和,n-1,次混洗，所以其最大距離為,2n-1,。,互連網(wǎng)絡(luò)的種類,靜態(tài)互連網(wǎng)絡(luò),循環(huán)互連網(wǎng)絡(luò),多級互連網(wǎng)絡(luò),靜態(tài)互連網(wǎng)絡(luò)：在各結(jié)點(diǎn)之間有固定的連接通路，在運(yùn)行過程中不能改變。一般不能實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。,循環(huán)互連網(wǎng)絡(luò)：通過多次重復(fù)使用同一個(gè)單級互連網(wǎng)絡(luò)以實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。,多級互連網(wǎng)絡(luò)：將多套相同的單級互連網(wǎng)絡(luò)連接起來，實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連，是動(dòng)態(tài)互連網(wǎng)絡(luò)的一種，適用于,SIMD,和,MIMD,。,靜態(tài)互連網(wǎng)絡(luò),在各結(jié)點(diǎn)之間有固定的連接通路，在運(yùn)行過程中不能改變的網(wǎng)絡(luò)結(jié)構(gòu)。,一般靜態(tài)互連網(wǎng)絡(luò)不能實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。,一維的有線性陣列結(jié)構(gòu)；二維的有環(huán)形、星形、樹形、網(wǎng)格形等；三維的有立方體等；三維以上的有超立方體等。,循環(huán)互連網(wǎng)絡(luò),一般靜態(tài)互連網(wǎng)不能實(shí)現(xiàn)任意兩結(jié)點(diǎn)之間的互連。有兩種解決辦法：,循環(huán)互連網(wǎng)：多次重復(fù)使用同一個(gè)單級互連網(wǎng)絡(luò),多級互連網(wǎng)：將多套相同的單級互連網(wǎng)絡(luò)連接起來,前一種方法是犧牲時(shí)間換取設(shè)備，后一種方法是以設(shè)備換取時(shí)間。,多級互連網(wǎng)絡(luò),多級網(wǎng)絡(luò)互連是將多套單級互連網(wǎng)絡(luò)通過關(guān)模塊串連擴(kuò)展成多級互連網(wǎng)絡(luò)（簡稱,MIN,）的方式。與單級網(wǎng)絡(luò)相比，多級網(wǎng)絡(luò)可以通過改變開關(guān)的控制方式靈活地實(shí)現(xiàn)各種連接，滿足系統(tǒng)應(yīng)用的需要。,多級互連網(wǎng)絡(luò)采用多個(gè)相同的或不同的單級互連網(wǎng)絡(luò)直接連接起來。一個(gè)時(shí)鐘周期就能夠?qū)崿F(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。,常見的有多級立方體互連網(wǎng)絡(luò)、多級混洗交換網(wǎng)絡(luò)（,Omega,網(wǎng)絡(luò)）、多級,PM2I,網(wǎng)絡(luò)、多級,BENES,可重排網(wǎng)絡(luò)及多級,CLOS,網(wǎng)絡(luò)等。,多級互連網(wǎng)絡(luò)采用的關(guān)鍵技術(shù)：,(1),交換開關(guān)，,(2),交換開關(guān)之間的拓?fù)溥B接，,(3),對交換開關(guān)的不同控制方式。,1.,交換開關(guān),一個(gè),a,b,交換開關(guān)有,a,個(gè)輸入和,b,個(gè)輸出。最常用的二元開關(guān)：,a=b=2,。,每個(gè)輸入可與一個(gè)或多個(gè)輸出相連，但是在輸出端必須避免發(fā)生沖突。一對一和一對多映射是容許的；但不容許有多對一映射。,只容許一對一映射時(shí)稱為置換連接，稱這種開關(guān)為交叉開關(guān)。,具有直通和交換兩種功能的開關(guān)稱為二功能開關(guān)，或交換開關(guān)。用一位控制信號控制。,具有所有,4,種功能的交換開關(guān)稱為四功能開關(guān)，用兩位控制信號控制。,交換開關(guān)的四種功能,2.,拓?fù)浣Y(jié)構(gòu),又稱為級間連接模式,ISC(interstage connection),，是前一級交換開關(guān)的輸出端與后一級交換開關(guān)的輸入端之間的連接模式稱為拓?fù)浣Y(jié)構(gòu)。,級間連接是固定的，可以用互連函數(shù)表示級間連接模式。常用的級間連接模式包括混洗、交叉、立方體連接等，從而構(gòu)成具有不同連接特性的多級互連網(wǎng)絡(luò)。,3.,控制方式,控制方式是指通過對開關(guān)模塊的狀態(tài)控制來實(shí)現(xiàn)多級網(wǎng)絡(luò)間互連要求的方式，稱之為互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可動(dòng)態(tài)重構(gòu)。有多級交換開關(guān)，每一級又有多個(gè)交換開關(guān)。,通常有三種控制方式,級控制：同一級交換開關(guān)使用同一個(gè)控制信號控制。,單元級控制：每個(gè)交換開關(guān)分別控制。,部分級控制：第,i,級使用,i+1,個(gè)控制信號控制（,0,i,n-1,）。,同一個(gè)多級互連網(wǎng)絡(luò)分別常用三種不同的控制方式，可以構(gòu)成三種不同的互連網(wǎng)絡(luò)。,4.,多級立方體網(wǎng)絡(luò),是將,Cube0,、,Cube1,和,Cube2,三種函數(shù)構(gòu)成的單級網(wǎng)絡(luò)串接起來，是一種,STARAN,網(wǎng)絡(luò)。使用二功能交換開關(guān)，即直通和交換，分級控制，可實(shí)現(xiàn)交換網(wǎng)絡(luò)功能。采用不同方式控制，可實(shí)現(xiàn)不同連通功能。即當(dāng)?shù)?i,級控制信號為,0,