計(jì)算機(jī)系統(tǒng)機(jī)構(gòu)-第7章課件

計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第一章基本概念第二章指令系統(tǒng)第三章存儲(chǔ)系統(tǒng)第四章輸入輸出系統(tǒng)第五章標(biāo)量處理機(jī)第六章向量處理機(jī)第七章互連網(wǎng)絡(luò)第八章并行處理機(jī)第九章多處理機(jī)1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第一章基本概念1互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)用于實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件之間的相互連接第七章互連網(wǎng)絡(luò)2互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)第七章互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)的基本概念消息傳遞機(jī)制3第七章互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)的基本概念37.1互連網(wǎng)絡(luò)的基本概念互連網(wǎng)絡(luò)的作用互連函數(shù)互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù)互連網(wǎng)絡(luò)的種類47.1互連網(wǎng)絡(luò)的基本概念互連網(wǎng)絡(luò)的作用47.1.1互連網(wǎng)絡(luò)的作用用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件之間的相互連接。為并行處理系統(tǒng)的核心組成部分。對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的性能價(jià)格比有著決定性的影響。57.1.1互連網(wǎng)絡(luò)的作用用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多具有本地存儲(chǔ)器、私有高速緩存、共享存儲(chǔ)器和共享外圍設(shè)備的一般處理機(jī)系統(tǒng)的互連結(jié)構(gòu)IPMN(處理機(jī)-存儲(chǔ)器網(wǎng)絡(luò))PION(處理機(jī)-I/O網(wǎng)絡(luò))IPCN(處理機(jī)之間通信網(wǎng)絡(luò))P(處理機(jī))C(高速緩沖存儲(chǔ)器)SM(共享存儲(chǔ)器)LM(本地存儲(chǔ)器)磁盤SM1SM2SMmIPMN……CnPnLMC1P1LMIPCN……………………PION磁帶打印機(jī)終端網(wǎng)絡(luò)…(共享存儲(chǔ)器)(共享I/O與外設(shè))6具有本地存儲(chǔ)器、私有高速緩存、共享存儲(chǔ)器和共享外圍設(shè)備的一般7.1.2互連函數(shù)互連函數(shù)將互連網(wǎng)的N個(gè)輸入和N個(gè)輸出端分別用整數(shù)(0,1,2,...,N-1)來表示，則表示相互連接的輸出端號(hào)和輸入端號(hào)之間的一一對(duì)應(yīng)關(guān)系表示方法：互連函數(shù)法，圖形表示法,輸入輸出對(duì)應(yīng)表示法函數(shù)表示法：x表示輸入端號(hào)，常用n位二進(jìn)制形式表示xn-1xn-2...x1x0f(x)表示互連函數(shù)，為：f(xn-1xn-2...x1x0)圖形表示法:用圖形表示輸入和輸出端之間的連接輸入輸出對(duì)應(yīng)(矩陣)表示法：循環(huán)表示法:把互連函數(shù)f(x)表示為：

(x0，x1，...，xj)(xk，xk+1，...，xl)...表示對(duì)應(yīng)關(guān)系為:f(x0)=x1，f(x1)=x2，...，f(xj)=x0

j+1稱為該循環(huán)的長度012...N-1f(0)f(1)f(2)...f(N-1)77.1.2互連函數(shù)互連函數(shù)012...常用的互連函數(shù)如下：1恒等置換：

I(xn-1xn-2...

x1x0)=xn-1xn-2...x1x08常用的互連函數(shù)如下：1恒等置換：82交換置換Exchange實(shí)現(xiàn)二進(jìn)制地址編號(hào)中第0位位值不同的輸入和輸出端之間的連接。

E(xn-1xn-2...

x1x0)=xn-1xn-2...

x1x0其他互連函數(shù)還有：方體置換、均勻洗牌置換、蝶式置換、位序顛倒置換、移數(shù)置換、加減2i置換92交換置換Exchange實(shí)現(xiàn)二進(jìn)制地址編號(hào)中第0位位值不3、方體置換Cube當(dāng)n=3時(shí)，共有3種函數(shù)，每種函數(shù)能夠表示8個(gè)結(jié)點(diǎn)之間的連接關(guān)系。由于交換函數(shù)主要用于超立方體互連網(wǎng)中，因此也稱為超立方體函數(shù)，用Cube表示，如：Cube0、Cube1、Cube2等。用交換函數(shù)構(gòu)成的互連網(wǎng)絡(luò)的結(jié)點(diǎn)度為n，網(wǎng)絡(luò)直徑也為n。103、方體置換Cube10變化發(fā)生在0，1，2位分別是高2，1，0位相同的為一個(gè)組組內(nèi)加/減1，2，4C0C2C111變化發(fā)生在0，1，2位C0C2C1114、均勻洗牌置換Perfectshuffle把二進(jìn)制結(jié)點(diǎn)循環(huán)左移一位。子混洗(subshuffle)S(k)最低k位循環(huán)左移一位超混洗牌(supershuffle)S(k)最高k位循環(huán)左移一位顯然成立：逆混洗函數(shù)：教材P397L2,3,6錯(cuò)124、均勻洗牌置換Perfectshuffle124、均勻洗牌置換Perfectshuffle子洗牌是將整組數(shù)據(jù)分成若干個(gè)子組，對(duì)每個(gè)子組完成均勻洗牌變換。S(2)分兩組0，1，2，3；4，5，6，7只用均勻洗牌函數(shù)不能實(shí)現(xiàn)任意結(jié)點(diǎn)之間的互連通常用均勻洗牌函數(shù)與其他函數(shù)，如交換函數(shù)一起構(gòu)成互連網(wǎng)絡(luò)。均勻洗牌與逆均勻洗牌是兩種十分有用的互連函數(shù)以它們代表的鏈路與以交換置換代表的開關(guān)多級(jí)組合起來可構(gòu)成Omega(Ω)網(wǎng)絡(luò)與逆Omega(Ω^-1)網(wǎng)絡(luò)。

逆均勻洗牌是均勻洗牌的逆函數(shù)，兩者的輸入端和輸出端正好互換134、均勻洗牌置換Perfectshuffle135、蝶式置換Butterfly蝶式函數(shù)的名稱來自于FFT變換時(shí)的圖形，如蝴蝶式樣。將輸入端二進(jìn)制結(jié)點(diǎn)號(hào)的最高位和最低位互換位置。子蝶式(subbutterfly)B(k)最低k位的最高位與最低位互換位置超蝶式(superbutterfly)B(k)最高k位的最高位與最低位互換位置顯然成立教材P398L1,2錯(cuò)145、蝶式置換Butterfly蝶式函數(shù)的名稱來自于FFT變換5、蝶式置換Butterfly與全混洗函數(shù)類似，只用蝶式函數(shù)也不能實(shí)現(xiàn)任意結(jié)點(diǎn)之間的互連。155、蝶式置換Butterfly156、位序顛倒置換BitReversal將輸入端二進(jìn)制地址的位序反過來就得相應(yīng)輸出的地址。子反位序函數(shù)：最低k位的位序反過來超反位序函數(shù)：最高k位的位序反過來對(duì)于n=3的情況，正好有R=B，R(2)=B(2)，R(2)=B(2)。166、位序顛倒置換BitReversal將輸入端二進(jìn)制地址的7、移數(shù)置換將輸入端數(shù)組循環(huán)移動(dòng)一定的位置向輸出端傳輸。也可以將整個(gè)輸入數(shù)組分成若干個(gè)子數(shù)組，在子數(shù)組內(nèi)進(jìn)行循環(huán)移數(shù)置換，這種段內(nèi)循環(huán)移數(shù)的表達(dá)式可寫成為兩個(gè)式子如下： (a)移數(shù)量換k=2(b)段內(nèi)移數(shù)置換k=1,r=2177、移數(shù)置換將輸入端數(shù)組循環(huán)移動(dòng)一定的位置向輸出端傳輸。178、加減2i置換其中：0xN-1，0in-1，n=log2N。188、加減2i置換188、加減2i置換通常采用移數(shù)函數(shù)可以構(gòu)成環(huán)型網(wǎng)(包括單向環(huán)網(wǎng)、雙向環(huán)網(wǎng)、弦環(huán)網(wǎng))、方格網(wǎng)、移數(shù)網(wǎng)等。例如，Illiac函數(shù)是構(gòu)成IlliacIV陣列的基礎(chǔ)，它包含PM20和PM2n/2等四個(gè)互連函數(shù)。采用全部移數(shù)函數(shù)構(gòu)成網(wǎng)絡(luò)稱為移數(shù)網(wǎng)，移數(shù)網(wǎng)的結(jié)點(diǎn)度d=2n-1，網(wǎng)絡(luò)直徑D=n/2198、加減2i置換通常采用移數(shù)函數(shù)可以構(gòu)成環(huán)型網(wǎng)(包括單向環(huán)網(wǎng)7.1.3互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù)1互連網(wǎng)絡(luò)的特性互連網(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ù)表示207.1.3互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù)1互連網(wǎng)絡(luò)的特性27.1.3互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù)(5)等分寬度：當(dāng)某一網(wǎng)絡(luò)被切成相等的兩半時(shí)，沿切口的最小邊數(shù)(通道)稱為通道等分寬度，用b表示。于是線等分寬度就是B=b×w，w為通道寬度(用位表示)。等分寬度是說明沿等分網(wǎng)絡(luò)最大通信帶寬的一個(gè)參數(shù)。網(wǎng)絡(luò)的所有其它橫截面都應(yīng)限在等分寬度之內(nèi)。(6)結(jié)點(diǎn)間的線長：兩個(gè)結(jié)點(diǎn)間連線的長度。用米、公里等表示(7)對(duì)稱性：從任何結(jié)點(diǎn)看到拓?fù)浣Y(jié)構(gòu)都是一樣的網(wǎng)絡(luò)稱為對(duì)稱網(wǎng)絡(luò)。對(duì)稱網(wǎng)絡(luò)比較易實(shí)現(xiàn)，編程也較容易。217.1.3互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù)(5)等分寬度：22互連網(wǎng)絡(luò)傳輸?shù)男阅軈?shù)一臺(tái)機(jī)器發(fā)送消息給另一臺(tái)機(jī)器時(shí)，發(fā)送方的步驟如下：(1)用戶程序把要發(fā)送的數(shù)據(jù)拷貝到操作系統(tǒng)的緩沖區(qū)。(2)操作系統(tǒng)把緩沖區(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ā)回答信號(hào)。(3)把接收到的數(shù)據(jù)拷貝到用戶地址空間。發(fā)送方接收到回答信號(hào)后，釋放系統(tǒng)緩沖區(qū)222互連網(wǎng)絡(luò)傳輸?shù)男阅軈?shù)一臺(tái)機(jī)器發(fā)送消息給另一臺(tái)機(jī)器時(shí)，發(fā)互連網(wǎng)絡(luò)在傳輸方面的主要性能參數(shù)(1)頻帶寬度(Bandwidth)： 互連網(wǎng)絡(luò)傳輸信息的最大速率(2)傳輸時(shí)間(Transmissiontime)： 等于消息長度除以頻寬(3)飛行時(shí)間(Timeofflight)：

