资源简介

(共210张PPT)
第10章 并行处理与互连网络
10.1 并行处理的概念
10.2 并行处理机基本结构
10.3 SIMD计算机基本结构
10.4 SIMD计算机的应用
10.5 互连网络的概念
10.6 静态互连网络
10.7 动态互连网络
10.8 互连网络的消息传递机制
关联
习题
10.1 并行处理的概念　
10.1.1 并行性
　　研究改进计算机系统结构的一个主要方面是如何开发出并行性。并行性(Parallelism)是指问题中具有可同时进行运算或操作的特性。如在同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的任务为并行性。开发并行性的目的是为了能予以并行处理，以提高解题效率。
　　并行性有两个含义：一是同时性(Simultaneity)，是指两个或多个事件在同一时刻发生在多个资源中；二是并发性(Concurrency)，指两个或多个事件在同一时间间隔内发生在多个资源中。
　　并行处理是一种有效地强调开发计算过程中并行事件的信息处理方式，是提高系统性能的主要手段之一。如在运算器中采用串行结构运算，每次进行一位运算，那么完成n位数据的运算要花费n个时间单位。如果采用并行结构，设置一个n位运算器，则用1个时间单位就可完成(理想状态下)。可以看出，在元器件速度相同的条件下，后者的速度几乎是前者的n倍。可见，并行处理能大幅度地提高计算机系统的运行速度。
10.1.2 并行性的等级和分类
　　从不同的角度看，并行性可分为不同的类型。
　　1．从计算机系统处理数据的角度
　　从计算机系统处理数据的角度看，并行性等级由低到高，分别是位串字串(串行单处理机，无并行性)、位并字串(传统并行单处理机)、位片串字并、全并行。
　　2．从计算机信息加工的各个步骤和阶段的角度
　　从计算机信息加工的各个步骤和阶段的角度看，并行性等级可分为如下四种：
　　1) 存储器操作并行性
　　存储器操作并行性是指可采用单体多字、多体交叉存取等方式，在一个存储周期内访问多个字。如并行存储器和相连处理机。
　　2) 处理器操作步骤并行
　　处理器操作步骤并行是指指令处理器在执行取指令、分析指令、执行指令等过程中的并行。如流水线处理机。
　　3) 处理器操作并行
　　处理器操作并行是指为支持向量、数组运算，可以通过重复设置处理单元进行。如阵列并行处理机。
　　4) 指令、任务、作业的并行
　　这种并行称为高级并行，指令级以上并行是指多个处理机同时对多条指令及有关的数据进行处理。如多指令流多数据流多处理机、分布处理系统和计算机网络等。
　　3．从计算机系统中执行程序的角度
　　从计算机系统中执行程序的角度看，并行性等级由低到高，分别是指令内各微操作之间的并行、多条指令之间的并行、多个任务或进程之间的并行和多个作业或程序之间的并行。
　　4．从系统结构发展的角度
　　从系统结构发展来看，并行性等级由低到高，分别是高性能的单处理机、SIMD并行处理机、多处理机和多计算机系统、冯·诺依曼计算机。
　　按照Flynn分类法归纳的并行计算机体系结构如图10-1所示。
图10-1 并行计算机的Flynn分类图
10.1.3 开发并行性的途径
　　可通过多种技术途径来提高计算机系统的并行性。通常以时间重叠、资源重复和资源共享为开发并行性的三个主要途径。
　　1．时间重叠(Time Interleaving)
　　时间重叠是在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度，如指令内部各操作步骤采用重叠流水的工作方式。一条指令的解释分为取指、分析、执行三大步骤，分别在相应的硬件上完成。只要不出现相关，则每过一个t时间，就可以流出结果，从而加快了程序的执行速度。这种时间重叠技术原则上不需要增加更多的硬件设备就可以提高计算机系统的性能价格比。
　　2．资源重复(Resource Replication)
　　资源重复是在并行性中引入空间的因素。它是靠重复设置硬件资源来提高可靠性或性能的，如通过使用两台或多台完全相同的处理机或计算机完成同样的任务来提高性能。典型的例子是双工系统、相连处理机和阵列处理机等。
　　3．资源共享
　　资源共享是用软件方法让多个用户共用同一套资源，通过提高系统资源的利用率来提高系统的性能和效率。典型的例子是多道程序分时系统，它是利用共享CPU、主存资源以降低系统价格来提高设备利用率的一个实例。例子还包括计算机网络和分布处理系统等。
　　沿时间重叠途径，多个处理机进行流水线构成的多处理机，一般都是非对称型或异构型的；沿资源重复途径，构成的相联处理机和阵列处理机都是对称型或同构型的多处理机；沿资源共享途径发展的多处理机则既可以是同构型的，也可以是异构型的。
10.2 并行处理机基本结构
　　并行处理机也称阵列机，采用资源重复的并行性措施实现。并行处理机将大量重复设置的多个处理单元PE(Processing Element)按一定方式互连成阵列，在统一的控制部件CU(Control Unit)控制下，对各自所分配的不同数据并行执行同一指令规定的操作，是操作并行的SIMD(单指令流多数据流)计算机。它采用资源重复的措施开发并行性，是以SIMD方式工作的。这里的PE是指不带指令控制部件的算术逻辑运算单元。
10.2.1 并行处理机的两种典型结构
　　并行处理机通常由一个控制器(Control Unit，CU)、N个处理单元(Processing Element，PE)、M个存储模块以及一个互连网络部件(Inter Connection Network，ICN)组成。根据其中存储器模块的分布方式，并行处理机可分为两种基本结构：分布式存储器的并行处理机和共享存储器的并行处理机。这两种结构的共同特点是在整个系统中设置多个处理单元，各个处理单元按照一定的连接方式交换信息，在统一的控制部件作用下，各自对分配来的数据并行地完成同一条指令所规定的操作。下面分别对这两种基本结构进行介绍。
　　1．分布式存储器结构并行处理机
　　分布式存储器结构并行处理机具备四个特点：① 包含重复设置的多个同样的处理单元PE，通过数据寻径网络以一定方式互相连接；② 各PE都拥有自己的局部存储器(Processing Element Memory，PEM)，存放被分配的数据并只能被本处理单元直接访问；③ 在统一的阵列控制部件作用下，实现并行操作；④ 程序和数据通过主机装入控制存储器。由于通过控制部件的是单指令流，所以指令的执行顺序还是和单处理机一样，基本上是串行处理。其结构图如图10-2所示。
图10-2 分布式存储器的并行处理机结构图
　　这种结构的并行处理机处理单元的数目和存储体的数目是相同的，每个处理单元仅和自己的存储体相连，直接交换数据。在实现时，为了有效地进行高速处理，数据应在各存储体间合理分配，使各处理单元都可以依靠自身存储体中的数据进行运算。各数据单元之间交换数据是经过两条途径相互联系：一条是直接通过互连网络；另外一条是如果在某个存储体中存有各处理单元都需要的公共数据，则可以通过将处理单元局部存储体PEM读入控制单元，然后通过公共数据总线“广播”到全部处理单元中。在处理单元很多的并行处理机中，PE之间的互连网络只能是有限而固定的连接。
　　ILLIAC-IV是这种结构的SIMD机器，它由64个本地存储器的PE组成，PE间通过8×8环绕连接网格实现互连，因而也称为阵列处理机，其处理速度达每秒150×106次64位浮点加法运算。各种SIMD机器的主要差别在于进行PE之间互相通信的数据寻径网络不同。目前的大部分并行处理机是基于分布式存储器模型的系统。
　　2．共享存储器并行处理机
　　共享存储器并行处理机结构有M个存储体构成统一的并行处理机存储器，经过互连网络ICN连接，为全部处理单元PE0～PEn-1所共享，其结构图如图10-3所示。
图10-3 共享存储器的并行处理机结构图
　　为了使各处理单元能同时对向量的各个元素进行并行处理，一般都使存储体的数量M大于或等于处理单元的数量n。同时，在存储体之间合理分配数据，使各处理单元数据能来自不同的存储体，从而受存储器冲突的影响最小。从图10-3中可以看出，在这种结构中，互连网络是处理单元和存储器之间交换数据的通道，它提供多种连接方式，每个处理单元之间的数据传送使大多数向量运算不受影响。同时也可以看到，这种互连网络是复杂的，因此，这种结构在处理单元数量不大的情况下是很理想的。如Burroughs公司和伊利诺斯大学在1979年研制的科学处理机BSP，就属于这种结构，它有16个处理单元，17个存储体，最高的向量运算速度可达50×106次浮点加法运算。
10.2.2 并行处理机的特点
　　并行处理机利用多个处理单元对向量或数组所包含的各个分量同时进行运算，从而易于获得很高的处理速度。与同样擅长于向量处理的流水线处理机相比，并行处理机有如下特点：
　　1．多处理单元的互连网络连接
　　互连网络是并行处理的最有特色的一个组成部分，它规定了处理单元的连接方式，决定了并行处理能适应的算法类别，对系统整体的各项性能指标产生了重要的影响。
　　2．依靠资源重复并行措施
　　并行处理机获得高速度的主要原因就是使用大量的处理单元对向量所包含的各个分量进行运算，每一个处理单元要负责多种处理功能，相当于向量处理机中的多功能流水线部件，但其效率要比单个的功能流水线低。因此，只有在硬件价格降低和系统结构不断改进，并行处理机才具有较好的性能价格比。
　　3．同时性
　　并行处理机的每个处理单元在同一时刻要同等地担负起各种运算功能，相当于向量处理机的多功能流水线部件那样，但其效率(设备利用率)可能没有多个单功能流水线部件那样高。
　　4．运算速度高
　　主要是靠增大处理单元个数，与依靠缩短时钟周期的向量流水线处理机来说，速度提高的潜力要大得多。
　　正像并行处理机的特点描述一样，并行处理机主要是由处理单元代替了向量处理机中的流水线，用设备的重复设置达到高速运算的目的。事实上，SIMD计算机正是属于多处理单元的这一类，下面将重点介绍SIMD计算机的结构与设计。
10.3 SIMD计算机基本结构
　　SIMD计算机属于多处理机单元范畴，它含一个控制单元、多个处理单元，取指令在控制单元的作用下进行，取出的指令经分析译码后送给各处理器协作完成任务，也就是说，指令流是单独的，数据流是多倍的。下面着重以典型SIMD计算机为例介绍其发展进程、结构和设计。
10.3.1 SIMD计算机模型
　　SIMD计算机的抽象模型可以理解为：在同一个控制部件管理下，有多个处理单元，所以处理单元均收到从控制部件广播来的同一条指令，但操作对象是不同的数据。
　　H.J.Siegel提出了SIMD计算机的操作模型，如图10-4所示。
图10-4 SIMD计算机的操作模型
　　SIMD计算机的操作模型可用五元组表示：M=(N,C,I,M,R)，其字母所代表的含义如下：
　　N为机器的处理单元(PE)数。例如，Illiac Ⅳ采用64个PE，连接机(Connection Machine)CM-2采用65 536个PE。
　　C为由控制部件(CU)直接执行的指令集，包括标量和程序流控制指令。
　　I为由CU广播至所有PE进行并行执行的指令集，它包括算术运算、逻辑运算、数据寻径、屏蔽以及其它由每个活动的PE对它的数据所执行的局部操作。
　　M为屏蔽方案集，其中每种屏蔽将PE集划分为允许操作和禁止操作两种子集。
　　R是数据寻径功能集，说明互连网络中PE间通信所需要的各种设置模式。
10.3.2 SIMD计算机发展过程
　　Illiac Ⅳ是最先采用SIMD计算机结构的计算机。它分成两个分支，一个是用位线PE制造的SIMD计算机，如Goodyear MPP、AMT/DSP610和TMC/CM-2，CM-5是以SIMD模式运行的同步SIMD计算机；另外一个是用字宽运算PE的中粒度SIMD计算机，如BSP是16台处理机和17个存储模块同步工作的共享存储SIMD计算机，MasPar MP-1是中粒度SIMD计算机。SIMD计算机的发展过程如图10-5所示。
图10-5 SIMD计算机的发展过程图
10.3.3 Illiac Ⅳ计算机
　　Illiac Ⅳ阵列机是世界上最早采用SIMD结构设计的计算机，由美国宝来公司(Burroughs)和伊利诺斯大学于1965年合作研制，并于1972年生产。Illiac Ⅳ 系统结构如图10-6所示。
图10-6 Illiac Ⅳ 的系统结构框图
　　Illiac Ⅳ 由两大部分组成，即Illiac Ⅳ 阵列和Illiac Ⅳ 输入/输出系统。具体来讲，它是由三种类型处理机联合组成的多机系统：一是专门对付数组运算的处理单元阵列(Processing Element Array)；二是阵列控制器(Array Control Unit)，它既是处理单元阵列的控制部分，又可以看做是一台相对独立的小型标量处理机；三是一台标准的Burrouths B6700计算机，担负Illiac Ⅳ 输入/输出系统和操作系统的管理功能。
　　1．Illiac Ⅳ 阵列
　　Illiac Ⅳ 阵列处理器采用分布式存储器结构。每个处理单元配有专用的存储器模块，共由64个处理单元、64个处理单元存储器和存储器逻辑部件所组成。这个阵列的64个处理部件PU0～PU63排列成8×8的方阵，每一个PUi只和其东、西、南、北四个近邻PUi+1(mod 64)、PUi-1(mod 64)、PUi+8(mod 64)和PUi-8(mod 64)有直接连接。按照此规则，南北方向上同一列的PU两端相连成一个双向环，东西方向上每一行的东端PU与下一行的西端PU双向相连，最下面一行的东端PU则与最上面一行的西端PU双向相连，从而8行构成一个闭合螺线形状。因此，Illiac Ⅳ 的阵列结构又称为闭合螺线阵列。如图10-7所示。
图10-7 Illiac Ⅳ 各处理单元阵列结构的闭合螺线连接方式
　　这种连接方式既便于一维长向量(最多64个元素)的处理，又便于两维数组运算，从而缩短处理单元之间数据传送的路径距离。在这个阵列中，任意两个单元之间的数据传送步距不超过7步。一般来讲，这种闭合螺线结构的连接方式，有n×n个单元组成的阵列中，任意两个处理单元之间的最短距离不会超过(n-1)步。例如，从PU10到PU45的距离以下列路径为最短：
PU10→PU1→PU57→PU56→PU48→PU47→PU46→PU45
　　处理单元数组处理的运算部分，可对64位、32 位和8位操作数进行多种算术和逻辑操作，包括48位、24位或8位定点运算。处理单元存储器PEM分属每一个处理单元，各有2048×64位的存储容量和不大于350 ns的取数时间。64个PEM联合组成阵列存储器，存放数据和指令。PE和PEM之间经过存储器逻辑部件MLU相连，这些部件用于处理机与存储模块接口的逻辑电路，它包含存储器信息寄存器和有关控制逻辑线路，用于实现PEM分别与PE、CU以及I/O之间的信息传送。
　　2．阵列控制器
　　阵列控制器CU实际上是一台小型控制计算机。它除了对阵列的处理单元实行控制以外，如发控制信号、广播公共地址、广播公共数据，还能利用本身的内部资源执行一整套指令，用以完成标量操作，在时间上与各PE的数组操作重叠起来。因此，控制器的功能有以下五个方面：
　　(1) 对指令流进行控制和译码，包括执行一整套标量操作指令；
　　(2) 向各处理单元发出执行数组操作指令所需的控制信号；
　　(3) 产生和向所有处理单元广播公共的地址部分；
　　(4) 产生和向所有处理单元广播公共的数据；
　　(5) 接收和处理由各PE(如计算出错时)、系统I/O操作以及B6700所产生的陷阱中断信号。
　　Illiac Ⅳ 阵列控制器CU与处理单元阵列之间的信息联系有以下四条信息通路：
　　1) CU总线
　　处理单元存储器PEM经过CU总线把指令和数据送往阵列控制器，以8个64位字为一信息块。这里指令是指分布存放在阵列存储器中用户程序的指令；而数据可以是处理所需的公共数据，先将它们送到CU，再利用CU的广播功能送到各处理单元。
　　2) 公共数据总线CDB(Common Data Bus)
　　这是64位总线，用作向64个处理单元同时广播公共数据的通路。
　　3) 模式位线(Mode Bit Line)
　　每一个单元都可以经过模式位线把它的模式寄存器(mode register)状态送到CU中，送来的信息中也包括该处理单元的“活动”状态位。只有那些处于“活动”状态的处理单元才执行单指令流所规定的公共操作。
　　4) 指令控制线
　　处理单元微操作控制信号和处理单元存储器地址、读/写控制信号都经过约200根指令控制线由CU送到阵列处理单元PE和存储器逻辑部件MLU中。
　　3．输入/输出系统
　　Illiac Ⅳ 输入/输出系统由磁盘文件系统DFS(Disk File System)、I/O分系统和B6700处理机组成。
　　磁盘文件系统DFS是两套大容量并行读写磁盘系统及其相应的控制器。I/O分系统由输入/输出开关I/OS(Input/Output Switch)、控制描述字控制器CDC(Control Description Word Controller)和输入/输出缓冲存储器BIOM(Buffer of Input and Output Memory)三个部分组成。I/OS的功能有两个：一是作为名副其实的开关，用以把DFS或可能连上的实时装置转接到阵列存储器，进行大批数据的I/O传送；二是作为DFS和PEM之间的缓冲，以平衡两边不同的数据宽度。CDC的功能是对阵列控制器的I/O请求进行管理。BIOM处在DFS和B6700之间，作为缓冲，使两者的传送频带匹配。
　　B6700管理计算机一般配置一个CPU(另一CPU可选)、32K字内存(最大可扩充至512K字)和经过多路开关控制的一大批外围设备(包括一台容量为1012位的激光外存储器以及ARPA网络接口)。B6700的作用是管理全部系统资源，完成用户程序的编译或汇编，为Illiac Ⅳ 进行作业调度、存储分配、产生入/出控制描述字并送至CDC、处理中断，以及提供操作系统所具备的其它服务等。
10.3.4 BSP计算机　
　　BSP(Burroughs Scientific Processor)是美国Burroughs公司和伊里诺大学合作设计的用于科学计算的并行处理机，于1979年生产。与Illiac Ⅳ 不同，这台计算机是采用共享集中式主存结构，是共享存储器SIMD结构的典型代表。BSP计算机系统组成如图10-8所示。它由系统管理计算机B7700/B7800和BSP处理机两大部分组成。
图10-8 BSP科学计算机系统结构图
　　BSP不能够单独工作，而是作为管理机B7700/B7800的后台机工作的。BSP大部分与分布式相同，区别是它的系统的存储器是由K个存储体(M0～Mk-1)集中在一起构成的，经过互连网络ICN为全部N个处理单元(PE0～PEN-1)所共享。
　　这种结构形式中，为使各处理单元对长度为N的向量中的各个元素都能同时并行处理， 存储体的个数K通常总是等于或多于处理单元的个数N。为了各处理单元在访问主存时，尽可能避免发生分体冲突，也要求有合适的算法能够将数据按一定规律合理地分配到各个存储体中。与分布式存储器结构另一个不同之处在于互连网络ICN的作用不同。集中式主存的结构形式中，互连网络是用来连接处理单元和存储器分体之间的数据通路的，希望能让各个处理单元以高速、灵活的方式连到不同的存储体上。因此有的并行处理机系统将其称为对准网络(Alignment Network)。
　　BSP系统采用了全面并行化操作， 即把资源重复和时间重叠两种并行性技术结合起来，有人将其称为第二代并行处理机。BSP科学处理机系统由系统管理机(又称系统资源机)和科学处理机两大系统构成。系统管理机担负BSP编译、任务调度、数据通信、外部设备管理等任务，而科学处理机本身又包括控制处理机、文件存储器及并行处理机三大部分。
　　1．BSP处理机的组成
　　BSP处理机可分为4个部分，即并行处理机、控制处理器、文件存储器和对准网络。
　　1) 并行处理机
　　并行处理机包含16个算术单元、由17个存储模块(与16最接近的质数)组成的一个无冲突访问的并行存储器和一套对准网络。
　　并行机中每个处理器以160 ns的时钟周期进行向量计算。所有16个算术单元AE对不同的数据组(从并行处理机控制器广播来)进行同一种指令操作，大部分的算术运算能在2个时钟周期(320 ns)内完成。进行向量运算的数据是存在17个并行存储器模块中的，每个模块的容量可达512千字，17个存储器模块的组织形成了一个无冲突访问存储器，它容许对任意长度以及跳距不是17倍数的向量实现无冲突存取。
　　2) 控制处理器
　　控制处理器是一台用于控制的计算机，其核心是标量处理单元，处理机的时钟频率是1 MHz。它除了用以控制并行处理机以外，还提供了与系统管理机相连的接口。标量处理机则处理存储在控制存储器中的全部操作系统和用户程序的指令，即指令/控制存储器。
　　3) 文件存储器
　　文件存储器是一个半导体辅助存储器，是一个高速大容量外存储器，是唯一置于BSP直接控制下的外围设备。BSP的计算任务文件由系统管理机加载，然后对这些任务进行排队，由控制处理机取出并加以执行。BSP在运行过程中产生的输出文件和中间结果也都暂存于文件存储器中，由于读写速度较快，可很好地解决处理机和外设之间的带宽瓶颈。
　　4) 对准网络
　　对准网络包涵完全交叉开关以及用来实现数据从一个源广播至几个目的地以及当几个源寻找一个目的地址时能分解冲突的硬件。这就需要在算术单元阵列和存储器模块之间具备通用的互连特性，而存储模块和对准网络的组合功能则提供了并行存储器的无冲突访问能力。算术单元也利用输出对准网络来实现一些诸如数据压缩和扩展操作以及快速傅立叶变换算法等专用功能。
　　2．BSP的并行存储器
　　BSP并行存储器又称为质数存储系统，由17个存储模块组成，存储周期为160 ns。BSP并行存储器的无冲突访问是它的一个独特的技术性能。其实现的硬件技术包括：质数个存储器端口(BSP并行存储器的存储体数是一个质数17)、存储器端口和AE之间的完全交叉开关(对准网络)以及特殊的存储器地址生成机构。
　　3．BSP的并行流水技术
　　BSP系统采用了全面的并行性技术，它并不依靠提高时钟频率获得高速，而是依靠并行性。在BSP中，存储器－存储器型的浮点运算是流水进行的。BSP的流水线组织由5个功能级组成，尤其是并行处理机由16个处理单元、17个存储器模块和2套互连网络(亦称对准网络)组合在一起，形成了一条五级的数据流水线，使连续几条向量指令能在时间上重叠起来执行。其结构示意图如图10-9所示，五级的功能作用依次是：
　　① 由17个存储器模块并行读出16个操作数；
　　② 经对准网络NW1将16个操作数重新排列成16个处理单元所需要的次序；
　　③ 将排列好的16个操作送到并行处理单元完成操作；
　　④ 所得的16个结果经过对准网络NW2重新排列成17个存储器模块所需要的次序；
　　⑤ 写入存储器。
图10-9 BSP数据流水线结构示意图
　　在读与写存储器时两套对准网络NW1/2的作用分别是，使得并行存储器中为保证无冲突访问而错开存放的操作数顺序能够与算术单元并行处理要求的正常顺序一致。整个流水线由统一的指令译码和控制部件进行控制。这种流水线结构是很新颖的，对提高系统处理效率起着很大的作用。
　　BSP还有一个高效率的FORTRAN编译程序，具有很强的向量化功能，对程序中隐含的并行性保证有较高识别率。向量程序不但能够处理明显的数组操作，还能处理线性递归，循环内部的条件分支等进程，并产生明显的加速效果。
10.3.5 CM-2计算机　
　　CM-2是Thinking Machines Co-operation于1987年推出的Connection Machine系列机中的一台高档机，是一台细粒度的SIMD计算机，它由数千个位片PE组成，它的峰值处理速度超过10 Gflo/s，它的系统结构如图10-10所示。
图10-10 CM-2的系统结构图
　　所有程序从前端开始执行，当需要并行数据操作时，发送微指令到后端处理阵列。定序器(sequencer)分解这些微指令并且把它们广播给阵列中的所有数据处理器(data processor)。前端机和处理阵列之间有三条交换数据计算结果的通路：广播总线(broadcasting)、全局组合总线(global combining)和标量存储器总线(scalar memory bus)，其组成部分介绍如下。
　　1．处理阵列
　　CM-2是一台数据并行计算的后端机。处理阵列包含4 K到64 K个位片数据处理器，所有数据处理器都由定序器控制。定序器对来自前端机的微指令进行译码，然后把毫微指令广播到阵列中各个处理器。所有处理器可以同时访问它们的存储器，它们以锁步方式执行广播来的指令。
　　处理器之间通过寻径、NEWS网格(NEWS gird)或扫描机构(scanning mechanism)相互交换数据。这些网络也与I/O接口相连。称为数据穹(data vault)的大容量存储器子系统与I/O相连，它可存储多达60 G字节的数据。
　　2．寻径器、NEWS网格和扫描机构
　　CM-2处理机间能够快速高效地通信，主要通过下列技术构造的互联网络来实现。
　　1) 寻径器
　　每个处理器芯片包含一个用于处理器之间数据寻径的专门硬件。把所有处理器芯片上的寻径器结点用线连在一起形成一个布尔n-立方体。在CM-2最大配置时，所有处理器芯片上共有4096个寻径器结点，连成一个12维的超立方体。
　　2) NEWS网格
　　每个处理器芯片中的16个物理处理器可以排列成8×2、1×16、4×4、4×2×2或2×2×2×2等形式的网格。规定每个物理处理器有64个虚拟处理器。可以想象这64个虚拟处理器在芯片中排列成8×8网格。
　　3) 扫描机构
　　除了通过超立方体寻径器可以动态地重构NEWS网格外，CM-2还有专门的硬件支持对整个NEWS网格的扫描或传播。这些都是很有效的并行操作，在整个阵列中进行快速的数据组合和传播。
　　3．输入/输出系统
　　Connection Machine不仅强调计算的大规模并行性，还强调计算结果的可视化。2～16条高速I/O通道用于数据和/或图像I/O操作。连接到I/O通道的外围设备包括数据穹、CM-HIPPI系统、CM-IOP系统和VME总线接口控制器，如图10-10所示。数据穹(Data Vault)是基于磁盘的海量存储系统，用来存放程序文件和大数据库。
　　CM-2已经用于解决几乎所有MPP所面临的具有重大挑战性的应用问题。特别是Connection Machine系列已经用于借助相关反馈技术的文档检索、基于记忆的推理，如用在医疗诊断系统QUACK中摸拟诊断疾病以及处理工作量很大的自然语言等。CM-2的其他应用包括SPICE的VLSI电路分析和布线、计算流体动力学、信号/图像/视觉处理和集成、神经网络模拟和连接模型、动态规划，上下文无关文法分析、射线追踪图以及计算几何等问题。
10.4 SIMD计算机的应用　
10.4.1 计算模型及有限差分
　　哈辛诺在1986年将物理计算模型分成连续模型和离散模型(粒子模型)。
　　连续模型是指所有计算的时间和空间是连续变化的物理量，且这些物理量是一定范围内的平均值。典型的参数如电荷密度、温度和压力等。粒子模型则将世界看成是由离散的粒子组成的，这些物理量反映单个粒子的当前状态，典型的参数如速度、力和动量等。两种模型只是对同一问题的两种不同观察方法而已。
　　连续模型和离散模型的主要区别是：连续模型符合偏微分方程，按离散形式处理时，方程式中所有变量的变化都是其近邻变量的函数，远程变量没有直接的影响。先通过作用于近邻变量，近邻变量再作用于随后的近邻变量，由此向前非直接地作用于整个媒质，也就是通过局部作用而将作用传送到整个媒质。离散模型(粒子模型)允许粒子受远程粒子的影响。任何粒子在任何时刻都与模型中的其它粒子有关。
　　应用有限差分方法求解连续模型对于并行计算具有很大的吸引力。有限差分方法是求解偏微分方程的一种有效方法，它把一个有规则的网格履盖在整个模型域上，用网格点上变量值写出差分方程组，以代替连续模型的偏微分方程来进行计算。作为连续模型，在解决物理问题时，我们描述以下平面域的拉普拉斯方程：
　　将这个方程离散化，即在x和y方向上每隔一段相同的距离h取一个样值点，这个微分方程就可以用差分方程的形式表示。下面就是二阶偏导数表示为差分形式，式中(x, y)为平面直角坐标，h为网格间距。
　　把上述差分方程代入原方程，则可得有限差分计算公式为
　　Illiac Ⅳ 的阵列结构特别适用于计算在网格上定义的有限差分函数。这是因为，根据拉普拉斯方程，任一网格点(x, y)上的函数值均可由其四周邻近点的函数值计算出来，这一要求正好反映了阵列处理机每个处理单元与其4个近邻连接的性质。实际计算时，应利用张弛法进行。每一网格点上的函数值用求其四邻平均值的方法计算，经多次迭代，逐次逼近其最终的平均值。网格边缘的函数值是已知的，由场域的边界条件决定；而对于内部各点的函数值，开始时可选择为零，然后根据拉普拉依方程多次迭代求U(x, y)值，直至连续二次迭代所求值的差小于规定误差为止(已知迭代过程是收敛的)。
　　Illiac Ⅳ 在计算时，是把内部网格点分配给各个处理单元的。因此，上述计算过程可以并行地完成，从而可成倍地提高处理速度。由于实际问题中所遇到的内部网格点数目很大，因此需将其分成许多子网格，然后才能在Illiac Ⅳ 上求解。
10.4.2 阵列处理机的几种基本算法　
　　1．矩阵加
　　在阵列处理机上，实现矩阵加的算法是最简单的一维数组运算。设A和B是n×n阶矩阵，A、B相加的和矩阵为C，它也是n×n阶矩阵。矩阵加的算法为
A + B = C
其中cij = aij + bij。
2．矩阵乘
　　设A和B是n×n阶矩阵，A、B的乘积矩阵C也是n×n阶矩阵。矩阵乘的传统串行算法为A × B = C，
cij= 　aikbkj
其中，0≤i≤n-1且0≤j≤n-1。
　　3．累加和
　　累加和并行算法是将N个数的顺序相加过程变为并行相加过程。串行求和的FORTRAN程序如下：
　　　　C(-1) = 0
　　　　DO 10 I = 0，N
　　10 　C(I)=C(I-1) + A(I)
　　在并行处理机上，采用递归加法，FORTRAN程序如下：
　　 　　DO 10 I = 0，lbN-1
　　10 　　A=A + SRL(A, 2**I) ；把A向量逻辑右移2i个PE，只需做lbN次加法。
　　例如，当N=8时，在SISD计算机要用8次加法时间。如果在并行处理机上，采用成对递归相加的算法，则只需lb8=3次加法时间就够了。首先，原始数据A(I)，0　　第一步 置全部PE为活动状态；
　　第二步 全部A(I), 0　　第三步 令K = 0；
　　第四步 全部PE的(RGA)转送到RGR；
　　第五步 全部PE的(RGR)经过互连网络向右传送2k步距；
　　第六步 j=2k-1-1；
　　第七步 置PE0至PEj为不活动状态；
　　第八步 处于活动状态的PE执行(RGA): =(RGA)+(RGR)操作；
　　第九步 k:=k+1；
　　第十步 若k<3，则转回第四步，否则继续往下执行；
　　第十一步 置全部PE为活动状态；
　　第十二步 全部PE的(RGA)存入相应PEM的a+1单元中。
　　采用SIMD并行算法，运算速度提高，加速比为N/lbN倍，运算次数增加。从N次增加到NlbN次，效率降低，实际效率为1/lbN。例如当N=1024，速度提高100倍，运算参数增加10到倍，效率只有1/10。如果N=220，即100万个数求和，速度可以提高5万倍。
10.5 互连网络的概念
　　互连网络是一种由开关元件按照一定的拓扑结构和控制方式将集中式系统或分布式系统中的结点连接起来所构成的网络，这些结点可能是处理器、存储模块或者其他设备，它们通过互连网络相互连接并进行信息交换。互连网络已成为并行处理系统的核心组成部分，它对并行处理系统的性能起着决定性的作用。
10.5.1 互连网络的基本概念和作用
　　在多计算机系统中，无论是处理机之间，还是处理器与存储器之间，都要通过互连网络实现信息交换。决定互连网络性价比的主要因素是结构复杂性(反应成本)和通信频带及结构灵活性(反应性能)
　　如果我们把处理单元或存储体看成结点(Node)，互连网络则为输入和输出二组结点之间提供一组互连或映射(Mappings)。对于有N个输入结点和M个输出结点的情况，从输入到输出的映射可定义出N×M种映射的互连网络，我们称之为广义互连网络(Generailsed Connection Network)。图10-11画出了3个输入结点和2个输出结点的广义互连网络。它的映射关系可以分为两类：一对多的映射(见图10-11(a))，一是一对一映射(见图10-11(b))。如果只有一对一映射，则共有N！种映射。对于有N！种映射的互连网络，我们称之为连接网络(Connection Network)或全排列网络。
图10-11 3个输入结点和2个输出
结点的网络映射
　　实现广义互连网络的直观方法是全交叉开关网络(Full Crosser Network)。它是互连网络中最通用的一种形式，图10-12显示了具有4个输入和4个输出的全交叉开关网络。对于任一输入和输出之间，都有一个交叉点，每个交叉点实际代表一套开关，而且包含必要的用来分解多重访问冲突的硬件设备。这种网络由于任意一对输入和输出之间都有直接连接，因此通信频带宽、灵活性好。但由于交叉点的数量为N×M个，再考虑到总线的线数，整个交叉开关非常复杂。当N很大时，交叉开关的成本会超过N+M个处理单元和存储器的成本。因此，它只用于输入输出端数目较少的情况。如BSP用了两个这种网络，一个是N=16，M=17；另一个是N=17，M=16。
图10-12 具有4个输入和4个输出的
全交叉开关网络
　　互连网络主要涉及到链路、交换开关和网络接口电路等。其中链路也称为链或通道，它用来将计算机系统中两个硬件部件进行物理连接；交换开关也称为路由器，它用于建立交换网络；网络接口电路也称为网卡。
　　互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。随着各个领域对高性能计算的要求越来越高，多处理机和多计算机系统的规模越来越大，处理机之间或处理单元和存储模块之间的通信要求和难度也越来越突出。所以互连网络已成为并行处理系统的核心组成部分，它对整个计算机系统的性能价格比有着决定性的影响。互连网络在多处理机系统中位置和作用如图10-13所示。
图10-13 互连网络在多处理机系统中位置和作用
10.5.2 特性参数和性能参数
　　1．互连网络的结构特性参数
　　网络用有向边或无向边连接有限个结点的图来表示。下面从图的角度定义几个用于估算复杂性、通信效率和网络价格的参数，即网络特性。
　　1) 网络规模
　　网络中结点数称为网络规模，它表示该网络所能连接的部件的多少。
　　2) 结点度
　　与结点相连接的边(即链路或通道)数称为结点度，用d表示。在单向通道情况下，进入结点的通道数称为入度，而从结点出来的通道数则称为出度。结点度就是二者之和。结点度反映了结点所需要的I/O端口数，也即反映了结点的价格。为了降低价格，应尽可能使d小。为构造可扩展系统，使构件能模块化，则要求结点度保持恒定。
　　3) 距离
　　两结点之间相连的最少边数。
　　4) 网络直径
　　网络直径是网络中任意两个结点之间距离的最大值。它是说明网络通信性能的一个指标。因此从通信的观点来看，网络直径应当尽可能地小。
　　5) 等分宽度
　　当某一网络被切成相等的两半时，沿切口的最小边数(通道)称为通道等分宽度，用b表示。于是，线等分宽度就是B=b×w，w为通道宽度(用位表示)。因此，等分宽度是说明沿等分网络最大通信带宽的一个参数。网络的所有其它横截面都应限在等分宽度之内。
　　6) 结点间的线长
　　结点间的线长是两个结点间的线的长度。它会影响信号的时延、时钟扭斜和对功率的
需要。
　　7) 对称性
　　网络对称性是指，如果从网络任意结点看上去网络的拓扑结构都是相同的，则称该网络是对称的；否则网络是非对称的。对称网络较易实现，编程也较容易。
　　8) 数据寻径
　　数据寻径网络用来进行PE间数据交换的方式有以下几种：① 对一通信也称点对点通信，仅有一个发送者和一个接收者；② 对多通信包括广播和散射；③ 多对一通信包括聚集和归约，④ 多对多通信中最简单的形式是置换。图10-14形象化地给出了几种常见的数据寻径方式。
图10-14 几种常见的数据寻径方式
　　2．网络的传输性能参数
　　下面以图10-15所示的两台计算机互连的最简单的网络为例来讨论网络的传输性能参数，每台计算机有一个FIFO的数据队列。
图10-15 连接两台计算机的简单网络
　　当一台计算机发送数据给另一台时，发送方的步骤如下：
　　步骤1 应用程序把要发送的数据拷贝到操作系统的缓冲区。
　　步骤2 操作系统根据要发送的数据计算出检查和，并把它加在消息中，同时启动超时计数器。
　　步骤3 操作系统把缓冲区中的数据送到网络接口硬件并通知硬件开始发送消息。
　　消息包的接收和上述步骤正好相反，即
　　步骤1 系统把数据从网络接口硬件拷贝到操作系统缓冲区。
　　步骤2 系统根据接收到的数据计算出检查和。如果计算出的检查和与发送过来的检查和匹配，则接收方发一个回答信号给发送方；如果不匹配，则删除这个消息，因为发送方在超时计数器超时后会重发这个消息。
　　步骤3 如果数据通过检查，系统把接收到的数据拷贝到用户地址空间并启动应用程序继续执行。
　　发送方接收到回答信号后，即可以释放系统缓冲区的消息。如果发送方的超时计数器已超时，那么需重发消息。从消息包的发送和接收步骤来看，一个消息从发送到接收经历的时间过程为：发送方的开销时间、消息在线路上的传播时间、接收方的开销时间。下面给出互连网络传输方面和时延有关的性能参数：
　　(1) 频宽(bandwidth)。它是指消息进入网络后，互连网络传输信息的最大速率。它的单位是兆位/秒，而不用兆字节/秒。
　　(2) 传输时间(transmission time)。消息通过网络的时间，它等于消息长度除以频宽。
　　(3) “飞行”时间(time of flight)。消息的第一位信息到达接收方所花费的时间，它包括由于网络中转发或其它硬件所起的时延。
　　(4) 传输时延(transport latency)。它等于“飞行”时间和传输时间之和。它是消息在互连网络上所花费的时间，但不包括消息进入网络和到达目的结点后从网络接口硬件取出数据所花费的时间。
　　(5) 发送方开销(sender overhead)。处理器把消息放到互连网络的时间，这里包括软件和硬件所花费的时间。
　　(6) 接收方开销(receiver overhead)。处理器把到达的消息从互连网络取出来的时间，这里包括软件和硬件所花的时间。所以一个消息的总时延可以用下面公式表示：
　　总时延 = 发送方开销 +“飞行”时间 + 传输时间 + 接收方开销　
　　以上传输性能参数间的关系如图10-16所示。
图10-16 互连网络的传输性能参数间的关系
　　【例10-1】 假设一个网络的频宽为10 Mb/s，发送方开销和接收方开销分别等于230 ms和270 ms。如果两台机器相距100 m，现在要发送一个1000 Byte的消息给另一台机器，试计算总时延。如果两台机器相距1000 km，那么总时延为多大？
　　解：光的速度为299 792.5 km/s，信号在导体中传递速度大约是光速的50%，所以“飞行”时间可以计算出来了。那么相距100 m时总时延为
T = 发送方开销 +“飞行”时间 + 　+ 接收方开销
= 230 ms +　　　　　　　　　 　 + 270 ms
= 230 ms + 0.67 ms + 800 ms + 250 ms
= 1301 ms
相距1000 km时的总时延为
T = 230 ms +　　　　　　　　　+ 270 ms
= 230 ms + 6671 ms + 800 ms + 270 ms
= 7971 ms
10.5.3 互连函数
　　为了反映不同互连网络的连接特性，每种互连网络可用一组互连函数来描述。如果将互连网络的N个输入端和N个输出端分别用整数0，1，…，N-1来表示，则互连函数表示相互连接的输出端号和输入端号之间的一一对应关系。或者说，存在互连函数f，在它的作用下，输入i应与输出f(i)相连，其中0≤i≤N-1。当互连网络用来实现处理器与处理器之间的数据变换时，互连函数也反映了网络输入数组与输出数组间对应的置换关系或称排列关系。所以互连函数有时也称为置换函数或排列函数。
　　表示互连函数通常用三种方法：函数表示法、输入/输出对应表示法、图形表示法。
　　函数表示法用x表示输入端变量，用f(x)表示互连函数。x还常用几位二进制形式来表示，写成Xn-1Xn-2 … X1X0，互连函数则对应地表示为f(Xn-1Xn-2 … X1X0)。
　　输入/输出对应表示法把互连函数表示为：
　　这就是说，将0变换为f(0)，1变换为f(1)，…，N-1变换成f(N-1)。例如，N=8均匀洗牌函数的这种表示形式为：
　　图形表示法用输入/输出的连接图表示关系。这种表示法较为直观，但有时显得较为繁琐，难以体现内在规律。因此一般函数表示法和输入/输出对应表示法结合使用。
　　有一种特殊的互连函数表示法称为循环表示法。它将互连函数f(x)表示为(X0X1…Xj-1Xj)，所代表的对应关系为f(X0)=X1,f(X1)=X2,…，f(Xj)= X0，其中j+1称为该循环的长度。
　　下面介绍常用的基本互连函数的函数表达式及主要特征。
　　1．立方体(cube)
　　立方体的每个顶点代表一个结点，结点的编号用二进制码(C2C1C0)表示。如图10-17所示为N=8的三维立方体结构。
图10-17 N＝8的三维立方体结构
　　立方体单级网络的互连函数实现二进制编号中第k位值不同的结点之间的连接。故三维的立方体单级网络有三种互连函数：Cube0、Cube1和Cube2，分别建立结点编号中C0不同或C1不同或C2不同的结点之间的连结，其连接方式如图10-18。一般情况下，一个n维立方体有N＝2n个结点，共有n种互连函数，分别由n位编号中的每一位的位求反来确定。即
Cubei (Pn-1 … Pi … P1P0) = Pn-1 … P1P0
其中，Pi为入端标号的二进制代码第i位，且0≤i≤n-1。当维数n＞3时，称为超立方体(Hyper Cube)网络。对于n维立方体单级网络，要实现任意两个结点之间的连接，最多需使用n次不同的互连函数，因此n维立方体单级网络的最大距离为n。
图10-18 N＝8的三维立方体三种互连方式
　　2．PM2I
　　PM2I是加减2i的简称(plus-minus2i)，图10-19中给出了PM2I互连网络的部分连接图。
图10-19 N＝8的PM2I互连网络的部分连接图
　　PM2I单级网络能实现j号结点与j±2i mod N号结点的直接相连，N为处理器的个数，PM2I单级网络的最大距离为[n/2]，n = lbN。因此，它共有2n个互连函数，即
　　　PM2＋i (j) = j + 2i mod N
　　　PM2－i (j) = j- 2i mod N
式中，0≤j≤N-1，0≤i≤n-1。如设N = 8，则共有2n = 6个互连函数，各互连循环函数表示为：
PM2＋0：(01234567)
PM2－0：(76543210)
PM2＋1：(0246)(1357)
PM2－1：(6420)(7531)
PM2±2：(04)(15)(26)(37)
　　3．混洗交换(Shuffle Exchange)
　　混洗交换互连网络包含全混洗和交换两种互连函数，混洗交换又称为洗牌置换。
　　1) 全混洗(Perfect Shuffle)
　　这种连接规律是把全部按标号次序排列的处理器从当中分为数目相等的两半，然后洗牌达到理想的“全混”状态一样，这也是“混洗”这个名词的由来。正如人们在洗扑克牌时，先将整副牌分成两半，然后通过洗牌以达到最理想的状态一样，因此这种方法也称为均匀洗牌。全混洗的互连函数为
(Pn－1Pn－2…P1P0) = Pn－2…P1P0Pn－1
　　可见，全混洗是将输入端的二进制编码循环左移1位得到输出端二进制编码的方法，图10-20所示为全混洗置换图。
图10-20 全混洗置换图
　　2) 交换(Exchange)
　　由于单一的全混洗互连网络不能实现二进制编号为全“0”和全“1”的结点与其他任何结点的连接，所以又增加了Cube0交换互连函数。同时采用了全混洗和交换的单级互连网络称为混洗交换单级互连网络。如图10-21所示为混洗交换单级互连网络图。
图10-21 混洗交换单级互连网络图
　　4．蝶形(Butterfly)
　　图10-22是蝶形置换的图形表示。蝶形互连网络的互连函数为
　　Butterfly(Pn－1Pn－2…P1P0)= P0Pn－2…P1Pn－1
　　它是将入端二进制编号的最高位和最低位互换位置即可得相应出端的二进制编号。
图10-22 n=8蝶形置换的图形表示
　　5．恒等置换
　　相同编号的输入端与输出端一一对应互连所实现的置换即为恒等置换，其表达式为
　　I(xn 1 xn 2 xn 3…x1 x0)= xn 1 xn 2 xn 3…x1 x0
即二进制编码完全相同，其中等式左边括号内的xn 1 xn 2 xn 3… x1 x0和等式右边的xn 1 xn 2 xn 3… x1 x0均为网络输入端和输出端的二进制地址编号。
　　6．交换置换
　　交换置换是将输出编号的二进制编号中第0位取反，得到的互连函数称为交换置换。其表达式为
E(xn 1 xn 2 xn 3…x1 x0)= xn 1 xn 2 xn 3…x0
10.6 静态互连网络
　　静态互连网络是指在各结点间使用的直接链路，且一旦构成后就固定不变的网络。这种网络比较适合于构造通信模式可预测或可用静态连接实现的并行处理系统和分布计算机系统。集中式系统的多系统之间或分布式系统的多个计算机之间的固定连接通常采用静态拓扑结构，并工作于异步状态下，采用分组交换的方法进行通信。　
10.6.1　静态互连网络结构
　　静态互连网络结构主要包含一维线性阵列、环和带弦环、循环移数网络、树形和胖树形、网格形与环形网格、超立方体和带环立方体、k元n立方体等7种结构，下面分别做简单介绍。
　　1．线性阵列
　　线性阵列是一种一维的线性网络，其中N个结点用N-1条链路连成一行，如图10-23所示。首尾结点的度是1，内部结点度为2，端结点度为1，直径为N-1，等分宽度为1，结构不对称。这种结构不同于总线结构，总线结构是通过时分切换使用多对结点时分进行通信，而线形阵列允许不同的结点对并发使用系统的不同通道。线性阵列是连接最简单的拓扑结构，当N很大时，通信效率很低。
图10-23 一维线性阵列连接结构
　　2．环和带弦环
　　用一条附加链路将线性阵列的两个端结点连接在一起，就构成了环。每个结点的度都是相等的，都是2。环可以单向工作，也可以双向工作。双向环有两个方向，当其中的一个单向环出现故障时，另一个环还可以继续工作。环是对称的，结点度为2。双向环直径为[N/2]，单向环直径为N。增加一条或两条附加链路，就可以得到结点度分别为3和4的带弦环。
　　3．循环移数网络和全连接
　　循环移数网络是通过环形网络结构上增加“弦”的方法使直径减小的改进网络。其规则是将环上每个结点出发与距该结点距离为2的整数幂的结点之间都增加一条附加链路而构成的。全连接网络是环上任意两个结点间都有附加链路连接。这种全连接网络是一个对称的网络，当网络规模为N时，结点度为N-1，网络直径为1，链路数为N(N-1)/2。
　　4．树形和星形网络连接
　　一棵5层31个结点的二叉树如图10-24(a)所示。顶部的一个结点称为根，底部的16个结点称为叶，其他的称为中间结点。除了叶子结点之外，每个结点都有两个孩子结点。一棵k层完全平衡的二叉树应有N=2k-1个结点，最大结点度为3，直径是2(k-1)。从一个叶结点到另外一个叶结点的通信必须经过叶→根→叶的过程。由于各子树和叶无横向的联系，因此这种结构的扩展性较好，只是直径较大。
图10-24 二叉树和星形网络连接结构
　　树形网络连接的另外一个应用是通信量不平衡问题。树形结构中叶子结点的通信量最小，而根结点的通信量最大。且随着层次的增加将呈现指数级增加，在所有的链路带宽相同的情况下，很容易造成网络阻塞。为了解决这个问题，即根结点瓶颈问题，1985年，Leiserson提出了胖树的概念。思想为通道带宽从叶结点往根结点上行方向逐渐增宽，越靠近根结点，链路带宽越大。
　　星形网络连接是树的一种特殊结构，是一种2层树，结点度为N-1，网络直径为常数2。图10-24(b)所示的是一个结点数为9的星形网络。
　　5．二叉胖树形网络结构
　　二叉胖树网络结构如图10-25所示，胖树的链路数从叶结点往根结点上行方向逐渐增多。
　　互连网络结构还包含网格形、环网形、搏动式阵列、超立方体、带环立方体和k元n-立方体网络等。搏动式阵列通常是为实现某种特定数据流算法而设计的一类多维流水线阵列结构。超立方体是一种二元n维立方体结构。带环立方体结构从超立方体结构改进而来，即将立方体的每个顶点结点用一个环形网络代替。k元n-立方体网络中的参数k是沿每个方向的结点数，n是立方体的维数。这两个数与网络中结点数N的关系为N=kn。一般来说，低维k元n-立方体称为环网，而高维二元n-立方体则称为超立方体。
图10-25 二叉胖树网络结构
10.6.2　静态互连网络特性
　　大多数网络的结点度都小于4，这是较为理想的。全连接网络和星型网络的结点度均太高，超立方体的结点度随lbN的增大而增大，当N值很大时，其结点度也很高。由于较高的结点度要求为结点提高较多的通信资源，因而在选择使用网络时，结点度不宜太高。静态连接网络特性如表10-1所示。
表10-1 静态连接网络特性
　　网络直径关系到消息传输时可能造成的时沿，一般要选择直径较小的网络。但是这存在两种例外情况，一是在一些情况下，人们可能更愿意使用平均距离来衡量一个网络可能造成的传输时沿，而不愿意用表示最大距离的直径，因为实际上可能只有极少量的通信在网络直径距离上进行的；另一种情况就是消息在网络中传输的机制，如果消息采用“虫蚀”方式(一种硬件寻址方式，它将包进一步分成更小的片，同一个包中所有的片不间断地以流水方式顺序地传送，只有头片知道包将发往何处)寻径，消息使用流水线机制传输，就像流水一样通过各结点、通信延迟几乎是固定不变的。但是，网络直径还是人们选择网络时经常要考虑的问题之一。
　　除了结点度和网络直径之外，链路数会影响网络的价格，等分宽带B将影响网络的带宽，对称性会影响网络的可扩展性和寻径效率。一般来讲，网络的总价格会随着结点度和链路数的增大而上升。
　　根据上述性能选择的简单规则，环形、网格、带环立方体和k元n-立方体都具有一定的条件用来构造未来的大规模并行处理系统。
10.7 动态互连网络
动态互连网络可根据程序要求实现所需的通信模式。它不采用固定连接，而是沿着连接路径使用开关或仲裁器以提供动态连接特性。根据级间连接方式，动态连接网络有单级和多级两类。单级网络只有有限的几种连接，任意两个结点之间的信息传送可能须经过在单级网络中循环多次才能实现，故单级网络也称循环网络。多级网络由多个单级网络串联组合而成，以实现任意两个结点之间的连接。按照价格和性能增加的顺序，动态互连网络可分为总线互连方式、交叉开关互连方式、多级网络互连方式等。
10.7.1　动态互连网络的互连形式　
　　1．总线互连方式的动态连接网络
　　总线互连方式又称为公共介质，是实现动态连接最简单的一种结构形式。用一条公用系统总线将多个处理机、存储器模块和I/O部件通过各自的接口部件或是多个由CPU、本地存储器和I/O部件所组成的计算机模块通过公共的接口部件互连起来。总线上的各模块以分时或多路转换方式通过总线在主设备与从设备之间传送信息。在多个请求情况下，总线仲裁逻辑每次只能将总线服务分配或重新分配给一个请求。图10-26所示为总线连接的多处理机系统。
图10-26 总线连接的多处理机系统
　　总线上的各模块是通过争用或时分方式获得总线服务，因此总线也被称为争用总线或时分复用总线，与另外两种动态互连方式相比，总线系统价格较低，带宽较窄。但由于价格低的优势，总线的使用很广，有很多的工业标准和IEEE总线标准。
　　总线系统通常设置在印刷电路底板上，连接到总线上的其他设备往往通过总线插槽或电缆与总线相连。总线系统中需要解决的主要问题有总线仲裁、中断处理和Cache一致性等问题。
　　2．交叉开关互连方式的动态连接网络
　　交叉开关(crossbar)互连由一组纵横开关阵列组成，将横向的p个处理机P及i个I/O模块与纵向的m个存储器模块M连接起来，如图10-27所示。
图10-27 交叉开关互连方式
　　行与列的交叉点上是由开关来控制其接通与否。交叉开关网络中的每一个开关只有两种状态：“通”或“断”。如果P1处理机要访问M3存储模块，只要将P1行线与M3列线交叉点的开关置为“通”，即可实现P1处理机和M3存储模块的互连。这里的交叉点开关，实际上是一组受同一信号控制的开关，可能包括地址线、数据线及其必要的控制线的连接。
　　交叉开关网络的每一行中可以同时接通多个交叉点开关，阵列中的总线条数等于全部相连的模块数之和m+p+i，且当m≥p+i时，可以使每个处理机和I/O设备都能分到一套总线与某个存储器模块相连，从而大大加宽互连传输带宽和提高系统的效率。与总线互连中采用分时使用总线不同，交叉开关采用的是空间分配机制。
　　为了保证系统的正常工作，每条列线上只允许有一个开关处于接通状态，否则可能由于多个处理机接入同一个存储模块而形成冲突。但是反过来，如果系统设计中允许处理机访问多个存储模块，每一条行线上可能会有多个开关被接通。如果希望同时读写多个存储模块，必须采用空间上或时间上的分隔使用。
　　交叉开关网络是目前使用最为广泛的一种网络，其优点是可以随工作进程随时改变开关的连接方式，以达到改变通信链路的目标；采用多级交叉开关网络虽然降低了硬件复杂性，但时延会随着网络级数的增加而增大。
　　3．多级网络互连方式的动态连接网络
　　多级网络互连是将多套单级互连网络通过开关模块串连扩展成多级互连网络(简称MIN)的方式。现在几乎所有的MIMD和SIMD计算机系统中都采用了多级互连网络结构，这样可以满足处理机之间灵活通信的需求。与单级网络相比，多级网络可以通过改变开关的控制方式灵活地实现各种连接，满足系统应用的需要。图10-28所示为由a×b开关模块和级间连接模式ISC构成的通用多级互连网络结构。
图10-28 由a×b开关模块和级间连接模式ISC构成
的通用多级互连网络结构
　　各种多级互连网络的区别就在于所用开关模块、级间连接(ISC)模式和控制方式上的不同。它们构成多级网络互连方式中的三个重要内容，从而形成各种不同的多级互连网络。
10.7.2　动态网络互连方式的比较
　　构成动态网络的总线、多级网络、交叉开关三种互连方式中，总线的造价最低，但其缺点是每台处理器可用的带宽较窄。总线所存在的另一个问题是容易产生故障，有些容错系统常采用双总线以防止系统产生简单的故障。由于交叉开关的硬件复杂性以n2倍上升、所以其造价最为昂贵。但是交叉开关的带宽和路由性能最好。如果网络的规模较小，它就是一种理想的选择。多级网络则是两个极端之间的折衷。它的主要优点在于采用模块结构，因而可扩展性较好。然而，其时延随网络级数logkn的增加而上升。另外由于增加了连线和开关复杂性，价格也是一种限制因素。如表10-2汇总了构成动态网络的总线、多级网络、交叉开关的主要特性。
表10-2 动态网络互连方面的比较表
10.7.3 多级互连网络
　　多级互连网络是各种置换连接将各级开关连接在一起，形成的一个完整网络。从外部看，整个多级互连网络只有输入端和输出端，输入和输出端之间的功能也是某种特定的置换连接。
　　与单级网络相比，多级网络具有更多的优势。从直观上理解，多级网络可以通过改变开关的控制方式，灵活地变换所实现的连接，使其更能适应系统的需要。也正是因为网络所实现的环路具有可变性，所以多级互连网络是动态网络中非常重要的一员，在多处理机系统中得到了广泛的应用。
　　动态多级互连网络可分为阻塞网、可重排非阻塞网和非阻塞网三种类型。
　　在同时实现多对入端与出端之间的连接时，可能会引起开关和通信链路使用上的冲突。具有此类性质的互连网络称为阻塞网络。换句话讲，是指一对以上输入端和输出端可同时实现互连的网络。在阻塞网络中，可能发生2个或2个以上的输入端对输出端的连接产生路径争用冲突。各种阻塞网络都能实现一些典型互连函数表示的连接，但不能实现任意的互连函数。一般来讲，阻塞网络所采用的开关数量少，路径控制比较简单，所以所产生的时沿比较小，且能够实现某种互连函数所表示的置换。由于其简单，能够实现的互连函数也是比较有限。典型的阻塞网络有：Ω网络、STARAN网络、基准网络、间接二进制n方体网络、δ网络和数据交换网络等。
　　可重排非阻塞网络是如果重新安排现有的连接，就可实现无阻塞的任意结点对的连接，从而满足一个新的结点对的连接请求。它在实现非阻塞网络连接时，往往需要通过重新安排开关的控制才能满足新的连接要求。典型网络有可重排Close网、Benes二进制置换网络等。
　　非阻塞网络不必改变原来的开关状态就可满足任意输入端和输出端之间的连接请求。它同可重排非阻塞网络是不同的，可重排非阻塞网络要通过改变原来的开关状态来改变连接的路径，才能满足新的连接请求。多级Close网络就属于此类网络。
10.8 互连网络的消息传递机制
　　消息传递机制的研究在互连网络的研究中占有非常重要的地位。在多计算机系统中通过互连网络进行消息传递需要专门的硬件和软件的支持。在这一节将研究各种寻径方法，并分析它们的通信时延问题。我们还要引入虚拟通道的概念，考察消息传递网络产生死锁的各种情况，说明怎样用虚拟通道来避免死锁。为了实现无死锁的消息寻径，人们提出了确定的和自适应两种寻径算法。
10.8.1 消息寻径
　　1．消息格式
　　首先掌握消息、包和片的基本概念和相关联系。
　　消息(Message)是在多计算机系统的处理结点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。包(Packet)的长度随协议不同而不同，它是信息传送的最小单位，64～512 b。片(Flit)的长度固定，一般为8位，它们的相互关系如图10-29所示。
图10-29 消息、包和片的相互关系图
　　消息寻径中的信息单位如图10-30。消息是结点间通信的逻辑单位，它常常由任意数目的长度固定的包组成，因此它的长度是可变的。
图10-30 消息的组织方式
　　包是包含寻径目的地址的基本单位。由于不同的包可能异步地到达目的结点，因此每个包需要一个序号，以便把传递的消息重新装配起来。可以进一步把包分成一些固定长度的数据片。寻径信息(目的地址)和序号形成头片，其余的片是数据片。
　　在采用存储转发寻径方式的多计算机系统中，包是信息传送的最小单位。在采用虫蚀寻径网络的多计算机中，包可以进一步分成片。片的长度往往受网络大小的影响，256个结点的网络需要片长为8位，即一个由256个结点组成的网络，常用8位作为一个片的长度。包的长度取决于寻径方式和网络的实现方法。典型的包的长度为64～512位。包中顺序号通常要占用1、2个片，这取决于系统在组织消息时所采用的策略和消息的长度。如果消息长度控制在256个包以内，那么只有1个片就足够了，反之就需要两个片。
　　包和片的大小还与通道频宽、寻径器设计以及网络流量密度等有关。
　　2．四种寻径方式
　　消息寻径方式可以分为两大类：线路交换和包交换。包交换是当前数据传输中效率最高，也是使用和研究得最多的方式。其中包交换又包括：存储转发寻径、虚拟直通寻径和虫蚀寻径等。下面逐一进行讨论。
　　1) 线路交换(circuit switch)
　　线路交换是一种以建立从源结点到目的结点间的直达物理通路为信息传输基础的交换方式。即在传递一个消息之前，先建立一条从源结点到目的结点的物理通路，然后再传递消息。如图10-31所示，图中的每一个带阴影的片是建立一个连接通路所需要的时间，经过4个时间片，打通了4个结点之间的通路，建立起到目的结点之间的通道。传输开始后，4个结点将无迟滞地传送全部信息。
图10-31 线路交换寻径示意图
　　线路交换寻径的传输时延用公式表示为T= 　
　　(Lt/B)×D+L/B，式中，Lt是在一个结点中建立路径所需要的小信息包长度，B为带宽，D为通路上总的结点数，L为信息包的长度。
　　在并行计算机中的频繁的小信息包通信的这种方式下，由于在传递一个消息之前，需要频繁地建立从源结点到目的结点的物理通路，开销将会很大，这种寻径方式与以下的几种包交换(packet switch)的寻径方式相比这是一个很大的缺点。包交换的寻径方式以其较高的传输带宽和较低的平均传输时延，更适合于具有动态和突发特性的MPP数据传送。相应地，如果是短信息包传输时采用此种方式，系统效率不高，因为建立路径的开销占信息传输时间的比例就会上升。
　　2) 存储转发寻径(store and forward)
　　在存储转发网络中包是信息流的基本单位，每个结点有一个包缓冲区。包从源结点经过一系列中间结点到达目的结点。即先按寻径信息传送到最近的结点存储，再根据寻径信息从此结点出发传至下一结点，逐段传送—存储，直至到达目的结点。
　　当一个包到达一个中间结点时，它首先被存入缓冲区。当所要求的输出通道和接收结点的包缓冲区可使用时，然后再将它传送给下一个结点。存储转发方式可以根据网络各结点间的忙闲情况调整信息包的发送路径和时间，比较灵活，但是时延长是其最致命的缺点，特别是当中间结点数量大时更加突出。如图10-32所示，存储转发网络的时延与源和目的地之间的距离(段数)成正比。第一代多计算机系统采用这种寻径方式。
图10-32 存储转发寻径示意图
　　存储转发的时延用公式表示为T=(L/B)×D+L/B=(D+1)×L/B。由图和公式可以看到，存储转发寻径有两个很大的缺点：一是包缓冲区大，不利于VLSI的实现；二是时延大，与结点距离成正比。
　　3) 虚拟直通(virtual cut through)
　　目前有一些多计算机系统采用的是虚拟直通的寻径方式。虚拟直通的寻径方式的思想是，为了减少时延，没有必要等到整个消息全部缓冲后再作路由选择，只要接收到用作寻径的消息头部即可判断。其通信时延用公式表示为T= (Lh/B)×D+L/B= (Lh×D+L)/B。式中Lh是消息中用于寻径那部分信息的长度。一般来说，L的长度远较Lh×D更大，所以公式可以近似为T=L/B，可以看到此时通信时延与结点数无关，这相对于存储转发的寻径方式来说是一个非常大的改进，所以虚拟直通寻径的延时接近于线路交换。
　　然而，当出现寻径阻塞时，虚拟直通方式只有将整个消息全部存储在寻径结点中，直到寻径通道不阻塞时才能将消息发出，这就需要每个寻径结点都有足够的缓冲区来存储可能出现的最大的信息包，在这一点上，虚拟直通方式与存储转发的寻径方式是一样的，同样不利于VLSI的实现。因此，虚拟直通方式在最坏的情况下与存储转发方式的通信时延是一样的。由此出现了下面将要讨论的新的寻径方式虫蚀寻径方式，它改进了以上提到的缺点。
　　4) 虫蚀寻径(wormhole)
　　新型的多计算机系统很多采用的是虫蚀寻径方式，把包进一步分成更小的片，且与结点相连的硬件寻径器中有片缓冲区。而消息从源结点传送到目的结点传输就要经过一系列寻径器，如图10-33所示。
图10-33 源结点传送到目的结点传输中的寻径器
　　同一个包中所有的片像不可分离的同伴一样以流水方式顺序地传送。包可以看做是一条蠕虫(一列火车)，由蠕虫头(火车头、即头片)和被牵引的蠕虫的节(车厢，即数据片)组成。头中包中含有目的地址，因此只有头片知道包将发往何处。所有的数据片必须跟着头片。不同的包可以交替地传送，但不同包的片不能交叉，否则它们可能被送到错误的目的地。虫蚀寻径传输过程如图10-34所示。
图10-34 虫蚀寻径传输过程示意图
　　用头片直接开辟一条以输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水方式在网络中向前“蠕动”。每个片相当于虫的一个节，“蠕动”是以节为单位顺序地向前爬行。传输过程就像一条蠕虫一样往前爬行，因此这种方式称为虫蚀寻径。
　　当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径消息立即做出路由选择：如果所选择的通道空闭且所选择的结点B的片缓冲区可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B。随后的其它数据片跟着相应地向前“蠕动”一步。当消息的尾片向前“蠕动”一步之后，它刚才所占有的结点就被放弃了。如果所选择的通道忙或所选择的结点的片缓冲区不可用时，那么这个头片就必须在该结点的片缓冲区中等待，直到上述两者都可用时为止，其它数据片也在原来的结点上等待。此时，被阻塞的消息不从网络中移去，片也不放弃它所占有的结点和通道。
　　全部通信的延时公式为：
T = Tf×D+L/B = (Lf /B)×D+L/B = (Lf×D+L)/B
　　式中，Lf是片的长度，Tf是一个片经过一个结点所需的时间。通常，Lf×D总是远小于L，所以可以认为：T = L/B，即延时长短与结点数的多少基本无关。
　　可以看出，虫蚀寻径有以下的优点：
　　(1) 每个结点的缓冲区较小，易于VLSI实现。
　　(2) 较低的网络传输时延。所有的片以流水方式向前传输，采用了时间并行性。而存储转发方式的消息包整个地从一个结点“跳”到另一个结点，通道的使用是串行的，所以它的传输时延基本上正比于消息在网络中传输的距离。虫蚀寻径方式的网络传输时延正比于消息包的长度，传输距离对它的影响很小。
　　(3) 通道共享性好，利用率高，对通道的预约和释放是结合在一起的一个完整的过程，有一段新的通道后将立即放弃用过的一段旧通道。
　　(4) 易于实现选播和广播通信方式。允许寻径器复制消息包的片并把它们从其多个输出通道输出。
　　然而虫蚀寻径方式也有缺点，当消息的一个片被阻塞时，整个消息的所有片都将被阻塞在所在结点，占用了结点资源，因此需要采用虚拟通道的方式来避免由此引起一连串的阻塞。
　　虫蚀寻径方式也可以分为无缓冲和有缓冲两类，区别在于缓冲的大小。缓冲大有利于性能的提高，但会增加结点的复杂度。IBM SP2采用的寻径方式就是带缓冲的虫蚀寻径方式，它采用共享的存储区来对输入/输出消息进行缓冲。
10.8.2 死锁和虚拟通道
　　虫蚀寻径多计算机网络的通信通道实际上由许多源和目的对共享。也就是说有多对通信对象使用同一条物理通道，而各结点之间建立起的连接只是一个逻辑通道，即一个虚拟的通道，图10-35形象地表示了物理与虚拟通道之间的关系。即从共享物理通道可以引出虚拟通道的概念。这一节我们将介绍这一概念并讨论它在避免死锁方面的应用。
图10-35 物理与虚拟通道之间的关系图
　　1．虚拟通道
　　虚拟通道是两个结点间的逻辑链，它由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成。图10-36说明了四条虚拟通道共享一条物理通道的概念。
图10-36 四条虚拟通道共享一条物理通道
　　源结点和接收结点各有4个片缓冲区。当物理通道分配给某对缓冲区时，这一对的源缓冲区和接收缓冲区形成了一条虚拟通道。换句话说，物理通道由所有的虚拟通道分时地共享。除了有关的缓冲区和通道之外，还必须用某些通道状态(如R/A信号)来表示不同的虚拟通道。源缓冲区存放等待使用通道的片，如图10-36中有两对片缓冲区已经分配给了两个包使用(用阴影部分标出)，也就是说在一条物理通道上，建立了两个虚拟通道。接收缓冲区存放由通道刚刚传送过来的片。通道(电缆或光纤)是它们之间的通信媒介。
　　2．死锁的产生和避免
　　缓冲区或通道上的循环等待会引起死锁，如图10-37所示。它可以分两种情况，一种是缓冲区死锁，另外一种是通道死锁。
图10-37 存储转发网络中所产生的缓冲区死锁
　　四个消息A、B、C、D包占用了四个结点的四个缓冲区，各自的消息包分别向C、D、B、A结点发送消息。开始时，结点的缓冲区都是空的，所以4个结点都沿逆时针方向向下一个结点发出数据包。如图中所示的时刻，B结点中存放是A结点要发送给C结点的数据包，记作(A，C)；C结点中存放是(B，D)；D结点中存放是(A，C)；A结点中存放是(D、B)。此时，4个缓冲区都已充满，按照握手信号的规定，这时4个结点都是向前一个结点发出禁止传输的信号。于是形成缓冲区的相关环，导致循环等待。除非扬弃某个消息包或者某个包的寻径出错，否则死锁不会解除。其死锁时示意图如10-38所示
　　那么如何避免死锁呢？
　　由于死锁是循环等待造成的，因此可以用破坏循环的方法来打破死锁。解决死锁问题的方法是增加虚拟通道，根据虚拟通道的含义，如果在结点上增加一个缓冲区，就相当于多了一条虚拟通道，图10-39所示为利用虚拟通道将通道相关图中的环路变成螺旋线来避免死锁的方法。
图10-39 存储转发方式增加虚拟通道规避死锁示意图
　　图10-40所示为四个通道之间因循环等待而出现了死锁。图中结点表示通道，带方向的箭头表示通道之间的依赖关系。图10-40(a)表示为4个通道之间因循环等待而出现了死锁；图10-40(b)表示为通道相关图，是一个环路。
图10-40 利用虚拟通道避免死锁
　　利用虚拟通道方法可以避免死锁。通过增加两条虚拟通道V3和V4，可以打破死锁循环，如图10-40(c)所示；增加虚拟通道V3和V4可得到一张修改后的通道相关图，如图10-40(d)所示，在使用通道C2之后不再使用C3和C4。
　　通道多路复用可在片一级进行，如果包长度足够的话，也可以在包一级进行。
　　虚拟通道可以用单向通道或者双向通道实现。把两条单向通道组合在一起可以构成一条双向通道，这不仅增加了利用率还可使通道的频宽加倍。然而，双向通道中的仲裁要复杂一点。用双向通道互连的相邻结点需要专用的仲裁线，用它来控制信息流的方向。
　　实际上，和单向通道相比较，双向通道由于要做方向仲裁，因而增加了延迟，又由于控制复杂，因而还增加了成本。如果网络的流量不大，则双向通道的效率比较高。虚拟通道可能会使每个请求可用的有效通道频宽降低。确定虚拟通道数目时，需要对网络吞吐量和通信时延折中考虑。实现数目很大的虚拟通道需要用高速的多路选择开关。
10.8.3 单播方式下的寻径
　　单播方式是多处理机系统中最常见的一种工作方式，其基本工作特点是实现点对点的通信。在对目的结点进行寻径的过程中，最重要的问题就是尽一切可能避免出现死锁。虽然在前面介绍了采用增加虚拟通道的方法来避免死锁，但是从更根本上看，死锁的形成在于结点之间相处循环的包冲突。在多处理机系统中，由于各处理机是以异步方式工作的，在错综复杂的通信需求中有极大的可能造成某结点的包冲突，一旦出现包冲突，并且同时满足循环堵塞的条件，那么死锁就会产生。
　　所以必需有一套解决包冲突的方法，以避免出现更严重的冲突情况。即当两个或更多的包在某个结点为竞争缓冲区或通道资源而发生冲突时，必须确定如何解决冲突的策略。这一节将考察各种不会引起拥挤或死锁现象的控制网络流量的策略。下面将以这些策略为基础，讨论为一对一通信设计的确定寻径算法和自适应寻径算法。
　　1．包冲突及其解决策略
　　通道流水线上的两个相邻结点之间要传送片时，必须具备以下三个条件。
　　条件1：源缓冲区已存有该片；
　　条件2：通道已分配好；
　　条件3：接收缓冲区准备接收该片。
　　但是当两个包到达同一个结点时，它们可能会请求用同一个接收缓冲区或者要用同一个输出通道。即当一个结点同时面对两个源结点时，就可能出现两个包同时争用一个缓冲器的现象，这就发生了包冲突(又称为包阻塞)。
　　因此必须对两个问题做出仲裁：第一是把通道分配给哪个包？第二是如何处理没有分配到通道的包？为了解决上述问题，解决包冲突的结果有四种方法，如图10-41所示为解决包冲突的四种策略。 　　
　　1) 虚拟直通寻径缓冲法
　　Kermani和Kleinrock提出了一种虚拟直通寻径(virtual cut-through routing)缓冲方法。在冲突结点中设立一个包缓冲器，足以将一个结点的整个包接收到本结点，使本结点与前一个被拒收的结点间建立一个直通的途径，但是这个途径是虚拟的。而已分配通道的包仍按正常的工作途径获得通道。如图10-41(a)所示，包2被暂时存放在一个包缓冲区。当通道可以使用时再传送包2。
图10-41 解决包冲突的四种策略
　　这种缓冲方法的好处是不会浪费已经分配的资源，但是需要一个能存放整个包的缓冲区。此外，通信路径上的包缓冲区不应形成循环。由于包缓冲区不可能做在寻径器芯片上，因此要用本地存储器作为包缓冲区，这会引起相当大的存储延迟。虚拟直通方法是存储转发和虫蚀两种寻径方法的折中。当不发生冲突时，就如同虫蚀寻径方法一样工作。在最坏情况下，效果则与存储转发寻径方法相同。
　　2) 堵塞流控制法
　　如图10-41(b)所示，对于拒绝的包采用简单的阻断方式，纯粹的虫蚀寻径在出现冲突时就采用阻塞(blocking)策略，即图中第2个包被阻塞不再前进，但是并没有被放弃。它直到通路打开为止。
　　3) 丢弃后重发法
　　如图10-41(c)所示的是丢弃(discard)策略，它简单地把被阻塞的包扬弃掉。即当出现冲突时，对于没有分配通道的包采取丢弃的方法，在通道允许后要求前结点重发。
　　4) 堵塞后迂回法
　　堵塞后迂回法又称绕道(detour)，如图10-41(d)所示。它也是一种智能方法，当一个包被阻塞时，包被送到一条绕行的通道，使其有可能通过别的结点到最终的目的结点。
　　阻塞策略的实现成本低，但可能出现分配给阻塞包的资源空闲的情况。丢弃策略可能会出现资源严重浪费，并且需要包重新发送和回答，否则被扬弃的包也许会丢失。现在已很少使用这种策略，因为包的输送率不稳定。BBN Butterfly网络采用了这种扬弃策略。绕道寻径为包寻径提供了更大的灵活性。然而，绕道可能要用更多的通道资源才能到达目的地。而且绕行的包可能进入一个活锁(livelock)循环，这将浪费网络资源。Connection Machine和Denelcor HEP采用了这种绕道策略。实际上，某些多计算机网络综合了以上某些流控制策略的优点，采用混合策略。
　　2．确定寻径和自适应寻径
　　寻径可以分为确定和自适应两类。采用确定寻径时，通信路径完全由源和目的地址确定。换句话说，寻找的路径是预先唯一确定的，与网络的状况无关。自适应寻径与网络的状况有关，可能会有几条路径。这两种寻径都需要无死锁算法。所谓“自适应”，是指2个或2个以上消息包在同一结点中发生冲突时，网络具有自动选择迂回路径的一种能力。采用自适应寻径要特别注意避免死锁。虚拟通道的概念使实现自适应寻径更经济和更灵活。
10.8.4 广播方式下的寻径　
　　多计算机网络中会出现以下四种通信模式：
　　(1) 单播(unicast)模式，对应于一对一的通信情况，即一个源结点发送消息到一个目的结点。
　　(2) 选播(multicast)模式，对应于一到多的通信情况，即一个源结点发送同一个消息到多个目的结点。
　　(3) 广播(broadcast)模式，对应于一到全体的通信情况，即一个源结点发送同一个消息到全部结点。
　　(4) 会议(conference)模式，对应于多到多的通信情况。
　　通道流量(channel traffic)和通信时延(communication latency)是描述效率常用的两个参数。通道流量可用传输有关消息所使用的通道数来表示。通信时延则用包的最长传输时间来表示。
关 联
习 题
　　10.1 解释下列概念。
并行处理 时间重叠 资源重叠 资源共享 SIMD并行处理机
共享存储器结构 分布式存储器结构 互连网络 互联函数 静态互联函数　动态互联函数 结点度数 网络直径 网络等分宽度 交叉开关 阻塞网络　非阻塞网络 存储转发寻径 虫蚀寻径 虚拟通道 自适应寻径
　　10.2 请从运算方式、体系结构方面比较SIMD与向量计算机的主要区别。
　　10.3 连续计算模型有何特点？为什么SIMD计算机比较适合此类计算？
　　10.4 在Illiac Ⅳ 上实现8×8矩阵乘法，要求J和K的循环并行完成，数据在存储器中不准重复存放，请设计能使64个处理单元全并行工作的算法。
　　10.5 设有一个向量A=(A0，A1，…，A15)，要计算其累加和S=　　。在SISD计算机上用Fortran语言表示为：
　　　　　s = 0.0
　　　　　do 10 I = 0, 15
　　10 s = s + A(i)
　　这是一个串行程序。在SISD计算机上，它要用16次加法时间。如果在阵列机上采用递归相加算法，则只需要lb16=4次加法时间就够了。首先，原始数据A(i),0≤i≤15，存放在16个PEM的a单元中，请写出阵列处理机上用成对递归相加的算法求和步骤。
　　10.6 BSP计算机是一台由16个PE和17个共享存储器模块构成的SIMD计算机。试证明：如果跳数不是17的倍数，那么对任意长度向量的访问都不会出现访问存储器冲突。
　　10.7 设16个处理器的编号为0、1、…、15，采用单级互连网络，当互联函数分别为Cube3、PM2+3、PM2-0、Shuffle时，第13号处理器与哪一个处理器相连？
　　10.8 设编号分别是0，1，2，…，F的16个处理器之间，要实现下列结点对之间的通信：(B，1)，(8，2)，(7，D)，(6，C)，(E，4)，(A，0)，(9，3)，(5，F)。试选择所用的互连网络类型、控制方式并画出该互连网络的拓扑结构和各级交换开关的状态图。
　　10.9 在一个16×16的 网络中，如果开关的控制信号为1100，那么9号结点被连接到哪个结点上？
　　10.10 假定8×8的矩阵A=(aij)顺序存放在存储单元的64个单元中，用什么样的单级互连网络可实现对该矩阵的转置变换？总共需要传送多少步？
　　10.11 对于采用级控制方式的三级立方体网络，当第i级开关(0≤i≤2)为直送状态时，不能实现哪些结点之间的通信？为什么？当第i级开关为交叉状态时，不能实现哪些结点之间的通信？
　　10.12 网络中每一个开关都是单元控制的，其连接情况由终端地址决定。
　　(1) 请说明开关控制也可以由T = S D来担任。
　　(2) 请给出实现广播连接的算法。
　　10.13 什么是死锁？发生死锁的原因有哪些？死锁与阻塞有什么区别？

展开更多......

收起↑