計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)3

計(jì)算機(jī)科學(xué)與技術(shù)系研究生課程

高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系高性能計(jì)算研究所

鄭緯民教授

2000年9月

高等計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

第一章高等計(jì)算機(jī)的核心技術(shù)——并行處理

第二章加速比性能模型與可擴(kuò)展性分析

第三章互連與通信

第四章劃分與調(diào)度

第五章并行存儲器系統(tǒng)

第六章CacheCoherence

第七章MemoryConsistency

第八章指令級并行處理

第三章互連與通信

3.1互連網(wǎng)絡(luò)的作用

3.2靜態(tài)網(wǎng)絡(luò)

3.3動態(tài)網(wǎng)絡(luò)

3.4通信問題

3.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)部多個處

理機(jī)或多個功能部件間的相互連接。

操作方式：I

同步通信(SynchronousCommunication)

異步通信(AsynchronousCommunication)

控制策略：I

集中控制(Centralizedcontrol)

分布控制(Distributedcontrol)

交換方式：

電路交換(Circuitswitching)

分組交換(Packetswitching)

Wormhole交換(Wormholeswitching)

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：

靜態(tài)網(wǎng)絡(luò)(Staticnetwork)

動態(tài)網(wǎng)絡(luò)(Dynamicnetwork)

第三章互連與通信

3.1互連網(wǎng)絡(luò)的作用

3.2靜態(tài)網(wǎng)絡(luò)

3.2.1靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo)

3.2.2典型的靜態(tài)網(wǎng)絡(luò)

3.3動態(tài)網(wǎng)絡(luò)

3.4通信問題

3.2靜態(tài)網(wǎng)絡(luò)

3.2.1靜態(tài)網(wǎng)絡(luò)的特點(diǎn)與指標(biāo)

1.靜態(tài)網(wǎng)絡(luò)的特點(diǎn)■

靜態(tài)網(wǎng)絡(luò)由點(diǎn)一點(diǎn)直接相連而成,這種連

結(jié)方式在程序執(zhí)行過程中不會改變。

如果用圖來表示，結(jié)點(diǎn)代表開關(guān)，邊代表

通信鏈路，則

(1)結(jié)點(diǎn)間的鏈路無源，不能重構(gòu)■

(2)開關(guān)元件與處理機(jī)相連

(3)不直接相連結(jié)點(diǎn)間的通信需通過中

間結(jié)點(diǎn)中轉(zhuǎn)。

2.靜態(tài)網(wǎng)絡(luò)的指標(biāo)

結(jié)點(diǎn)度：與結(jié)點(diǎn)相連接的邊（鏈路或通道）

數(shù)，表示節(jié)點(diǎn)所需要的I/O端口數(shù)，模塊化要

求結(jié)點(diǎn)度保持恒定。根據(jù)通道到結(jié)點(diǎn)的方向,

結(jié)點(diǎn)度可以進(jìn)一步表示為：

結(jié)點(diǎn)度=入度+出度

其中入度是進(jìn)入結(jié)點(diǎn)的通道數(shù)，出度是從結(jié)

點(diǎn)出來的通道數(shù)。

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

網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個結(jié)點(diǎn)間距離的

最大值。

網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)，表示該網(wǎng)絡(luò)功

能連結(jié)部件的多少。

等分寬度：某一網(wǎng)絡(luò)被切成相等的兩半時,

沿切口的最小邊數(shù)稱為該網(wǎng)絡(luò)的等分寬度。

結(jié)點(diǎn)間的線長：兩個結(jié)點(diǎn)間的線的長度。

對稱性：從任何結(jié)點(diǎn)看，拓?fù)浣Y(jié)構(gòu)都一樣,

這種網(wǎng)絡(luò)實(shí)現(xiàn)和編程都很容易。I

結(jié)點(diǎn)是否同構(gòu)。

通道是否有緩沖。

3.2.2典型的靜態(tài)網(wǎng)絡(luò)

1.線性陣列

對N個結(jié)點(diǎn)的線性陣列，有N-1條鏈路，直