第一位信息到達(dá)接收方所花費(fèi)的時(shí)間(4)傳輸時(shí)延(Transportlatency)： 等于飛行時(shí)間與傳輸時(shí)間之和(5)發(fā)送方開銷(Senderoverhead)： 處理器把消息放到互連網(wǎng)絡(luò)的時(shí)間(6)接收方開銷(Receiveroverhead)： 處理器把消息從網(wǎng)絡(luò)取出來的時(shí)間23互連網(wǎng)絡(luò)在傳輸方面的主要性能參數(shù)(1)頻帶寬度(Bandw一個(gè)消息的總時(shí)延總時(shí)延=發(fā)送方開銷+飛行時(shí)間+消息長度/頻寬+接收方開銷24一個(gè)消息的總時(shí)延總時(shí)延=發(fā)送方開銷+飛行時(shí)間+消息長度/頻寬例7.1假設(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%，相距100米時(shí)總時(shí)延相距1000公里時(shí)的總時(shí)延25例7.1假設(shè)一個(gè)網(wǎng)絡(luò)的頻寬為10Mb/S，發(fā)送方開銷為2307.1.4互連網(wǎng)絡(luò)的種類互連網(wǎng)絡(luò)的種類很多，分類方法也很多以互連特性為特征，可分為如下幾類靜態(tài)互連網(wǎng)絡(luò)：連接通路是固定的，一般靜態(tài)互連網(wǎng)絡(luò)不能實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連循環(huán)互連網(wǎng)絡(luò)：通過多次重復(fù)使用同一個(gè)單級(jí)互連網(wǎng)絡(luò)以實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連多級(jí)互連網(wǎng)絡(luò)：將多套相同的單級(jí)互連網(wǎng)絡(luò)連接起來，實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連全排列互連網(wǎng)絡(luò)：不僅能夠?qū)崿F(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連，而且能夠同時(shí)實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連全交叉開關(guān)網(wǎng)絡(luò)：除了能夠同時(shí)實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連之外，還能夠?qū)崿F(xiàn)廣播和多播267.1.4互連網(wǎng)絡(luò)的種類互連網(wǎng)絡(luò)的種類很多，分類方法也很多21靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)是指在各結(jié)點(diǎn)間有專用的連接通路，且在運(yùn)行中不能改變的網(wǎng)絡(luò)在靜態(tài)互連網(wǎng)絡(luò)中，每一個(gè)開關(guān)元件固定地與一個(gè)結(jié)點(diǎn)相連，建立該結(jié)點(diǎn)與鄰近結(jié)點(diǎn)之間的連接通路，直接實(shí)現(xiàn)兩結(jié)點(diǎn)間的通信一維的有線性陣列結(jié)構(gòu)二維的有環(huán)形、星形、樹形、網(wǎng)格形等三維的有立方體等三維以上的有超立方體等271靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)是指在各結(jié)點(diǎn)間有專用的連接通路，(1)線性陣列一種一維網(wǎng)絡(luò)，其中N個(gè)結(jié)點(diǎn)用N-1條鏈路連成一行內(nèi)部的結(jié)點(diǎn)度為2，端點(diǎn)的結(jié)點(diǎn)度為1。直徑為N-1當(dāng)N大時(shí)，直徑也比較大。等分寬度b=1線性陣列是最簡單的拓?fù)浣Y(jié)構(gòu)。這種結(jié)構(gòu)不對(duì)稱，當(dāng)N很大時(shí)，通信效率很低在N很小的情況下，如N=2，實(shí)現(xiàn)線性陣列是相當(dāng)經(jīng)濟(jì)的。由于直徑隨N線性增大，因此當(dāng)N比較大時(shí)，就不應(yīng)使用這種網(wǎng)絡(luò)了28(1)線性陣列一種一維網(wǎng)絡(luò)，其中N個(gè)結(jié)點(diǎn)用N-1條鏈路連成一(1)線性陣列線性陣列與總線的區(qū)別是很大的，后者是通過切換與其連接的許多結(jié)點(diǎn)來實(shí)現(xiàn)時(shí)分特性的線性陣列允許不同的源結(jié)點(diǎn)和目的結(jié)點(diǎn)對(duì)并發(fā)使用系統(tǒng)的不同部分(通道)765489101115141312012329(1)線性陣列線性陣列與總線的區(qū)別是很大的，后者是通過切換與(2)環(huán)和帶弦環(huán)(3)循環(huán)移數(shù)網(wǎng)絡(luò)采用移數(shù)函數(shù)。使用不同的移數(shù)函數(shù)，可以構(gòu)成多種環(huán)形網(wǎng)單向環(huán)行網(wǎng)右環(huán)網(wǎng)，采用PM2+0函數(shù)左環(huán)網(wǎng)，采用PM2-0函數(shù)雙向環(huán)行網(wǎng)：又稱為一維鄰居網(wǎng)，采用{PM2+0，PM2-0}函數(shù)環(huán)行網(wǎng)是對(duì)稱的，結(jié)點(diǎn)度是常數(shù)2雙向環(huán)網(wǎng)的直徑為N/2，單向環(huán)形網(wǎng)的直徑是N將結(jié)點(diǎn)度由2提高至3，可得到弦環(huán)網(wǎng)增加的弦愈多，則結(jié)點(diǎn)度愈高，網(wǎng)絡(luò)直徑愈小循環(huán)移數(shù)網(wǎng)絡(luò)也是一種環(huán)形網(wǎng)，它將環(huán)上每個(gè)結(jié)點(diǎn)與其距離為2的整數(shù)冪的結(jié)點(diǎn)之間連接構(gòu)成循環(huán)移數(shù)網(wǎng)的結(jié)點(diǎn)度為2n-1，直徑為[n/2]30(2)環(huán)和帶弦環(huán)(3)循環(huán)移數(shù)網(wǎng)絡(luò)采用移數(shù)函數(shù)。使用不同的移10234576循環(huán)移數(shù)網(wǎng)(2)環(huán)和帶弦環(huán)(3)循環(huán)移數(shù)網(wǎng)絡(luò)0123456789101112131415度為3的帶弦環(huán)01234567891011121314153110234576循環(huán)移數(shù)網(wǎng)(2)環(huán)和帶弦環(huán)(3)循環(huán)移數(shù)網(wǎng)絡(luò)二叉樹網(wǎng)二叉胖樹網(wǎng)星形網(wǎng)(4)樹形和星形(5)胖樹形一棵k層完全平衡二叉樹有N=2^k-1個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)度3，直徑2(k-1)星形是一種特殊的2層樹，結(jié)點(diǎn)度很高，為d=N-1，直徑2星形結(jié)構(gòu)已用于有集中監(jiān)督結(jié)點(diǎn)的系統(tǒng)中二叉胖樹的結(jié)點(diǎn)度從葉子結(jié)點(diǎn)往根結(jié)點(diǎn)逐漸增加胖樹緩解了一般二叉樹根結(jié)點(diǎn)通信速度高的矛盾32二叉樹網(wǎng)二叉胖樹網(wǎng)星形網(wǎng)(4)樹形和星形(5)胖樹形32(6)網(wǎng)格和環(huán)網(wǎng)形網(wǎng)格網(wǎng)是一種比較流行的網(wǎng)絡(luò)結(jié)構(gòu)，有各種變體形式在IlliacIV、MPP、DAP、CM-2和InetlParagon中得到了實(shí)現(xiàn)一般網(wǎng)格網(wǎng)，N=n^k結(jié)點(diǎn)的k維網(wǎng)格的結(jié)點(diǎn)度為2k，直徑為k(n-1)環(huán)網(wǎng)形網(wǎng)格網(wǎng)沿陣列每行每列都有環(huán)形連接。一個(gè)n×n二元環(huán)網(wǎng)的結(jié)點(diǎn)度為4，直徑為2[n/2]。環(huán)網(wǎng)是一種對(duì)稱的拓?fù)浣Y(jié)構(gòu)。附加的回繞連接使直徑減至的網(wǎng)格的一半一個(gè)n×nIlliac網(wǎng)格直徑為d=n-1，為純網(wǎng)格直徑的一半IlliacIV的8×8Illiac網(wǎng)格，其結(jié)點(diǎn)度為4，直徑為733(6)網(wǎng)格和環(huán)網(wǎng)形網(wǎng)格網(wǎng)是一種比較流行的網(wǎng)絡(luò)結(jié)構(gòu)，有各種變體網(wǎng)格形環(huán)形網(wǎng)Illiac網(wǎng)(6)網(wǎng)格和環(huán)網(wǎng)形34網(wǎng)格形環(huán)形網(wǎng)Illiac網(wǎng)(6)網(wǎng)格和環(huán)網(wǎng)形34(7)搏動(dòng)式陣列這是一類為實(shí)現(xiàn)確定算法而設(shè)計(jì)的多維流水線陣列結(jié)構(gòu)圖7.15(d)所示就是為完成矩陣相乘而專門設(shè)計(jì)的搏動(dòng)式陣列。內(nèi)部結(jié)點(diǎn)度為6一般說來，靜態(tài)搏動(dòng)式陣列可在多個(gè)方向上使數(shù)據(jù)流變成以流水線方式工作商用InteliWarp系統(tǒng)就是用搏動(dòng)式結(jié)構(gòu)設(shè)計(jì)而成自從1978年Kung和Leiserson提出搏動(dòng)式陣列后，它已成為廣泛研究的領(lǐng)域通過確定的互連和同步操作，搏動(dòng)式陣列可與算法的通信結(jié)構(gòu)相匹配對(duì)信號(hào)/圖象處理等特殊應(yīng)用，搏動(dòng)式陣列可提供更好的性能/價(jià)格比但結(jié)構(gòu)的實(shí)用性有限，而且編制程序也很難35(7)搏動(dòng)式陣列這是一類為實(shí)現(xiàn)確定算法而設(shè)計(jì)的多維流水線陣列(7)搏動(dòng)式陣列36(7)搏動(dòng)式陣列36n維立方體由N=2^n個(gè)結(jié)點(diǎn),分布在n維上,每維有兩個(gè)結(jié)點(diǎn)超立方體網(wǎng)采用交換函數(shù)，結(jié)點(diǎn)度為n，直徑也為n4-立方體可通過將兩個(gè)3-立方體的相應(yīng)結(jié)點(diǎn)互連組成(8)超立方體YXZ011000010110111101100n維立方體由N=2^n個(gè)結(jié)點(diǎn),分布在n維上,每維有兩個(gè)結(jié)(9)帶環(huán)立方體這種結(jié)構(gòu)是從超立方體改進(jìn)而來的一個(gè)3-立方體可改成帶環(huán)3-立方體(CCC)。構(gòu)成的辦法是將3-立方體的角結(jié)點(diǎn)(頂角)用一個(gè)結(jié)點(diǎn)環(huán)來代替從一個(gè)k-立方體構(gòu)成一個(gè)有n=2^k個(gè)結(jié)點(diǎn)環(huán)的帶環(huán)k-立方體所用的辦法是用k個(gè)結(jié)點(diǎn)的環(huán)取代k維超立方體的每個(gè)頂角這樣，一個(gè)k-立方體可變成k×2^k個(gè)結(jié)點(diǎn)的k-CCC3-CCC的直徑為6，比原來3-立方體的直徑大一倍。一般說來，k-CCC的網(wǎng)格直徑2k。CCC的主要改進(jìn)之處即在其結(jié)點(diǎn)度為常數(shù)3，與超立方體的維數(shù)無關(guān)一超立方體有N=2^n結(jié)點(diǎn)。一個(gè)有同樣N結(jié)點(diǎn)數(shù)的CCC一定是由低維k-立方體組成，即2^n=k×2^k，其中k<n對(duì)應(yīng)于n=6和k=4的情況，一個(gè)64結(jié)點(diǎn)的CCC可用4結(jié)點(diǎn)的環(huán)取代4-立方體的角結(jié)點(diǎn)組成。CCC的直徑為2k=8，比6-立方體的6要長些。但是，CCC的結(jié)點(diǎn)度為3，比6-立方體的結(jié)點(diǎn)度6要小容許一定的時(shí)延,CCC是一種構(gòu)造可擴(kuò)展系統(tǒng)的較好的結(jié)構(gòu)38(9)帶環(huán)立方體這種結(jié)構(gòu)是從超立方體改進(jìn)而來的38(9)帶環(huán)立方體YXZ01100001011011110110039(9)帶環(huán)立方體YXZ0110000101101111011(10)k元n-立方體網(wǎng)絡(luò)環(huán)形、網(wǎng)格形、環(huán)網(wǎng)形、二元n-立方體(超立方體)和W網(wǎng)絡(luò)都是k元n-立方體網(wǎng)絡(luò)系列的拓?fù)渫瑯?gòu)體參數(shù)n是立方體的維數(shù)，k是基數(shù)或者說是沿每個(gè)方向的結(jié)點(diǎn)數(shù)(多重性)。這兩個(gè)數(shù)與網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)N的關(guān)系為k元n-立方體的結(jié)點(diǎn)可用基數(shù)為k的n位地址A=a1a2…an來表示，其中ai代表第i維結(jié)點(diǎn)位置。為簡單起見，所有鏈路都認(rèn)為是雙向的。網(wǎng)絡(luò)中每條線代表兩個(gè)通信通道，每個(gè)方向一個(gè)40(10)k元n-立方體網(wǎng)絡(luò)環(huán)形、網(wǎng)格形、環(huán)網(wǎng)形、二元n-立方圖7.17k=4和n=3的k元n-立方體網(wǎng)絡(luò)(1)4結(jié)點(diǎn)串成綠色環(huán)(2)4綠色環(huán)并排成面，同一列用黃色環(huán)連接(3)4黃色面堆成體，同一行用藍(lán)色環(huán)連接41圖7.17k=4和n=3的k元n-立方體網(wǎng)絡(luò)41(a)傳統(tǒng)環(huán)網(wǎng)(4元2-立方體) (b)折疊連接的環(huán)網(wǎng)SHOWAVI42422動(dòng)態(tài)互連網(wǎng)絡(luò)動(dòng)態(tài)互連網(wǎng)絡(luò)設(shè)置有源開關(guān)根據(jù)需要借助控制信號(hào)對(duì)連接通路加以重新組合，實(shí)現(xiàn)所要求的通信模式包括總線、多級(jí)互連網(wǎng)和交叉開關(guān)網(wǎng)絡(luò)432動(dòng)態(tài)互連網(wǎng)絡(luò)動(dòng)態(tài)互連網(wǎng)絡(luò)設(shè)置有源開關(guān)43(1)總線總線系統(tǒng)是一組導(dǎo)線和插座用于處理與總線相連接的處理機(jī)、存儲(chǔ)器模塊和外圍設(shè)備間的數(shù)據(jù)業(yè)務(wù)總線被稱為多個(gè)功能模塊間爭用總線或時(shí)分總線總線系統(tǒng)與其它兩種動(dòng)態(tài)連接網(wǎng)絡(luò)相比，其價(jià)格較低，帶寬較窄。有很多可用的工業(yè)和IEEE總線標(biāo)準(zhǔn)44(1)總線總線系統(tǒng)是一組導(dǎo)線和插座用于處理與總線相連接的處理(2)開關(guān)模塊一個(gè)ab開關(guān)模塊有a個(gè)輸入和b個(gè)輸出。一個(gè)二元開關(guān)則與a=b=2的22開關(guān)模塊相對(duì)應(yīng)。實(shí)際中a和b通常選為a=b=2^k，k>=1最常用的二元開關(guān)：a=b=2每個(gè)輸入可與一個(gè)或多個(gè)輸出相連，但是在輸出端必須避免發(fā)生沖突。一對(duì)一和一對(duì)多映射是容許的；但不容許有多對(duì)一映射只容許一對(duì)一映射時(shí)稱為置換連接，稱這種開關(guān)為n×n交叉開關(guān)具有直通和交換兩種功能的交換開關(guān)稱為二功能開關(guān)，或交換開關(guān)。用一位控制信號(hào)控制具有所有四種功能的交換開關(guān)稱為四功能開關(guān)，用兩位控制信號(hào)控制45(2)開關(guān)模塊一個(gè)ab開關(guān)模塊有a個(gè)輸入和b個(gè)輸出。一個(gè)二直通交換上播下播模塊大小合法狀態(tài)交換連接2×2424×4256248×81677721640320n×nnnn!交換開關(guān)和合法狀態(tài)46直通交換上播下播模塊大小合法狀態(tài)交換連接2×2424×425(3)多級(jí)網(wǎng)絡(luò)能夠?qū)崿F(xiàn)結(jié)點(diǎn)到結(jié)點(diǎn)之間的任意互連是互連網(wǎng)絡(luò)的一種基本功能多級(jí)互連網(wǎng)絡(luò)采用多個(gè)相同的或不同的互連網(wǎng)絡(luò)直接連接起來屬于組合邏輯線路，一個(gè)時(shí)鐘周期就能夠?qū)崿F(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連多級(jí)互連網(wǎng)絡(luò)采用的關(guān)鍵技術(shù)(1)交換開關(guān)(2)交換開關(guān)之間的拓?fù)溥B接(3)對(duì)交換開關(guān)的不同控制方式(3)多級(jí)網(wǎng)絡(luò)能夠?qū)崿F(xiàn)結(jié)點(diǎn)到結(jié)點(diǎn)之間的任意互連是互連網(wǎng)絡(luò)的一(3)多級(jí)網(wǎng)絡(luò)(3a)拓?fù)浣Y(jié)構(gòu)(級(jí)間連接)前一級(jí)交換開關(guān)的輸出端與后一級(jí)交換開關(guān)的輸入端之間的連接模式稱為拓?fù)浣Y(jié)構(gòu)通常采用前面介紹的互連函數(shù)實(shí)現(xiàn)拓?fù)浣Y(jié)構(gòu)從結(jié)點(diǎn)的輸出到第一級(jí)交換開關(guān)的輸入，及從最后一級(jí)交換開關(guān)的輸出到結(jié)點(diǎn)的輸入也可以采用拓?fù)浣Y(jié)構(gòu)連接(3b)控制方式在多級(jí)互連網(wǎng)絡(luò)中有多級(jí)交換開關(guān)，每一級(jí)又有多個(gè)交換開關(guān)(1)級(jí)控制：同一級(jí)交換開關(guān)使用同一個(gè)控制信號(hào)控制(2)單元級(jí)控制：每個(gè)交換開關(guān)分別控制(3)部分級(jí)控制：如，第i級(jí)使用i+1個(gè)控制信號(hào)控制(0<=i<=n-1)同一個(gè)多級(jí)互連網(wǎng)絡(luò)分別使用三種不同的控制方式，可以構(gòu)成三種不同的互連網(wǎng)絡(luò)(3)多級(jí)網(wǎng)絡(luò)(3a)拓?fù)浣Y(jié)構(gòu)(級(jí)間連接)圖7.20一種由a×b開關(guān)模塊和級(jí)間連接模式49圖7.20一種由a×b開關(guān)模塊和級(jí)間連接模式49采用二功能開關(guān)，總共需要開關(guān)n2^(n-1)個(gè)。采用交換函數(shù)構(gòu)成拓?fù)浣Y(jié)構(gòu)，各級(jí)分別采用E0、E1、…En-1交換函數(shù)當(dāng)所有開關(guān)都直通時(shí)，實(shí)現(xiàn)恒等變換當(dāng)A、B、C、D四個(gè)開關(guān)交換，其余直通時(shí)實(shí)現(xiàn)E0互連函數(shù)當(dāng)E、F、G、H四個(gè)開關(guān)交換，其余直通時(shí)實(shí)現(xiàn)E1互連函數(shù)當(dāng)I、J、K、L四個(gè)開關(guān)交換，其余直通時(shí)實(shí)現(xiàn)E2互連函數(shù)采用三種不同的控制方式，可以構(gòu)成三種不同的互連網(wǎng)絡(luò)。采用級(jí)控制可以構(gòu)成STARAN交換網(wǎng)采用部分級(jí)控制，可以構(gòu)成STARAN移數(shù)網(wǎng)采用單元控制可以構(gòu)成間接二進(jìn)制n方體網(wǎng)(3c)多級(jí)立方體網(wǎng)50采用二功能開關(guān)，總共需要開關(guān)n2^(n-1)個(gè)。(3c)

