互連網(wǎng)絡(luò)的基本概念課件

互連網(wǎng)絡(luò)的基本概念互聯(lián)網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用來(lái)實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件之間的相互連接和信息交換。硬件接口軟件接口硬件接口軟件接口硬件接口軟件接口硬件接口軟件接口…互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)的基本概念互聯(lián)網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)溆?SM1SM2SMm…IPMNP1PnIPCNPIONCnLMC1LM…………磁帶部件磁盤部件打印機(jī)終端網(wǎng)絡(luò)···IPMN：處理機(jī)-存儲(chǔ)器網(wǎng)絡(luò)IPCN：處理機(jī)間網(wǎng)絡(luò)PION：處理機(jī)-I/O網(wǎng)絡(luò)P：處理機(jī)SM：共享存儲(chǔ)器LM：本地存儲(chǔ)器C：高速緩沖存儲(chǔ)器一般多處理機(jī)系統(tǒng)的互連結(jié)構(gòu)SM1SM2SMm…IPMNP1PnIPCNPIONCnLM2互連函數(shù)互連函數(shù)f(x)表示互連網(wǎng)絡(luò)的輸出端號(hào)和輸入端號(hào)之間的對(duì)應(yīng)關(guān)系若x與f(x)是一對(duì)一的，則稱為置換連接若一個(gè)x對(duì)應(yīng)多個(gè)f(x)，則稱為播送連接互連函數(shù)互連函數(shù)f(x)表示互連網(wǎng)絡(luò)的輸出端號(hào)和3互連函數(shù)的表示方法：函數(shù)表示法輸入輸出對(duì)表示法01N-1f(0)f(1)f(N-1)……互連函數(shù)的表示方法：01N-1f(0)f(1)f(N-1)…4圖形表示法用輸入輸出的連線圖表示變換關(guān)系循環(huán)互連函數(shù)表示法

f(x0)=x1

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