徑為N-1（任意兩點(diǎn)之間距離的最大值），

度為2,不對稱，等分寬度為1。

N很大時，通信效率很低。

線性陣列與總線的區(qū)別：

線性陣列：允許不同的源結(jié)點(diǎn)和目的結(jié)點(diǎn)

對并發(fā)使用系統(tǒng)的不同部分。

總線：通過切換與其相連的許多結(jié)點(diǎn)來實(shí)

現(xiàn)時分特性，同一時刻只有一對結(jié)點(diǎn)在傳送

數(shù)據(jù)。

2.環(huán)

對N個結(jié)點(diǎn)的環(huán)，考慮相鄰結(jié)點(diǎn)數(shù)據(jù)傳送方向:

雙向環(huán)：鏈路數(shù)為N,直徑［N/2」，度為2,

對稱，等分寬度為2。比如KSR-1(1990)。

單向環(huán)：鏈路數(shù)為N,直徑N-L度為2,1

對稱，等分寬度為2。

3,帶弦環(huán)

度

為

對上圖中12個結(jié)點(diǎn)的帶弦雙向環(huán)，

結(jié)點(diǎn)度為3:鏈路數(shù)為18,直徑4（比如紅

色結(jié)點(diǎn)），度為3，不對稱，等分寬度為2。

結(jié)點(diǎn)度為4:鏈路數(shù)為24,直徑3（比如紅

色結(jié)點(diǎn)），度為4，對稱，等分寬度為8。

4.鏈接

鏈接是帶弦環(huán)的一種特殊情形。鏈接中的

每個結(jié)點(diǎn)和其他結(jié)點(diǎn)之間都有單一的直接鏈

路。如下圖中8個結(jié)點(diǎn)的鏈接：

有28條鏈路，直徑為L度為7,對稱，等

分寬度為16。

5木

4

層

的

二

叉

樹

一棵K層完全二叉樹應(yīng)有N=2K-1個結(jié)點(diǎn),

對大結(jié)點(diǎn)度為3,直徑為2(K-1)(即右邊

任意一個葉子結(jié)點(diǎn)到左邊任意一個葉子結(jié)

點(diǎn))。不對稱，等分度為L

由于結(jié)點(diǎn)度為常數(shù)，所以樹是一種可擴(kuò)展

的系統(tǒng)結(jié)構(gòu)。

樹形的擴(kuò)展:

二

叉

胖

樹

這兩種結(jié)構(gòu)都可以緩解根結(jié)點(diǎn)的瓶頸問題。

6.星形

星形實(shí)際上是一種二層樹（如右圖）。有N

個結(jié)點(diǎn)的星形網(wǎng)絡(luò)，有N-1條鏈路，直徑為2,

最大結(jié)點(diǎn)度為N-L非對稱，等分寬度為1。

7.網(wǎng)

