計算機系統結構

（第23講）

計算機系統結構

第一章基本概念第六章向量處理機

第二章指令系統第七章互連網絡

第三章存儲系統第八章并行處理機和

第四章輸入輸出系統多處理機

第五章標量處理機

第七章互連網絡

本章主要內容：并行處理機和

多處理機系統中的互連網絡

7.1互連網絡的基本概念

7.2互連網絡的種類

7.3消息傳遞機制

7.4互連網絡實例

7.1互連網絡的基本概念

7.1.1互連網絡的作用

7.1.2互連網絡的特性■

7.1.3互連網絡的性能參數

7.1.4互連網絡的表示方法

7.1.1互連網絡的作用

用來實現計算機系統內部多個處理機或

多個功能部件之間的相互連接。

互連網絡已成為并行處理系統的核心組

成部分。

互連網絡對整個計算機系統的性能價格

比有著決定性的影響。

具有本地存儲器、私有高速緩存、共

享存儲器和共享外圍設備的一般處理

機系統的互連結構

IPCN

計算機系統結構

（第24講）

7.L2互連網絡的特性

互連網絡通常是用有向邊或無向邊連接有

限個結點的組成。

互連網絡的主要特性有：

(1)網絡規模：網絡中結點的個數

(2)結點度：與結點相連接的邊數稱為結

點度。包括入度和出度。進入結點的邊

數叫入度，從結點出來的邊數則叫出度

(3)距離：兩個結點之間相連的最少邊數

(4)網絡直徑：網絡中任意兩個結點間距

離的最大值。用結點間的連接邊數表示

⑸結點間的線長：兩個結點間連線的長

度。用米、公里等表示

(6)對稱］：從任何結點看到拓撲結構都

是一樣的網絡稱為對稱網絡。對稱網絡

比較易實現，編程也較容易。

7.1.3互連網絡的性能參數

一臺機器發送消息給另一臺機器時，發送

方的步驟如下：

(1)用戶程序把要發送的數據拷貝到操作

系統的緩沖區。

(2)操作系統把緩沖區中的數據打包，并

發送的網絡接口部件。

(3)網絡接口硬件開始發送消息。

數據包的接收步驟如下：

(1)把數據包從網絡接口部件拷貝到操作

系統緩沖區。

(2)檢查收到的數據包，如果正確，給接

收方發回答信號。

(3)把接收到的數據拷貝到用戶地址空間。

發送方接收到回答信號后，釋放系統緩

沖區

互連網絡在傳輸方面的主要性能參數：

(1)頻帶寬度(Bandwidth)：互連網絡傳輸

信息的最大速率。

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

息長度除以頻寬。

(3)飛行時間(Timeofflight)：第一位信

息到達接收方所花費的時間。

(4)傳輸時延(Transportlatency)：等于

飛行時間與傳輸時間之和。

(5)發送方開銷(Senderoverhead)：處理

器才融肖息放到互連網絡的時間。

(6)接收方開銷(Receiveroverhead)：處

理器把消息從網絡取出來的時間。

一個消息的總時延可以用下面公式表示：

總時延=發送方開銷+飛行時間+

消息長度/頻寬+接收方開銷

例7.1:

假設一個網絡的頻寬為10Mb/S,發送

方開銷為230us,接收方開銷為270us。

如果兩臺機器相距100米，現在要發送

一個1000字節的消息給另一臺機器，試

計算總時延。如果兩臺機器相距1000公

里，那么總時延為多大？

解：I

光的速度為299792.5KM/S,信號在導

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

100米時總時延為：

消息長度

T=發送方開銷+飛行時間+頻寬+接收方開銷

0.1Km1000x8位

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

0.5x299792.5Km/s10兆位/秒

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

相距1000公里時的總時延為:

1000X1061000X8

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

0.5x299792.510

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

7.1.4互連網絡的表示方法

為了在輸入結點與輸出結點之間建立對應關

系，互連網絡有三種表示方法：

(1)互連函數表示法：

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

自變量和函數可以用二進制表示，

也可以用十進制等表示

(2)圖形表示法(3)輸入輸出對應表示法

0—d—k0

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

：網絡：輸出：10325476

n-1——n-1

第七章互連網絡