(x0x1x2…xj)j+1稱為循環(huán)長(zhǎng)度圖形表示法循環(huán)互連函數(shù)表示法5基本互連函數(shù)恒等置換I(xn-1xn-2…x1x0)=xn-1xn-2…x1x00123456701234567n=3，N=8的恒等置換基本互連函數(shù)恒等置換I(xn-1xn-2…x1x0)6交換置換E(xn-1xn-2…x1x0)=xn-1xn-2…x1x00123456701234567n=3，N=8的交換置換交換置換E(xn-1xn-2…x1x0)=xn-1x7方體置換Ck(xn-1xn-2…xk+1xkxk-1…x1x0)=xn-1xn-2…xk+1xkxk-1…x1x0將2n個(gè)輸入端和輸出端均分為2n-k組，每組2k個(gè)。每相鄰兩組輸入與相應(yīng)兩組輸出交叉對(duì)應(yīng)。C0(x2x1x0)=x2x1x0C1(x2x1x0)=x2x1x0C2(x2x1x0)=x2x1x0方體置換Ck(xn-1xn-2…xk+1xkxk-18012345670123456701234567012345670123456701234567n=3，N=8的方體置換C0方體置換C1方體置換C2方體置換0123456701234567012345670123459均勻洗牌置換σ(xn-1xn-2…xk+1xkxk-1…x1x0)=xn-2xn-3…xk+1xkxk-1…x1x0xn-1將2n個(gè)輸入端分為前后兩半，前一半與偶數(shù)輸出端依次相連，后一半與奇數(shù)輸出端依次相連。將輸出端序列分為前后兩組，每組輪流出牌所得序列即輸入端序列。040123456715263701234567891011121314150819210311412513614715均勻洗牌置換σ(xn-1xn-2…xk+1xkxk-10子洗牌置換σ(k)(xn-1xn-2…xk+1xkxk-1…x1x0)=xn-1xn-2…xk+1xk-1…x1x0xk將2n個(gè)輸入端分為2n-k-1組，每2k+1個(gè)輸入為一組，組內(nèi)進(jìn)行均勻洗牌置換子洗牌置換σ(k)(xn-1xn-2…xk+1xkx11超洗牌置換σ(k)(xn-1xn-2…xn-kxn-k-1xn-k-2…x1x0)=xn-2…xn-kxn-k-1xn-1…x1x0xkσ(n-1)(x)=σ(n-1)(x)=σ(x)σ(0)(x)=σ(0)(x)=x將2n個(gè)輸入端分為2n-k-1組，低n-k-1位完全相同的輸入為一組，組內(nèi)進(jìn)行均勻洗牌置換超洗牌置換σ(k)(xn-1xn-2…xn-kxn-k120123456701234567012345670123456701234567012345670123456701234567均勻洗牌置換σ子洗牌置換σ(1)超洗牌置換σ(1)逆均勻洗牌置換σ-1n=3，N=8的洗牌置換01234567012345670123456701234513逆洗牌置換σ-1(xn-1xn-2…xk+1xkxk-1…x1x0)=x0xn-1xn-2xn-3…xk+1xkxk-1…x1

將偶數(shù)輸入端與前一半輸出端依次相連，將奇數(shù)輸入端與后一半輸出端依次相連。將輸入端序列分為前后兩組，每組輪流出牌所得序列即輸出端序列。040123456715263701234567891011121314150819210311412513614715逆洗牌置換σ-1(xn-1xn-2…xk+1xkxk14蝶式置換β(xn-1xn-2…xk+1xkxk-1…x1

x0)=x0xn-2…xk+1xkxk-1…x1

xn-1子蝶式置換β(k)(xn-1xn-2…xk+1

xkxk-1…x1

x0)=xn-1xn-2…xk+1

x0xk-1…x1

xk蝶式置換連接中共有2n-1個(gè)恒等連接，2n-2對(duì)交叉連接。對(duì)于前一半輸入端的偶數(shù)部分進(jìn)行恒等連接，奇數(shù)部分對(duì)應(yīng)后一半輸出端的偶數(shù)部分。對(duì)于后一半輸入端的奇數(shù)部分進(jìn)行恒等連接，偶數(shù)部分對(duì)應(yīng)前一半輸出端的奇數(shù)部分。蝶式置換β(xn-1xn-2…xk+1xkxk-115012345670123456701234567012345670123456701234567蝶式置換β子蝶式置換β(1)超蝶式置換β

(1)n=3，N=8的蝶式置換β(n-1)(x)=β(n-1)(x)=β(x)β(0)(x)=β(0)(x)=x01234567012345670123456701234516超蝶式置換β(k)(xn-1xn-2…xn-k

xn-k-1xn-k-2…x1x0)=xn-k-1xn-2…xn-k

xn-1xn-k-2…x1x0子蝶式置換連接中共有2n-1個(gè)恒等連接，2n-2對(duì)交叉連接。共分為2n-k-1組，每2k+1個(gè)輸入/輸出端為一組，組內(nèi)進(jìn)行蝶式置換超蝶式置換連接中共有2n-1個(gè)恒等連接，2n-2對(duì)交叉連接。共分為2n-k-1組，低n-k-1位相同的為一組超蝶式置換β(k)(xn-1xn-2…xn-kxn-k17位序顛倒置換ρ(xn-1xn-2…xk+1xkxk-1…x1x0)=x0x1…xk-1xkxk+1…xn-2xn-1對(duì)于輸入x=0或2n-1，輸出仍為x，即恒等連接子位序顛倒置換ρ(k)(xn-1xn-2…xk+1xkxk-1…x1x0)=xn-1xn-2…xk+1x0x1…xk-1xk超位序顛倒置換ρ(k)(xn-1xn-2…xn-kxn-k-1xn-k-2…x1x0)=xn-k-1xn-k…xn-2xn-1xn-k-2…x1x0ρ(n-1)(x)=ρ

(n-1)(x)=ρ

(x)ρ(0)(x)=ρ

(0)(x)=x位序顛倒置換ρ(xn-1xn-2…xk+1xkxk-18012345670123456701234567012345670123456701234567位序顛倒置換ρ子位序顛倒置換ρ(1)超位序顛倒置換ρ

(1)n=3，N=8的位序顛倒置換01234567012345670123456701234519移數(shù)置換α(x)=(x±k)modN0≤x<N1≤k<N

組內(nèi)移數(shù)置換α(x)(n-1):r=(x)(n-1):r

α(x)(r-1):0=((x)(r-1):0

±k)mod2r

共分為2n-r組，組內(nèi)進(jìn)行循環(huán)移數(shù)置換加減2I置換PM2+i(x)=(x+2i)modN0≤x<N0≤

i<n

PM2-i(x)=(x-2i)modN0≤x<N0≤

i<n

1≤k<2r1≤r≤

nα(n)(x)=α(x)

移數(shù)置換α(x)=(x±k)modN0≤x<N20012345670123456701234567012345670123456701234567左移移數(shù)置換k=2n=3，N=8的移數(shù)置換0123456701234567右移移數(shù)置換k=2組內(nèi)左移移數(shù)置換k=1r=2組內(nèi)右移移數(shù)置換k=1r=201234567012345670123456701234521左移移數(shù)置換k=2(0246)(1357)右移移數(shù)置換k=2(6420)(7531)組內(nèi)左移移數(shù)置換k=1r=2(0123)(4567)組內(nèi)右移移數(shù)置換k=1r=2(3210)(7654)PM2+0=(01234567)PM2-0=(76543210)PM2+1=(0246)(1357)PM2-1=(6420)(7531)PM2+2=(04)(15)(26)(37)PM2-2=(40)(51)(62)(73)左移移數(shù)置換k=2(0246)(13522012345670123456701234567012345670123456701234567i=0n=3，N=8的加減2I置換i=+1i=+201234567012345670123456701234523互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)

網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)。表示網(wǎng)絡(luò)所能連接的部件個(gè)數(shù)。

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

一個(gè)結(jié)點(diǎn)射入或射出的邊數(shù)。在單向網(wǎng)絡(luò)中，入射邊的數(shù)目稱為入度，出射邊的數(shù)目稱為出度。結(jié)點(diǎn)度為入度和出度之和。在無(wú)向網(wǎng)絡(luò)中，結(jié)點(diǎn)度為與結(jié)點(diǎn)相連的邊數(shù)?；ミB網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)與性能指標(biāo)互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)網(wǎng)絡(luò)規(guī)模24

結(jié)點(diǎn)距離兩結(jié)點(diǎn)間相連的最少邊數(shù)。

網(wǎng)絡(luò)直徑互連網(wǎng)絡(luò)中任意兩結(jié)點(diǎn)間距離的最大值。

網(wǎng)絡(luò)對(duì)剖寬度一個(gè)網(wǎng)絡(luò)被切分為結(jié)點(diǎn)數(shù)相等的兩半時(shí)，沿切口的最少邊數(shù)。結(jié)點(diǎn)距離網(wǎng)絡(luò)直徑網(wǎng)絡(luò)對(duì)剖寬度25

網(wǎng)絡(luò)對(duì)稱性若從網(wǎng)絡(luò)的任意結(jié)點(diǎn)來(lái)看，網(wǎng)絡(luò)的結(jié)構(gòu)都是相同的，則稱該網(wǎng)絡(luò)是對(duì)稱網(wǎng)絡(luò)。

網(wǎng)絡(luò)可擴(kuò)展性在網(wǎng)絡(luò)拓?fù)湫阅鼙３植蛔兊那闆r下，可擴(kuò)充結(jié)點(diǎn)的能力。網(wǎng)絡(luò)對(duì)稱性網(wǎng)絡(luò)可擴(kuò)展性26互連網(wǎng)絡(luò)的傳輸性能參數(shù)AB機(jī)器A機(jī)器B機(jī)器A發(fā)送數(shù)據(jù)的步驟：機(jī)器A應(yīng)用程序待發(fā)送數(shù)據(jù)機(jī)器A操作系統(tǒng)緩沖區(qū)機(jī)器A操作系統(tǒng)根據(jù)要發(fā)送的數(shù)據(jù)計(jì)算檢查和，并把它放在消息中，同時(shí)啟動(dòng)超時(shí)計(jì)數(shù)器機(jī)器A操作系統(tǒng)緩沖區(qū)網(wǎng)絡(luò)接口硬件消息互連網(wǎng)絡(luò)的傳輸性能參數(shù)AB機(jī)器A機(jī)器B機(jī)器A發(fā)送數(shù)據(jù)的步驟27若收到機(jī)器B的回答信號(hào)則釋放緩沖區(qū)中消息；若超時(shí)計(jì)數(shù)器超時(shí)還未收到回答信號(hào)則重發(fā)消息操作系統(tǒng)通知硬件開始發(fā)送消息等待來(lái)自機(jī)器B的回應(yīng)若收到機(jī)器B的回答信號(hào)則釋放緩沖區(qū)中消息；操作系統(tǒng)通知硬件開28機(jī)器B接收數(shù)據(jù)的步驟：網(wǎng)絡(luò)接口硬件機(jī)器B操作系統(tǒng)緩沖區(qū)消息機(jī)器B操作系統(tǒng)根據(jù)接收到的數(shù)據(jù)計(jì)算檢查和。若計(jì)算出的檢查和與發(fā)送過(guò)來(lái)的匹配，向接收方發(fā)出回答信號(hào)；若不匹配，則刪除消息若數(shù)據(jù)通過(guò)檢查：機(jī)器B操作系統(tǒng)緩沖區(qū)數(shù)據(jù)用戶地址空間啟動(dòng)應(yīng)用程序繼續(xù)執(zhí)行機(jī)器B接收數(shù)據(jù)的步驟：網(wǎng)絡(luò)接口硬件機(jī)器B操作系統(tǒng)緩沖區(qū)消息機(jī)29

頻寬

互連網(wǎng)絡(luò)傳輸信息的最大速率。MB/s

傳輸時(shí)間發(fā)送方傳輸時(shí)間：發(fā)送方從開始發(fā)送第一位信息起到把消息完全發(fā)送至網(wǎng)絡(luò)所需時(shí)間接收方傳輸時(shí)間：接收方從接收到第一位信息起到完全接收到消息的時(shí)間頻寬傳輸時(shí)間30

“飛行”時(shí)間消息的第一位信息到達(dá)接收方所需時(shí)間。包括網(wǎng)絡(luò)中轉(zhuǎn)發(fā)或其他硬件的時(shí)間延遲

傳輸時(shí)延發(fā)送方發(fā)送第一位信息到接收方完全接收到消息所需時(shí)間“飛行”時(shí)間+傳輸時(shí)間“飛行”時(shí)間傳輸時(shí)延31

發(fā)送方開銷發(fā)送方在緩沖區(qū)中準(zhǔn)備好待發(fā)送消息并送至網(wǎng)絡(luò)接口硬件的時(shí)間

接收方開銷接收方把消息從網(wǎng)絡(luò)接口硬件取至緩沖區(qū)并拷貝至用戶地址空間的時(shí)間發(fā)送方開銷接收方開銷32

總時(shí)延總時(shí)延=發(fā)送方開銷+“飛行”時(shí)間+消息長(zhǎng)度頻寬+接收方開銷傳輸時(shí)間總時(shí)延=發(fā)送方開銷+“飛行”時(shí)間++接收方開銷總時(shí)延=發(fā)送方開銷+傳輸時(shí)延+接收方開銷總時(shí)延總時(shí)延=發(fā)送方開銷+“飛行”時(shí)間+消息長(zhǎng)度頻寬+接收33發(fā)送開銷傳輸(發(fā)送)時(shí)間飛行時(shí)間接收開銷傳輸(接收)時(shí)間發(fā)送開銷傳輸(發(fā)送)時(shí)間飛行時(shí)間接收開銷傳輸(接收)時(shí)間34發(fā)送方開銷傳輸(發(fā)送)時(shí)間飛行時(shí)間傳輸(接收)時(shí)間接收方開銷傳輸時(shí)延互連網(wǎng)絡(luò)的傳輸性能參數(shù)關(guān)系圖總時(shí)延發(fā)送第一個(gè)發(fā)送最后一個(gè)第一個(gè)到達(dá)接收方最后一個(gè)到達(dá)接收方發(fā)送方開銷傳輸(發(fā)送)時(shí)間飛行時(shí)間傳輸(接收)時(shí)間接收方開銷35例：假設(shè)一個(gè)網(wǎng)絡(luò)的頻寬為10Mb/s，發(fā)送方開銷為230us，接收方開銷為270us，如果兩臺(tái)機(jī)器相距100米，現(xiàn)要發(fā)送一個(gè)1000字節(jié)的消息給另一臺(tái)機(jī)器，試計(jì)算總時(shí)延。如果兩臺(tái)機(jī)器相距1000公里，總時(shí)延為多大？（光速為299792.5km/s，信號(hào)在導(dǎo)體中的傳遞速度大約是光速的50%）例：假設(shè)一個(gè)網(wǎng)絡(luò)的頻寬為10Mb/s，發(fā)送方開銷36T=270us+230us+0.1km299792.5km/s*0.51000*8b10Mb/s+=270us+230us+0.67us+800us=1301usT=270us+230us+1000*106us299792.5km/s*0.51000*8b10Mb/s+=270us+230us+6671us+800us=7971usT=270us+230us+0.1km299792.5km/37互連網(wǎng)絡(luò)的性能指標(biāo)

通信時(shí)延從源結(jié)點(diǎn)到目的結(jié)點(diǎn)傳送一條消息所需的總時(shí)間軟件開銷（取決于收發(fā)端的軟件內(nèi)核）在源結(jié)點(diǎn)和目的結(jié)點(diǎn)用于收發(fā)消息的軟件所需的執(zhí)行時(shí)間互連網(wǎng)絡(luò)的性能指標(biāo)通信時(shí)延38通道時(shí)延（取決于瓶頸鏈路的通道帶寬）

通道時(shí)延=消息長(zhǎng)度/通道帶寬選路時(shí)延（取決于傳送路徑上的結(jié)點(diǎn)數(shù)）消息在傳送路徑上進(jìn)行選路決策所需的時(shí)間開銷競(jìng)爭(zhēng)時(shí)延（取決于網(wǎng)絡(luò)的傳輸狀態(tài)）多個(gè)消息同時(shí)在網(wǎng)絡(luò)中傳送時(shí)解決或避免網(wǎng)絡(luò)資源爭(zhēng)用沖突所需時(shí)間通道時(shí)延（取決于瓶頸鏈路的通道帶寬）39

網(wǎng)絡(luò)時(shí)延

網(wǎng)絡(luò)時(shí)延=通道時(shí)延+選路時(shí)延與程序行為和網(wǎng)絡(luò)傳輸狀態(tài)無(wú)關(guān)

端口帶寬網(wǎng)絡(luò)中從任意一個(gè)端口單位時(shí)間傳送到其他端口的最大信息量。（b/s或B/s）網(wǎng)絡(luò)時(shí)延端口帶寬40

聚集帶寬網(wǎng)絡(luò)從一半結(jié)點(diǎn)到另一半結(jié)點(diǎn)，單位時(shí)間傳送的最大信息量。

對(duì)剖帶寬通過(guò)最小對(duì)剖平面的所有邊的單位時(shí)間傳送的最大信息量。聚集帶寬對(duì)剖帶寬41靜態(tài)互連網(wǎng)絡(luò)各結(jié)點(diǎn)間有專用的連接通路，且在運(yùn)行中不能改變連接的網(wǎng)絡(luò)。靜態(tài)互連網(wǎng)絡(luò)各結(jié)點(diǎn)間有專用的連接通路，且在運(yùn)行中不42線性陣列中間結(jié)點(diǎn)2網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格線性陣列端結(jié)點(diǎn)1N-1N-11否N線性陣列允許不同的結(jié)點(diǎn)對(duì)并發(fā)使用系統(tǒng)的不同部分（通道）線性陣列網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑鏈路數(shù)l等分寬度對(duì)稱性網(wǎng)絡(luò)43環(huán)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格環(huán)2單向環(huán)N-1雙向環(huán)N/2N2是N環(huán)網(wǎng)絡(luò)類型結(jié)點(diǎn)度網(wǎng)絡(luò)直徑鏈路數(shù)l等分寬度對(duì)稱性網(wǎng)絡(luò)規(guī)格環(huán)44帶弦環(huán)把環(huán)中不直接相連的每?jī)蓚€(gè)距離相等的結(jié)點(diǎn)用一條邊連接起來(lái)0123456781011121314159度為3的帶弦環(huán)帶弦環(huán)把環(huán)中不直接相連的每?jī)蓚€(gè)距離相等的結(jié)點(diǎn)用一條0123450123456781011121314159度為4的帶弦環(huán)0123456781011121314159度為4的帶弦環(huán)46循環(huán)移數(shù)網(wǎng)絡(luò)將環(huán)上每個(gè)結(jié)點(diǎn)與其距離為2整數(shù)冪的結(jié)點(diǎn)間增加一條附加鏈路而構(gòu)成。設(shè)網(wǎng)絡(luò)規(guī)模為N=2n，則結(jié)點(diǎn)x與以下結(jié)點(diǎn)有鏈路相連：(x±2i)mod2n(0≤i＜n)0123456789101112131415+2i

i=0,1,..,n-1正度=n-2i

i=0,1,..,n-2負(fù)度=n-1循環(huán)移數(shù)網(wǎng)絡(luò)將環(huán)上每個(gè)結(jié)點(diǎn)與其距離為2整數(shù)冪的結(jié)點(diǎn)間增加047網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l對(duì)稱性網(wǎng)絡(luò)規(guī)格循環(huán)移數(shù)網(wǎng)絡(luò)2n-1n/22n-1(2n-1)是N=2n等分寬度b2n-1n網(wǎng)絡(luò)類型結(jié)點(diǎn)度網(wǎng)絡(luò)直徑鏈路數(shù)l對(duì)稱性網(wǎng)絡(luò)規(guī)格循環(huán)移2n-148全連接網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格全連接N-11N(N-1)/2是N(N/2)2全連接網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度網(wǎng)絡(luò)直徑鏈路數(shù)l等分寬度對(duì)稱性網(wǎng)絡(luò)49N/2N/2N/2N/2*N/2N/2N/2N/2*50樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是一棵完全二叉樹。設(shè)有N個(gè)結(jié)點(diǎn)，共k層，則N=2k-1優(yōu)點(diǎn)：可擴(kuò)展性好缺點(diǎn)：直徑長(zhǎng)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格樹形葉結(jié)點(diǎn)1根結(jié)點(diǎn)2分支結(jié)點(diǎn)32(k-1)N-11否N=2k-1樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是一棵完全二叉樹。設(shè)有N個(gè)結(jié)點(diǎn)，共k網(wǎng)絡(luò)類51星形網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格星形根結(jié)點(diǎn)N-1葉結(jié)點(diǎn)12N-1N/2否N星形網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑鏈路數(shù)l等分寬度對(duì)稱性網(wǎng)絡(luò)52胖樹形網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格胖樹形第j層結(jié)點(diǎn)3(k-j)+12≤j≤k根結(jié)點(diǎn)2k-2j=1j=2j=3j=42(k-1)k-1否N=2k-12k+1-2k-2緩解通向根結(jié)點(diǎn)的通信瓶頸胖樹形網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑鏈路數(shù)l等分寬度對(duì)稱性網(wǎng)53l=j=1k-1(k-j)*2jl=j=1k-1(k-j)*2j54網(wǎng)格形網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格2D網(wǎng)格k維網(wǎng)格角結(jié)點(diǎn)2邊結(jié)點(diǎn)3內(nèi)結(jié)點(diǎn)4內(nèi)結(jié)點(diǎn)2k2(n-1)k(n-1)N=n2N=nk否否2N-2nknk-1(n-1)nnk-1網(wǎng)格形網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑鏈路數(shù)l等分對(duì)稱性網(wǎng)絡(luò)規(guī)55三維網(wǎng)格形網(wǎng)絡(luò)的內(nèi)結(jié)點(diǎn)度為6，邊結(jié)點(diǎn)度為4，角結(jié)點(diǎn)度為3，面內(nèi)結(jié)點(diǎn)度為5。三維網(wǎng)格形網(wǎng)絡(luò)的內(nèi)結(jié)點(diǎn)度為6，邊結(jié)點(diǎn)度為4，56ABAB57ABAB58Illiac網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格Illiac網(wǎng)絡(luò)4n-12N2n否N=n2Illiac網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑鏈路數(shù)l等分寬度對(duì)59ABAB60環(huán)網(wǎng)形網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格2D環(huán)網(wǎng)42n/22N2n是N=n2環(huán)網(wǎng)形網(wǎng)絡(luò)網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑鏈路數(shù)l等分寬度對(duì)稱性網(wǎng)61搏動(dòng)式陣列網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格搏動(dòng)式陣列左右兩角結(jié)點(diǎn)2上下兩角結(jié)點(diǎn)3邊結(jié)點(diǎn)4內(nèi)結(jié)點(diǎn)62(n-1)3n2-4n+12n-1否N=n2搏動(dòng)式陣列網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)鏈路數(shù)l等分寬度對(duì)稱性網(wǎng)絡(luò)規(guī)62超立方體網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格超立方體nnnN/2N/2是N=2n超立方體網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑鏈路數(shù)l等分寬度對(duì)稱性網(wǎng)絡(luò)63互連網(wǎng)絡(luò)的基本概念課件64環(huán)中有K個(gè)結(jié)點(diǎn)帶環(huán)立方體環(huán)中有帶環(huán)立方體65k/2

下一維指針環(huán)中下一結(jié)點(diǎn)環(huán)中上一結(jié)點(diǎn)k/2

K維轉(zhuǎn)發(fā),d=(2k-1)+k/2

網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格帶環(huán)k-立方體32k-1+k/23N/2N/(2k)是N=k×2k(k≥3)k/2下一維指針環(huán)中下一結(jié)點(diǎn)環(huán)中上一結(jié)點(diǎn)k/266ABCDEFGHIJKLMNOPA1B1B2C2C3G3G4O4O3O2A1O2ABCDEFGHIJKLMNOPA1B1B2C2C3G3G467k元n-立方體網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑D鏈路數(shù)l等分寬度b對(duì)稱性網(wǎng)絡(luò)規(guī)格k元n-立方體2nnNnk/22kn-1是N=knk元n-立方體網(wǎng)絡(luò)類型結(jié)點(diǎn)度d網(wǎng)絡(luò)直徑鏈路數(shù)l等分寬度對(duì)68動(dòng)態(tài)互連網(wǎng)絡(luò)動(dòng)態(tài)互連網(wǎng)絡(luò)可通過(guò)設(shè)置有源開關(guān)，從而根據(jù)需要借助控制信號(hào)對(duì)連接通路加以重新組合，實(shí)現(xiàn)所要求的通信模式。動(dòng)態(tài)互連網(wǎng)絡(luò)動(dòng)態(tài)互連網(wǎng)絡(luò)可通過(guò)設(shè)置有源開關(guān)，從而根69多處理機(jī)總線互連

用一組導(dǎo)線和插座將處理機(jī)、存儲(chǔ)模塊和各種外圍設(shè)備互連起來(lái)，總線上的各模塊需要通信時(shí)，發(fā)出申請(qǐng)，由總線仲裁邏輯對(duì)多個(gè)請(qǐng)求進(jìn)行仲裁，進(jìn)行總線服務(wù)分配?？偩€上各模塊通過(guò)爭(zhēng)用或時(shí)分方式獲得總線服務(wù)。價(jià)格較低，帶寬較窄多處理機(jī)總線互連

用一組導(dǎo)線和插座將處理機(jī)、存儲(chǔ)模塊和各種外70本地總線LMCPUIOC高速緩存IFCPU板本地外圍設(shè)備存儲(chǔ)器總線IF存儲(chǔ)器板MC存儲(chǔ)器單元數(shù)據(jù)總線IOP緩沖IFI/O板IF數(shù)據(jù)總線緩沖IF通信板IFCC系統(tǒng)總線（底板上）磁盤和磁帶部件打印機(jī)或繪圖儀網(wǎng)絡(luò)（以太網(wǎng)等）本地總線LMCPUIOC高速緩存IFCPU板本地外圍設(shè)備71機(jī)群間總線CCCPCP…CCCPCP…CCCPCP……存儲(chǔ)器存儲(chǔ)器……存儲(chǔ)器機(jī)群間總線CCCPCP…CCCPCP…CCCPCP……存儲(chǔ)器72總線互連的缺點(diǎn)

帶寬有限沒(méi)有冗余鏈路可擴(kuò)展性有限層次總線的可擴(kuò)展層次數(shù)有限總線互連的缺點(diǎn)73交叉開關(guān)互連大大展寬了互連傳輸頻帶，提高了系統(tǒng)的效率；但交叉開關(guān)設(shè)備量過(guò)大，成本過(guò)高（一般n≤16）采用按空間分配的機(jī)制交叉開關(guān)互連大大展寬了互連傳輸頻帶，提高了系統(tǒng)的效率；74M1M2Mn…P1PmI/O1I/Or……n≥r+mM1M2Mn…P1PmI/O1I/Or……n≥r+m75存儲(chǔ)器模塊多路轉(zhuǎn)換器模塊仲裁模塊數(shù)據(jù)讀/寫地址自處理機(jī)P0~Pn-1數(shù)據(jù)讀/寫地址請(qǐng)求0請(qǐng)求1請(qǐng)求n-1存儲(chǔ)器使能控制結(jié)點(diǎn)開關(guān)的結(jié)構(gòu)存儲(chǔ)器多路轉(zhuǎn)換仲裁模塊數(shù)據(jù)讀/寫地址自處理機(jī)數(shù)據(jù)讀/寫地址請(qǐng)76多級(jí)互連網(wǎng)絡(luò)a×b……a×b………a×b……a×b……a×b………a×b……………………a×b……a×b………a×b………………ISCISCISC10a-1a+1a2a-1an-aan-a+1an-110b-1b+1b2b-1bn-b+1bn-bbn-1an-1個(gè)ban-2個(gè)bn-1個(gè)級(jí)1級(jí)2級(jí)n多級(jí)互連網(wǎng)絡(luò)……………77多級(jí)互連網(wǎng)絡(luò)把重復(fù)設(shè)置的多套動(dòng)態(tài)單級(jí)網(wǎng)絡(luò)串聯(lián)起來(lái)，單級(jí)網(wǎng)絡(luò)級(jí)間采用固定的級(jí)間連接模式，通過(guò)動(dòng)態(tài)控制各單級(jí)網(wǎng)絡(luò)的開關(guān)狀態(tài)實(shí)現(xiàn)多級(jí)互連網(wǎng)絡(luò)的輸入端和輸出端之間所需要的連接多級(jí)互連網(wǎng)絡(luò)把重復(fù)設(shè)置的多套動(dòng)態(tài)單級(jí)網(wǎng)78開關(guān)模塊a×b……10a-110b-1通常取a=b=2k（k≥1）2功能開關(guān)4功能開關(guān)0101010101010101直送交叉上播下播開關(guān)模塊……10a-110b-1通常取a=b=2k（k≥179級(jí)間連接模式多級(jí)互連網(wǎng)絡(luò)中上一級(jí)開關(guān)模塊的輸出端和下一級(jí)開關(guān)模塊的輸入端相互連接的模式可用互連函數(shù)表示級(jí)間連接模式80控制方式互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可動(dòng)態(tài)重構(gòu)：可通過(guò)控制信號(hào)動(dòng)態(tài)控制開關(guān)模塊的狀態(tài)來(lái)實(shí)現(xiàn)所要求的互連級(jí)控方式對(duì)同一級(jí)的所有開關(guān)用一個(gè)控制信號(hào)控制組控方式對(duì)第i級(jí)的開關(guān)分為i+1組，每組用一個(gè)控制信號(hào)控制（0≤i≤n-1）單元控制方式每一個(gè)開關(guān)有自己?jiǎn)为?dú)的控制信號(hào)控制方式級(jí)控方式81多級(jí)互連網(wǎng)絡(luò)的分類

