計算機系統(tǒng)結構3

計算機科學與技術系研究生課程

高等計算機系統(tǒng)結構

清華大學計算機科學與技術系高性能計算研究所

鄭緯民教授

2000年9月

高等計算機系統(tǒng)結構

第一章高等計算機的核心技術——并行處理

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

第三章互連與通信

第四章劃分與調度

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

第六章CacheCoherence

第七章MemoryConsistency

第八章指令級并行處理

第三章互連與通信

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

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

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

3.4通信問題

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

定義：由開關元件按一定拓撲結構和控制方

式構成的網(wǎng)絡以實現(xiàn)計算機系統(tǒng)內部多個處

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

操作方式：I

同步通信(SynchronousCommunication)

異步通信(AsynchronousCommunication)

控制策略：I

集中控制(Centralizedcontrol)

分布控制(Distributedcontrol)

交換方式：

電路交換(Circuitswitching)

分組交換(Packetswitching)

Wormhole交換(Wormholeswitching)

網(wǎng)絡拓撲結構：

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

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

第三章互連與通信

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

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

3.2.1靜態(tài)網(wǎng)絡的特點與指標

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

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

3.4通信問題

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

3.2.1靜態(tài)網(wǎng)絡的特點與指標

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

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

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

如果用圖來表示，結點代表開關，邊代表

通信鏈路，則

(1)結點間的鏈路無源，不能重構■

(2)開關元件與處理機相連

(3)不直接相連結點間的通信需通過中

間結點中轉。

2.靜態(tài)網(wǎng)絡的指標

結點度：與結點相連接的邊（鏈路或通道）

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

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

結點度可以進一步表示為：

結點度=入度+出度

其中入度是進入結點的通道數(shù)，出度是從結

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

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

網(wǎng)絡直徑：網(wǎng)絡中任意兩個結點間距離的

最大值。

網(wǎng)絡規(guī)模：網(wǎng)絡中結點數(shù)，表示該網(wǎng)絡功

能連結部件的多少。

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

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

結點間的線長：兩個結點間的線的長度。

對稱性：從任何結點看，拓撲結構都一樣,

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

結點是否同構。

通道是否有緩沖。

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

1.線性陣列

對N個結點的線性陣列，有N-1條鏈路，直

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

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

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

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

線性陣列：允許不同的源結點和目的結點

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

總線：通過切換與其相連的許多結點來實

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

數(shù)據(jù)。

2.環(huán)

對N個結點的環(huá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個結點的帶弦雙向環(huán)，

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

色結點），度為3，不對稱，等分寬度為2。

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

色結點），度為4，對稱，等分寬度為8。

4.鏈接

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

每個結點和其他結點之間都有單一的直接鏈

路。如下圖中8個結點的鏈接：

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

分寬度為16。

5木

4

層

的

二

叉

樹

一棵K層完全二叉樹應有N=2K-1個結點,

對大結點度為3,直徑為2(K-1)(即右邊

任意一個葉子結點到左邊任意一個葉子結

點)。不對稱，等分度為L

由于結點度為常數(shù)，所以樹是一種可擴展

的系統(tǒng)結構。

樹形的擴展:

二

叉

胖

樹

這兩種結構都可以緩解根結點的瓶頸問題。

6.星形

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

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

最大結點度為N-L非對稱，等分寬度為1。

7.網(wǎng)

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

2N-2r條鏈路，直徑為2(r-1),結點度為4,

非對稱，等分寬度為r。

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

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

2N條鏈路，直徑為21”2」，結點度為4，對稱。

c.搏動式陣列(SystolicArray)

8.超立方體

4-立方體

一個n-立方體由N=2n個結點構成,它們分

布在n維上）每維有兩個結點。直徑為ri,結

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

所以超立方體不是一種可擴展結構。

例子：

Intel的iPSC/1、iPSC/2、nCUBE

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

一個帶環(huán)n-立方體由N=2n個結點環(huán)構成，

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

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

對稱。

J

4元3-立方體（隱藏的結點與連接沒有畫出）

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

N=kL即：I

k=\[N,

n=]ogkN

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

數(shù)(dimension)。

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

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

維結點的位置。

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

第三章互連與通信

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

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

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

3.3.1互連函數(shù)—

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

3.4通信問題

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

特點：

網(wǎng)絡的開關元件有源，鏈路可通過設置這

些開關的狀態(tài)來重構。

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

機相連。

331互連函數(shù)

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

法叫做一個N排列。

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

換叫做N階置換。

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

入端和輸出端的連接關系可以用置換來表示

（輸入端與輸出端一'一對應）。

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

示：

1.恒等函數(shù)

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

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

制）。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-立方體各結點地址如下：

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個結點的網(wǎng)絡為

<PM2JJ)=/+2'modN