有個結(jié)點(diǎn)的rxr網(wǎng)(其中尸=，^卜有

2N-2r條鏈路，直徑為2(r-1),結(jié)點(diǎn)度為4,

非對稱，等分寬度為r。

b.環(huán)形網(wǎng)(2D—Torus)

有個結(jié)點(diǎn)的rxr網(wǎng)（其中尸有

2N條鏈路，直徑為21”2」，結(jié)點(diǎn)度為4，對稱。

c.搏動式陣列(SystolicArray)

8.超立方體

4-立方體

一個n-立方體由N=2n個結(jié)點(diǎn)構(gòu)成,它們分

布在n維上）每維有兩個結(jié)點(diǎn)。直徑為ri,結(jié)

點(diǎn)度為n,對稱。由于結(jié)點(diǎn)度隨維數(shù)線性增加,

所以超立方體不是一種可擴(kuò)展結(jié)構(gòu)。

例子：

Intel的iPSC/1、iPSC/2、nCUBE

9.帶環(huán)立方體

一個帶環(huán)n-立方體由N=2n個結(jié)點(diǎn)環(huán)構(gòu)成，

每個結(jié)點(diǎn)環(huán)是一個有n個結(jié)點(diǎn)的環(huán)，所以結(jié)

點(diǎn)總數(shù)為n2n個。直徑通常為2小結(jié)點(diǎn)度為3,

對稱。

J

4元3-立方體（隱藏的結(jié)點(diǎn)與連接沒有畫出）

在一個k元n-立方體網(wǎng)絡(luò)中，結(jié)點(diǎn)的數(shù)目

N=kL即：I

k=\[N,

n=]ogkN

其中，k稱為基數(shù)(radix),n稱為維

數(shù)(dimension)。

k元n-立方體的結(jié)點(diǎn)可以用基數(shù)為k的n

位地址A=a0Hia2…an來表示,其中a1代表第i

維結(jié)點(diǎn)的位置。

傳統(tǒng)的環(huán)網(wǎng)等價(jià)于4元2-立方體。

第三章互連與通信

3.1互連網(wǎng)絡(luò)的作用

3.2靜態(tài)網(wǎng)絡(luò)

3.3動態(tài)網(wǎng)絡(luò)

3.3.1互連函數(shù)—

3.3.2多級互聯(lián)網(wǎng)絡(luò)

3.4通信問題

3.3動態(tài)網(wǎng)絡(luò)

特點(diǎn)：

網(wǎng)絡(luò)的開關(guān)元件有源，鏈路可通過設(shè)置這

些開關(guān)的狀態(tài)來重構(gòu)。

只有在網(wǎng)絡(luò)邊界上的開關(guān)元件才能與處理

機(jī)相連。

331互連函數(shù)

排列：N個數(shù)的每一種有確定次序的放置方

法叫做一個N排列。

置換：把一個N排列變成另一個N排列的變

換叫做N階置換。

在有N個輸入端和N個輸出端的網(wǎng)絡(luò)中，輸

入端和輸出端的連接關(guān)系可以用置換來表示

（輸入端與輸出端一'一對應(yīng)）。

一些常見的置換方式可以用下面的函數(shù)表

示：

1.恒等函數(shù)

W.2??X…切=—??X??&）

其中，*4/42..入1....”是「￡的地址（通常為二進(jìn)

制）。n為3時的恒等函數(shù)的連接情形如下：

000-------------------------------000

001-------------------------------001

010-------------------------------010

011-------------------------------011

100-------------------------------100

101-------------------------------101

110-------------------------------110

111-------------------------------111

2.方體函數(shù)（cube。，cubet?...?cube^j）

cubek（Xn_xXn_2…心―一?…/…X。）

方體函數(shù)是由n個互連函數(shù)組成，其中OVkVn。

比如）n為3時,3-立方體各結(jié)點(diǎn)地址如下：

Yt

010011

110

001

Q—-----------?

z000X

100101

乙一9s一女￡一zi-o

in----------in

on-----------on

101----------101

OOI----------001

no----------IIO

oio-----------010

100----------100

ooo----------000

=CxVx^qno：o9qnD

(°xlx3y)=(°xly3x)：l^j

（°丫才女）=（°丫力區(qū)），儼。：％qn0

3.洗牌函數(shù)

o234567

洗牌函數(shù)的變形：

a.均勻洗牌(Shuffle-Exchange)

是洗牌函數(shù)與Cube0函數(shù)的組合o

：洗牌：Cube0

b.第k個子洗牌

Shk（Xn-……X。）=（Z-…X""…X￡）

即最低k位循環(huán)左移-位。

c.第k個超洗牌

S/（X/-2…片的心…X。）=代_2…人料'一園一,X。）

即最高k-1位循環(huán)左移一位。

4,逆洗牌函數(shù)

01234567

5.蝶式

夕—…MX。)=(X°X〃_2…X￡_J

6.PM2I函數(shù)（加減0）

共有2n個互連函數(shù)，對N個結(jié)點(diǎn)的網(wǎng)絡(luò)為

<PM2JJ)=/+2'modN

2T(/)=J-TmodN