阻塞網(wǎng)：在一對(duì)以上輸入端和輸出端可同時(shí)實(shí)現(xiàn)互連的網(wǎng)絡(luò)中，可能發(fā)生2個(gè)或2個(gè)以上的輸入端對(duì)輸出端的連接要求產(chǎn)生路徑爭(zhēng)用沖突。所用開關(guān)數(shù)量少，延時(shí)不長(zhǎng)，路徑控制較簡(jiǎn)單。多級(jí)互連網(wǎng)絡(luò)的分類82可重排非阻塞網(wǎng)絡(luò)：如果重新安排現(xiàn)有的連接，就可實(shí)現(xiàn)無(wú)阻塞的任意端點(diǎn)對(duì)的連接，從而滿足一個(gè)新的端點(diǎn)對(duì)的連接請(qǐng)求。

多級(jí)非阻塞網(wǎng)絡(luò)：不必改變?cè)瓉?lái)的開關(guān)狀態(tài)就可滿足任意輸入端和輸出端的連接請(qǐng)求。交叉開關(guān)網(wǎng)絡(luò)為單級(jí)非阻塞網(wǎng)可重排非阻塞網(wǎng)絡(luò)：如果重新安排現(xiàn)有的83Omega網(wǎng)絡(luò)N*N；共n=log2N級(jí)開關(guān)，從輸入端至輸出端依次為Kn-1,…,K1,K0采用2*2的4功能開關(guān)每級(jí)N/2個(gè)開關(guān)，共m=(N/2)log2N個(gè)開關(guān)，可實(shí)現(xiàn)4m種置換連接采用單元控制方式Omega網(wǎng)絡(luò)N*N；共n=log2N級(jí)開關(guān)，從輸入端至84級(jí)間連接從輸入端至輸出端依次為Cn,…,C1,C0;其中，Cn~C1為均勻洗牌置換，C0為恒等置換

