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

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

（第23講）

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

第一章基本概念第六章向量處理機(jī)

第二章指令系統(tǒng)第七章互連網(wǎng)絡(luò)

第三章存儲(chǔ)系統(tǒng)第八章并行處理機(jī)和

第四章輸入輸出系統(tǒng)多處理機(jī)

第五章標(biāo)量處理機(jī)

第七章互連網(wǎng)絡(luò)

本章主要內(nèi)容：并行處理機(jī)和

多處理機(jī)系統(tǒng)中的互連網(wǎng)絡(luò)

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

7.2互連網(wǎng)絡(luò)的種類

7.3消息傳遞機(jī)制

7.4互連網(wǎng)絡(luò)實(shí)例

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

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

7.1.2互連網(wǎng)絡(luò)的特性■

7.1.3互連網(wǎng)絡(luò)的性能參數(shù)

7.1.4互連網(wǎng)絡(luò)的表示方法

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

用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或

多個(gè)功能部件之間的相互連接。

互連網(wǎng)絡(luò)已成為并行處理系統(tǒng)的核心組

成部分。

互連網(wǎng)絡(luò)對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的性能價(jià)格

比有著決定性的影響。

具有本地存儲(chǔ)器、私有高速緩存、共

享存儲(chǔ)器和共享外圍設(shè)備的一般處理

機(jī)系統(tǒng)的互連結(jié)構(gòu)

IPCN

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

（第24講）

7.L2互連網(wǎng)絡(luò)的特性

互連網(wǎng)絡(luò)通常是用有向邊或無(wú)向邊連接有

限個(gè)結(jié)點(diǎn)的組成。

互連網(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ù)表示

⑸結(jié)點(diǎn)間的線長(zhǎng)：兩個(gè)結(jié)點(diǎn)間連線的長(zhǎng)

度。用米、公里等表示

(6)對(duì)稱］：從任何結(jié)點(diǎn)看到拓?fù)浣Y(jié)構(gòu)都

是一樣的網(wǎng)絡(luò)稱為對(duì)稱網(wǎng)絡(luò)。對(duì)稱網(wǎng)絡(luò)

比較易實(shí)現(xiàn)，編程也較容易。

7.1.3互連網(wǎng)絡(luò)的性能參數(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ū)

互連網(wǎng)絡(luò)在傳輸方面的主要性能參數(shù)：

(1)頻帶寬度(Bandwidth)：互連網(wǎng)絡(luò)傳輸

信息的最大速率。

(2)傳輸時(shí)間(Transmissiontime)：等于消

息長(zhǎng)度除以頻寬。

(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í)間。

一個(gè)消息的總時(shí)延可以用下面公式表示：

總時(shí)延=發(fā)送方開銷+飛行時(shí)間+

消息長(zhǎng)度/頻寬+接收方開銷

例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í)延為多大？

解：I

光的速度為299792.5KM/S,信號(hào)在導(dǎo)

體中傳遞速度大約是光速的50%,相距

100米時(shí)總時(shí)延為：

消息長(zhǎng)度

T=發(fā)送方開銷+飛行時(shí)間+頻寬+接收方開銷

0.1Km1000x8位

=230"s+------------------------------------+-------------------+270/js

0.5x299792.5Km/s10兆位/秒

=230jus+0.67"s+800pis+270jus=1301jus

相距1000公里時(shí)的總時(shí)延為:

1000X1061000X8

T=2304s+-----------------------jus+--------------jus+270/ns

0.5x299792.510

=230Lis+6671jus+800us+270LIS=7971us

7.1.4互連網(wǎng)絡(luò)的表示方法

為了在輸入結(jié)點(diǎn)與輸出結(jié)點(diǎn)之間建立對(duì)應(yīng)關(guān)

系，互連網(wǎng)絡(luò)有三種表示方法：

(1)互連函數(shù)表示法：

如：f(xn-1...x1x0)=x0xn-2...xlxn-1

自變量和函數(shù)可以用二進(jìn)制表示，

也可以用十進(jìn)制等表示

(2)圖形表示法(3)輸入輸出對(duì)應(yīng)表示法

0—d—k0

1—>互連一?1輸入:01234567

：網(wǎng)絡(luò)：輸出：10325476

n-1——n-1

第七章互連網(wǎng)絡(luò)

本章主要內(nèi)容：并行處理機(jī)和

多處理機(jī)系統(tǒng)中的互連網(wǎng)絡(luò)

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

7.2互連網(wǎng)絡(luò)的種類

7.3消息傳遞機(jī)制

7.4互連網(wǎng)絡(luò)實(shí)例

7.2互連網(wǎng)絡(luò)的種類

721靜態(tài)互連網(wǎng)絡(luò)

722循環(huán)互連網(wǎng)絡(luò)

723多級(jí)互連網(wǎng)絡(luò)

7.2互連網(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)之間的互連之外，還能夠