其中,0W/WN-LOW，V〃一Ln=log2N

N=8(8個結(jié)點(diǎn)),則n=log28=3,所

以：i=0)L2;j=0)1).??，7o

6個PM2I函數(shù)如下:

PM2+0:(01234567)

PM2_0:(76543210)

PM2+1:(0246)(1357)

PM2(6420)(7531)

例2:

上面的網(wǎng)絡(luò)可以用四個PM2I函數(shù)表示。

PM2+0:(012...15)

PM2.0:(151413...0)

PM2±2:(04)(15)(26)(37)

(48)(59)(610)(711)

(812)(913)(1014)(1115

(120)(131)(142)(153)

3.3.2多級互連網(wǎng)絡(luò)

1.多級網(wǎng)絡(luò)的三要素

(1)開關(guān)單元：a個輸入a個輸出的開關(guān)單

元記做axa的開關(guān)單元，其中，a是2的整數(shù)

倍。常見的有2x2、4x4、8x8等。

根據(jù)開關(guān)單元功能的多少，2x2又可以分

為兩功能和四功能開關(guān)。如下圖所示：

0——----------------00

1——i----------------1

1

直送交叉

00A0

11A1

上播下播

(2)級間互連模式(InterStageConnection):

均勻洗牌、蝶式、多路洗牌(比如四路洗

牌即是把牌平均分成4份，然后4堆分別進(jìn)行均

勻洗牌)、縱橫開關(guān)(CrossSwitch)及立方體連

結(jié)等。

(3)控制方式

級控制：每級只有一個控制信號

單元控制：每個開關(guān)一個控制信號

部分級控制：幾個開關(guān)合用一個控制信號

2.Q網(wǎng)

第o級第1級第2級

。網(wǎng)的特點(diǎn)：

開關(guān)單元：2x2四功能開關(guān)

ISC:洗牌變換+恒等變換

控制方式：采用單元控制方式。當(dāng)目的地

址編碼從高位開始的第i位（從0開始）為0時,

第i級的2x2開關(guān)的輸入端與上輸出端連接，

否則輸入端與下輸出端連接。I

UIUC的Cedar

IBM的RP3

NYU的Ultracomputer

無阻塞的實(shí)現(xiàn)置換

兀1=(07642)(13)(5)

置換兀2=(06473)(15)(2)

在開關(guān)F、G、H、I和J上發(fā)生阻塞

第0級第1級第2級

。網(wǎng)的特點(diǎn)(2):

并不是所有的置換在Q網(wǎng)中一次通過便可

以實(shí)現(xiàn)。

Q網(wǎng)是阻塞網(wǎng)絡(luò)：出現(xiàn)沖突時，可以采用

幾次通過的方法來解決沖突。

。網(wǎng)的特點(diǎn)(3):

當(dāng)采用kxk開關(guān)元件時，則可以定義k路洗

牌函數(shù)來構(gòu)造更大的級數(shù)為1og內(nèi)的Q網(wǎng)絡(luò)。

3.蝶式網(wǎng)絡(luò)(Butterflyswitchnetwork)

蝶式網(wǎng)絡(luò)的開關(guān)不允許廣播功能，它

實(shí)際上是Omega網(wǎng)的一個子集。

兩級54x64的蝶式網(wǎng)絡(luò)如下圖所示：

它采用16個8x8交叉開關(guān)構(gòu)成，兩級間采用

8路洗牌連接。

兩級64義64的蝶式網(wǎng)絡(luò)

第0級第1級

00

77

88

1515

5656

6363

4.其他連接方式

總線

交叉開關(guān)

第三章互連與通信

3.1互連網(wǎng)絡(luò)的作用

3.2靜態(tài)網(wǎng)絡(luò)

3.3動態(tài)網(wǎng)絡(luò)

3.4通信問題

341基本術(shù)語與性能指標(biāo)

3.4.2尋徑算法

343虛擬通道與死鎖

3.4.4包沖突的解決

3.4.5維序?qū)絀

346通信模式

3.4通信問題