Ω=σEσE…σEI=(σE)n（E為開關(guān)級(jí)在開關(guān)控制方式下實(shí)現(xiàn)的交換置換）級(jí)間連接從輸入端至輸出端依次為Cn,…,850123456701234567K2K1K0C3C2C1C0Omega網(wǎng)絡(luò)(N=8)0123456701234567K2K1K0C3C2C1C086采用終端標(biāo)記尋徑（D標(biāo)記尋徑）

xn-1xn-2…x1x0

yn-1yn-2…y1y0(D)xn-1xn-2…x1x0Cnxn-2xn-3…x1x0xn-1Kn-1xn-2xn-3…x1x0xn-1’Cn-1xn-3…x1x0xn-1’xn-2Kn-2xn-3…x1x0xn-1’xn-2’C1x0xn-1’xn-2’…x1’xn-1’xn-2’…x1’x0K0xn-1’xn-2’…x1’x0’C0xn-1’xn-2’…x1’x0’=yn-1yn-2…y1y0…………K1yi=0，第i級(jí)即Ki開關(guān)級(jí)上對(duì)應(yīng)開關(guān)的輸入端與開關(guān)的上輸出端相連；yi=1，第i級(jí)即Ki開關(guān)級(jí)上對(duì)應(yīng)開關(guān)的輸入端與開關(guān)的下輸出端相連；采用終端標(biāo)記尋徑（D標(biāo)記尋徑）xn-1xn-2…x1x0C87可能產(chǎn)生爭(zhēng)用開關(guān)狀態(tài)的沖突xi-1…x0xn-1’…xi+1’xiKixi-1…x0xn-1’…xi+1’xi’若兩對(duì)連接的源端xi-1,…x0,xn-1’,…xi+1’均相同，xi不同，終端xi’(yi)相同，則該兩對(duì)連接在Ki開關(guān)級(jí)的xi-1,…x0,xn-1’,…xi+1’開關(guān)上產(chǎn)生沖突例如:000101與100110在K2級(jí)開關(guān)0上產(chǎn)生爭(zhēng)用下輸出端的沖突；101100與011101在K1級(jí)開關(guān)3上產(chǎn)生爭(zhēng)用上輸出端的沖突；在實(shí)現(xiàn)源與終端結(jié)點(diǎn)各不相同的置換連接時(shí)，如果不產(chǎn)生沖突，所有開關(guān)均不會(huì)出現(xiàn)上播或下播的狀態(tài)；可能產(chǎn)生爭(zhēng)用開關(guān)狀態(tài)的沖突xi-1…x0xn-1’…xi+88例：在N=8的Omega網(wǎng)絡(luò)中采用終端標(biāo)記尋徑法，至少要連接幾次才能實(shí)現(xiàn)蝶式置換所要求的連接？第一次實(shí)現(xiàn)00,14,22,36第二次實(shí)現(xiàn)41,55,63,7700,41爭(zhēng)用K2級(jí)0開關(guān)的上輸出端，從而爭(zhēng)用K1級(jí)0開關(guān)的上輸出端；14,55爭(zhēng)用K2級(jí)1開關(guān)的下輸出端，從而爭(zhēng)用K1級(jí)3開關(guān)的上輸出端；22,63爭(zhēng)用K2級(jí)2開關(guān)的上輸出端，從而爭(zhēng)用K1級(jí)0開關(guān)的下輸出端；36,77爭(zhēng)用K2級(jí)3開關(guān)的下輸出端，從而爭(zhēng)用K1級(jí)3開關(guān)的下輸出端例：在N=8的Omega網(wǎng)絡(luò)中采用終端標(biāo)記尋徑法，第一次實(shí)現(xiàn)890123456701234567K2K1K0C3C2C1C00123456701234567K2K1K0C3C2C1C090例：試給出一個(gè)簡(jiǎn)單的尋徑算法實(shí)現(xiàn)Omega網(wǎng)絡(luò)的任一源端對(duì)所有終端的廣播連接。Si=01使Ki級(jí)相應(yīng)開關(guān)上播使Ki級(jí)相應(yīng)開關(guān)下播僅在播送連接中才可能出現(xiàn)開關(guān)的上播和下播狀態(tài)例：試給出一個(gè)簡(jiǎn)單的尋徑算法實(shí)現(xiàn)Omega網(wǎng)絡(luò)Si=01使K910123456701234567K2K1K0C3C2C1C00123456701234567K2K1K0C3C2C1C092例：用一個(gè)N=8的三級(jí)Omega網(wǎng)絡(luò)連接8個(gè)處理機(jī)(P0~P7)，8個(gè)處理機(jī)的輸出端分別依序連接Omega網(wǎng)絡(luò)的8個(gè)輸入端0~7，8個(gè)處理機(jī)的輸入端分別依序連接Omega網(wǎng)絡(luò)的8個(gè)輸出端0~7。如果處理機(jī)P6要把數(shù)據(jù)播送給處理機(jī)P0~P4，處理機(jī)P3要把數(shù)據(jù)播送給處理機(jī)P5~P7。那么，Omega網(wǎng)絡(luò)能否同時(shí)為它們的播送要求實(shí)現(xiàn)連接？請(qǐng)畫出實(shí)現(xiàn)播送的Omega網(wǎng)絡(luò)的開關(guān)狀態(tài)圖。例：用一個(gè)N=8的三級(jí)Omega網(wǎng)絡(luò)連接8個(gè)處理930123456701234567K2K1K0C3C2C1C00123456701234567K2K1K0C3C2C1C094STARAN網(wǎng)絡(luò)N*N；共n=log2N級(jí)開關(guān)，從輸入端至輸出端依次為K0,K1…,Kn-1采用2*2的2功能開關(guān)，直送和交叉