本章主要內容：并行處理機和

多處理機系統中的互連網絡

7.1互連網絡的基本概念

7.2互連網絡的種類

7.3消息傳遞機制

7.4互連網絡實例

7.2互連網絡的種類

721靜態互連網絡

722循環互連網絡

723多級互連網絡

7.2互連網絡的種類

互連網絡的種類很多，分類方法也很多

以互連特性為特征，可分為如下幾類：

靜態互連網絡：連接通路是固定的，一

般靜態互連網絡不能實現任意結點到結

點之間的互連。

循環互連網絡：通過多次重復使用同一

個單級互連網絡以實現任意結點到結點

之間的互連。

多級互連網絡：將多套相同的單級互連

網絡連接起來，實現任意結點到結點之

間的互連。

全排列互連網絡：不僅能夠實現任意結

點到結點之間的互連，而且能夠同時實

現任意結點到結點之間的互連。

全交叉開關網絡：除了能夠同時實現任

意結點到結點之間的互連之外，還能夠

實現廣播和多播。

721靜態互連網絡

在各結點之間有固定的連接通路，在運行

過程中不能改變的網絡結構。

一維的有線性陣列結構；二維的有環形、

星形、樹形、網格形等；三維的有立方

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

1、環形網

采用移數函數。使用不同的移數函數，可

以構成多種環形網。一

單向環行四：右環網，采用PM2+0函數。

左環網，采用PM2-0函數。

雙向環行網：又稱為一維鄰居網，采用

{PM2+o,PM2.。}函數。

環行網是對稱的，結點度是常數2。雙向環

網的直徑為N/2,單向環形網的直徑是N

如果將結點度由2提高至3,可得到弦環網。

增加的弦愈多，則結點度愈高，網絡直

徑愈小。

循環移數網絡也是一種環形網，它將環上

每個結點與其距離為2的整數幕的結點之

間連接構成。循環移數網的結點度為2n-

1,直徑為「n/21。

2、樹形和星形網

一棵k層二叉樹有N=2k—1個結點，結點

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

星形是一種特殊的2層樹，結點度很高，］

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

二叉胖樹的結點度從葉子結點往根結點

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

結點通信速度高的矛盾。

3、網格形網

是一種比較流行的網絡結構，有各種變I

體形式。在IlliacIV、MPP、DAP、

CM-2和InetlParagon中得到了實現。

一般網格網，N=nk結點的k維網格的結

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

環網形網格網沿陣列每行每列都有環形

連接。一個nXn二元環網的結點度為4,

直徑為2?n/2?。環網是一種對稱的拓撲

結構。

IlliacIV的8X8Illiac網格,其結點度為4,

直徑為7。一個nXnllliac網格的直徑為

d=n-1,為純網格直徑的一半。

4、超立方體網

n維立方體由N=2n

個結點,分布在n

維上,每維有兩

個結點

超立方體網采用交

換函數，結點度

為n,直徑也為n

722循環互連網絡

一般靜態互連網不能實現任意兩結點之間

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

循環互連網：多次重復使用同一個

單級互連網絡

多級互連網：將多套相同的單級互

連網絡連接起來

前一種方法是犧牲時間換取設備，

后一種方法是以設備換取時間

RN為網絡連接寄存器，它有三個用處：I

發送消息，接收消息，轉發消息

例如：對于一個3維立方體網，如果要從

PEO發送消息到PE3,需要經過如下4步:

時鐘周期1：PEOfRNO

時鐘周期2：RNOfRN1

時鐘周期3：RN1-RN3

時鐘周期4：RN3-PE3

單級互連網

723多級互連網絡

能夠實現結點到結點之間的任意互連是互

連網絡的一種基本功能。循環互連網絡

雖然能夠實現結點到結點之間的任意互

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

多級互連網絡采用多個相同的或不同的互

連網絡直接連接起來。屬于組合邏輯線

路，一個時鐘周期就能夠實現任意結點

到結點之間的互連。

多級互連網絡采用的關鍵技術：

（1）交換開關

(2)交換開關之間的拓撲連接

(3)對交換開關的不同控制方式

1、交換開關

一個aXb交換開關有a個輸入和b個輸出。

最常用的二元開關：a=b=2o