B(2) B(3) S-1ABCDEFGHIJKL0123456701234567k=0k=1k=2(3c)多級(jí)立方體網(wǎng)51ABCDEFGHIJKL0123456701234567k=(4)Ω網(wǎng)絡(luò)16×16Ω網(wǎng)絡(luò)，共需4級(jí)2×2開關(guān)網(wǎng)絡(luò)左側(cè)有16個(gè)輸入，右側(cè)有16個(gè)輸出ISC是對(duì)16個(gè)對(duì)象的均勻洗牌模式2路洗牌相當(dāng)于n個(gè)輸入端平均地分成2個(gè)子組，然后2個(gè)子組均勻地洗牌一個(gè)n輸入的Ω網(wǎng)絡(luò)需要log2n級(jí)2×2開關(guān)，每級(jí)要用n/2個(gè)開關(guān)模塊，網(wǎng)絡(luò)共需(nlog2n)/2個(gè)開關(guān)不同的開關(guān)狀態(tài)組合可實(shí)現(xiàn)各種置換、廣播或從輸入到輸出的其它連接每級(jí)的拓?fù)浣Y(jié)構(gòu)相同采用單元控制能夠?qū)崿F(xiàn)任意一個(gè)輸入端到任意一個(gè)輸出端的連接不能同時(shí)實(shí)現(xiàn)多個(gè)輸入端到多個(gè)輸出端的連接通過檢查二進(jìn)制目的地址編碼來控制數(shù)據(jù)路徑目的地址編碼從高位開始的第i位為0時(shí)，第i級(jí)的2×2開關(guān)的輸入端與上輸出端連接，否則輸入端與下輸出端連接52(4)Ω網(wǎng)絡(luò)16×16Ω網(wǎng)絡(luò)，共需4級(jí)2×2開關(guān)52均勻洗牌置換輸入1可連接到哪幾個(gè)輸出?53均勻洗牌置換輸入1可連接到哪幾個(gè)輸出?53

(5)基準(zhǔn)網(wǎng)絡(luò)Wu和Feng研究過多級(jí)互連網(wǎng)絡(luò)之間的關(guān)系基準(zhǔn)網(wǎng)絡(luò)可如圖7.22(a)所示遞歸生成第1級(jí)為一個(gè)N×N模塊第2級(jí)為兩個(gè)(N/2)×(N/2)子模塊，以C0和C1表示以上構(gòu)成方法可遞歸用于子模塊直至得到2×2的N/2子模塊為止各小框和最終的子模塊構(gòu)件是2×2開關(guān)，每個(gè)有兩個(gè)合法連接狀態(tài)：兩個(gè)輸入和兩個(gè)輸出間的直送和交叉連接54