實(shí)現(xiàn)廣播和多播。

721靜態(tài)互連網(wǎng)絡(luò)

在各結(jié)點(diǎn)之間有固定的連接通路，在運(yùn)行

過程中不能改變的網(wǎng)絡(luò)結(jié)構(gòu)。

一維的有線性陣列結(jié)構(gòu)；二維的有環(huán)形、

星形、樹形、網(wǎng)格形等；三維的有立方

體等；三維以上的有超立方體等。

1、環(huán)形網(wǎng)

采用移數(shù)函數(shù)。使用不同的移數(shù)函數(shù)，可

以構(gòu)成多種環(huán)形網(wǎng)。一

單向環(huán)行四：右環(huán)網(wǎng)，采用PM2+0函數(shù)。

左環(huán)網(wǎng)，采用PM2-0函數(shù)。

雙向環(huán)行網(wǎng)：又稱為一維鄰居網(wǎng)，采用

{PM2+o,PM2.。}函數(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/21。

2、樹形和星形網(wǎng)

一棵k層二叉樹有N=2k—1個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)

度是3,直徑是2(k-l)。

星形是一種特殊的2層樹，結(jié)點(diǎn)度很高，］

為(1=?<-1,直徑是2。

二叉胖樹的結(jié)點(diǎn)度從葉子結(jié)點(diǎn)往根結(jié)點(diǎn)

逐漸增加。胖樹緩解了一般二叉樹根

結(jié)點(diǎn)通信速度高的矛盾。

3、網(wǎng)格形網(wǎng)

是一種比較流行的網(wǎng)絡(luò)結(jié)構(gòu)，有各種變I

體形式。在IlliacIV、MPP、DAP、

CM-2和InetlParagon中得到了實(shí)現(xiàn)。

一般網(wǎng)格網(wǎng)，N=nk結(jié)點(diǎn)的k維網(wǎng)格的結(jié)

點(diǎn)度為2k,直徑為k(n-l)。

環(huán)網(wǎng)形網(wǎng)格網(wǎng)沿陣列每行每列都有環(huán)形

連接。一個(gè)nXn二元環(huán)網(wǎng)的結(jié)點(diǎn)度為4,

直徑為2?n/2?。環(huán)網(wǎng)是一種對(duì)稱的拓?fù)?/p>

結(jié)構(gòu)。

IlliacIV的8X8Illiac網(wǎng)格,其結(jié)點(diǎn)度為4,

直徑為7。一個(gè)nXnllliac網(wǎng)格的直徑為

d=n-1,為純網(wǎng)格直徑的一半。

4、超立方體網(wǎng)

n維立方體由N=2n

個(gè)結(jié)點(diǎn),分布在n

維上,每維有兩

個(gè)結(jié)點(diǎn)

超立方體網(wǎng)采用交

換函數(shù)，結(jié)點(diǎn)度

為n,直徑也為n

722循環(huán)互連網(wǎng)絡(luò)

一般靜態(tài)互連網(wǎng)不能實(shí)現(xiàn)任意兩結(jié)點(diǎn)之間

的互連。有兩種解決辦法：

循環(huán)互連網(wǎng)：多次重復(fù)使用同一個(gè)

單級(jí)互連網(wǎng)絡(luò)

多級(jí)互連網(wǎng)：將多套相同的單級(jí)互

連網(wǎng)絡(luò)連接起來

前一種方法是犧牲時(shí)間換取設(shè)備，

后一種方法是以設(shè)備換取時(shí)間

RN為網(wǎng)絡(luò)連接寄存器，它有三個(gè)用處：I

發(fā)送消息，接收消息，轉(zhuǎn)發(fā)消息

例如：對(duì)于一個(gè)3維立方體網(wǎng)，如果要從

PEO發(fā)送消息到PE3,需要經(jīng)過如下4步:

時(shí)鐘周期1：PEOfRNO

時(shí)鐘周期2：RNOfRN1

時(shí)鐘周期3：RN1-RN3

時(shí)鐘周期4：RN3-PE3

單級(jí)互連網(wǎng)

723多級(jí)互連網(wǎng)絡(luò)

能夠?qū)崿F(xiàn)結(jié)點(diǎn)到結(jié)點(diǎn)之間的任意互連是互

連網(wǎng)絡(luò)的一種基本功能。循環(huán)互連網(wǎng)絡(luò)

雖然能夠?qū)崿F(xiàn)結(jié)點(diǎn)到結(jié)點(diǎn)之間的任意互

連，但是，其通信速度低。

多級(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)的不同控制方式

1、交換開關(guān)

一個(gè)aXb交換開關(guān)有a個(gè)輸入和b個(gè)輸出。

最常用的二元開關(guān)：a=b=2o

每個(gè)輸入可與一個(gè)或多個(gè)輸出相連，但是

在輸出端必須避免發(fā)生沖突。一對(duì)一和