每級(jí)N/2個(gè)開關(guān)，共m=(N/2)log2N個(gè)開關(guān)，共可實(shí)現(xiàn)2m種置換連接STARAN網(wǎng)絡(luò)N*N；共n=log2N級(jí)開關(guān)，從輸入端95采用級(jí)控方式或組控方式級(jí)間連接從輸入端至輸出端依次為C0,C1,…,Cn;其中，C1~Cn為逆洗牌置換，C0為恒等置換

S=IEσ-1Eσ-1…Eσ-1=(Eσ-1)n（E為開關(guān)級(jí)在開關(guān)控制方式下實(shí)現(xiàn)的交換置換）采用級(jí)控方式或組控方式級(jí)間連接從輸入端至輸出端依次為C0960123456701234567K0K1K2C0C1C2C3STARAN網(wǎng)絡(luò)(N=8)0123456701234567K0K1K2C0C1C2C397xn-1xn-2…x1x0C0K0C1K1Cn-1xn-3’xn-2’…x0’xn-1xn-2’xn-2’xn-3’…x0’xn-1Kn-1xn-2’xn-3’…x0’xn-1’Cnxn-1’xn-2’…x1’x0’=yn-1yn-2…y1y0…………Kn-2(S)xn-1xn-2…x1x0

yn-1yn-2…y1y0(D)xn-1xn-2…x1x0xn-1xn-2…x1x0’x0’xn-1xn-2…x1x0’xn-1xn-2…x1’C2xn-1xn-2…x1x0C0K0C1K1Cn-1xn-3’98級(jí)控方式及交換置換xi’=E(xi)=xi+fixi-1’…x0’xn-1…xiKixi-1’…x0’xn-1…xi’E(xn-1xn-2…x1x0)=(+fn-1,xn-1+fn-2,xn-2…+f1,x1+f0)x0可實(shí)現(xiàn)N種置換級(jí)控方式及交換置換xi’=E(xi)=xi+fixi-1’99若級(jí)控信號(hào)F中僅fi為1，其余各位為0：