(5)基準(zhǔn)網(wǎng)絡(luò)Wu和Feng研究過多級(jí)互連網(wǎng)絡(luò)之間的每個(gè)交換開關(guān)的輸出分成上下兩組，分別連到兩個(gè)N/255551組16結(jié)點(diǎn)S-12組8結(jié)點(diǎn)S-14組4結(jié)點(diǎn)S-1遞歸終點(diǎn)為1個(gè)2x2子模塊，即僅有兩個(gè)結(jié)點(diǎn)56遞歸終點(diǎn)為1個(gè)2x2子模塊，即僅有兩個(gè)結(jié)點(diǎn)56(6)交叉開關(guān)網(wǎng)絡(luò)全交叉開關(guān)網(wǎng)絡(luò)能夠同時(shí)實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連還能夠?qū)崿F(xiàn)廣播和多播全交叉開關(guān)網(wǎng)絡(luò)的帶寬和互連特性最好在多處理機(jī)系統(tǒng)中，處理機(jī)、存儲(chǔ)器和IOP之間用交叉開關(guān)網(wǎng)絡(luò)連接可看作是一個(gè)單級(jí)開關(guān)網(wǎng)絡(luò)。象電話交換機(jī)一樣，交叉點(diǎn)開關(guān)能在對(duì)偶(源、目的)之間形成動(dòng)態(tài)連接，每個(gè)交叉點(diǎn)開關(guān)在對(duì)偶間提供一條專用連接通路，開關(guān)可根據(jù)程序的要求動(dòng)態(tài)地設(shè)置“開”或“關(guān)”57(6)交叉開關(guān)網(wǎng)絡(luò)全交叉開關(guān)網(wǎng)絡(luò)能夠同時(shí)實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之另一種分類58另一種分類587.2消息傳遞機(jī)制研究各種尋徑方法，并分析它們的通信時(shí)延問題引入虛擬通道的概念，說明怎樣用虛擬通道來避免死鎖確定的和自適應(yīng)兩種尋徑算法拓?fù)浣Y(jié)構(gòu)與尋徑策略有一定的關(guān)系597.2消息傳遞機(jī)制研究各種尋徑方法，并分析它們的通信時(shí)延問7.2.1消息尋徑方式四種尋徑方式線路交換存儲(chǔ)轉(zhuǎn)發(fā)虛擬直通蟲蝕尋徑1.消息格式消息是結(jié)點(diǎn)間通信的邏輯單位常常由任意數(shù)目的長度固定的包所組成其長度是可變的。包是包含尋徑目的地址的基本單位。每個(gè)包需要一個(gè)序號(hào)，以便重新組裝消息。可以將包進(jìn)一步分成一些固定長度的片尋徑信息和序號(hào)形成頭片，其余的片是數(shù)據(jù)片。607.2.1消息尋徑方式四種尋徑方式60消息包片DDDDDDSRR：在消息傳遞網(wǎng)絡(luò)中通信的信息單位：消息、包和片的格式R：導(dǎo)徑信息S：序號(hào)D：數(shù)據(jù)片包消息包片據(jù)片頭片尾片……順序號(hào)數(shù)bbbbbbbb61消息包片DDDDDDSRR：在消息傳遞網(wǎng)絡(luò)中通信的信息單位：在采用存儲(chǔ)轉(zhuǎn)發(fā)尋徑方式的多計(jì)算機(jī)系統(tǒng)中，包是信息傳送的最小單位在采用蟲蝕尋徑網(wǎng)絡(luò)的多計(jì)算機(jī)中，包可以進(jìn)一步分成片。片的長度往往受網(wǎng)絡(luò)大小的影響256個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)需要片長為8位包的長度取決于尋徑方式和網(wǎng)絡(luò)的實(shí)現(xiàn)方法典型的包的長度為64～512位。序號(hào)可能占用1～2個(gè)片，取決于消息的長度包和片的大小還與通道頻寬、尋徑器設(shè)計(jì)以及網(wǎng)絡(luò)流量密度等有關(guān)62在采用存儲(chǔ)轉(zhuǎn)發(fā)尋徑方式的多計(jì)算機(jī)系統(tǒng)中，包是信息傳送的最小單2、四種尋徑方式兩大類線路交換包交換(存儲(chǔ)轉(zhuǎn)發(fā)、虛擬直通和蟲蝕尋徑)(1)線路交換(circuitswitch)先建立一條從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通路，然后再傳遞消息傳輸時(shí)延公式T=(Lt/B)*D+L/B其中：Lt為建立路徑所需小信息包的長度L為信息包的長度D為經(jīng)過的結(jié)點(diǎn)數(shù)B為帶寬優(yōu)點(diǎn)：實(shí)際通信時(shí)間較短，使用緩沖區(qū)少缺點(diǎn)：建立源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通路開銷很大，占用物理通路時(shí)間長632、四種尋徑方式兩大類63(2)存儲(chǔ)轉(zhuǎn)發(fā)(storeandforward)每個(gè)結(jié)點(diǎn)有一個(gè)包緩沖區(qū)，包從源結(jié)點(diǎn)經(jīng)過中間結(jié)點(diǎn)到達(dá)目的結(jié)點(diǎn)存儲(chǔ)轉(zhuǎn)發(fā)網(wǎng)絡(luò)的時(shí)延與源和目的地之間的距離成正比。傳輸時(shí)延公式：T=(L/B)*D+L/B=(D+1)*L/B優(yōu)點(diǎn)：占用物理通路的時(shí)間比較短缺點(diǎn)：包緩沖區(qū)大，時(shí)延大(與結(jié)點(diǎn)距離成正比)64(2)存儲(chǔ)轉(zhuǎn)發(fā)(storeandforward)每個(gè)結(jié)點(diǎn)(3)虛擬直通(virtualcutthrough)當(dāng)接收到用作尋徑的消息頭部時(shí)，即開始路由選擇。通信時(shí)延公式：T=(Lh/B)*D+L/B=(Lh*D+L)/B其中：Lh是消息的尋徑頭部的長度，一般有，L>>Lh×D；通信時(shí)延可以近似為：T=L/B與結(jié)點(diǎn)數(shù)無關(guān)當(dāng)出現(xiàn)尋徑阻塞時(shí)，只能將整個(gè)消息存儲(chǔ)在尋徑結(jié)點(diǎn)中主要優(yōu)點(diǎn)：通信延遲與結(jié)點(diǎn)數(shù)無關(guān)主要缺點(diǎn)：每個(gè)結(jié)點(diǎn)需要有足夠大的緩沖區(qū)來存儲(chǔ)最大信息包在最壞的情況下與存儲(chǔ)轉(zhuǎn)發(fā)方式的通信時(shí)延是一樣的，經(jīng)過的每個(gè)結(jié)點(diǎn)都發(fā)生阻塞，都需緩沖65(3)虛擬直通(virtualcutthrough)當(dāng)接(4)蟲蝕尋徑(wormhole)把包分成更小的片。每個(gè)結(jié)點(diǎn)的尋徑器中有片緩沖區(qū)用頭片直接開辟一條從輸入結(jié)點(diǎn)到輸出結(jié)點(diǎn)的路徑。每個(gè)消息中的片以流水方式在網(wǎng)絡(luò)中向前“蠕動(dòng)”當(dāng)消息的頭片到達(dá)一個(gè)結(jié)點(diǎn)A的尋徑器后，尋徑器根據(jù)頭片的尋徑消息立即做出路由選擇如所選擇的通道空閑且所選擇的結(jié)點(diǎn)B的片緩沖區(qū)可用，那么這個(gè)頭片就不必等待，直接通過結(jié)點(diǎn)A傳向下一個(gè)結(jié)點(diǎn)B隨后的其它數(shù)據(jù)片跟著相應(yīng)地向前“蠕動(dòng)”一步當(dāng)消息的尾片向前“蠕動(dòng)”一步之后，它剛才所占有的結(jié)點(diǎn)就被放棄如果所選擇的通道或的結(jié)點(diǎn)的片緩沖區(qū)不可用時(shí)，頭片必須在該結(jié)點(diǎn)的片緩沖區(qū)中等待，其它數(shù)據(jù)片也在原來的結(jié)點(diǎn)上等待通信時(shí)延用公式：T=Tf×D+L/B=(Lf/B)×D+L/B=(Lf×D+L)/B其中：Lf是片的長度，Tf是片經(jīng)過一個(gè)結(jié)點(diǎn)所需時(shí)間。一般有L>>Lf×D，可近似為T=L/B，通信時(shí)延與結(jié)點(diǎn)數(shù)無關(guān)66(4)蟲蝕尋徑(wormhole)把包分成更小的片。每個(gè)結(jié)點(diǎn)蟲蝕尋徑的優(yōu)點(diǎn)每個(gè)結(jié)點(diǎn)的緩沖區(qū)較小，易于VLSI實(shí)現(xiàn)較低的網(wǎng)絡(luò)傳輸時(shí)延所有的片以流水方式向前傳輸，采用了時(shí)間并行性存儲(chǔ)轉(zhuǎn)發(fā)方式的消息包整個(gè)地從一個(gè)結(jié)點(diǎn)“跳”到另一個(gè)結(jié)點(diǎn)，通道的使用是串行的，所以它的傳輸時(shí)延基本上正比于消息在網(wǎng)絡(luò)中傳輸?shù)木嚯x蟲蝕尋徑方式的網(wǎng)絡(luò)傳輸時(shí)延正比于消息包的長度，傳輸距離對(duì)它的影響很小通道共享性好，利用率高對(duì)通道的預(yù)約和釋放是結(jié)合在一起的一個(gè)完整的過程有一段新的通道后將立即放棄用過的一段舊通道易于實(shí)現(xiàn)選播和廣播通信方式允許尋徑器復(fù)制消息包的片并把它們從其多個(gè)輸出通道輸出67蟲蝕尋徑的優(yōu)點(diǎn)每個(gè)結(jié)點(diǎn)的緩沖區(qū)較小，易于VLSI實(shí)現(xiàn)67蟲蝕尋徑的缺點(diǎn)：當(dāng)消息的一個(gè)片被阻塞時(shí)，整個(gè)消息都被阻塞，占用了結(jié)點(diǎn)資源需要采用虛擬通道的方式來避免由此引起的一連串的阻塞蟲蝕尋徑方式也可以分為無緩沖和有緩沖兩類，區(qū)別在于緩沖的大小緩沖大有利于性能的提高，但會(huì)增加結(jié)點(diǎn)的復(fù)雜度IBMSP2采用的尋徑方式就是帶緩沖的蟲蝕尋徑方式，它采用共享的存儲(chǔ)區(qū)來對(duì)輸入/輸出消息進(jìn)行緩沖68蟲蝕尋徑的缺點(diǎn)：68圖7.25幾種尋徑方式的時(shí)空?qǐng)D(a)線路開關(guān)尋徑(1)N1-->N4(2)通過識(shí)別消息頭部，N1接到N2，N2接到N3，N3接到N4(3)N1發(fā)送，以極小的延遲通過中間結(jié)點(diǎn)N2，N3到達(dá)N469圖7.25幾種尋徑方式的時(shí)空?qǐng)D(a)線路開關(guān)尋徑69(b)存儲(chǔ)轉(zhuǎn)發(fā)尋徑(1)N1-->N4(2)N1發(fā)送到N2存儲(chǔ)(3)N2轉(zhuǎn)發(fā)到N3存儲(chǔ)(4)N3轉(zhuǎn)發(fā)到N470(b)存儲(chǔ)轉(zhuǎn)發(fā)尋徑70(c)蟲蝕尋徑(1)N1-->N4(2)頭片由N1尋徑至N2，N1發(fā)送頭片到N2存儲(chǔ)(3)頭片由N2尋徑至N3，N2發(fā)送頭片到N3存儲(chǔ)

N1發(fā)送1號(hào)片到N2存儲(chǔ)(4)頭片由N3尋徑至N4，N3發(fā)送頭片到N4

N2發(fā)送1號(hào)片到N3存儲(chǔ)

N1發(fā)送2號(hào)片到N2存儲(chǔ)N1,N2,N3類似流水線的三段，頭片,1號(hào)片,2號(hào)片類似流水線的三條指令