3.4.1基本術(shù)語與性能指標(biāo)

1.消息、包和片

消息（Message）:是在多計(jì)算機(jī)系統(tǒng)的

處理接點(diǎn)之間傳遞包含數(shù)據(jù)和同步消息的信

息包。它是一種邏輯單位，可由任意數(shù)量的

包構(gòu)成。

包（Packet）:包的長度隨協(xié)議不同而不

同，它是信息傳送的最小承位，64-512位。

片（Flit）:片的長度固定，一般為8位。

它們的相互關(guān)系如下圖：

消息

包

片

2.互連網(wǎng)絡(luò)

互連網(wǎng)絡(luò)用來在多計(jì)算機(jī)系統(tǒng)的處理結(jié)點(diǎn)

之間傳遞消息?；ミB網(wǎng)絡(luò)的描述：

拓?fù)?Topology)

尋徑算法(Routing)

流控制(FlowControl)

互連網(wǎng)絡(luò)性能的兩個重要指標(biāo)：

傳輸時延(TransmissionLatency)

吞吐量(Throughput)

3.傳輸時延與吞吐量

一個消息的傳輸時延：從它在源結(jié)點(diǎn)進(jìn)行

發(fā)送初始化到它在目的結(jié)點(diǎn)完整的被接收所

耗費(fèi)的時間。

一個網(wǎng)絡(luò)的傳輸時延：在一定條件下發(fā)送

消息的平均時延。

網(wǎng)絡(luò)的吞吐量：單位時間內(nèi)網(wǎng)絡(luò)所能傳輸

的消息數(shù)目或長度。

4.傳輸時延的公式

T=工+5

其中，工稱為建立時延，T「稱為網(wǎng)絡(luò)時

延，幾稱為阻塞時延。

它們具體定義如下：

建立時延工：一個消息在源結(jié)點(diǎn)和目的結(jié)

點(diǎn)上裝配和分解、從存儲器拷貝到通信緩沖

區(qū)以及正確性驗(yàn)證等所耗費(fèi)的時間。它和機(jī)

器本身的硬件、軟件技術(shù)有關(guān)。■

TS=TSS+Tsd?

其中：

Tss稱為源結(jié)點(diǎn)時延：從發(fā)送進(jìn)程開始消

息發(fā)送初始化到消息的頭部進(jìn)入網(wǎng)絡(luò)所經(jīng)歷的

時間。

Tsd稱為目的結(jié)點(diǎn)時延：從消息的尾部到

達(dá)目的結(jié)點(diǎn)到消息完全被接收進(jìn)程接收所經(jīng)歷

的時間。

網(wǎng)絡(luò)時延工：消息頭部從源結(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)

到消息的尾部到達(dá)目的結(jié)點(diǎn)的時間間隔。

T/TpXD+LIBI

其中：

TpXD稱為結(jié)點(diǎn)時延：其中T1是消息在它所

經(jīng)過的路徑上的每個中間結(jié)點(diǎn)上的平均時延,

D為中間結(jié)點(diǎn)或源結(jié)點(diǎn)與目的結(jié)點(diǎn)之間的距

離。

L/B稱為線路時延：其中L為消息長度，B

為結(jié)點(diǎn)之間的通道帶寬。

阻塞時延「.：消息傳遞過程中其他所有可

能的時延（主要原因是資源沖突）。

5.網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

第一代并行計(jì)算機(jī)：HyperCube

第二代并行計(jì)算機(jī)：n—Mesh

6.網(wǎng)絡(luò)的尋徑算法

決定發(fā)送一個消息到其目的地所經(jīng)過的

路徑。

可以分為：

最短路徑算法

非最短路徑算法］

或者：

確定性算法：路徑的選擇只依賴于它所

發(fā)送的消息的源結(jié)點(diǎn)和目的結(jié)點(diǎn)。

可適應(yīng)算法：消息從結(jié)點(diǎn)A到結(jié)點(diǎn)B可以

由幾條不同的路徑。