2T(/)=J-TmodN

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

N=8(8個結點),則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)絡可以用四個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)絡

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

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

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

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

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

為兩功能和四功能開關。如下圖所示：

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

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

1

直送交叉

00A0

11A1

上播下播

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

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

牌即是把牌平均分成4份，然后4堆分別進行均

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

結等。

(3)控制方式

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

單元控制：每個開關一個控制信號

部分級控制：幾個開關合用一個控制信號

2.Q網(wǎng)

第o級第1級第2級

。網(wǎng)的特點：

開關單元：2x2四功能開關

ISC:洗牌變換+恒等變換

控制方式：采用單元控制方式。當目的地

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

第i級的2x2開關的輸入端與上輸出端連接，

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

UIUC的Cedar

IBM的RP3

NYU的Ultracomputer

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

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

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

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

第0級第1級第2級

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

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

以實現(xiàn)。

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

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

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

當采用kxk開關元件時，則可以定義k路洗

牌函數(shù)來構造更大的級數(shù)為1og內的Q網(wǎng)絡。

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

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

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

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

它采用16個8x8交叉開關構成，兩級間采用

8路洗牌連接。

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

第0級第1級

00

77

88

1515

5656

6363

4.其他連接方式

總線

交叉開關

第三章互連與通信

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

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

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

3.4通信問題

341基本術語與性能指標

3.4.2尋徑算法

343虛擬通道與死鎖

3.4.4包沖突的解決

3.4.5維序尋徑I

346通信模式

3.4通信問題

3.4.1基本術語與性能指標

1.消息、包和片

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

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

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

包構成。

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

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

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

它們的相互關系如下圖：

消息

包

片

2.互連網(wǎng)絡

互連網(wǎng)絡用來在多計算機系統(tǒng)的處理結點

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

拓撲(Topology)

尋徑算法(Routing)

流控制(FlowControl)

互連網(wǎng)絡性能的兩個重要指標：

傳輸時延(TransmissionLatency)

吞吐量(Throughput)

3.傳輸時延與吞吐量

一個消息的傳輸時延：從它在源結點進行

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

耗費的時間。

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

消息的平均時延。

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

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

4.傳輸時延的公式

T=工+5

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

延，幾稱為阻塞時延。

它們具體定義如下：

建立時延工：一個消息在源結點和目的結

點上裝配和分解、從存儲器拷貝到通信緩沖

區(qū)以及正確性驗證等所耗費的時間。它和機

器本身的硬件、軟件技術有關?！?/p>

TS=TSS+Tsd?

其中：

Tss稱為源結點時延：從發(fā)送進程開始消

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

時間。

Tsd稱為目的結點時延：從消息的尾部到

達目的結點到消息完全被接收進程接收所經(jīng)歷

的時間。

網(wǎng)絡時延工：消息頭部從源結點進入網(wǎng)絡

到消息的尾部到達目的結點的時間間隔。

T/TpXD+LIBI

其中：

TpXD稱為結點時延：其中T1是消息在它所

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

D為中間結點或源結點與目的結點之間的距

離。

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

為結點之間的通道帶寬。

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

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

5.網(wǎng)絡的拓撲結構

第一代并行計算機：HyperCube

第二代并行計算機：n—Mesh

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

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

路徑。

可以分為：

最短路徑算法

非最短路徑算法］

或者：

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

發(fā)送的消息的源結點和目的結點。

可適應算法：消息從結點A到結點B可以

由幾條不同的路徑。

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

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

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

342尋徑算法

我們介紹四種尋徑方式：

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

虛擬直通(Virtualcutthrough)

線路交換(CircuitSwitching)

Wormhole交換(WormholeSwitching)

1.存儲轉發(fā)

當一個消息到達中間結點A時，A把整個消

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

制下選擇下一個相鄰結點B,當從A到B的通

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

A發(fā)向B。

缺點：

每個結點必須對整個消息進行緩沖，緩沖器

較大。

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

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