--------流水方式，蠕動(dòng)，一個(gè)包傳送完成前，蠕動(dòng)路徑不能和其他包的蠕動(dòng)路徑交叉頭片逐個(gè)結(jié)點(diǎn)尋徑，尾片逐個(gè)結(jié)點(diǎn)放棄蠕動(dòng)路徑71(c)蟲蝕尋徑717.2.2死鎖和虛擬通道1虛擬通道虛擬通道是兩個(gè)結(jié)點(diǎn)間的邏輯鏈由源結(jié)點(diǎn)的片緩沖區(qū)、結(jié)點(diǎn)間的物理通道以及接收結(jié)點(diǎn)的片緩沖區(qū)組成物理通道由所有的虛擬通道分時(shí)共享如圖四條虛擬通道分時(shí)共享一條物理通道727.2.2死鎖和虛擬通道1虛擬通道72物理通道四條虛擬通道以片傳遞為基礎(chǔ)分時(shí)地共享一條物理通道73物理通道四條虛擬通道以片傳遞為基礎(chǔ)分時(shí)地共享一條物理通道732死鎖的產(chǎn)生和避免由于緩沖區(qū)或通道上的循環(huán)等待會(huì)引起死鎖采用存儲(chǔ)轉(zhuǎn)發(fā)尋徑的四個(gè)結(jié)點(diǎn)間出現(xiàn)緩沖區(qū)死鎖DDDDD包緩沖區(qū)CCCCC包緩沖區(qū)BBBBB包緩沖區(qū)AAAAA包緩沖區(qū)742死鎖的產(chǎn)生和避免由于緩沖區(qū)或通道上的循環(huán)等待會(huì)引起死鎖D結(jié)點(diǎn)A結(jié)點(diǎn)D結(jié)點(diǎn)B結(jié)點(diǎn)Cm3m2m1m4尋徑器C尋徑器B片緩沖區(qū)消息1消息2消息3尋徑器A消息4尋徑器D采用蟲蝕尋徑的四個(gè)結(jié)點(diǎn)之間出現(xiàn)通道死鎖75結(jié)點(diǎn)A結(jié)點(diǎn)D結(jié)點(diǎn)B結(jié)點(diǎn)Cm3m2m1m4尋徑器C尋徑器B片緩如何避免死鎖緩沖區(qū)或通道上的循環(huán)等待會(huì)引起死鎖利用虛擬通道方法可以減少死鎖。增加兩條虛擬通道V3和V4利用虛擬通道避免死鎖虛擬通道可以用單向通道或者雙向通道實(shí)現(xiàn)將兩條單向通道組合在一起可以構(gòu)成一條雙向通道虛擬通道可能會(huì)使每個(gè)請(qǐng)求可用的有效通道頻寬降低確定虛擬通道數(shù)目，需要對(duì)網(wǎng)絡(luò)吞吐量和通信時(shí)延折衰考慮實(shí)現(xiàn)數(shù)目很大的虛擬通道需要用高速的多路選擇開關(guān)76如何避免死鎖緩沖區(qū)或通道上的循環(huán)等待會(huì)引起死鎖76(b)包含循環(huán)的通道相關(guān)圖 (d)利用虛擬通道后修改的通道相關(guān)圖77777.2.3流控制策略1包沖突的解決在兩個(gè)相鄰結(jié)點(diǎn)之間傳送片時(shí)，必須具備三個(gè)條件(1)源緩沖區(qū)已存有該片(2)通道已分配好(3)接收緩沖區(qū)準(zhǔn)備接收該片接收緩沖區(qū)或輸出通道沖突的仲裁(1)把后一個(gè)包暫時(shí)存放在緩沖區(qū)(2)阻塞后一個(gè)包(3)揚(yáng)棄后一個(gè)包(4)繞道787.2.3流控制策略1包沖突的解決78圖7.31解決兩個(gè)包請(qǐng)求同一條輸出通道發(fā)生沖突時(shí)的流控制方法(a)用緩沖實(shí)現(xiàn)虛擬直徑尋徑 (b)阻塞流控制(c)揚(yáng)棄并重發(fā) (d)阻塞后繞道79圖7.31解決兩個(gè)包請(qǐng)求同一條輸出通道發(fā)生沖突時(shí)的流控制方法2確定尋徑和自適應(yīng)尋徑如何找出一條從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的路徑來傳送消息？尋徑可以分為確定和自適應(yīng)兩類采用確定尋徑時(shí)，通信路徑完全由源和目的地址確定即尋找的路徑是預(yù)先唯一確定的，與網(wǎng)絡(luò)的狀況無關(guān)自適應(yīng)尋徑與網(wǎng)絡(luò)的狀況有關(guān)，可能會(huì)有幾條路徑兩種尋徑都需要無死鎖算法802確定尋徑和自適應(yīng)尋徑如何找出一條從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的路徑來(1)確定尋徑維序?qū)剿惴ò凑斩嗑S網(wǎng)絡(luò)維序的特定順序來選擇后繼通道在二維網(wǎng)格網(wǎng)絡(luò)中稱為X-Y尋徑首先沿著X維方向確定路徑，然后沿著Y維方向選擇路徑在超立體(或n立方體)網(wǎng)絡(luò)中，采用最初由Sullivan和Bashkow于1977年提出的稱為E立方體尋徑(E-cuberouting)方法。逐維改變(a)二維網(wǎng)格網(wǎng)絡(luò)的X-Y尋徑假定從任意源結(jié)點(diǎn)s=(x1，y1)到任意目的結(jié)點(diǎn)d=(x2，y2)尋徑從s開始首先沿X方向前進(jìn)一直到d所在的第x2列為止然后沿Y方向前進(jìn)直到y(tǒng)2,即d總是首先沿X維方向?qū)剑缓笤傺豗維方向?qū)?，尋徑就不?huì)出現(xiàn)死鎖或循環(huán)等待81(1)確定尋徑維序?qū)剿惴?1與東-北、東-南、西-北及西-南的路徑方向相對(duì)應(yīng)，X-Y尋徑共有4種模式(2,1;7,6)東-北(0,7;4,2)東-南...82與東-北、東-南、西-北及西-南的路徑方向相對(duì)應(yīng)，X-Y尋徑按照維序，可以很容易地將X-Y尋徑擴(kuò)充到n維網(wǎng)絡(luò)以三維網(wǎng)格為例，可以類似地說明X-Y-Z尋徑方法X-Y方式不會(huì)產(chǎn)生死鎖尋徑，可用于存儲(chǔ)轉(zhuǎn)發(fā)或蟲蝕尋徑網(wǎng)絡(luò)，在源和目的結(jié)點(diǎn)之間形成一條距離最短的路徑對(duì)于環(huán)網(wǎng)網(wǎng)絡(luò)，采用維序?qū)椒椒ú荒艿玫阶疃搪窂綖榱藴p少網(wǎng)絡(luò)流量或其它原因，不會(huì)產(chǎn)生死鎖的非最短尋徑算法有時(shí)會(huì)使包通過的路徑較長83按照維序，可以很容易地將X-Y尋徑擴(kuò)充到n維網(wǎng)絡(luò)83(b)超立方體網(wǎng)絡(luò)的E立方體尋徑假設(shè)有一N=2n個(gè)結(jié)點(diǎn)的n方體。每個(gè)結(jié)點(diǎn)的二進(jìn)制編碼為b=bn-1bn-2…b1b0。這樣，源結(jié)點(diǎn)為s=sn-1sn-2…s1s0，目的結(jié)點(diǎn)d=dn-1bn-2…d1d0現(xiàn)在要確定一條從s到d的步數(shù)最小的路徑將n維表示成i=1，2，…，n，其中第i維對(duì)應(yīng)于結(jié)點(diǎn)地址中的第i-1位。設(shè)u=un-1un-2…u1u0是路徑中的任一結(jié)點(diǎn)路徑可以根據(jù)以下方法唯一地確定①計(jì)算方向位ri=si-1⊕di-1，其中i=1，2，...，n。使i=1，v=s②如果ri=1，從當(dāng)前結(jié)點(diǎn)u尋徑到下一結(jié)點(diǎn)。如果ri=0，則跳過這一步③i←i+1。如果i≤n，則轉(zhuǎn)第②步，否則退出尋徑是按照從維1到維4的順序進(jìn)行的如果s和d的第i位相同，則沿維i方向不需要尋徑否則從當(dāng)前結(jié)點(diǎn)沿著這一維方向走到其它結(jié)點(diǎn)重復(fù)這一過程直到到達(dá)目的結(jié)點(diǎn)E立方體尋徑也不會(huì)產(chǎn)生死鎖尋徑，也可用于存儲(chǔ)轉(zhuǎn)發(fā)和蟲蝕網(wǎng)絡(luò)，在源和結(jié)點(diǎn)之間形成一條距離最短的路徑84(b)超立方體網(wǎng)絡(luò)的E立方體尋徑假設(shè)有一N=2n個(gè)結(jié)點(diǎn)的n圖中，n=4，s=0110，d=1101r=r4r3r2r1=s⊕d=0110⊕1101=1011i=1,r1=1，v=s=0110尋徑到v=v⊕2^0=0110⊕1=0111i=2,r2=1，v=0111尋徑到v=v⊕2^1=0111⊕10=0101i=3,r3=0，跳過維i=3這一步i=4,r4=1，v=0101尋徑到v=v⊕2^3=0101⊕1000=1101=d85圖中，n=4，s=0110，d=110185(2)自適應(yīng)尋徑采用自適應(yīng)尋徑要特別注意避免死鎖虛擬通道的概念使實(shí)現(xiàn)自適應(yīng)尋徑更經(jīng)濟(jì)和更靈活在網(wǎng)格連接網(wǎng)絡(luò)中，同一維的所有連接都使用虛擬通道圖7.34是一個(gè)用X-Y尋徑的網(wǎng)格網(wǎng)絡(luò)，在Y維上用了2對(duì)虛擬通道圖7.34(c)中的虛擬網(wǎng)絡(luò)可以用來避免消息在向西傳輸出現(xiàn)的死鎖，因?yàn)樗邢驏|的X通道都沒有使用圖7.34(d)中的虛擬網(wǎng)絡(luò)使用另一組Y方向虛擬通道來支持只向東的傳輸不同的時(shí)刻使用兩個(gè)虛擬網(wǎng)絡(luò)，這樣死鎖就可以自動(dòng)避免P424L3，X改成Y86(2)自適應(yīng)尋徑采用自適應(yīng)尋徑要特別注意避免死鎖86圖7.34利用虛擬通道避免死鎖的自適應(yīng)X-Y尋徑(a)沒有虛擬通道的原形網(wǎng)絡(luò) (b)Y維方向有兩對(duì)虛擬通道

