第八章 并行处理机和多处理机

  2.寻径器、NEWS网格和扫描机构
  (1)寻径器 每个处理器芯片包含一个用于处理器之间数据寻径的专门硬件。把所有处理器芯片上的寻径器结点用线连在一起形成一个布尔n-立方体。在CM-2最大配置时,所有处理器芯片上共有4096个寻径器结点,连成一个12维的超立方体。
  每个寻径器结点与12个其它寻径器结点相连接,其中包括它的对偶结点在内(图8.9)。属于同一结点上的16个处理器在发送消息给12-立方体另一顶点上的任一处理器时具有相同的能力。下面说明这种消息传递的概念。
  例如12-立方体的每个顶点上的处理器编号为0到15。4096个顶点的超立方体的寻径器编号为0到4095。第7号寻径器结点上的第5号处理器在整个系统中的编号为117,因为16×7+5=117。
  假设处理器117要发送一个消息给处理器361。处理器361位于第22号结点的第9号处理器(16×22+9=361)。由于寻径器结点7=(0000000000111)2,寻径器结点22=(00000001010)2,这两个二进制编号在维0和维4不同。
  这一消息一定通过维0和维4到达它的目的结点。如果不存在争用超立方体连线现象,那么消息从寻径器结点7开始,首先沿维0方向传到寻径器结点6=(00000000110)2,然后再沿维4方向传到寻径器结点22。如果寻径器点7号的另一消息正在使用维0方向的连线,那么为了避免发生通道冲突。消息传送的路径可以改变为先沿维4方向传到寻径器结点23=(000000010111)2,然后再沿维0方向到达最终的目的结点。
  (2)NEWS网格 每个处理器芯片中的16个物理处理器可以排列成8×2,1×16,4×4,4×2×2或2×2×2×2等形式的网格。规定每个物理处理器有64个虚拟处理器。可以想象这64个虚拟处理器在芯片中排列成8×8网格。
  NEWS网格是建立在各种不同配置网格的每个处理器都有东、南、西、北四个邻居这一事实的基础上的。而且,可以选择一部分超立方体的连线把212个结点连成一个任意形状的二维网格,64×64是一种可能的网格形状。
  把每个结点的内部网格与全局网格结合在一起,就可以把处理器排列成任意维任何形状的NEWS网格。这些灵活的处理器间互连方式使得数据非常有效地沿着根据应用要求而建立的专门网格进行传递。
  (3)扫描机构 除了通过超立方体寻径器可以动态地重构NEWS网格外,CM-2还有专门的硬件支持对整个NEWS网格的扫描或传播。这些都是很有效的并行操作,在整个阵列中进行快速的数据组合和传播。
  对NEWS网格扫描是把通信和计算结合在一起。可以沿某一维方向同时对网格的每一行扫描,求出该行的部分和、找出最大值或最小值、进行按位或、与、异或计算。扫描操作可以扩展到对整个阵列的所有元素进行。
  传播能将一个数据传送给其它芯片上的处理器。一位二进制数只用75步就可以沿着超立方体连线从一个芯片送到所有其它芯片。为了便于访问,各种形式的扫描和传播操作已经设计在Pairs 指令中了。

  3. 输入输出系统
  Connection Machine不但强调计算的大规模并行性,还强调计算结果的可视化。2到16条高速I/O通道用于数据和/或图象I/O操作。连接到I/O通道的外围设备包括数据穹、CM-HIPPI系统、CM-IOP系统和VME总线接口控制器,如图8.11所示。数据穹是基于磁盘的海量存储系统,用来存放程序文件和大数据库。
  CM-2已经用于解决几乎所有MPP所面临的具有重大挑战性的应用问题。特别是Connection Machine系列已经用于借助相关反馈技术的文档检索、基于记忆的推理,如用在医疗诊断系统QUACK中摸拟诊断疾病以及处理工作量很大的自然语言等。CM-2的其它应用还包括SPICE的VLSI电路分析和布线、计算流体动力学、信号/图象/视觉处理和集成、神经网络模拟和连接模型、动态规划,上下文无关文法分析、射线追踪图以及计算几何等问题。