每個輸入可與一個或多個輸出相連，但是

在輸出端必須避免發生沖突。一對一和

一對多映射是容許的；但不容許有多對

一映射。

只容許一對一映射時稱為置換連接，稱這

種開關為nXn交叉開關。

具有直通和交換兩種功能的交換開關稱為二

功能開關，或交換開關。用一位控制信號

控制。

具有所有四種功能的交換開關稱為四功能開

關，用兩位控制信號控制。

直通交換上播下播

交換開關和合法狀態

模塊大小合法狀態交換連接

2x242

4><425624

8x81677721640320

nxnnnn!

2、拓撲結構

前一級交換開關的輸出端與后一級交換開關

的輸入端之間的連接模式稱為拓撲結構。

通常采用前面介紹的互連函數實現拓撲結構

實際上，從結點的輸出到第一級交換開關的

輸入，以及從最后一級交換開關的輸出到

結點的輸入也可以采用拓撲結構連接。

3、控制方式

在多級互連網絡中有多級交換開關，每一級

又有多個交換開關。通常有三種控制方式

(1)級控制：同一級交換開關使用同一個控

制信號控制。

(2)%?元級控制：每個交換開關分別控制。

(3)部分級控制:例如,第i級使用i+1個控

制信號控制(0ViVn-1)。

同一個多級互連網絡分別常用三種不同的控

制方式，可以構成三種不同的互連網絡。

4、多級立方體網

采用二功能開關，總共需要開關n2n-l個。

采用交換函數構成拓撲結構，各級分別采用

E(p???E-交換函數。

當所有開關都直通時，實現恒等變換。

當A、B、C、D四個開關交換，其余直通

時實現Eo互連函數。

當E、F、G、H四個開關交換，其余直通

時實現Ei互連函數。

當I、J、K、L四個開關交換，其余直

通時實現E2互連函數。

采用三種不同的控制方式，可以構成三種不

同的互連網絡。

采用級控制可以構成STARAN交換網。

采用部分級控制，可以構成STARAN

移數網。

采用單元控制可以構成間接二進制n方

體網。

7654321。

計算機系統結構

（第25講）

第七章互連網絡

本章主要內容：并行處理機和

多處理機系統中的互連網絡

7.1互連網絡的基本概念

7.2互連網絡的種類

7.3消息傳遞機制

7.3消息傳遞機制

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

延問題

7.3.1消息尋徑方式

四種尋徑方式：線路交換，存儲轉發、虛

擬直通和蟲蝕尋徑等。

1、線路交換(circuitswitch)

先建立一條從源結點到目的結點的物理通

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

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

其中：Lt為建立路徑所需小信息包的長度

L為信息包的長度，D為經過的結點數，

B為帶寬。

優點：實際通信時間較短，使用緩沖區少。

缺點：建立源結點到目的結點的物理通路

開銷很大，占用物理通路的時間長。

2、存儲轉發(storeandforward)

每個結點有一個包緩沖區，包從源結點經

過中間結點到達目的結點。

存儲轉發網絡的時延與源和目的地之間的

距離成正比。傳輸時延公式：

7.3消息傳遞機制

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

延問題

7.3.1消息尋徑方式

四種尋徑方式：線路交換，存儲轉發、虛

擬直通和蟲蝕尋徑等。

1、線路交換(circuitswitch)

先建立一條從源結點到目的結點的物理通

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

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

其中：Lt為建立路徑所需小信息包的長度

L為信息包的長度，D為經過的結點數，

B為帶寬。

優點：實際通信時間較短，使用緩沖區少。

缺點：建立源結點到目的結點的物理通路

開銷很大，占用物理通路的時間長。

2、存儲轉發(storeandforward)

每個結點有一個包緩沖區，包從源結點經

過中間結點到達目的結點。

存儲轉發網絡的時延與源和目的地之間的

距離成正比。傳輸時延公式：

T=(L/B)xD+L/B=(D+1)xL/B

優點：占用物理通路的時間比較短。

缺點：包緩沖區大，時延大(與結點距離I

成正比)。

3、虛擬直通(virtualcutthrough)

當接收到用作尋徑的消息頭部時，即開始|

路由選擇。通信時延公式：

T=(Lh/B)xD+