(c)向西方向傳輸信息 (d)向東方向傳輸信息c,d有循環(huán)等待嗎87圖7.34利用虛擬通道避免死鎖的自適應(yīng)X-Y尋徑c,d有循圖7.35是在X維和Y維方向各有兩條虛擬通道的網(wǎng)格形網(wǎng)絡(luò)這些虛擬通道可以用來生成4個(gè)虛擬網(wǎng)絡(luò)西-北方向通信應(yīng)該使用圖7.35(b)所示的虛擬網(wǎng)絡(luò)類似地，其它方向的通信可以構(gòu)造另外3個(gè)虛擬網(wǎng)絡(luò)注意，任何一個(gè)虛擬網(wǎng)絡(luò)都不會(huì)出現(xiàn)環(huán)路在這些網(wǎng)絡(luò)上實(shí)現(xiàn)X-Y尋徑方法時(shí)，完全可以避免死鎖如果相鄰結(jié)點(diǎn)之間的兩對(duì)通道都是物理通道，那么4個(gè)虛擬網(wǎng)絡(luò)中任何兩個(gè)都可以同時(shí)使用而不會(huì)產(chǎn)生沖突如果相鄰結(jié)點(diǎn)之間雙虛擬通道只能共享一對(duì)物理通道只有(b)和(e)或(c)和(d)可以同時(shí)使用其它組合如(b)和(c)，或(b)和(d)，或(c)和(e)，或(d)和(e)都不能同時(shí)存在，因?yàn)槿鄙偻ǖ谰W(wǎng)絡(luò)的通道數(shù)增加，尋徑的自適應(yīng)性也將增加成本的增加將很可觀，要避免使用過多的資源P425L3，b和c改成b和e88圖7.35是在X維和Y維方向各有兩條虛擬通道的網(wǎng)格形網(wǎng)絡(luò)88圖7.35雙通道網(wǎng)格網(wǎng)絡(luò)可實(shí)現(xiàn)4個(gè)虛擬網(wǎng)絡(luò)(a)雙通道的3×3網(wǎng)絡(luò) (b)西-北子網(wǎng) (c)東-北子網(wǎng) (d)西-南子網(wǎng) (e)東-南子網(wǎng)b,c,d,e有循環(huán)等待嗎89圖7.35雙通道網(wǎng)格網(wǎng)絡(luò)可實(shí)現(xiàn)4個(gè)虛擬網(wǎng)絡(luò)b,c,d,e7.2.4選播與廣播尋徑算法四種通信模式(1)單播(unicast),一對(duì)一傳送(2)選播(multicast),一個(gè)源結(jié)點(diǎn)發(fā)送同一個(gè)消息到多個(gè)目的結(jié)點(diǎn)(3)廣播(broadcast),一個(gè)源結(jié)點(diǎn)發(fā)送同一個(gè)消息到全部結(jié)點(diǎn)(4)會(huì)議(conference),對(duì)應(yīng)于多到多的通信情況907.2.4選播與廣播尋徑算法四種通信模式90廣播與選播算法廣播是將一個(gè)結(jié)點(diǎn)的數(shù)據(jù)復(fù)制到全部N個(gè)結(jié)點(diǎn)；選播是將一個(gè)結(jié)點(diǎn)的數(shù)據(jù)復(fù)制到多個(gè)(N'個(gè))結(jié)點(diǎn)，1≤N'≤N研究廣播與選播算法的目的是盡量利用互連網(wǎng)的并行傳輸能力，尋找花費(fèi)時(shí)間最少或者動(dòng)用信道次數(shù)(又稱"流量"或"通道數(shù)")最少的方案這里所說的并行傳輸，指多個(gè)結(jié)點(diǎn)向同一方向的相鄰結(jié)點(diǎn)發(fā)送自己的數(shù)據(jù)副本。向不同方向進(jìn)行的發(fā)送不能同時(shí)進(jìn)行(具有這種能力的互連網(wǎng)不屬于現(xiàn)在的討論范圍)對(duì)不同的網(wǎng)絡(luò)，適用的廣播與選播算法也不同91廣播與選播算法廣播是將一個(gè)結(jié)點(diǎn)的數(shù)據(jù)復(fù)制到全部N個(gè)結(jié)點(diǎn)；選播選播選播算法的設(shè)計(jì)目標(biāo)有3種：時(shí)間最少、流量最少、在時(shí)間最少的多個(gè)方案中選取流量最少方案選播時(shí)間最少算法是通過單播時(shí)間最少算法裁剪而成(教材P426圖7.36(a)→(b))選播流量最少算法是最小成本生成樹算法，具體操作順序既可以是先短邊后長邊“長樹”，也可以是先長邊后短邊“砍樹”(教材P426圖7.36(c))實(shí)現(xiàn)第3種目標(biāo)的一種重要算法是貪婪算法(教材P426圖7.36(b))不論對(duì)何種網(wǎng)絡(luò)，貪婪算法總是重復(fù)使用一個(gè)固定的操作規(guī)則從當(dāng)前擁有數(shù)據(jù)的結(jié)點(diǎn)出發(fā)，向需要數(shù)據(jù)的結(jié)點(diǎn)數(shù)最多的方向并行傳送一步如此循環(huán)，直至傳遍所有需要數(shù)據(jù)的結(jié)點(diǎn)如果最后發(fā)現(xiàn)某個(gè)通道(即一次數(shù)據(jù)發(fā)送操作)不在通往給定目標(biāo)結(jié)點(diǎn)的路徑上，則應(yīng)將其刪去92選播選播算法的設(shè)計(jì)目標(biāo)有3種：時(shí)間最少、流量最少、在時(shí)間最少擴(kuò)散向最近的結(jié)點(diǎn)的方向移動(dòng)1步5次點(diǎn)對(duì)點(diǎn),1個(gè)流量為相鄰結(jié)點(diǎn)一次傳輸向可達(dá)結(jié)點(diǎn)數(shù)最多的方向移動(dòng)1步123444412364593擴(kuò)散向最近的結(jié)點(diǎn)的方向移動(dòng)1步5次點(diǎn)對(duì)點(diǎn),向可達(dá)結(jié)點(diǎn)數(shù)最多的圖7.37貪婪算法4立方體廣播樹和選播樹(a)一個(gè)根結(jié)點(diǎn)為0000的4立方體。超立方體廣播樹的流量最小。(b)是一棵貪婪選播樹，可從結(jié)點(diǎn)0101發(fā)送包到7個(gè)目的結(jié)點(diǎn)94圖7.37貪婪算法4立方體廣播樹和選播樹(a)一個(gè)根結(jié)點(diǎn)為貪婪選播算法的基本思想是向那些可達(dá)到最多剩余目的結(jié)點(diǎn)的維方向發(fā)送包圖7.37(a)是一個(gè)根結(jié)點(diǎn)為0000的4立方體。超立方體廣播樹的流量最小圖7.37(b)是一棵貪婪選播樹，可從結(jié)點(diǎn)0101發(fā)送包到7個(gè)目的結(jié)點(diǎn)從源結(jié)點(diǎn)S=0101開始，由維2方向可以到達(dá)2個(gè)目的結(jié)點(diǎn)，由維4方向可以達(dá)到5個(gè)目的結(jié)點(diǎn)。第1層所用的通道是0101→0111和0101→1101從結(jié)點(diǎn)1101，由維2方向可以到達(dá)3個(gè)目的結(jié)點(diǎn)，由維1方向可以到達(dá)4個(gè)目的結(jié)點(diǎn)。第2層所用的通道是1101→1111，1101→1100和0111→0110同理，第3層所用的通道是1111→1110，1111→1011，1100→1000和0110→0010第4層所用的通道是1110→101095貪婪選播算法的基本思想是向那些可達(dá)到最多剩余目的結(jié)點(diǎn)的維方向在擴(kuò)充選播樹時(shí)首先應(yīng)該比較所有各維方向的可達(dá)性(reachability)然后選擇某些維使剩余目的結(jié)點(diǎn)的集合最小如果兩維之間有連線，那么選擇其中任何一維都可以。因此，所生成的樹不是唯一的已經(jīng)證明貪婪選播算法所需的通道數(shù)與多次單播或廣播樹相比要少在蟲蝕尋徑網(wǎng)絡(luò)中，實(shí)現(xiàn)選播操作時(shí)，每個(gè)結(jié)點(diǎn)的尋徑器應(yīng)有復(fù)制片緩沖區(qū)中數(shù)據(jù)的能力為了與選播樹或廣播樹的增長同步，樹中同一層的所有輸出通道必須在傳輸向前推進(jìn)一層之前處于就緒狀態(tài)，否則中間結(jié)點(diǎn)需要增加緩沖區(qū)96在擴(kuò)充選播樹時(shí)96(1)單級(jí)網(wǎng)格網(wǎng)(Mash網(wǎng))貪婪算法教材P426圖7.36(a)指出總共有1個(gè)源結(jié)點(diǎn)S和5個(gè)目的結(jié)點(diǎn)圖(b)指出從S出發(fā)，首先應(yīng)向右鄰結(jié)點(diǎn)發(fā)送數(shù)據(jù)，因?yàn)镾的左方只有1個(gè)目的結(jié)點(diǎn)、上方有3個(gè)目的結(jié)點(diǎn)、右方有４個(gè)目的結(jié)點(diǎn)第二步從這2個(gè)擁有數(shù)據(jù)的結(jié)點(diǎn)出發(fā)，可以再向右發(fā)送(有3個(gè)目的結(jié)點(diǎn))，也可以改向上發(fā)送(也有3個(gè)目的結(jié)點(diǎn))，……只要每步遵守貪婪算法的規(guī)則，最后形成的不同路徑樹的時(shí)間和流量都是相同的97(1)單級(jí)網(wǎng)格網(wǎng)(Mash網(wǎng))貪婪算法教材P426圖7.36教材P426圖7.37(a)指出廣播算法的時(shí)間是4，流量是15。Cube0～Cuben-1的使用順序?qū)V播算法的時(shí)間和流量沒有影響，但對(duì)小圖(b)的選播算法的時(shí)間和流量有影響先看一個(gè)簡單的例子(下圖)：已知N=4，維數(shù)n=2，源結(jié)點(diǎn)是0，目的結(jié)點(diǎn)是1和3源結(jié)點(diǎn)編號(hào)的二進(jìn)制形式00在bit0位與兩個(gè)目的結(jié)點(diǎn)的二進(jìn)制形式01、11都不相同，而在bit1位僅與一個(gè)目的結(jié)點(diǎn)的二進(jìn)制形式不同，所以應(yīng)該先傳bit0方向、再傳bit1方向，如右圖(a)所示，這時(shí)流量=2；如果先傳bit1方向、再傳bit0方向，如右圖(b)所示，則流量=3(2)單級(jí)立方體網(wǎng)絡(luò)貪婪算法98教材P426圖7.37(a)指出廣播算法的時(shí)間是4，流量是1教材P426圖7.37(b)的例子。源結(jié)點(diǎn)編號(hào)的二進(jìn)制形式0101在Cube0～Cube3位分別與5、5、4、5個(gè)目的結(jié)點(diǎn)的二進(jìn)制形式不同，所以Cube2方向應(yīng)該最后發(fā)送，其它3個(gè)方向的發(fā)送先后順序則沒有限制。教材P427采用了Cube3、Cube1、Cube0、Cube2的發(fā)送順序，如下圖所示，時(shí)間=4，總流量=1099教材P426圖7.37(b)的例子。源結(jié)點(diǎn)編號(hào)的二進(jìn)制形式07.3互連網(wǎng)絡(luò)實(shí)例著重研究下面幾種多處理機(jī)的互連網(wǎng)絡(luò)總線結(jié)構(gòu)、環(huán)形互連、交叉開關(guān)、混洗交換互連等處理機(jī)系統(tǒng)采用哪種互連結(jié)構(gòu)主要取決于系統(tǒng)的最大通信量反過來，系統(tǒng)的最大通信量受到互連結(jié)構(gòu)的限制7.3互連網(wǎng)絡(luò)實(shí)例著重研究下面幾種多處理機(jī)的互連網(wǎng)絡(luò)7.3.1總線互連目前，大部分處理機(jī)內(nèi)部采用總線結(jié)構(gòu)CPU與存儲(chǔ)器之間有系統(tǒng)總線存儲(chǔ)器與輸入輸出設(shè)備之間有I/O總線總線與總線之間通過總線橋連接總線的主要優(yōu)點(diǎn)是結(jié)構(gòu)簡單，能夠很方便實(shí)現(xiàn)廣播通信總線的主要缺點(diǎn)是帶寬低，發(fā)生總線沖突的可能性大總線沖突的解決辦法有(1)設(shè)置靜態(tài)優(yōu)先級(jí)(2)在同步方式中采用時(shí)間片(3)采用動(dòng)態(tài)優(yōu)先級(jí)(如LRU法等)(4)先來先服務(wù)1017.3.1總線互連目前，大部分處理機(jī)內(nèi)部采用總線結(jié)構(gòu)101總線結(jié)構(gòu)的多處理機(jī)102總線結(jié)構(gòu)的多處理機(jī)102為了提高總線的通信帶寬，有如下方法(1)采用多總線結(jié)構(gòu)(2)層次總線結(jié)構(gòu)(3)多維總線結(jié)構(gòu)多總線西門子公司的SMS系統(tǒng)(StracturedMultiprocessorSystem)通過8條總線連接128個(gè)處理機(jī)層次總線卡內(nèi)基梅隆大學(xué)的Cm*多處理機(jī)系統(tǒng)采用層次總線結(jié)構(gòu)三級(jí)總線：群總線、Map總線、處理機(jī)總線每群14臺(tái)處理機(jī)為了提高總線的通信帶寬，有如下方法主機(jī)P1P2P16P17P18P32P113P114P128………………………………總線驅(qū)動(dòng)器SMS多總線結(jié)構(gòu)主機(jī)P1P2P16P17P18P32P113P114P128卡內(nèi)基梅隆大學(xué)的Cm*層次總線結(jié)構(gòu)CmCmCm…KmCmBCm…KmCmCmCm…Km…MIOP群間總線卡內(nèi)基梅隆大學(xué)的Cm*層次總線結(jié)構(gòu)CmCmCm…KmCmBC7.3.2環(huán)形互聯(lián)一種互連方法，它既能具有總線型互連的簡單性，又可以克服總線所固有的缺點(diǎn)信息的傳送過程是發(fā)送進(jìn)程把信息放到環(huán)上，通過環(huán)形網(wǎng)絡(luò)不斷向下一臺(tái)處理機(jī)傳播，直到此信息回到發(fā)送者為止1067.3.2環(huán)形互聯(lián)一種互連方法，它既能具有總線型互連的簡單性IEEE802.5令牌環(huán)(TokenRing)IEEE802.5令牌環(huán)(TokenRing)標(biāo)準(zhǔn)是把環(huán)形看作邏輯總線的協(xié)議發(fā)送信息的處理機(jī)擁有一個(gè)唯一的令牌，在同一時(shí)刻只有一臺(tái)處理機(jī)持有這個(gè)令牌當(dāng)發(fā)送者發(fā)送信息時(shí)，這個(gè)環(huán)形網(wǎng)絡(luò)的作用如同總線一樣，其它處理機(jī)都處于接收信息的狀態(tài)信息傳送結(jié)束時(shí)，發(fā)送者播送一個(gè)令牌，這個(gè)令牌是在普通信息中不會(huì)出現(xiàn)的特定信號(hào)。每臺(tái)處理機(jī)依次看到令牌如果某臺(tái)處理機(jī)等待發(fā)送信息，那么它便接收這個(gè)令牌而不再傳遞給下一臺(tái)處理機(jī)，這時(shí)這臺(tái)處理機(jī)就可以通過環(huán)形網(wǎng)絡(luò)發(fā)送信息了假如沒有想發(fā)送信息的處理機(jī)，那么令牌就將在環(huán)形網(wǎng)絡(luò)上不斷循環(huán)，直到某臺(tái)處理機(jī)需要發(fā)送信息為止107IEEE802.5令牌環(huán)(TokenRing)IEEE令牌環(huán)的優(yōu)點(diǎn)是點(diǎn)點(diǎn)連接，而不是總線連接，其物理參數(shù)更容易控制令牌環(huán)形互連非常適于高帶寬的光纖通信。N較小的總線互連系統(tǒng)很難采用光纖通信，N較大的系統(tǒng)也還未實(shí)現(xiàn)令牌環(huán)形互連的一個(gè)主要缺點(diǎn)是每個(gè)總線接口都有延遲通常是1位的延遲當(dāng)互連處理機(jī)臺(tái)數(shù)增加時(shí)，在環(huán)中的信息傳輸延遲將正比例地增加但是當(dāng)系統(tǒng)負(fù)載很重時(shí)，系統(tǒng)的帶寬卻不會(huì)像總線互連系統(tǒng)那樣下降108令牌環(huán)的優(yōu)點(diǎn)是點(diǎn)點(diǎn)連接，而不是總線連接，其物理參數(shù)更容易控制7.3.3交叉開關(guān)互連交叉開關(guān)網(wǎng)絡(luò)，它把N臺(tái)處理機(jī)和N個(gè)存儲(chǔ)器連接起來圖中處理機(jī)臺(tái)數(shù)與存儲(chǔ)器個(gè)數(shù)相等，一般情況是存儲(chǔ)器數(shù)目等于或是處理機(jī)數(shù)目的幾倍網(wǎng)絡(luò)中每個(gè)交叉點(diǎn)是一個(gè)允許任何一臺(tái)處理器與任何一個(gè)存儲(chǔ)器連接的開關(guān)7.3.3交叉開關(guān)互連交叉開關(guān)網(wǎng)絡(luò)，它把N臺(tái)處理機(jī)和N個(gè)系統(tǒng)允許N個(gè)存取操作并行執(zhí)行任意兩個(gè)存取操作不能涉及同一臺(tái)處理機(jī)或同一個(gè)存儲(chǔ)器如果兩個(gè)或兩個(gè)以上存取操作同時(shí)要訪問某個(gè)存儲(chǔ)器，那么爭用現(xiàn)象就發(fā)生了如處理機(jī)P1和P2同時(shí)要訪問存儲(chǔ)器M1減少爭用，在系統(tǒng)結(jié)構(gòu)方面大有文章可做如果爭用是由于多臺(tái)處理機(jī)同時(shí)要訪問同一存儲(chǔ)模塊中不同單元的數(shù)據(jù)而引起的，一種解決爭用的方法是盡量使這些數(shù)據(jù)平均地分配到多個(gè)不同的存儲(chǔ)模塊中，而不要把它們集中在一個(gè)存儲(chǔ)模塊中把一個(gè)數(shù)據(jù)塊中數(shù)據(jù)依次分配到相繼的存儲(chǔ)模塊中同樣，共享程序代碼也應(yīng)該這樣分配這樣，當(dāng)兩臺(tái)或兩臺(tái)以上的處理機(jī)同時(shí)訪問共享程序代碼或數(shù)據(jù)時(shí)，爭用只使其中一臺(tái)處理機(jī)延遲一個(gè)周期只要兩臺(tái)處理機(jī)順序地不斷地訪問，兩者不會(huì)再發(fā)生沖突這種尋址技術(shù)也可用于流水線多處理機(jī)中，使各臺(tái)處理機(jī)能彼此步調(diào)一致地存取向量數(shù)據(jù)110系統(tǒng)允許N個(gè)存取操作并行執(zhí)行1107.3.4混洗交換互連和合并開關(guān)混洗交換網(wǎng)絡(luò)能提供一種重要的功能，稱為合并開關(guān)它使某些操作在網(wǎng)絡(luò)一級(jí)并行地執(zhí)行，從而減少爭用現(xiàn)象否則這些需要訪問存儲(chǔ)器的操作只能串行地執(zhí)行對(duì)那些需要互斥地訪問共享變量的進(jìn)程來說，這種方法很有潛力互斥地訪問共享變量限制了大部分多處理機(jī)系統(tǒng)的性能當(dāng)出現(xiàn)多個(gè)進(jìn)程要存取某個(gè)共享變量時(shí)，無論系統(tǒng)再增加多少臺(tái)處理機(jī)也不可能再提高其速度1117.3.4混洗交換互連和合并開關(guān)混洗交換網(wǎng)絡(luò)能提供一種重要8臺(tái)處理器和8個(gè)存儲(chǔ)器通過混洗交換互連網(wǎng)絡(luò)連接1128臺(tái)處理器和8個(gè)存儲(chǔ)器通過混洗交換互連網(wǎng)絡(luò)連接1127.3.5Omega網(wǎng)絡(luò)采用了全混洗函數(shù)和交換函數(shù)，又稱為混洗交換網(wǎng)絡(luò)Omega網(wǎng)已經(jīng)用于伊利諾依大學(xué)的Cedar多處理機(jī)、IBM的RP3系統(tǒng)和紐約大學(xué)Ultracomputer中N個(gè)輸入的Omega網(wǎng)絡(luò)有l(wèi)og2N級(jí)每級(jí)有N/2個(gè)2×2的四功能交換開關(guān)每級(jí)的拓?fù)浣Y(jié)構(gòu)相同采用單元控制(每一級(jí)的控制信號(hào)均相同)能夠?qū)崿F(xiàn)任意一個(gè)輸入端到任意一個(gè)輸出端的連接不能同時(shí)實(shí)現(xiàn)多個(gè)輸入端到多個(gè)輸出端的連接通過檢查二進(jìn)制目的地址編碼來控制數(shù)據(jù)路徑目的地址編碼從高位開始的第i位為0時(shí)，第i級(jí)的2×2開關(guān)的輸入端與上輸出端連接，否則輸入端與下輸出端連接1137.3.5Omega網(wǎng)絡(luò)采用了全混洗函數(shù)和交換函數(shù)，又稱為混8個(gè)輸入端的Omega網(wǎng)絡(luò)2路洗牌相當(dāng)于8個(gè)輸入端平均地分成2個(gè)子組，然后2個(gè)子組均勻地洗牌同時(shí)實(shí)現(xiàn)06和47有沖突沖突的還有：30和51，30和73，50和71等01230101011148個(gè)輸入端的Omega網(wǎng)絡(luò)0開關(guān)設(shè)置從輸入端001到輸出端011的路徑。它使用了開關(guān)A、B、C目的地址編碼011的最高位“0”，輸入端001與開關(guān)A的上輸出端(編號(hào)為2)連接,開關(guān)A設(shè)置成直送狀態(tài)011的次高位是“1”，輸入端4和下輸出端連接，開關(guān)B設(shè)置成交換狀態(tài)011的最低位是“1”，輸入端4和下輸出端連接，開關(guān)C設(shè)置成直送狀態(tài)輸入端101到輸出端101的路徑？115開關(guān)設(shè)置115116116如果采用級(jí)控制，是STARAN交換網(wǎng)的逆網(wǎng)如果采用部分級(jí)控制，是STARAN移數(shù)網(wǎng)的逆網(wǎng)因此，Omega網(wǎng)的許多性質(zhì)與多級(jí)立方體網(wǎng)相反，如發(fā)生沖突的情況Omega網(wǎng)屬于多級(jí)互連網(wǎng)當(dāng)有N個(gè)輸入端時(shí)，共有N^(N/2)個(gè)變換要同時(shí)實(shí)現(xiàn)任意一個(gè)輸入端到任意一個(gè)輸出端的連接，總共需要N!個(gè)變換8個(gè)輸入端的Omega網(wǎng)絡(luò)實(shí)際上只能實(shí)現(xiàn)全部變換的10%(8^4/8!=4096/40320=0.1016)，有90%的變換將引起阻塞Omega網(wǎng)絡(luò)是一種阻塞網(wǎng)絡(luò)，采用多次通過來解決沖突有N個(gè)輸入端時(shí)，實(shí)現(xiàn)連接的通過次數(shù)最多為log2N117如果采用級(jí)控制，是STARAN交換網(wǎng)的逆網(wǎng)117Omega網(wǎng)能夠?qū)崿F(xiàn)從任意一個(gè)輸入端到所有輸出端的廣播采用上播或下播開關(guān)設(shè)置118Omega網(wǎng)能夠?qū)崿F(xiàn)從任意一個(gè)輸入端到所有輸出端的廣播采用上用4×4開關(guān)元件作為構(gòu)成塊的Omega網(wǎng)絡(luò)用4×4開關(guān)元件作為構(gòu)成塊的Omega網(wǎng)絡(luò)，級(jí)間是4路洗牌連接，而不是2路洗牌連接16個(gè)輸入端的Omega網(wǎng)絡(luò)的級(jí)數(shù)為log416=24路洗牌相當(dāng)于16個(gè)輸入端平均地分成4個(gè)子組，然后4個(gè)子組均勻地洗牌采用k×k開關(guān)元件時(shí)，可以定義k路洗牌函數(shù)來構(gòu)造更大的級(jí)數(shù)為logkn的Omega網(wǎng)絡(luò)012301230123119用4×4開關(guān)元件作為構(gòu)成塊的Omega網(wǎng)絡(luò)用4×4開關(guān)元件作017017蝶式網(wǎng)絡(luò)16個(gè)8×8交叉開關(guān)構(gòu)成的兩級(jí)64×64碟式網(wǎng)絡(luò)

