互联网络培训教程[2]

互联网络培训教程[2]

 5.广播和选播

    广播是一种一对全体的映射，选播是一个子集到另一子集(多对多)的映射。消息传递型多处理机一般有广播信息机构，广播常常作为多处理机中的全局操作来处理。通过上面的讨论，我们可概括出影响互连网络性能的因素为：

    (1) 功能特性——网络如何支持路由、中断处理、同步、请求/消息组合和一致性。

    (2) 网络时延——单位消息通过网络传送时最坏情况下的时间延迟。

    (3) 带宽——通过网络的最大数据传输率，用MB/s表示。

    (4) 硬件复杂性——诸如导线、开关、连接器、仲裁和接口逻辑等的造价。

    (5) 可扩展性——在增加机器资源使性能可扩展的情况下，网络具备模块化可扩展的能力。

    6.3.2静态连接网络

    静态网络使用直接链路，它一旦构成后就固定不变。这种网络比较适合于构造通信模式可预测或可用静态连接实现的计算机系统。 下面介绍几种静态网络的拓扑结构、网络参数及其可扩展性。

 1.线性阵列(linear array)

　　这是一种一维的线性网络，其中N个结点用N-1个链路连成一行(图6.3.7)。内部结点度为2，端结点度为1。直径为N-1，N较大时，直径就比较长。等分宽度为1。线性阵列是连接最简单的拓扑结构。这种结构不对称，当N很大时，通信效率很低。

    在N很小的情况下，使用线性阵列是相当经济和合理的。由于直径随N线性增大，因此当N比较大时，就不应使用这种方案了。

 2. 环和带弦环(chordal ring)

    环是用一条附加链路将线性阵列的两个端点连接起来而构成的(图6.3.8)。环可以单向工作，也可以双向工作。它是对称的，结点度是常数2。双向环的直径为N/2，单向环的直径是N。

    如果将结点度由2提高至3或4，即可得到如图6.3.9所示的两种带弦环。增加的链路愈多，结点度愈高，网络直径就愈小。16个结点的环(图6.3.8)与两个带弦环(图6.3.9)相比，网络直径分别由8减至5和3。在极端情况下，图6.3.10 的全连接网络(completely connected network)的结点度为15，直径最短，为1。

    3. 循环移数网络(barrel shifter)

    图6.3.11所示的是一个循环移数网络，其结点数N=16，它是通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成的。这就是说,如果｜j-i｜=2r，r=0,1,2,…,n-1，网络规模N=2n，则结点i与结点j连接。这种循环移数网络的结点度为d=2n-1，直径D=n/2。

4. 树形和星形(tree and star)

    一棵5层31个结点的二叉树如图6.3.12所示

    一般说来，一棵k层完全平衡的二叉树有N=2k-1个结点。最大结点度是3，直径是2(k-1)。由于结点度是常数，因此二叉树是一种可扩展的结构，但其直径较长。哥伦比亚大学于1987年研制成的DADO多处理机即采用10层二叉树形式，有1023个结点。星形是一种2层树，结点度较高，为d=N-1(图6.3.13)。直径较小，是一常数2。星形结构一般用于有集中监督结点的系统中。

5. 胖树形

    1985年Leiserson提出将计算机科学中所用的一般树结构修改为胖树形(fat tree)。叉胖树结构如图6.3.14所示，胖树的通道宽度从叶结点往根结点上行方向逐渐增宽，它更像真实的树，愈靠近树根的枝叉愈粗。

    使用传统二叉树的主要问题之一就是通向根结点的瓶颈问题，这是因为根部的交通最忙。胖树的提出使该问题得到了缓解。

    6. 网格形和环网形

    图6.3.15为一个3×3网格形网络。这是一种比较流行的结构，它已经以各种变体形式在CM-2和Intel Paragon等机器中得到了实现。

一般说来，N=nk 个结点的k维网络的内部结点度为2k ，网络直径为k(n-1)。必须指出，图6.3.15所示的纯网络形不是对称的。边结点和角结点的结点度分别为3或2。

    图6.3.16所示的环形网可看做是直径更短的另一种网格。这种拓扑结构将环形和网格组合在一起，并能向高维扩展。环形网沿阵列每行和每列都有环形连接。一般说来，一个n×n二元环网的结点度为4，直径为2*[n/2]。

    环网是一种对称的拓扑结构，所有附加的回绕连接可使其直径比网格结构减少二分之一。