7.網(wǎng)絡(luò)的流控制

當(dāng)一個消息在網(wǎng)絡(luò)中沿著某條路徑傳送時,

互連網(wǎng)絡(luò)如何來為它分配通道和緩沖器。

342尋徑算法

我們介紹四種尋徑方式：

存儲轉(zhuǎn)發(fā)(Store-and-Forward)

虛擬直通(Virtualcutthrough)

線路交換(CircuitSwitching)

Wormhole交換(WormholeSwitching)

1.存儲轉(zhuǎn)發(fā)

當(dāng)一個消息到達(dá)中間結(jié)點(diǎn)A時，A把整個消

息放入其通信緩沖器中，然后在尋徑算法的控

制下選擇下一個相鄰結(jié)點(diǎn)B,當(dāng)從A到B的通

道空閑并且B的通信緩沖器可用時，把J肖息從

A發(fā)向B。

缺點(diǎn)：

每個結(jié)點(diǎn)必須對整個消息進(jìn)行緩沖，緩沖器

較大。

網(wǎng)絡(luò)時延與發(fā)送消息所經(jīng)歷的結(jié)點(diǎn)數(shù)成正比

Tn=TpXD+LIB=(LI+B=(LI+?

2.虛擬直通

中間結(jié)點(diǎn)沒有必要等到整個消息全部被緩沖

后再作出路由選擇，只要消息的目的信息域可

用后，就可以作出路由選擇。

=TpxD+L/B=(LJB)xD+L/B=(LhxD+L)/B

其中，Lh為消息頭部開始到其目的信息域的

長度)顯然有L>>Lh,所以的影響比較小。

而當(dāng)通向下一結(jié)點(diǎn)的通道忙或結(jié)點(diǎn)的緩沖

器非空閑時，必須把整個消息緩沖起來，這時

和存儲轉(zhuǎn)發(fā)一樣。

3.線路開關(guān)

在傳遞一個消息之前，就為它建立一條從源

結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通道。在傳遞的全部過

程中，線路的每一段都被占用，當(dāng)消息的尾部

經(jīng)過網(wǎng)絡(luò)后，整條物理鏈路才被廢棄。

fxD+LIB=(LJB)xD+LIB=1LcXD+L)lB

其中，L是為消息建立物理通路所傳遞的控

制信息的長度。當(dāng)L〉〉。時，D的影響較小。

缺點(diǎn)：

物理通道非共享

傳輸過程中物理通道一直被占用

4.Wormhole

Dally于1986年提出。

首先把一個消息分成許多片，消息的頭片包

含了這個消息的所有尋徑信息。尾片是一個其

最后包含了消息結(jié)束符的片。中間的片均為數(shù)

據(jù)片。

片是最小信息單位。每個結(jié)點(diǎn)上只需要緩

沖一個片就能滿足要求。

用一個頭片直接開辟一條從輸入鏈路到輸

出鏈路的路徑的方法來進(jìn)行操作。每個消息中

的片以流水的方式在網(wǎng)絡(luò)中向前"蠕動"。每

個片相當(dāng)于Worm的一個節(jié)，“蠕動”以節(jié)為

單位順序的向前爬行。

當(dāng)消息的頭片到達(dá)一個結(jié)點(diǎn)A的尋徑器后，

尋徑器根據(jù)頭片的尋徑信息立即做出路由選

擇：

(1)如果所選擇的通道空閑而且所選

擇的結(jié)點(diǎn)B的通信緩沖器可用，那么這個頭

片就不必等待,直接通過結(jié)點(diǎn)A傳向下一個

結(jié)點(diǎn)B;隨后的其它片跟著相應(yīng)的向前“蠕

動力一步。當(dāng)消息的尾片向前“蠕動”一步

后)它剛才所占用的結(jié)點(diǎn)就被放棄了。

(2)如果所選擇的通道非空閑或者所

選擇的結(jié)點(diǎn)的通信緩沖器非可用，那么這個

頭片就必須在此結(jié)點(diǎn)的通信緩沖器中等待，