64個(gè)輸入端的蝶式網(wǎng)絡(luò)由2級(jí)(2=logkn=log864)8×8交叉開關(guān)組成開關(guān)數(shù)16=8+8=nlogkn/k=64*log864/8級(jí)間采用8路洗牌連接，64/8組(路)=8個(gè)結(jié)點(diǎn)/組第0個(gè)8×8模塊的輸出連至第1級(jí)的各個(gè)開關(guān)的第0個(gè)輸入0輸出連至第1級(jí)的第0個(gè)開關(guān)的第0個(gè)輸入1輸出連至第1級(jí)的第1個(gè)開關(guān)的第0個(gè)輸入...7輸出連至第1級(jí)的第7個(gè)開關(guān)的第0個(gè)輸入第1個(gè)8×8模塊的輸出連至第1級(jí)的各個(gè)開關(guān)的第1個(gè)輸入0輸出連至第1級(jí)的第0個(gè)開關(guān)的第1個(gè)輸入1輸出連至第1級(jí)的第1個(gè)開關(guān)的第1個(gè)輸入...7輸出連至第1級(jí)的第7個(gè)開關(guān)的第1個(gè)輸入...第7個(gè)8×8模塊的輸出連至第1級(jí)的各個(gè)開關(guān)的第7個(gè)輸入0輸出連至第1級(jí)的第0個(gè)開關(guān)的第7個(gè)輸入1輸出連至第1級(jí)的第1個(gè)開關(guān)的第7個(gè)輸入...7輸出連至第1級(jí)的第7個(gè)開關(guān)的第7個(gè)輸入12000192個(gè)8×8交叉開關(guān)構(gòu)成的三級(jí)512×512碟式網(wǎng)絡(luò)512個(gè)輸入端的蝶式網(wǎng)絡(luò)級(jí)間采用64路洗牌連接(從第2級(jí)向左看，8個(gè)結(jié)點(diǎn)一組，512/8=64組(路))從第0,1級(jí)向右看，64個(gè)結(jié)點(diǎn)一組，512/64=8組(路)，8路洗牌，第2級(jí)8個(gè)8×8開關(guān)構(gòu)成一個(gè)64個(gè)結(jié)點(diǎn)的組和第0,1級(jí)的8個(gè)組連接3級(jí)(3=logkn=log8512)8×8開關(guān)組成16個(gè)8×8開關(guān)構(gòu)成的兩級(jí)64×64碟式網(wǎng)絡(luò)64×64碟式網(wǎng)絡(luò)共8個(gè)第2級(jí)8個(gè)8×8交叉開關(guān)構(gòu)成64路連接64路連接共512/64=8組用這種模塊結(jié)構(gòu)構(gòu)造更大的蝶式網(wǎng)絡(luò)只要增加級(jí)數(shù)即可開關(guān)數(shù)192=16x8+8x8=nlogkn/k=512x3/8蝶式網(wǎng)絡(luò)不允許廣播連接，所以蝶式網(wǎng)絡(luò)是Omega網(wǎng)絡(luò)的一個(gè)有限的子集每個(gè)64×64的方框相當(dāng)于圖7.45(a)中的兩級(jí)蝶式網(wǎng)絡(luò)00x81x817

