计算机系统结构 互连与通信课件

ComputerArchitecture,Spring2008

TsinghuaUniversity

互连与通信

(InterconnectionandCommunication)

汪东升(Prof.DongshengWang)

wds@

互连与通信

互连网络的作用

静态网络

动态网络

通信问题

ComputerArchitecture,Spring2008

4手次孽

互连网络的作用TsinghuaUniversity

定义：由开关元件按一定拓扑结构和控制方式构成的网络以

实现计算机系统内部多个处理机或多个功能部件间的相互

连接。

操作方式：

同步通信(SynchronoysCommunication)

异步通信(AsynchronousCommunication)

控制策略：

集中控制(Centralizedcontrol)

分布控制(Distributedcontrol)

ComputerArchitecture,Spring2008

浦多义学

交换方式:

电路交换(Circuitswitching)

分组交换(Packetswitching)

Wormhole交换(Wormholeswitching)

网络拓扑结构：

静态网络(Staticnetwork)

动态网络(Dynamicnetwork)

ComputerArchitecture,Spring2008

浦多义学

互连与通信

互连网络的作用

静态网络

静态网络的特点与指标

典型的静态网络

动态网络

通信问题

ComputerArchitecture,Spring2008

浦多义学

静态网络

静态网络的特点与指标

1.静态网络的特点

静态网络由点一点直接相连而成，这种连结方式在程序

执行过程中不会改变。

如果用图来表示，结点代表开关，边代表通信链路，则

(1)结点间的链路无源，不能重构

(2)开关元件与处理机相连

(3)不直接相连结点间的通信需通过中间结点中转。

ComputerArchitecture,Spring2008

TsinghuaUniversity

2.静态网络的指标

结点度：与结点相连接的边（链路或通道）数，表示节

点所需要的I/O端口数，模块化要求结点度保持恒定。根据

通道到结点的方向，结点度可以进一步表示为：

结点度=入度+出度

其中入度是进入结点的通道数，出度是从结点出来的通道

数。

距离：与两个结点之间相连的最少边数。

网络直径：网络中任意两个结点间距离的最大值。

ComputerArchitecture,Spring2008

浦多义学

网络规模：网络中结点数，表示该网络功能连结部件的

多少。

等分宽度：某一网络被切成相等的两半时，沿切口的最

小边数称为该网络的等分宽度。

结点间的线长：两个结点间的线的长度。

对称性：从任何结点看，拓扑结构都一样，这种网络实

现和编程都很容易。

结点是否同构。

通道是否有缓冲。

ComputerArchitecture,Spring2008

浦多又承

典型的静态网络TsinghuaUniversity

1.线性阵列

。。。。。。。

对N个结点的线性阵列，有N・1条链路，直径为N・1（任

意两点之间距离的最大值），度为2,不对称，等分宽度为

1o

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

ComputerArchitecture,Spring2008

TsinghuaUniversity

线性阵列与总线的区别：

线性阵列：允许不同的源结点和目的结点对并发使用系

统的不同部分。

总线：通过切换与其相连的许多结点来实现时分特性，

同一时刻只有一对结点在传送数据。

ComputerArchitecture,Spring2008

浦多义学

2,环

对N个结点的环，考虑相邻结点数据传送方向:

双向环：链路数为N,直径［N/2」，度为2,

宽度为2。

单向环：链路数为N,直径N・1,度为2,

度为2。

ComputerArchitecture,Spring2008

3,带弦环

对上图中12个结点的带弦双向环，

结点度为3：链路数为18,直径4（比如红色结点），度

为3,不对称，等分宽度为2。

结点度为4：链路数为24,直径3（比如红色结点），度

为4,对称，等分宽度为8。

ComputerArchitecture,Spring2008

4.链接TsinghuaUniversity

链接是带弦环的一种特殊情形。链接中的每个结点和其

他结点之间都有单一的直接链路。如下图中8个结点的链接:

有28条链路，直径为1,度为7,对称，等分宽度为16。

ComputerArchitecture,Spring2008

一棵K层完全二叉树应有N=2K■1个结点，对大结点度

为3,直径为2(K-1)(即右边任意一个叶子结点到左边

任意一个叶子结点)。不对称，等分度为1。

由于结点度为常数，所以树是一种可扩展的系统结构。

ComputerArchitecture,Spring2008

这两种结构都可以缓解根结点的瓶颈问题。

ComputerArchitecture,Spring2008

星形实际上是一种二层树（如右图）。有N个结点的星形

网络，有N・1条链路，直径为2,最大结点度为N・1,非对

称，等分宽度为1。

ComputerArchitecture,Spring2008

彳又学

三一

W

7网一