2.虛擬直通

中間結點沒有必要等到整個消息全部被緩沖

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

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

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

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

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

而當通向下一結點的通道忙或結點的緩沖

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

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

3.線路開關

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

結點到目的結點的物理通道。在傳遞的全部過

程中，線路的每一段都被占用，當消息的尾部

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

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

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

制信息的長度。當L〉〉。時，D的影響較小。

缺點：

物理通道非共享

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

4.Wormhole

Dally于1986年提出。

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

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

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

據(jù)片。

片是最小信息單位。每個結點上只需要緩

沖一個片就能滿足要求。

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

出鏈路的路徑的方法來進行操作。每個消息中

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

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

單位順序的向前爬行。

當消息的頭片到達一個結點A的尋徑器后，

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

擇：

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

擇的結點B的通信緩沖器可用，那么這個頭

片就不必等待,直接通過結點A傳向下一個

結點B;隨后的其它片跟著相應的向前“蠕

動力一步。當消息的尾片向前“蠕動”一步

后)它剛才所占用的結點就被放棄了。

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

選擇的結點的通信緩沖器非可用，那么這個

頭片就必須在此結點的通信緩沖器中等待，

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

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

絡中移去，片不放棄它所占有的結點和通道。

這是Wormhole技術和其它流控制技術都不同

的地方。

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

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

優(yōu)點：

(1)每個結點的緩沖器的需求量小，易于

用VLSI實現(xiàn)。

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

水方式向前傳送，時間并形性。而在存儲轉

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

一個結點)通道的使用時串行的。所以它的

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

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

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

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

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

預約和釋放是結合在一起的一個完整的過程:

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

舊通道。

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

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

通道輸出。

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

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

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

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

5.幾種尋徑技術的時空圖

?L/B->

T

I

IlI;;;[;]

D

12I

D

時間

存儲轉發(fā)(Store-and-forward)尋徑技術

s

II

12

D

時間

電路開關尋徑技術

Wormhole尋徑技術

343死鎖和虛擬通道

1.虛擬通道

是兩個結點間的邏輯鏈。

由源結點的片緩沖區(qū)、結點間的物理通道

和接收結點的緩沖區(qū)組成。

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

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

時的共享一條物理通道。

源結點中的片緩沖區(qū)目的結點中的片緩沖

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

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

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

結點B結點C

采用存儲轉發(fā)，四個包占用了四個結點的四個緩沖

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

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

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

2.死鎖的避免

結點表示通道，帶方向的箭頭表示通道之間的

依賴關系。

344包沖突的解決

1.問題的提出■

兩個相鄰結點間要傳送包，必須具備下列

三個條件：

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

(2)通道已分配好■

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

當兩個包到達同一個結點時，可能請求同

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

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

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

2,四種解決方法

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

廠》緩沖區(qū)

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

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

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

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

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

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

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

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

第二個包被阻塞不再前進，但沒有被揚棄

(3)揚棄并重發(fā)

包1片緩沖區(qū)

包2輸出通道

//////

第二個包被揚棄

(3)阻塞后繞道

繞道通道

包1

片緩沖區(qū)

包2輸出通道

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

3.4.5維序尋徑

1.尋徑方式

確定尋徑(deterministicrouting):

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

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

絡的狀況無關)。

自適應尋徑(adaptiverouting):

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

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

2.兩種確定尋徑算法(維序尋徑)

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

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

著Y維方向選擇路徑。

假定從任意源結點s=(XIY1)到任意

目的結點d=(X2Y2)。尋徑從s開始，首先

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

然后沿Y方向前進直到d。

四種模式：

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

下面是一個例子:

特點：

總是先沿X維方向尋徑，然后再沿Y維方］

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

象。

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

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

源和目的結點之間形成一條距離最短的路

徑。

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

假設有一個N=2n個結點的n方體。每

個結點的二進制編碼為：

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

S=Sn.iS^...SiSo

d=dn-1dn_2...d1d0

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

將n維表示成i=1,2,??.n,其中第i維對應結

點地址中的第i-：位。設

V=Vn-lVn-2---VlV0

是路徑中的任一結點。

方法：

(1)計算方向位。

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

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

(2)如果u=1,則從當前結點v尋徑到下

一結點V?271

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

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

否則退出。

如下面的例子：

1101

11=4,s=01105d=1101

尋徑：

(1)計算方向位。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