E(xn-1…xi…x1x0)=xn-1…xi…x1x0=Cubei(x)分組交換置換：若分為2n-k組，每組2k個(gè)元素，則同組元素低k位必不同，高n-k位必相同。讓同組元素反序，得到輸出序列。

xn-1…xkxk-1…x1x0xn-1…xkxk-1…x1x0若級(jí)控信號(hào)F中僅fi為1，其余各位為0：分組交換置換：若100x2x1x04組2元4組2元+2組4元2組4元2組4元+1組8元4組2元+2組4元+1組8元4組2元+1組8元1組8元x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0例如：實(shí)現(xiàn)2組4元交換x2x1x04組2元4組2元+2組4元2組4元2組4元+1組101000001010011100101110111012345670123456710233210456754677654321076453201546776540123102376453201恒等4組2元4組2元2組4元2組4元2組4元1組8元4組2元2組4元1組8元4組2元1組8元1組8元iC0C1C0+C1C2C0+C2C1+C2C0+C1+C200000101001110010111011100123410201234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567F=(000)F=(001)F=(010)F=(011)F=(100)F=(101)F=(110)F=(111)0000000000000000F=(000)F=(001)103組控方式及移數(shù)置換組控信號(hào)F中有m=n(n+1)/2個(gè)位信號(hào)，可實(shí)現(xiàn)2m種置換

若n=3，F(xiàn)=(f23f22f21f12f11f0)可實(shí)現(xiàn)的移數(shù)置換：

α(x)=(x+2m)mod2P+x/2p*2p

(0≤m<p≤n)

共可實(shí)現(xiàn)(n2+n+2)/2種移數(shù)置換連接