直到上述兩者都可用為止；其它片也在原來

的結(jié)點(diǎn)上等待。此時，被阻塞的消息不從網(wǎng)

絡(luò)中移去，片不放棄它所占有的結(jié)點(diǎn)和通道。

這是Wormhole技術(shù)和其它流控制技術(shù)都不同

的地方。

Tn^TpxD+L/B=(Lf/B)xD+L/B=(LfxD+L)/B

其中，%是片的長度，通常很小。

優(yōu)點(diǎn)：

(1)每個結(jié)點(diǎn)的緩沖器的需求量小，易于

用VLSI實(shí)現(xiàn)。

(2)較低的網(wǎng)絡(luò)傳輸延遲。所有的片以流

水方式向前傳送，時間并形性。而在存儲轉(zhuǎn)

發(fā)中，消息是整個的從一個結(jié)點(diǎn)“跳”向另

一個結(jié)點(diǎn))通道的使用時串行的。所以它的

傳輸延遲基本上正比于消息在網(wǎng)絡(luò)中傳輸?shù)?/p>

距離。Wormhole與線路開關(guān)的網(wǎng)絡(luò)傳輸延遲

正比于消息包的長度，傳輸距離對它的影響

很小(消息包較長時的情況)。

（3）通道共享性好、利用率高。對通道的

預(yù)約和釋放是結(jié)合在一起的一個完整的過程:

占有一段新的通道后將立即放棄用過的一段

舊通道。

（4）易于實(shí)現(xiàn)Multicast和Broadcast。允許

尋徑器復(fù)制消息包的片并把它們從多個輸出

通道輸出。

Wormhole方式中）同一個包中所有的片象不

可分離的同伴一樣以流水方式順序的傳送。

包可看作是一列火車，由火車頭（頭片）和

被牽引的車廂（數(shù)據(jù)片）組成。

5.幾種尋徑技術(shù)的時空圖

?L/B->

T

I

IlI;;;[;]

D

12I

D

時間

存儲轉(zhuǎn)發(fā)(Store-and-forward)尋徑技術(shù)

s

II

12

D

時間

電路開關(guān)尋徑技術(shù)

Wormhole尋徑技術(shù)

343死鎖和虛擬通道

1.虛擬通道

是兩個結(jié)點(diǎn)間的邏輯鏈。

由源結(jié)點(diǎn)的片緩沖區(qū)、結(jié)點(diǎn)間的物理通道

和接收結(jié)點(diǎn)的緩沖區(qū)組成。

物理通道由所有虛擬通道分時共享。比如

在下例中，四條虛擬通道以片傳遞為基礎(chǔ)分

時的共享一條物理通道。

源結(jié)點(diǎn)中的片緩沖區(qū)目的結(jié)點(diǎn)中的片緩沖

四條虛擬通道以片傳遞為基礎(chǔ)分時共享一?條物理通道

2.死鎖的產(chǎn)生

緩沖區(qū)產(chǎn)生死鎖:

結(jié)點(diǎn)B結(jié)點(diǎn)C

采用存儲轉(zhuǎn)發(fā)，四個包占用了四個結(jié)點(diǎn)的四個緩沖

區(qū)，修導(dǎo)致循環(huán)等待。

通信產(chǎn)生死鎖:

消息的四個片同時占用了4個通道。

2.死鎖的避免

結(jié)點(diǎn)表示通道，帶方向的箭頭表示通道之間的

依賴關(guān)系。

344包沖突的解決

1.問題的提出■

兩個相鄰結(jié)點(diǎn)間要傳送包，必須具備下列

三個條件：

(1)源緩沖區(qū)已存該包

(2)通道已分配好■

(3)接收緩沖區(qū)準(zhǔn)備接收

當(dāng)兩個包到達(dá)同一個結(jié)點(diǎn)時，可能請求同

一個接收緩沖區(qū)或用同一個輸出通道：

(1)把通道分配給哪個包？

(2)沒有分配到通道的包怎么辦？

2,四種解決方法