有N个结点的rxr网(其中r=，⑺，有2N・2r条链路，直

径为2(r-1),结点度为4,非对称，等分宽度为r。

ComputerArchitecture,Spring2008

有N个结点的rxr网（其中r=VF）,有2N条链路，直径

为r・1,结点度为4。

ComputerArchitecture,Spring2008

b.环形网（2D—Torus）TsinghuaUniversity

_____

有N个结点的rxr网（其中r=有2N条链路，直

径为2匕/2」，结点度为4,对称。

ComputerArchitecture,Spring2008

TsinghuaUniversity

c.搏动式阵列(SystolicArray)

ComputerArchitecture,Spring2008

8.超立方体TsinghuaUniversity

oO

0-立方体1-立方体2-立方体

3-立方体

4-立方体

ComputerArchitecture,Spring2008

TsinghuaUniversity

一个n■立方体由N=211个结点构成，它们分布在n维上，

每维有两个结点。直径为n,结点度为n,对称。由于结点度

随维数线性增加，所以超立方体不是一种可扩展结构。

例子：

Intel的iPSC/1、iPSC/2、nCUBE

ComputerArchitecture,Spring2008

9,带环立方体

带环3-立方体

一个带环n■立方体由N=20个结点环构成，每个结点环是

一个有n个结点的环，所以结点总数为n2n个。直径通常为

2n,结点度为3,对称。

ComputerArchitecture,Spring2008

包头立方色《隐藏的结点与连接没有画出）

ComputerArchitecture,Spring2008

在一个k元n■立方体网络中，结点的数目N

k:\lN.

"=log左N

其中，k称为基数(radix),n称为维数

(dimension)。

k元n■立方体的结点可以用基数为k的n位地址A=a0

a〔a2…a”来表示，其中可代表第i维结点的位置。

ComputerArchitecture,Spring2008

传统的环网等价于4元2■立方体o

ComputerArchitecture,Spring2008

互连与通信

互连网络的作用

静态网络

动态网络

互连函数

多级互联网络

通信问题

ComputerArchitecture,Spring2008

TsinghuaUniversity

动态网络

特点：

网络的开关元件有源，链路可通过设置这些开关的状

态来重构。

只有在网络边界上的开关元件才能与处理机相连。

ComputerArchitecture,Spring2008

TsinghuaUniversity

互连函数

排列：N个数的每一种有确定次序的放置方法叫做一个N

排列。

置换：把一个N排列变成另一个N排列的变换叫做N阶置

换。

在有N个输入端和N个输出端的网络中，输入端和输出端

的连接关系可以用置换来表示（输入端与输出端一一对

应）。

一些常见的置换方式可以用下面的函数表示：

ComputerArchitecture,Spring2008

1,恒等函数TsinghuaUniversity

fe(XnjXn_2…乂卜…Xo)=(X42…Xk…X。)

其中，Xn“Xn2..Xk…X。是PE的地址（通常为二进制）。n为3时的恒等

函数的连接情形如下：

ComputerArchitecture,Spring2008

2.方体函数(cube0,cubevcube^)国TsinghuaUniversity

・

cubek(X,—XT・X…X。)=(X〃TX〃_2・♦X…X。)

方体函数是由n个互连函数组成，其中04k〈n。

比如，n为3时，3■立方体各结点地址如下：

Y

ComputerArchitecture,Spring2008

n

s

>B」

nu

B

ln

6!

E£

or-HOIoH

oII。HH

oOOIHHH

o

o

q

n

。

800C6u-」ds-9」nlo①l-llo」<-2ndEO。

0

寸

S

二一

一一

0二0

12

一2

。

。22

10

二0

2005

3000

000000

3

(OXIXexT(ox_x<)wq

>

:6qn。

Il­III

oi­oil

§lo-101

。2

10

二。

0303

soso

000000

(0x_xzxT(0x-x<>)sqN。

ns」B>un

:e)oqn。

3.洗牌函数TsinghuaUniversity

S"X,LK_2…X「・X0)=(XQ

o

ooo00

01234567

ComputerArchitecture,Spring2008

洗牌函数的变形:

a.均匀洗牌(Shuffle-Exchange)

是洗牌函数与Cube。函数的组合。

：洗牌：Cube()

ComputerArchitecture,Spring2008

学

浦

多

义

b.第k个子洗牌

S似・・"X".・・X0)=(X〃―・・—・・.X°XI

即最低k位循环左移一位。

c.第k个超洗牌

S吹XuXn-2.。'-^-n-k+l-^n-k…X0)=(XQ"'^n-k+l^n-l-^n-k•••X。)

即最高k・1位循环左移一位。

ComputerArchitecture,Spring2008

n

s

>B」

nu

(

"

：

？

X

O

X

T

(

O

X

I

X

…

?

x

T

q

s

"多义学

5.蝶式TsinghuaUniversity

-X〃TZ_2…X]Xo)=(X°X

000-0--0--0----------------------------

6.PM2I函数（加减Z）TsinghuaUniversity

共有2n个互连函数，对N个结点的网络为

<PM2£j）=j+2'modN

|PM2_Z.（J）=j