一對(duì)多映射是容許的；但不容許有多對(duì)

一映射。

只容許一對(duì)一映射時(shí)稱為置換連接，稱這

種開關(guān)為nXn交叉開關(guān)。

具有直通和交換兩種功能的交換開關(guān)稱為二

功能開關(guān)，或交換開關(guān)。用一位控制信號(hào)

控制。

具有所有四種功能的交換開關(guān)稱為四功能開

關(guān)，用兩位控制信號(hào)控制。

直通交換上播下播

交換開關(guān)和合法狀態(tài)

模塊大小合法狀態(tài)交換連接

2x242

4><425624

8x81677721640320

nxnnnn!

2、拓?fù)浣Y(jié)構(gòu)

前一級(jí)交換開關(guān)的輸出端與后一級(jí)交換開關(guān)

的輸入端之間的連接模式稱為拓?fù)浣Y(jié)構(gòu)。

通常采用前面介紹的互連函數(shù)實(shí)現(xiàn)拓?fù)浣Y(jié)構(gòu)

實(shí)際上，從結(jié)點(diǎn)的輸出到第一級(jí)交換開關(guān)的

輸入，以及從最后一級(jí)交換開關(guān)的輸出到

結(jié)點(diǎn)的輸入也可以采用拓?fù)浣Y(jié)構(gòu)連接。

3、控制方式

在多級(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)控制(0ViVn-1)。

同一個(gè)多級(jí)互連網(wǎng)絡(luò)分別常用三種不同的控

制方式，可以構(gòu)成三種不同的互連網(wǎng)絡(luò)。

4、多級(jí)立方體網(wǎng)

采用二功能開關(guān)，總共需要開關(guān)n2n-l個(gè)。

采用交換函數(shù)構(gòu)成拓?fù)浣Y(jié)構(gòu)，各級(jí)分別采用

E(p???E-交換函數(shù)。

當(dāng)所有開關(guān)都直通時(shí)，實(shí)現(xiàn)恒等變換。

當(dāng)A、B、C、D四個(gè)開關(guān)交換，其余直通

時(shí)實(shí)現(xiàn)Eo互連函數(shù)。

當(dāng)E、F、G、H四個(gè)開關(guān)交換，其余直通

時(shí)實(shí)現(xiàn)Ei互連函數(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)。

7654321。

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

（第25講）

第七章互連網(wǎng)絡(luò)

本章主要內(nèi)容：并行處理機(jī)和

多處理機(jī)系統(tǒng)中的互連網(wǎng)絡(luò)

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

7.2互連網(wǎng)絡(luò)的種類

7.3消息傳遞機(jī)制

7.3消息傳遞機(jī)制

研究各種尋徑方法，并分析它們的通信時(shí)

延問題

7.3.1消息尋徑方式

四種尋徑方式：線路交換，存儲(chǔ)轉(zhuǎn)發(fā)、虛

擬直通和蟲蝕尋徑等。

1、線路交換(circuitswitch)

先建立一條從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通

路，然后再傳遞消息。傳輸時(shí)延公式：

T=(Lt/B)xD+L/B,

其中：Lt為建立路徑所需小信息包的長(zhǎng)度

L為信息包的長(zhǎng)度，D為經(jīng)過的結(jié)點(diǎn)數(shù)，

B為帶寬。

優(yōu)點(diǎn)：實(shí)際通信時(shí)間較短，使用緩沖區(qū)少。

缺點(diǎn)：建立源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通路

開銷很大，占用物理通路的時(shí)間長(zhǎng)。

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í)延公式：

7.3消息傳遞機(jī)制

研究各種尋徑方法，并分析它們的通信時(shí)

延問題

7.3.1消息尋徑方式

四種尋徑方式：線路交換，存儲(chǔ)轉(zhuǎn)發(fā)、虛

擬直通和蟲蝕尋徑等。

1、線路交換(circuitswitch)

先建立一條從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通

路，然后再傳遞消息。傳輸時(shí)延公式：

T=(Lt/B)xD+L/B,

其中：Lt為建立路徑所需小信息包的長(zhǎng)度

L為信息包的長(zhǎng)度，D為經(jīng)過的結(jié)點(diǎn)數(shù)，

B為帶寬。

優(yōu)點(diǎn)：實(shí)際通信時(shí)間較短，使用緩沖區(qū)少。

缺點(diǎn)：建立源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通路

開銷很大，占用物理通路的時(shí)間長(zhǎng)。

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)xD+L/B=(D+1)xL/B

優(yōu)點(diǎn)：占用物理通路的時(shí)間比較短。

缺點(diǎn)：包緩沖區(qū)大，時(shí)延大(與結(jié)點(diǎn)距離I

成正比)。

3、虛擬直通(virtualcutthrough)

當(dāng)接收到用作尋徑的消息頭部時(shí)，即開始|

路由選擇。通信時(shí)延公式：

T=(Lh/B)xD+