(1)用緩沖實(shí)現(xiàn)虛擬直通尋徑

廠》緩沖區(qū)

好處：不會浪費(fèi)已經(jīng)分配的資源

缺點(diǎn)：需要一個能存放整個包的緩沖區(qū)，包

緩沖區(qū)不可能做在尋徑芯片上，要用存儲器作

為緩沖區(qū)，會有較大的存儲延遲。

(2)阻塞流控制(Wormhole尋徑)

控制■包1廠片緩沖區(qū)

/一--------------------一

包21一右.■/輸百通道、.

第二個包被阻塞不再前進(jìn)，但沒有被揚(yáng)棄

(3)揚(yáng)棄并重發(fā)

包1片緩沖區(qū)

包2輸出通道

//////

第二個包被揚(yáng)棄

(3)阻塞后繞道

繞道通道

包1

片緩沖區(qū)

包2輸出通道

第二個包繞道：被轉(zhuǎn)發(fā)到其它的尋徑器

3.4.5維序?qū)?/p>

1.尋徑方式

確定尋徑(deterministicrouting):

通信路徑完全由源和目的地址確定。(換句

話說，尋找的路徑是預(yù)先唯一確定的，與網(wǎng)

絡(luò)的狀況無關(guān))。

自適應(yīng)尋徑(adaptiverouting):

與網(wǎng)絡(luò)的狀況有關(guān)，可能會有幾條路徑。

(需要消除死鎖的算法)。

2.兩種確定尋徑算法(維序?qū)?

(1)二維網(wǎng)格中的X-Y尋徑：

首先沿著X維方向確定路徑，然后沿［

著Y維方向選擇路徑。

假定從任意源結(jié)點(diǎn)s=(XIY1)到任意

目的結(jié)點(diǎn)d=(X2Y2)。尋徑從s開始，首先

沿著X方向前進(jìn)一直到d所在的第X2列為止，

然后沿Y方向前進(jìn)直到d。

四種模式：

東一北)東一南)西一北)西一南。

下面是一個例子:

特點(diǎn)：

總是先沿X維方向?qū)?，然后再沿Y維方］

向?qū)?，尋徑不會出現(xiàn)死鎖或循環(huán)等待現(xiàn)

象。

可以擴(kuò)充到n維網(wǎng)絡(luò)，如X-Y-Z等等。

可用于存儲轉(zhuǎn)發(fā)或Wormhole尋徑網(wǎng)絡(luò),在

源和目的結(jié)點(diǎn)之間形成一條距離最短的路

徑。

(2)立方體網(wǎng)絡(luò)中的E立方體尋徑：

假設(shè)有一個N=2n個結(jié)點(diǎn)的n方體。每

個結(jié)點(diǎn)的二進(jìn)制編碼為：

b=bn.1bn.2...b1b0

S=Sn.iS^...SiSo

d=dn-1dn_2...d1d0

如何確定一條從s到d的步數(shù)最小的路徑？

將n維表示成i=1,2,??.n,其中第i維對應(yīng)結(jié)

點(diǎn)地址中的第i-：位。設(shè)

V=Vn-lVn-2---VlV0

是路徑中的任一結(jié)點(diǎn)。

方法：

(1)計(jì)算方向位。

々=S'-i田中i=1)2〉???72O

使i=l,v=s)開始下面的步驟。

(2)如果u=1,則從當(dāng)前結(jié)點(diǎn)v尋徑到下

一結(jié)點(diǎn)V?271

如果==0,則跳過這一步。

(3)i=i+l,如果iVn,則轉(zhuǎn)第(2)步,

否則退出。

如下面的例子：

1101

11=4,s=01105d=1101

尋徑：

(1)計(jì)算方向位。i=Lv=s

0110

十1101

1011

(R=r4r3r2刀

(2)h=L

???s至Us十2—=0110?0001=0111

2=%+1=2

(3)r2=L

???V=0111至h?22T=0111e0010=0101

2=%+1=3

(4)r3=0,

/.跳過一^步

i=i