高级体系结构-4.ppt

《高级体系结构-4.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、高性能计算机系统结构计算机科学与技术系研究生课程第四章互连与通信4.1互连网络的作用4.2静态网络4.3动态网络4.4通信问题4.1互连网络的作用定义：由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。操作方式：同步通信（SynchronousCommunication)异步通信(AsynchronousCommunication)控制策略：集中控制(Centralizedcontrol)分布控制(Distributedcontrol)交换方式：电路交

2、换(Circuitswitching)分组交换(Packetswitching)Wormhole交换(Wormholeswitching)网络拓扑结构：静态网络(Staticnetwork)动态网络(Dynamicnetwork)第四章互连与通信4.1互连网络的作用4.2静态网络4.2.1静态网络的特点与指标4.2.2典型的静态网络4.3动态网络4.4通信问题4.2静态网络4.2.1静态网络的特点与指标1.静态网络的特点静态网络由点—点直接相连而成，这种连结方式在程序执行过程中不会改变。如果用图来表示，

3、结点代表开关，边代表通信链路，则(1)结点间的链路无源，不能重构(2)开关元件与处理机相连(3)不直接相连结点间的通信需通过中间结点中转。2.静态网络的指标结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为：结点度=入度+出度其中入度是进入结点的通道数，出度是从结点出来的通道数。距离：与两个结点之间相连的最少边数。网络直径：网络中任意两个结点间距离的最大值。网络规模：网络中结点数，表示该网络功能连结部件的多少。等

4、分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。结点间的线长：两个结点间的线的长度。对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。结点是否同构。通道是否有缓冲。4.2.2典型的静态网络1.线性阵列对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1。N很大时，通信效率很低。线性阵列与总线的区别：线性阵列：允许不同的源结点和目的结点对并发使用系统的不同部分。总线：通过切换与其相连的许多结点来实现时分特性，

5、同一时刻只有一对结点在传送数据。2.环对N个结点的环，考虑相邻结点数据传送方向：双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。比如KSR-1（1990）。单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。3.带弦环对上图中12个结点的带弦双向环，结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。度为3的带弦环度为4的带弦环4.全链接全链接是带弦环的一种特殊情形。全链接中

6、的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的全链接：有28条链路，直径为1，度为7，对称，等分宽度为16。5.树形4层的二叉树一棵K层完全二叉树应有N=2K-1个结点，大多数结点的结点度为3，直径为2（K-1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1。由于结点度为常数，所以树是一种可扩展的系统结构。树形的扩展：带环树二叉胖树这两种结构都可以缓解根结点的瓶颈问题。6.星形星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N-1条链路，直径为2，最大结点

7、度为N-1，非对称，等分宽度为1。7.网格有N个结点的rr网格（其中)，有2N-2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。网格的变形：a.Illiac网有N个结点的rr网格（其中)，有2N条链路，直径为r-1，结点度为4。b.环形网（2D—Torus）有N个结点的rr网（其中)，有2N条链路，直径为2r/2，结点度为4，对称。c.搏动式阵列（SystolicArray）8.超立方体0-立方体1-立方体2-立方体3-立方体4-立方体一个n-立方体由N=2n个结点构成，它们

8、分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。例子：Intel的iPSC/1、iPSC/2、nCUBE9.带环立方体一个带环n-立方体由N=2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n2n个。直径通常为2n，结点度为3，对称。带环3-立方体10.k元n-立方体网络4元3-立方体（隐藏的结点与连接没有画出)在一个k元n-立方体网络中，结点的数目N=kn