第七章 互连网络

  (6)网格形和环网形 图7.15a所示为一个3×3网格形网络。这是一种比较流行的结构,它已以各种变体形式在Illiac IV、MPP、DAP、CM-2和Inetl Paragon中得到了实现。
  一般说来,结点的k维网格的内部结点度为2k,网格直径为k(n-1)。必须指出,图7.15a所示的纯网格形不是对称的。边结点和角结点的结点度为3或2。
  图7.15b画出了一种可回绕连接的网格图。假定Illiac IV系统采用8×8的这种Illiac网格,则其结点度为常数4,直径为7。N=16=4×4构型的Illiac网格与图7.13所示的结点度为4的带弦环在拓扑上是等效的。
  一般说来,一个n×n Illiac 网格的直径应为d=n-1,它仅为纯网格直径的一半。图7.15所示的环网形可看做是另一种直径更短的网格。这种拓扑结构将环形和网格组合在一起,并能向高维扩展。
  环网形沿阵列每行每列都有环形连接。一般说来,一个n×n二元环网的结点度为4,直径为2?n/2?。环网是一种对称的拓扑结构,所有附加的回绕连接可使其直径较之网格结构减少二分之一。

  (7)搏动式阵列 这是一类为实现确定算法而设计的多维流水线阵列结构。图7.15d所示就是为完成矩阵-矩阵相乘而专门设计的搏动式阵列。此例的内部结点度为6。
  一般说来,静态搏动式阵列可在多个方向上使数据流变成以流水线方式工作。商用Intel iWarp系统就是用搏动式结构设计而成的。自从1978年Kung和Leiserson提出搏动式阵列后,它已成为广泛研究的领域。
  通过确定的互连和同步操作,搏动式阵列可与算法的通信结构相匹配。对信号/图象处理等特殊应用,搏动式阵列可提供更好的性能/价格比。但是,其结构的实用性有限,而且编制程序也很难。