x863121192個(gè)8×8交叉開關(guān)構(gòu)成的三級(jí)512×512碟式網(wǎng)絡(luò)512級(jí)間采用64路洗牌連接(從第2級(jí)向左看，8個(gè)結(jié)點(diǎn)一組，512/8=64組(路))從第0,1級(jí)向右看，64個(gè)結(jié)點(diǎn)一組，512/64=8組(路)，8路洗牌，第2級(jí)8個(gè)8×8開關(guān)構(gòu)成一個(gè)64個(gè)結(jié)點(diǎn)的組和第0,1級(jí)的8個(gè)組連接第0個(gè)64×64模塊的輸出連至第2級(jí)的各個(gè)開關(guān)的第0個(gè)輸入0輸出連至第2級(jí)的第0個(gè)開關(guān)的第0個(gè)輸入1輸出連至第2級(jí)的第1個(gè)開關(guān)的第0個(gè)輸入...63輸出連至第2級(jí)的第63個(gè)開關(guān)的第0個(gè)輸入第1個(gè)64×64模塊的輸出連至第2級(jí)的各個(gè)開關(guān)的第1個(gè)輸入0輸出連至第2級(jí)的第0個(gè)開關(guān)的第1個(gè)輸入1輸出連至第2級(jí)的第1個(gè)開關(guān)的第1個(gè)輸入...63輸出連至第2級(jí)的第63個(gè)開關(guān)的第1個(gè)輸入...第63個(gè)64×64模塊的輸出連至第2級(jí)各個(gè)開關(guān)的第7個(gè)輸入0輸出連至第2級(jí)的第0個(gè)開關(guān)的第7個(gè)輸入1輸出連至第2級(jí)的第1個(gè)開關(guān)的第7個(gè)輸入...63輸出連至第2級(jí)的第63個(gè)開關(guān)的第7個(gè)輸入122級(jí)間采用64路洗牌連接(從第2級(jí)向左看，8個(gè)結(jié)點(diǎn)一組，5127.3.6蝶形操作略1237.3.6蝶形操作略1237.3.7合并網(wǎng)絡(luò)和取與加指令略1247.3.7合并網(wǎng)絡(luò)和取與加指令略124計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第一章基本概念第二章指令系統(tǒng)第三章存儲(chǔ)系統(tǒng)第四章輸入輸出系統(tǒng)第五章標(biāo)量處理機(jī)第六章向量處理機(jī)第七章互連網(wǎng)絡(luò)第八章并行處理機(jī)第九章多處理機(jī)125計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第一章基本概念1互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)用于實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件之間的相互連接第七章互連網(wǎng)絡(luò)126互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)第七章互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)的基本概念消息傳遞機(jī)制127第七章互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)的基本概念37.1互連網(wǎng)絡(luò)的基本概念互連網(wǎng)絡(luò)的作用互連函數(shù)互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù)互連網(wǎng)絡(luò)的種類1287.1互連網(wǎng)絡(luò)的基本概念互連網(wǎng)絡(luò)的作用47.1.1互連網(wǎng)絡(luò)的作用用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件之間的相互連接。為并行處理系統(tǒng)的核心組成部分。對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的性能價(jià)格比有著決定性的影響。1297.1.1互連網(wǎng)絡(luò)的作用用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多具有本地存儲(chǔ)器、私有高速緩存、共享存儲(chǔ)器和共享外圍設(shè)備的一般處理機(jī)系統(tǒng)的互連結(jié)構(gòu)IPMN(處理機(jī)-存儲(chǔ)器網(wǎng)絡(luò))PION(處理機(jī)-I/O網(wǎng)絡(luò))IPCN(處理機(jī)之間通信網(wǎng)絡(luò))P(處理機(jī))C(高速緩沖存儲(chǔ)器)SM(共享存儲(chǔ)器)LM(本地存儲(chǔ)器)磁盤SM1SM2SMmIPMN……CnPnLMC1P1LMIPCN……………………PION磁帶打印機(jī)終端網(wǎng)絡(luò)…(共享存儲(chǔ)器)(共享I/O與外設(shè))130具有本地存儲(chǔ)器、私有高速緩存、共享存儲(chǔ)器和共享外圍設(shè)備的一般7.1.2互連函數(shù)互連函數(shù)將互連網(wǎng)的N個(gè)輸入和N個(gè)輸出端分別用整數(shù)(0,1,2,...,N-1)來表示，則表示相互連接的輸出端號(hào)和輸入端號(hào)之間的一一對(duì)應(yīng)關(guān)系表示方法：互連函數(shù)法，圖形表示法,輸入輸出對(duì)應(yīng)表示法函數(shù)表示法：x表示輸入端號(hào)，常用n位二進(jìn)制形式表示xn-1xn-2...x1x0f(x)表示互連函數(shù)，為：f(xn-1xn-2...x1x0)圖形表示法:用圖形表示輸入和輸出端之間的連接輸入輸出對(duì)應(yīng)(矩陣)表示法：循環(huán)表示法:把互連函數(shù)f(x)表示為：

(x0，x1，...，xj)(xk，xk+1，...，xl)...表示對(duì)應(yīng)關(guān)系為:f(x0)=x1，f(x1)=x2，...，f(xj)=x0

j+1稱為該循環(huán)的長度012...N-1f(0)f(1)f(2)...f(N-1)1317.1.2互連函數(shù)互連函數(shù)012...常用的互連函數(shù)如下：1恒等置換：

I(xn-1xn-2...

x1x0)=xn-1xn-2...x1x0132常用的互連函數(shù)如下：1恒等置換：82交換置換Exchange實(shí)現(xiàn)二進(jìn)制地址編號(hào)中第0位位值不同的輸入和輸出端之間的連接。

E(xn-1xn-2...

x1x0)=xn-1xn-2...

x1x0其他互連函數(shù)還有：方體置換、均勻洗牌置換、蝶式置換、位序顛倒置換、移數(shù)置換、加減2i置換1332交換置換Exchange實(shí)現(xiàn)二進(jìn)制地址編號(hào)中第0位位值不3、方體置換Cube當(dāng)n=3時(shí)，共有3種函數(shù)，每種函數(shù)能夠表示8個(gè)結(jié)點(diǎn)之間的連接關(guān)系。由于交換函數(shù)主要用于超立方體互連網(wǎng)中，因此也稱為超立方體函數(shù)，用Cube表示，如：Cube0、Cube1、Cube2等。用交換函數(shù)構(gòu)成的互連網(wǎng)絡(luò)的結(jié)點(diǎn)度為n，網(wǎng)絡(luò)直徑也為n。1343、方體置換Cube10變化發(fā)生在0，1，2位分別是高2，1，0位相同的為一個(gè)組組內(nèi)加/減1，2，4C0C2C1135變化發(fā)生在0，1，2位C0C2C1114、均勻洗牌置換Perfectshuffle把二進(jìn)制結(jié)點(diǎn)循環(huán)左移一位。子混洗(subshuffle)S(k)最低k位循環(huán)左移一位超混洗牌(supershuffle)S(k)最高k位循環(huán)左移一位顯然成立：逆混洗函數(shù)：教材P397L2,3,6錯(cuò)1364、均勻洗牌置換Perfectshuffle124、均勻洗牌置換Perfectshuffle子洗牌是將整組數(shù)據(jù)分成若干個(gè)子組，對(duì)每個(gè)子組完成均勻洗牌變換。S(2)分兩組0，1，2，3；4，5，6，7只用均勻洗牌函數(shù)不能實(shí)現(xiàn)任意結(jié)點(diǎn)之間的互連通常用均勻洗牌函數(shù)與其他函數(shù)，如交換函數(shù)一起構(gòu)成互連網(wǎng)絡(luò)。均勻洗牌與逆均勻洗牌是兩種十分有用的互連函數(shù)以它們代表的鏈路與以交換置換代表的開關(guān)多級(jí)組合起來可構(gòu)成Omega(Ω)網(wǎng)絡(luò)與逆Omega(Ω^-1)網(wǎng)絡(luò)。

逆均勻洗牌是均勻洗牌的逆函數(shù)，兩者的輸入端和輸出端正好互換1374、均勻洗牌置換Perfectshuffle135、蝶式置換Butterfly蝶式函數(shù)的名稱來自于FFT變換時(shí)的圖形，如蝴蝶式樣。將輸入端二進(jìn)制結(jié)點(diǎn)號(hào)的最高位和最低位互換位置。子蝶式(subbutterfly)B(k)最低k位的最高位與最低位互換位置超蝶式(superbutterfly)B(k)最高k位的最高位與最低位互換位置顯然成立教材P398L1,2錯(cuò)1385、蝶式置換Butterfly蝶式函數(shù)的名稱來自于FFT變換5、蝶式置換Butterfly與全混洗函數(shù)類似，只用蝶式函數(shù)也不能實(shí)現(xiàn)任意結(jié)點(diǎn)之間的互連。1395、蝶式置換Butterfly156、