組控方式及移數(shù)置換組控信號(hào)F中有m=n(n+1)/2個(gè)位104f23f22f21f12f11f00010110111101110000000110001100000010000000123456712345670234567014567012312305674230167451032547601234567組控信號(hào)輸入端號(hào)移數(shù)功能移1mod8移2mod8移4mod8移1mod4移2mod4移1mod2不移恒等f(wàn)23001000001241210組輸移數(shù)移1移2移1050123456701234567K0K1K2C0C1C2C3例如：實(shí)現(xiàn)移2模8置換0123456701234567K0K1K2C0C1C2C310601234567012345670123456701234567012345670123456701234567012345670123456701234567移1模2移1模4移2模4恒等移1模80123456701234567移2模8移4模801234567012345670000000000移1模2移1模4移2模4恒等移1模800107例：設(shè)有一四級(jí)立方體網(wǎng)絡(luò)，對(duì)于下述連接分別寫出網(wǎng)絡(luò)的級(jí)控信號(hào)和互連函數(shù)。4組4元交換4組4元交換+1組16元交換E(x3x2x1x0)=x3x2x1x0=Cube1(Cube0(x3x2x1x0))F=f3f2f1f0=0011E(x3x2x1x0)=x3x2x1x0=Cube3(Cube2(x3x2x1x0))F=f3f2f1f0=1100例：設(shè)有一四級(jí)立方體網(wǎng)絡(luò)，對(duì)于下述連接分別E(x3x2x1x108間接二進(jìn)制n方體網(wǎng)絡(luò)N*N；共n=log2N級(jí)開關(guān)，從輸入端至輸出端依次為K0,K1…,Kn-1采用2*2的2功能開關(guān)，直送和交叉每級(jí)N/2個(gè)開關(guān)，共m=(N/2)log2N個(gè)開關(guān)，可實(shí)現(xiàn)2m種置換連接級(jí)間連接從輸入端至輸出端依次為C0,C1,…,Cn;其中，C1~Cn-1為子蝶式置換，C0為恒等置換

，Cn為逆洗牌置換

C=IE

(1)

E

(2)

…E

(n-1)

Eσ-1（E為開關(guān)級(jí)在開關(guān)控制方式下實(shí)現(xiàn)的交換置換）采用單元控制方式間接二進(jìn)制n方體網(wǎng)絡(luò)N*N；共n=log2N級(jí)開關(guān)，從輸1090123456701234567K0K1K2C0C1C2C3間接二進(jìn)制n方體網(wǎng)絡(luò)(n=3)0123456701234567K0K1K2C0C1C2C3110xn-1xn-2…x1x0C0K0C1K1Cn-1xn-1xn-3’xn-2’…x0’xn-2’xn-2’xn-3’…x0’xn-1Kn-1xn-2’xn-3’…x0’xn-1’Cnxn-1’xn-2’…x1’x0’=yn-1yn-2…y1y0…………Kn-2(S)xn-1xn-2…x1x0

yn-1yn-2…y1y0(D)xn-1xn-2…x1x0xn-1xn-2…x2x1x0’xn-1xn-2…x2x0’x1xn-1xn-2…x2x0’x1’xn-1…xi+1xi-1’…x0’xiKixn-1…xi+1xi-1’…x0’xi’Cn-2xn-1xn-2…x1x0C0K0C1K1Cn-1xn-1x111終端標(biāo)記尋徑（D標(biāo)記尋徑）用yi控制Ki級(jí)上所到達(dá)開關(guān)的狀態(tài)：若yi=0，從該開關(guān)的上輸出端輸出；若yi=1，從該開關(guān)的下輸出端輸出。若兩個(gè)源結(jié)點(diǎn)序號(hào)的xi+1~xn-1，x0’~xi-1’均相同，xi不同，即到達(dá)Ki級(jí)同一開關(guān)(開關(guān)號(hào)為xn-1…xi+1xi-1’…x0’)的不同輸入端。若yi相同，則產(chǎn)生對(duì)該開關(guān)的上(yi=0)或下(yi=1)通道的爭(zhēng)用沖突終端標(biāo)記尋徑（D標(biāo)記尋徑）用yi控制Ki級(jí)上所到達(dá)開關(guān)的狀112上控法用到達(dá)開關(guān)級(jí)Ki相應(yīng)開關(guān)的上輸入端(xi=0)的終端標(biāo)記yi來(lái)控制該開關(guān)的狀態(tài)：yi=0，該開關(guān)為直送狀態(tài)；yi=1，該開關(guān)為交叉狀態(tài)。若到達(dá)Ki級(jí)某開關(guān)的下輸入端，則遵守由到達(dá)該開關(guān)上輸入端的某對(duì)連接所確定的狀態(tài)。若遵守狀態(tài)后導(dǎo)致本連接xi’=yi（即兩個(gè)終結(jié)點(diǎn)序號(hào)yi相同），則產(chǎn)生沖突，不能同時(shí)實(shí)現(xiàn)此兩對(duì)連接。上控法用到達(dá)開關(guān)級(jí)Ki相應(yīng)開關(guān)的上輸入端(xi=0)的終端113T標(biāo)記尋徑法用ti=xiyi作為單元控制標(biāo)記。若ti=0，則開關(guān)狀態(tài)為直送；否則開關(guān)狀態(tài)為交叉。若兩個(gè)源結(jié)點(diǎn)到達(dá)Ki級(jí)同一開關(guān)的不同輸入端，即它們的xi+1~xn-1，x0’~xi-1’均相同，xi不同，開關(guān)號(hào)為xn-1…xi+1xi-1’…x0’。若xiyi不同，則產(chǎn)生開關(guān)狀態(tài)爭(zhēng)用沖突++T標(biāo)記尋徑法用ti=xiyi作為單元控制標(biāo)記。若t114例1：實(shí)現(xiàn)連接05，12，26，33，44，57，61，70。采用上控法和T標(biāo)記尋徑法是否會(huì)發(fā)生阻塞？12與26爭(zhēng)用K1級(jí)0開關(guān)的下輸出端，并導(dǎo)致K2級(jí)2開關(guān)為上播狀態(tài)；44與70爭(zhēng)用K1級(jí)2開關(guān)的上輸出端，并導(dǎo)致K2級(jí)0開關(guān)為下播狀態(tài)；例1：實(shí)現(xiàn)連接05，12，26，33，12與261150123456701234567K0K1K2C0C1C2C3采用上控法0123456701234567K0K1K2C0C1C2C31160123456701234567K0K1K2C0C1C2C3采用T標(biāo)記尋徑法0123456701234567K0K1K2C0C1C2C3117例2：實(shí)現(xiàn)連接03，16，24，31，42，57，65，70。采用上控法和T標(biāo)記尋徑法是否會(huì)發(fā)生阻塞？不發(fā)生阻塞。例2：實(shí)現(xiàn)連接03，16，24，31，不發(fā)生阻塞。1180123456701234567K0K1K2C0C1C2C3采用上控法0123456701234567K0K1K2C0C1C2C3119Delta網(wǎng)絡(luò)an*bn；開關(guān)從輸入端至輸出端依次為K1,K2…,Kn采用a*b的開關(guān)Ki級(jí)開關(guān)的開關(guān)數(shù)為an-ibi-1(1≤i≤

n)，Ki的輸入端數(shù)為an-i+1bi-1，輸出端數(shù)為an-ibiDelta網(wǎng)絡(luò)an*bn；開關(guān)從輸入端至輸出端依次為K1120級(jí)間連接從輸入端至輸出端依次為C0,C1,…,Cn;Ci的輸入和輸出端數(shù)均為an-ibi。C0和Cn為恒等連接，其余級(jí)間連接均采用q洗牌置換

q洗牌置換：將qr張牌分成q組，每組r張，洗牌時(shí)先將所有組的第一張牌順序放在前q個(gè)位置，再將所有組的第二牌順序放在接下來(lái)的q個(gè)位置，直到各組牌全部取完為止。f(x)=(xmodr)*q+x/r在Ci級(jí)中，對(duì)an-ibi個(gè)輸入端分為an-ibi-1組，每組b個(gè)進(jìn)行q洗牌置換級(jí)間連接從輸入端至輸出端依次為C0,C1,f(x)=(x121采用單元控制方式采用終端標(biāo)記尋徑方法來(lái)實(shí)現(xiàn)源端對(duì)終端的連接采用單元控制方式采用終端標(biāo)記尋徑方法來(lái)實(shí)現(xiàn)源端對(duì)終端122an×bn的Delta網(wǎng)絡(luò)a×b……a×b………a×b……a×b……a×b………a×b……………………a×b……a×b………a×b………………10a-1a+1a2a-1an-aan-a+1an-110b-1b+1b2b-1bn-b+1bn-bbn-1an-1個(gè)ban-2個(gè)bn-1個(gè)K1K2KnC0C1C2Cn-1Cn…q洗牌置換q洗牌置換q洗牌置換an×bn的Delta網(wǎng)絡(luò)……………12301230124567345891011678121314159101101230124567345891011678000102101112202122K1K2C0C1C2例：1742*32的Delta網(wǎng)絡(luò)012301245673458910116781213141124x經(jīng)開關(guān)Ki+1后變?yōu)椋簒/a*b+wi+1(0≤i<n,0≤wi+1<b)x經(jīng)級(jí)間連接Ci后變?yōu)椋?xmodb)*an-ibi-1+x/b(0<i<n)S=s0*a0+s1*a1+…sn-1*an-1D=d0*b0+d1*b1+…dn-1*bn-1SK1(s1*a0+…sn-1*an-2)*b+w1C1(s1*a0+…sn-1*an-2)+w1*an-1K2(s2*a0+…sn-1*an-3+w1*an-2)*b+w2C2(s2*a0+…sn-1*an-3+w1*an-2)+w2*an-2bKn-1(sn-1*a0+w1*a1+w2*ab…+wn-2*abn-3)*b+wn-1Cn-1(sn-1*a0+w1*a1+w2*ab…+wn-2*abn-3)+wn-1*abn-2x經(jīng)開關(guān)Ki+1后變?yōu)椋篠=s0*a0+s1125Kn(w1+w2*b1+…+wn-2*bn-3+wn-1*bn-2)*b+wn=d0*b0+d1*b1+…dn-2*bn-2+dn-1*bn-1=wn*b0+w1*b1+…wn-2*bn-2+wn-1*bn-1Cn(w1+w2*b1+…+wn-2*bn-3+wn-1*bn-2)*b+wn用di控制開關(guān)級(jí)Ki(1≤i<n)，d0控制開關(guān)級(jí)KnKn(w1+w2*b1+…+wn-2*bn-3+wn-1*b126例：比較4*9的單級(jí)交叉開關(guān)和用二級(jí)2*3的交叉開關(guān)組成的4*9的Delta網(wǎng)絡(luò)，比較這兩種互連網(wǎng)絡(luò)的開關(guān)設(shè)備量。4*9單級(jí)交叉開關(guān)的開關(guān)數(shù)為36，每套開關(guān)內(nèi)部有4選1的多路轉(zhuǎn)換邏輯和可對(duì)4個(gè)請(qǐng)求信號(hào)進(jìn)行仲裁的仲裁模塊。二級(jí)22*32的Delta網(wǎng)絡(luò)的開關(guān)數(shù)為30，每個(gè)開關(guān)只需2選1的多路選擇器和可對(duì)2個(gè)請(qǐng)求信號(hào)進(jìn)行仲裁的仲裁模塊。例：比較4*9的單級(jí)交叉開關(guān)和用二級(jí)2*3的交叉4*9單級(jí)交127Benes二進(jìn)制置換網(wǎng)絡(luò)N*N；共2log2N=2n級(jí)開關(guān)，從輸入端至輸出端依次為K0,K1…,Kn-1,Kn,…,K2n-1采用2*2的2功能開關(guān)，直送和交叉每級(jí)N/2個(gè)開關(guān)，共N(log2N)個(gè)開關(guān)Benes二進(jìn)制置換網(wǎng)絡(luò)N*N；共2log2N=2n級(jí)開128級(jí)間連接從輸入端至輸出端依次為C0,C1,…,Cn,Cn+1,…,C2n;其中，C0,Cn,C2n是恒等置換;C1~Cn-1為逆子洗牌置換(Ci=

(n-i)

-11≤i≤n-1);Cn+1~C2n-1為子洗牌置換(Ci=

(i-n)

n+1≤i≤2n-1)

=IE

(n-1)

-1

E

(n-2)-1…E(1)

-1EIE(1)…E(n-1)EI（E為開關(guān)級(jí)在開關(guān)控制方式下實(shí)現(xiàn)的交換置換）采用單元控制方式可將Kn-1和Kn級(jí)合并為一個(gè)開關(guān)級(jí)級(jí)間連接從輸入端至輸出端依次為C0,C1,采用單元控制方1290123456701234567K0K1K2K3K4K5C0

C1C2C3C4C5C6d0d1d2d2d1d0

(2)

-1

(1)

-1

(1)

(2)

III0123456701234567K0K1K2K3K4K5C0130(S)xn-1xn-2…x1x0

yn-1yn-2…y1y0(D)xn-1xn-2…x1x0K0xn-1xn-2…x1x0’C1x0’xn-1xn-2…x1K1x0’xn-1xn-2…x1’C2x0’x1’xn-1xn-2…x2K2x0’x1’xn-1xn-2…x2’C3x0’x1’x2’xn-1xn-2…x3Kn-1x0’x1’x2’…xn-1’Cnx0’x1’x2’…xn-1’Knx0’x1’x2’…xn-1’’Cn+1x0’x1’x2’…xn-1’’xn-2’…Kn+1x0’x1’…xn-1’’xn-2’’Cn+2x0’x1’…xn-1’’xn-2’’xn-3’…K2n-1xn-1’’xn-2’’…x1’’x0’’=yn-1yn-2…y1y0(S)xn-1xn-2…x1x0yn-1yn-2…y1131采用改進(jìn)的終端標(biāo)記控制算法：上控法或下控法上控法：用到達(dá)開關(guān)級(jí)Ki相應(yīng)開關(guān)的上輸入端的終端標(biāo)記yi來(lái)控制該開關(guān)的狀態(tài)：yi=0，該開關(guān)為直送狀態(tài)；yi=1，該開關(guān)為交叉狀態(tài)下控法：用到達(dá)開關(guān)級(jí)Ki相應(yīng)開關(guān)的下輸入端的終端標(biāo)記yi來(lái)控制該開關(guān)的狀態(tài)：yi=0，該開關(guān)為交叉狀態(tài)；yi=1，該開關(guān)為直送狀態(tài)采用改進(jìn)的終端標(biāo)記控制算法：上控法或上控法：用到達(dá)開關(guān)級(jí)132為可重排非阻塞網(wǎng)絡(luò)，可實(shí)現(xiàn)N!種源終端間的置換連接。但并不是所有置換連接都能一次實(shí)現(xiàn)，每一對(duì)源和終結(jié)點(diǎn)的連接至少存在兩條路徑，當(dāng)一條走不通時(shí)可選擇另一條又稱為全排列網(wǎng)絡(luò)N個(gè)輸入端和N個(gè)輸出端的置換連接共有N！種。為可重排非阻塞網(wǎng)絡(luò)，可實(shí)現(xiàn)N!種源終端又稱為全排列網(wǎng)絡(luò)N133網(wǎng)絡(luò)置換連接比例N=8比例值Omega(NN/2)/N!4096/40320STARAN級(jí)控N/N!8/40320STARAN組控2n(n+1)/2/N!64/40320間接二進(jìn)制n方體(NN/2)/N!4096/40320Benes二進(jìn)制置換N!/N!1網(wǎng)絡(luò)置換連接比例N=8比例值Omega(NN/2)/N!40134采用上控法若通過(guò)Ki(0≤i≤n-2)級(jí)某開關(guān)后使得xi’=yi，稱為產(chǎn)生了變異，若該變異能在K2n-1-i級(jí)恢復(fù)，則稱為變異被修正。若通過(guò)Ki(n≤i)級(jí)某開關(guān)后使得xi’’=yi，也稱產(chǎn)生了變異，且該變異是不能修正的。若通過(guò)Kn-1級(jí)某開關(guān)后使得xn-1’=yn-1，也稱產(chǎn)生了變異，且該變異是不能修正的。采用上控法若通過(guò)Ki(0≤i≤n-2)級(jí)某開關(guān)后使得135

所謂沖突情況是:當(dāng)某條路徑P經(jīng)過(guò)在某級(jí)I的某開關(guān)E時(shí),它自己的出路被別的路徑所占用。這樣，只好走另外的那條出路。（圖中：虛線為應(yīng)走路徑，實(shí)線為實(shí)走路徑）沖突上圖下圖修正所謂沖突情況是:當(dāng)某條路徑P經(jīng)過(guò)在某級(jí)I的某開關(guān)E時(shí)136

某條路徑P在某級(jí)I的開關(guān)E上的沖突意味著：它本應(yīng)該作“交換”卻沒(méi)有“交換”（上圖情況）；或它本不應(yīng)該作“交換”而卻作了“交換”（下圖情況）。這種情況我們稱為“變異”，這樣，有沖突必有變異。那么，怎樣去“修正”這種變異？

Benes二進(jìn)制置換網(wǎng)絡(luò)是左右對(duì)稱的，之所以這樣設(shè)計(jì)，是為了在左邊發(fā)生的變異而在右邊去修正這種變異。只是這種修正應(yīng)該在與左邊相對(duì)稱的開關(guān)級(jí)上進(jìn)行。某條路徑P在某級(jí)I的開關(guān)E上的沖突意味著：它本應(yīng)該作137例1：實(shí)現(xiàn)位序顛倒置換例1：實(shí)現(xiàn)位序顛倒置換1380123456701234567K0K1K2K3K4K5C0C1C2C3C4C5C6d0d1d2d2d1d0變異修正變異修正變異修正變異修正0123456701234567K0K1K2K3K4K5C0139例2：實(shí)現(xiàn)置換00,11,27,33,44,56,65,72例2：實(shí)現(xiàn)置換00,11,27,33,441400123456701234567K0K1K2K3K4K5C0C1C2C3C4C5C6d0d1d2d2d1d0變異修正變異變異修正變異修正變異變異變異變異修正變異修正未修正0123456701234567K0K1K2K3K4K5C0141互連網(wǎng)絡(luò)的消息傳遞機(jī)制數(shù)據(jù)傳遞的方式：共享變量方式共享存儲(chǔ)器多處理器系統(tǒng)消息傳遞方式分布式存儲(chǔ)器多處理器系統(tǒng)所有的處理器共享一個(gè)統(tǒng)一編址的物理存儲(chǔ)器，它可以是集中式的，也可以分布在各個(gè)處理器結(jié)點(diǎn)中每個(gè)處理器只能對(duì)本地存儲(chǔ)器直接進(jìn)行讀/寫操作互連網(wǎng)絡(luò)的消息傳遞機(jī)制數(shù)據(jù)傳遞的方式：所有的處理器共享一142消息格式消息：由任意數(shù)目的長(zhǎng)度固定的包組成，是結(jié)點(diǎn)間通信的基本單位包：包含尋徑目的地址的結(jié)點(diǎn)間通信的基本單位；可異步傳輸，每個(gè)包有一個(gè)包序號(hào)，以便在接收方進(jìn)行包重組片：將包分成等長(zhǎng)的片，尋徑信息（源地址和目的地址）和序號(hào)形成頭片，其余是數(shù)據(jù)片消息格式消息：由任意數(shù)目的長(zhǎng)度固定的包組成，是結(jié)包：包143DDDDDDSR消息包片R：尋徑信息S：順序號(hào)D：數(shù)據(jù)片DDDDDDSR消息包片R：尋徑信息S：順序號(hào)144消息尋徑方式

消息尋徑方式：消息從發(fā)送地傳送到目的地對(duì)路徑的選取方式消息尋徑方式消息尋徑方式：消息從發(fā)送地傳送到目的145