計(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)度

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

第六章CacheCoherence

第七章MemoryConsistency

第八章指令級(jí)并行處理

第三章互連與通信

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

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

3.3動(dòng)態(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)部多個(gè)處

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

操作方式：I

同步通信(SynchronousCommunication)

異步通信(AsynchronousCommunication)

控制策略：I

集中控制(Centralizedcontrol)

分布控制(Distributedcontrol)

交換方式：

電路交換(Circuitswitching)

分組交換(Packetswitching)

Wormhole交換(Wormholeswitching)

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

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

動(dòng)態(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動(dòng)態(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í)行過程中不會(huì)改變。

如果用圖來表示，結(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ù)。

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

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

最大值。

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

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

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

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

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

對(duì)稱性：從任何結(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.線性陣列

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

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

度為2,不對(duì)稱，等分寬度為1。

N很大時(shí)，通信效率很低。

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

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

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

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

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

數(shù)據(jù)。

2.環(huán)

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

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

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

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

對(duì)稱，等分寬度為2。

3,帶弦環(huán)

度

為

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

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

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

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

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

4.鏈接

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

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

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

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

分寬度為16。

5木

4

層

的

二

叉

樹

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

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

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

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

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

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

樹形的擴(kuò)展:

二

叉

胖

樹

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

6.星形

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

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

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

7.網(wǎng)

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

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

非對(duì)稱，等分寬度為r。

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

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

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

c.搏動(dòng)式陣列(SystolicArray)

8.超立方體

4-立方體

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

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

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

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

例子：

Intel的iPSC/1、iPSC/2、nCUBE

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

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

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

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

對(duì)稱。

J

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

在一個(gè)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動(dòng)態(tài)網(wǎng)絡(luò)

3.3.1互連函數(shù)—

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

3.4通信問題

3.3動(dòng)態(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個(gè)數(shù)的每一種有確定次序的放置方

法叫做一個(gè)N排列。

置換：把一個(gè)N排列變成另一個(gè)N排列的變

換叫做N階置換。

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

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

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

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

示：

1.恒等函數(shù)

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

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

制）。n為3時(shí)的恒等函數(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個(gè)互連函數(shù)組成，其中OVkVn。

比如）n為3時(shí),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個(gè)子洗牌

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

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

c.第k個(gè)超洗牌

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個(gè)互連函數(shù)，對(duì)N個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)為

<PM2JJ)=/+2'modN

2T(/)=J-TmodN

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

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

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

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

PM2+0:(01234567)

PM2_0:(76543210)

PM2+1:(0246)(1357)

PM2(6420)(7531)

例2:

上面的網(wǎng)絡(luò)可以用四個(gè)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多級(jí)互連網(wǎng)絡(luò)

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

(1)開關(guān)單元：a個(gè)輸入a個(gè)輸出的開關(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)級(jí)間互連模式(InterStageConnection):

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

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

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

結(jié)等。

(3)控制方式

級(jí)控制：每級(jí)只有一個(gè)控制信號(hào)

單元控制：每個(gè)開關(guān)一個(gè)控制信號(hào)

部分級(jí)控制：幾個(gè)開關(guān)合用一個(gè)控制信號(hào)

2.Q網(wǎng)

第o級(jí)第1級(jí)第2級(jí)

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

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

ISC:洗牌變換+恒等變換

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

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

第i級(jí)的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級(jí)第1級(jí)第2級(jí)

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

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

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

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

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

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

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

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

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

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

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

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

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

8路洗牌連接。

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

第0級(jí)第1級(jí)

00

77

88

1515

5656

6363

4.其他連接方式

總線

交叉開關(guān)

第三章互連與通信

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

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

3.3動(dòng)態(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ò)性能的兩個(gè)重要指標(biāo)：

傳輸時(shí)延(TransmissionLatency)

吞吐量(Throughput)

3.傳輸時(shí)延與吞吐量

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

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

耗費(fèi)的時(shí)間。

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

消息的平均時(shí)延。

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

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

4.傳輸時(shí)延的公式

T=工+5

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

延，幾稱為阻塞時(shí)延。

它們具體定義如下：

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

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

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

器本身的硬件、軟件技術(shù)有關(guān)?！?/p>

TS=TSS+Tsd?

其中：

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

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

時(shí)間。

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

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

的時(shí)間。

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

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

T/TpXD+LIBI

其中：

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

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

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

離。

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

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

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

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

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

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

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

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

決定發(fā)送一個(gè)消息到其目的地所經(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)一個(gè)消息在網(wǎng)絡(luò)中沿著某條路徑傳送時(shí),

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

342尋徑算法

我們介紹四種尋徑方式：

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

虛擬直通(Virtualcutthrough)

線路交換(CircuitSwitching)

Wormhole交換(WormholeSwitching)

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

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

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

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

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

A發(fā)向B。

缺點(diǎn)：

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

較大。

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

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

2.虛擬直通

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

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

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

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

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

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

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

器非空閑時(shí)，必須把整個(gè)消息緩沖起來，這時(shí)

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

3.線路開關(guān)

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

結(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〉〉。時(shí)，D的影響較小。

缺點(diǎn)：

物理通道非共享

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

4.Wormhole

Dally于1986年提出。

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

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

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

據(jù)片。

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

沖一個(gè)片就能滿足要求。

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

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

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

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

單位順序的向前爬行。

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

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

擇：

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

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

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

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

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

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

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

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

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

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

的結(jié)點(diǎn)上等待。此時(shí)，被阻塞的消息不從網(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)每個(gè)結(jié)點(diǎn)的緩沖器的需求量小，易于

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

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

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

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

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

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

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

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

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

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

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

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

舊通道。

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

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

通道輸出。

Wormhole方式中）同一個(gè)包中所有的片象不

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

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

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

5.幾種尋徑技術(shù)的時(shí)空?qǐng)D

?L/B->

T

I

IlI;;;[;]

D

12I

D

時(shí)間

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

s

II

12

D

時(shí)間

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

Wormhole尋徑技術(shù)

343死鎖和虛擬通道

1.虛擬通道

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

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

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

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

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

時(shí)的共享一條物理通道。

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

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

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

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

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

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

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

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

消息的四個(gè)片同時(shí)占用了4個(gè)通道。

2.死鎖的避免

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

依賴關(guān)系。

344包沖突的解決

1.問題的提出■

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

三個(gè)條件：

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

(2)通道已分配好■

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

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

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

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

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

2,四種解決方法

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

廠》緩沖區(qū)

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

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

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

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

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

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

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

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

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

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

包1片緩沖區(qū)

包2輸出通道

//////

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

(3)阻塞后繞道

繞道通道

包1

片緩沖區(qū)

包2輸出通道

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

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

1.尋徑方式

確定尋徑(deterministicrouting):

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

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

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

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

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

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

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。

四種模式：

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

下面是一個(gè)例子:

特點(diǎn)：

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

向?qū)剑瑢讲粫?huì)出現(xiàn)死鎖或循環(huán)等待現(xiàn)

象。

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

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

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

徑。

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

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

個(gè)結(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維對(duì)應(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