1、第10章 并行处理与互连网络第第10章章 并行处理与互连网络并行处理与互连网络10.1 并行处理的概念10.2 并行处理机基本结构10.3 SIMD计算机基本结构10.4 SIMD计算机的应用10.5 互连网络的概念10.6 静态互连网络10.7 动态互连网络10.8 互连网络的消息传递机制关联习题 第10章 并行处理与互连网络10.1 并行处理的概念并行处理的概念10.1.1 并行性并行性研究改进计算机系统结构的一个主要方面是如何开发出并行性。并行性(Parallelism)是指问题中具有可同时进行运算或操作的特性。如在同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的任务为并行性。
2、开发并行性的目的是为了能予以并行处理，以提高解题效率。并行性有两个含义：一是同时性(Simultaneity)，是指两个或多个事件在同一时刻发生在多个资源中；二是并发性(Concurrency)，指两个或多个事件在同一时间间隔内发生在多个资源中。第10章 并行处理与互连网络并行处理是一种有效地强调开发计算过程中并行事件的信息处理方式，是提高系统性能的主要手段之一。如在运算器中采用串行结构运算，每次进行一位运算，那么完成n位数据的运算要花费n个时间单位。如果采用并行结构，设置一个n位运算器，则用1个时间单位就可完成(理想状态下)。可以看出，在元器件速度相同的条件下，后者的速度几乎是前者的n倍。可
3、见，并行处理能大幅度地提高计算机系统的运行速度。第10章 并行处理与互连网络10.1.2 并行性的等级和分类并行性的等级和分类从不同的角度看，并行性可分为不同的类型。1从计算机系统处理数据的角度从计算机系统处理数据的角度从计算机系统处理数据的角度看，并行性等级由低到高，分别是位串字串(串行单处理机，无并行性)、位并字串(传统并行单处理机)、位片串字并、全并行。第10章 并行处理与互连网络2从计算机信息加工的各个步骤和阶段的角度从计算机信息加工的各个步骤和阶段的角度从计算机信息加工的各个步骤和阶段的角度看，并行性等级可分为如下四种：1)存储器操作并行性 存储器操作并行性是指可采用单体多字、多体交
4、叉存取等方式，在一个存储周期内访问多个字。如并行存储器和相连处理机。2)处理器操作步骤并行 处理器操作步骤并行是指指令处理器在执行取指令、分析指令、执行指令等过程中的并行。如流水线处理机。第10章 并行处理与互连网络3)处理器操作并行 处理器操作并行是指为支持向量、数组运算，可以通过重复设置处理单元进行。如阵列并行处理机。4)指令、任务、作业的并行 这种并行称为高级并行，指令级以上并行是指多个处理机同时对多条指令及有关的数据进行处理。如多指令流多数据流多处理机、分布处理系统和计算机网络等。第10章 并行处理与互连网络3从计算机系统中执行程序的角度从计算机系统中执行程序的角度从计算机系统中执行程
5、序的角度看，并行性等级由低到高，分别是指令内各微操作之间的并行、多条指令之间的并行、多个任务或进程之间的并行和多个作业或程序之间的并行。第10章 并行处理与互连网络4从系统结构发展的角度从系统结构发展的角度从系统结构发展来看，并行性等级由低到高，分别是高性能的单处理机、SIMD并行处理机、多处理机和多计算机系统、冯诺依曼计算机。按照Flynn分类法归纳的并行计算机体系结构如图10-1所示。第10章 并行处理与互连网络图10-1 并行计算机的Flynn分类图第10章 并行处理与互连网络10.1.3 开发并行性的途径开发并行性的途径可通过多种技术途径来提高计算机系统的并行性。通常以时间重叠、资源重
6、复和资源共享为开发并行性的三个主要途径。第10章 并行处理与互连网络1时间重叠时间重叠(Time Interleaving)时间重叠是在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度，如指令内部各操作步骤采用重叠流水的工作方式。一条指令的解释分为取指、分析、执行三大步骤，分别在相应的硬件上完成。只要不出现相关，则每过一个t时间，就可以流出结果，从而加快了程序的执行速度。这种时间重叠技术原则上不需要增加更多的硬件设备就可以提高计算机系统的性能价格比。第10章 并行处理与互连网络2资源重复资源重复(Resource Rep
7、lication)资源重复是在并行性中引入空间的因素。它是靠重复设置硬件资源来提高可靠性或性能的，如通过使用两台或多台完全相同的处理机或计算机完成同样的任务来提高性能。典型的例子是双工系统、相连处理机和阵列处理机等。第10章 并行处理与互连网络3资源共享资源共享资源共享是用软件方法让多个用户共用同一套资源，通过提高系统资源的利用率来提高系统的性能和效率。典型的例子是多道程序分时系统，它是利用共享CPU、主存资源以降低系统价格来提高设备利用率的一个实例。例子还包括计算机网络和分布处理系统等。沿时间重叠途径，多个处理机进行流水线构成的多处理机，一般都是非对称型或异构型的；沿资源重复途径，构成的相联
8、处理机和阵列处理机都是对称型或同构型的多处理机；沿资源共享途径发展的多处理机则既可以是同构型的，也可以是异构型的。第10章 并行处理与互连网络10.2 并行处理机基本结构并行处理机基本结构并行处理机也称阵列机，采用资源重复的并行性措施实现。并行处理机将大量重复设置的多个处理单元PE(Processing Element)按一定方式互连成阵列，在统一的控制部件CU(Control Unit)控制下，对各自所分配的不同数据并行执行同一指令规定的操作，是操作并行的SIMD(单指令流多数据流)计算机。它采用资源重复的措施开发并行性，是以SIMD方式工作的。这里的PE是指不带指令控制部件的算术逻辑运算单
9、元。第10章 并行处理与互连网络10.2.1 并行处理机的两种典型结构并行处理机的两种典型结构并行处理机通常由一个控制器(Control Unit，CU)、N个处理单元(Processing Element，PE)、M个存储模块以及一个互连网络部件(Inter Connection Network，ICN)组成。根据其中存储器模块的分布方式，并行处理机可分为两种基本结构：分布式存储器的并行处理机和共享存储器的并行处理机。这两种结构的共同特点是在整个系统中设置多个处理单元，各个处理单元按照一定的连接方式交换信息，在统一的控制部件作用下，各自对分配来的数据并行地完成同一条指令所规定的操作。下面分别
10、对这两种基本结构进行介绍。第10章 并行处理与互连网络1分布式存储器结构并行处理机分布式存储器结构并行处理机分布式存储器结构并行处理机具备四个特点：包含重复设置的多个同样的处理单元PE，通过数据寻径网络以一定方式互相连接；各PE都拥有自己的局部存储器(Processing Element Memory，PEM)，存放被分配的数据并只能被本处理单元直接访问；在统一的阵列控制部件作用下，实现并行操作；程序和数据通过主机装入控制存储器。由于通过控制部件的是单指令流，所以指令的执行顺序还是和单处理机一样，基本上是串行处理。其结构图如图10-2所示。第10章 并行处理与互连网络图10-2 分布式存储器的
11、并行处理机结构图第10章 并行处理与互连网络这种结构的并行处理机处理单元的数目和存储体的数目是相同的，每个处理单元仅和自己的存储体相连，直接交换数据。在实现时，为了有效地进行高速处理，数据应在各存储体间合理分配，使各处理单元都可以依靠自身存储体中的数据进行运算。各数据单元之间交换数据是经过两条途径相互联系：一条是直接通过互连网络；另外一条是如果在某个存储体中存有各处理单元都需要的公共数据，则可以通过将处理单元局部存储体PEM读入控制单元，然后通过公共数据总线“广播”到全部处理单元中。在处理单元很多的并行处理机中，PE之间的互连网络只能是有限而固定的连接。第10章 并行处理与互连网络ILLIAC
12、-IV是这种结构的SIMD机器，它由64个本地存储器的PE组成，PE间通过88环绕连接网格实现互连，因而也称为阵列处理机，其处理速度达每秒150106次64位浮点加法运算。各种SIMD机器的主要差别在于进行PE之间互相通信的数据寻径网络不同。目前的大部分并行处理机是基于分布式存储器模型的系统。第10章 并行处理与互连网络2共享存储器并行处理机共享存储器并行处理机共享存储器并行处理机结构有M个存储体构成统一的并行处理机存储器，经过互连网络ICN连接，为全部处理单元PE0PEn-1所共享，其结构图如图10-3所示。第10章 并行处理与互连网络图10-3 共享存储器的并行处理机结构图第10章 并行处
13、理与互连网络为了使各处理单元能同时对向量的各个元素进行并行处理，一般都使存储体的数量M大于或等于处理单元的数量n。同时，在存储体之间合理分配数据，使各处理单元数据能来自不同的存储体，从而受存储器冲突的影响最小。从图10-3中可以看出，在这种结构中，互连网络是处理单元和存储器之间交换数据的通道，它提供多种连接方式，每个处理单元之间的数据传送使大多数向量运算不受影响。同时也可以看到，这种互连网络是复杂的，因此，这种结构在处理单元数量不大的情况下是很理想的。如Burroughs公司和伊利诺斯大学在1979年研制的科学处理机BSP，就属于这种结构，它有16个处理单元，17个存储体，最高的向量运算速度可
14、达50106次浮点加法运算。第10章 并行处理与互连网络10.2.2 并行处理机的特点并行处理机的特点并行处理机利用多个处理单元对向量或数组所包含的各个分量同时进行运算，从而易于获得很高的处理速度。与同样擅长于向量处理的流水线处理机相比，并行处理机有如下特点：1多处理单元的互连网络连接多处理单元的互连网络连接互连网络是并行处理的最有特色的一个组成部分，它规定了处理单元的连接方式，决定了并行处理能适应的算法类别，对系统整体的各项性能指标产生了重要的影响。第10章 并行处理与互连网络2依靠资源重复并行措施依靠资源重复并行措施并行处理机获得高速度的主要原因就是使用大量的处理单元对向量所包含的各个分量
15、进行运算，每一个处理单元要负责多种处理功能，相当于向量处理机中的多功能流水线部件，但其效率要比单个的功能流水线低。因此，只有在硬件价格降低和系统结构不断改进，并行处理机才具有较好的性能价格比。3同时性同时性并行处理机的每个处理单元在同一时刻要同等地担负起各种运算功能，相当于向量处理机的多功能流水线部件那样，但其效率(设备利用率)可能没有多个单功能流水线部件那样高。第10章 并行处理与互连网络4运算速度高运算速度高主要是靠增大处理单元个数，与依靠缩短时钟周期的向量流水线处理机来说，速度提高的潜力要大得多。正像并行处理机的特点描述一样，并行处理机主要是由处理单元代替了向量处理机中的流水线，用设备的
16、重复设置达到高速运算的目的。事实上，SIMD计算机正是属于多处理单元的这一类，下面将重点介绍SIMD计算机的结构与设计。第10章 并行处理与互连网络10.3 SIMD计算机基本结构计算机基本结构SIMD计算机属于多处理机单元范畴，它含一个控制单元、多个处理单元，取指令在控制单元的作用下进行，取出的指令经分析译码后送给各处理器协作完成任务，也就是说，指令流是单独的，数据流是多倍的。下面着重以典型SIMD计算机为例介绍其发展进程、结构和设计。第10章 并行处理与互连网络10.3.1 SIMD计算机模型计算机模型SIMD计算机的抽象模型可以理解为：在同一个控制部件管理下，有多个处理单元，所以处理单元
17、均收到从控制部件广播来的同一条指令，但操作对象是不同的数据。H.J.Siegel提出了SIMD计算机的操作模型，如图10-4所示。第10章 并行处理与互连网络图10-4 SIMD计算机的操作模型第10章 并行处理与互连网络SIMD计算机的操作模型可用五元组表示：M=(N,C,I,M,R)，其字母所代表的含义如下：N为机器的处理单元(PE)数。例如，Illiac采用64个PE，连接机(Connection Machine)CM-2采用65536个PE。C为由控制部件(CU)直接执行的指令集，包括标量和程序流控制指令。I为由CU广播至所有PE进行并行执行的指令集，它包括算术运算、逻辑运算、数据寻径
18、、屏蔽以及其它由每个活动的PE对它的数据所执行的局部操作。M为屏蔽方案集，其中每种屏蔽将PE集划分为允许操作和禁止操作两种子集。R是数据寻径功能集，说明互连网络中PE间通信所需要的各种设置模式。第10章 并行处理与互连网络10.3.2 SIMD计算机发展过程计算机发展过程Illiac是最先采用SIMD计算机结构的计算机。它分成两个分支，一个是用位线PE制造的SIMD计算机，如Goodyear MPP、AMT/DSP610和TMC/CM-2，CM-5是以SIMD模式运行的同步SIMD计算机；另外一个是用字宽运算PE的中粒度SIMD计算机，如BSP是16台处理机和17个存储模块同步工作的共享存储S
19、IMD计算机，MasPar MP-1是中粒度SIMD计算机。SIMD计算机的发展过程如图10-5所示。第10章 并行处理与互连网络图10-5 SIMD计算机的发展过程图第10章 并行处理与互连网络10.3.3 Illiac 计算机计算机Illiac阵列机是世界上最早采用SIMD结构设计的计算机，由美国宝来公司(Burroughs)和伊利诺斯大学于1965年合作研制，并于1972年生产。Illiac系统结构如图10-6所示。第10章 并行处理与互连网络图10-6 Illiac 的系统结构框图第10章 并行处理与互连网络Illiac由两大部分组成，即Illiac阵列和Illiac输入/输出系统。具
20、体来讲，它是由三种类型处理机联合组成的多机系统：一是专门对付数组运算的处理单元阵列(Processing Element Array)；二是阵列控制器(Array Control Unit)，它既是处理单元阵列的控制部分，又可以看做是一台相对独立的小型标量处理机；三是一台标准的Burrouths B6700计算机，担负Illiac输入/输出系统和操作系统的管理功能。第10章 并行处理与互连网络1Illiac阵列阵列Illiac阵列处理器采用分布式存储器结构。每个处理单元配有专用的存储器模块，共由64个处理单元、64个处理单元存储器和存储器逻辑部件所组成。这个阵列的64个处理部件PU0PU63排
21、列成88的方阵，每一个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章 并行处理与互连网络图10-7 Illiac各处理单元阵列结构的闭合螺线连接方式第10章 并行处理与互连网络这种连接方式既便于一维长向量(最多64个元素)
22、的处理，又便于两维数组运算，从而缩短处理单元之间数据传送的路径距离。在这个阵列中，任意两个单元之间的数据传送步距不超过7步。一般来讲，这种闭合螺线结构的连接方式，有nn个单元组成的阵列中，任意两个处理单元之间的最短距离不会超过(n-1)步。例如，从PU10到PU45的距离以下列路径为最短：PU10PU1PU57PU56PU48PU47PU46PU45 第10章 并行处理与互连网络处理单元数组处理的运算部分，可对64位、32 位和8位操作数进行多种算术和逻辑操作，包括48位、24位或8位定点运算。处理单元存储器PEM分属每一个处理单元，各有204864位的存储容量和不大于350ns的取数时间。6
23、4个PEM联合组成阵列存储器，存放数据和指令。PE和PEM之间经过存储器逻辑部件MLU相连，这些部件用于处理机与存储模块接口的逻辑电路，它包含存储器信息寄存器和有关控制逻辑线路，用于实现PEM分别与PE、CU以及I/O之间的信息传送。第10章 并行处理与互连网络2阵列控制器阵列控制器阵列控制器CU实际上是一台小型控制计算机。它除了对阵列的处理单元实行控制以外，如发控制信号、广播公共地址、广播公共数据，还能利用本身的内部资源执行一整套指令，用以完成标量操作，在时间上与各PE的数组操作重叠起来。因此，控制器的功能有以下五个方面：(1)对指令流进行控制和译码，包括执行一整套标量操作指令；(2)向各处
24、理单元发出执行数组操作指令所需的控制信号；(3)产生和向所有处理单元广播公共的地址部分；(4)产生和向所有处理单元广播公共的数据；(5)接收和处理由各PE(如计算出错时)、系统I/O操作以及B6700所产生的陷阱中断信号。第10章 并行处理与互连网络Illiac阵列控制器CU与处理单元阵列之间的信息联系有以下四条信息通路：1)CU总线处理单元存储器PEM经过CU总线把指令和数据送往阵列控制器，以8个64位字为一信息块。这里指令是指分布存放在阵列存储器中用户程序的指令；而数据可以是处理所需的公共数据，先将它们送到CU，再利用CU的广播功能送到各处理单元。第10章 并行处理与互连网络2)公共数据总
25、线CDB(Common Data Bus)这是64位总线，用作向64个处理单元同时广播公共数据的通路。3)模式位线(Mode Bit Line)每一个单元都可以经过模式位线把它的模式寄存器(mode register)状态送到CU中，送来的信息中也包括该处理单元的“活动”状态位。只有那些处于“活动”状态的处理单元才执行单指令流所规定的公共操作。4)指令控制线处理单元微操作控制信号和处理单元存储器地址、读/写控制信号都经过约200根指令控制线由CU送到阵列处理单元PE和存储器逻辑部件MLU中。第10章 并行处理与互连网络3输入输入/输出系统输出系统Illiac输入/输出系统由磁盘文件系统DFS(
26、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之间的缓冲，以平衡两边不同的数
27、据宽度。CDC的功能是对阵列控制器的I/O请求进行管理。BIOM处在DFS和B6700之间，作为缓冲，使两者的传送频带匹配。第10章 并行处理与互连网络B6700管理计算机一般配置一个CPU(另一CPU可选)、32K字内存(最大可扩充至512K字)和经过多路开关控制的一大批外围设备(包括一台容量为1012位的激光外存储器以及ARPA网络接口)。B6700的作用是管理全部系统资源，完成用户程序的编译或汇编，为Illiac进行作业调度、存储分配、产生入/出控制描述字并送至CDC、处理中断，以及提供操作系统所具备的其它服务等。第10章 并行处理与互连网络10.3.4 BSP计算机计算机BSP(Bur
28、roughs Scientific Processor)是美国Burroughs公司和伊里诺大学合作设计的用于科学计算的并行处理机，于1979年生产。与Illiac不同，这台计算机是采用共享集中式主存结构，是共享存储器SIMD结构的典型代表。BSP计算机系统组成如图10-8所示。它由系统管理计算机B7700/B7800和BSP处理机两大部分组成。第10章 并行处理与互连网络图10-8 BSP科学计算机系统结构图第10章 并行处理与互连网络BSP不能够单独工作，而是作为管理机B7700/B7800的后台机工作的。BSP大部分与分布式相同，区别是它的系统的存储器是由K个存储体(M0Mk-1)集中在
29、一起构成的，经过互连网络ICN为全部N个处理单元(PE0PEN-1)所共享。第10章 并行处理与互连网络这种结构形式中，为使各处理单元对长度为N的向量中的各个元素都能同时并行处理，存储体的个数K通常总是等于或多于处理单元的个数N。为了各处理单元在访问主存时，尽可能避免发生分体冲突，也要求有合适的算法能够将数据按一定规律合理地分配到各个存储体中。与分布式存储器结构另一个不同之处在于互连网络ICN的作用不同。集中式主存的结构形式中，互连网络是用来连接处理单元和存储器分体之间的数据通路的，希望能让各个处理单元以高速、灵活的方式连到不同的存储体上。因此有的并行处理机系统将其称为对准网络(Alignme
30、nt Network)。第10章 并行处理与互连网络BSP系统采用了全面并行化操作，即把资源重复和时间重叠两种并行性技术结合起来，有人将其称为第二代并行处理机。BSP科学处理机系统由系统管理机(又称系统资源机)和科学处理机两大系统构成。系统管理机担负BSP编译、任务调度、数据通信、外部设备管理等任务，而科学处理机本身又包括控制处理机、文件存储器及并行处理机三大部分。第10章 并行处理与互连网络1BSP处理机的组成处理机的组成BSP处理机可分为4个部分，即并行处理机、控制处理器、文件存储器和对准网络。1)并行处理机并行处理机包含16个算术单元、由17个存储模块(与16最接近的质数)组成的一个无冲
31、突访问的并行存储器和一套对准网络。第10章 并行处理与互连网络并行机中每个处理器以160 ns的时钟周期进行向量计算。所有16个算术单元AE对不同的数据组(从并行处理机控制器广播来)进行同一种指令操作，大部分的算术运算能在2个时钟周期(320 ns)内完成。进行向量运算的数据是存在17个并行存储器模块中的，每个模块的容量可达512千字，17个存储器模块的组织形成了一个无冲突访问存储器，它容许对任意长度以及跳距不是17倍数的向量实现无冲突存取。第10章 并行处理与互连网络2)控制处理器控制处理器是一台用于控制的计算机，其核心是标量处理单元，处理机的时钟频率是1MHz。它除了用以控制并行处理机以外
32、，还提供了与系统管理机相连的接口。标量处理机则处理存储在控制存储器中的全部操作系统和用户程序的指令，即指令/控制存储器。第10章 并行处理与互连网络3)文件存储器文件存储器是一个半导体辅助存储器，是一个高速大容量外存储器，是唯一置于BSP直接控制下的外围设备。BSP的计算任务文件由系统管理机加载，然后对这些任务进行排队，由控制处理机取出并加以执行。BSP在运行过程中产生的输出文件和中间结果也都暂存于文件存储器中，由于读写速度较快，可很好地解决处理机和外设之间的带宽瓶颈。第10章 并行处理与互连网络4)对准网络对准网络包涵完全交叉开关以及用来实现数据从一个源广播至几个目的地以及当几个源寻找一个目
33、的地址时能分解冲突的硬件。这就需要在算术单元阵列和存储器模块之间具备通用的互连特性，而存储模块和对准网络的组合功能则提供了并行存储器的无冲突访问能力。算术单元也利用输出对准网络来实现一些诸如数据压缩和扩展操作以及快速傅立叶变换算法等专用功能。第10章 并行处理与互连网络2BSP的并行存储器的并行存储器BSP并行存储器又称为质数存储系统，由17个存储模块组成，存储周期为160ns。BSP并行存储器的无冲突访问是它的一个独特的技术性能。其实现的硬件技术包括：质数个存储器端口(BSP并行存储器的存储体数是一个质数17)、存储器端口和AE之间的完全交叉开关(对准网络)以及特殊的存储器地址生成机构。第1
34、0章 并行处理与互连网络3BSP的并行流水技术的并行流水技术BSP系统采用了全面的并行性技术，它并不依靠提高时钟频率获得高速，而是依靠并行性。在BSP中，存储器存储器型的浮点运算是流水进行的。BSP的流水线组织由5个功能级组成，尤其是并行处理机由16个处理单元、17个存储器模块和2套互连网络(亦称对准网络)组合在一起，形成了一条五级的数据流水线，使连续几条向量指令能在时间上重叠起来执行。其结构示意图如图10-9所示，五级的功能作用依次是：第10章 并行处理与互连网络 由17个存储器模块并行读出16个操作数；经对准网络NW1将16个操作数重新排列成16个处理单元所需要的次序；将排列好的16个操作
35、送到并行处理单元完成操作；所得的16个结果经过对准网络NW2重新排列成17个存储器模块所需要的次序；写入存储器。第10章 并行处理与互连网络图10-9 BSP数据流水线结构示意图第10章 并行处理与互连网络在读与写存储器时两套对准网络NW1/2的作用分别是，使得并行存储器中为保证无冲突访问而错开存放的操作数顺序能够与算术单元并行处理要求的正常顺序一致。整个流水线由统一的指令译码和控制部件进行控制。这种流水线结构是很新颖的，对提高系统处理效率起着很大的作用。BSP还有一个高效率的FORTRAN编译程序，具有很强的向量化功能，对程序中隐含的并行性保证有较高识别率。向量程序不但能够处理明显的数组操作
36、，还能处理线性递归，循环内部的条件分支等进程，并产生明显的加速效果。第10章 并行处理与互连网络10.3.5 CM-2计算机计算机CM-2是Thinking Machines Co-operation于1987年推出的Connection Machine系列机中的一台高档机，是一台细粒度的SIMD计算机，它由数千个位片PE组成，它的峰值处理速度超过10 Gflo/s，它的系统结构如图10-10所示。第10章 并行处理与互连网络图10-10 CM-2的系统结构图第10章 并行处理与互连网络所有程序从前端开始执行，当需要并行数据操作时，发送微指令到后端处理阵列。定序器(sequencer)分解这些
37、微指令并且把它们广播给阵列中的所有数据处理器(data processor)。前端机和处理阵列之间有三条交换数据计算结果的通路：广播总线(broadcasting)、全局组合总线(global combining)和标量存储器总线(scalar memory bus)，其组成部分介绍如下。第10章 并行处理与互连网络1处理阵列处理阵列CM-2是一台数据并行计算的后端机。处理阵列包含4K到64K个位片数据处理器，所有数据处理器都由定序器控制。定序器对来自前端机的微指令进行译码，然后把毫微指令广播到阵列中各个处理器。所有处理器可以同时访问它们的存储器，它们以锁步方式执行广播来的指令。处理器之间通过
38、寻径、NEWS网格(NEWS gird)或扫描机构(scanning mechanism)相互交换数据。这些网络也与I/O接口相连。称为数据穹(data vault)的大容量存储器子系统与I/O相连，它可存储多达60G字节的数据。第10章 并行处理与互连网络2寻径器、寻径器、NEWS网格和扫描机构网格和扫描机构CM-2处理机间能够快速高效地通信，主要通过下列技术构造的互联网络来实现。1)寻径器每个处理器芯片包含一个用于处理器之间数据寻径的专门硬件。把所有处理器芯片上的寻径器结点用线连在一起形成一个布尔n-立方体。在CM-2最大配置时，所有处理器芯片上共有4096个寻径器结点，连成一个12维的超
39、立方体。第10章 并行处理与互连网络2)NEWS网格每个处理器芯片中的16个物理处理器可以排列成82、116、44、422或2222等形式的网格。规定每个物理处理器有64个虚拟处理器。可以想象这64个虚拟处理器在芯片中排列成88网格。3)扫描机构 除了通过超立方体寻径器可以动态地重构NEWS网格外，CM-2还有专门的硬件支持对整个NEWS网格的扫描或传播。这些都是很有效的并行操作，在整个阵列中进行快速的数据组合和传播。第10章 并行处理与互连网络3输入输入/输出系统输出系统Connection Machine不仅强调计算的大规模并行性，还强调计算结果的可视化。216条高速I/O通道用于数据和/
40、或图像I/O操作。连接到I/O通道的外围设备包括数据穹、CM-HIPPI系统、CM-IOP系统和VME总线接口控制器，如图10-10所示。数据穹(Data Vault)是基于磁盘的海量存储系统，用来存放程序文件和大数据库。第10章 并行处理与互连网络CM-2已经用于解决几乎所有MPP所面临的具有重大挑战性的应用问题。特别是Connection Machine系列已经用于借助相关反馈技术的文档检索、基于记忆的推理，如用在医疗诊断系统QUACK中摸拟诊断疾病以及处理工作量很大的自然语言等。CM-2的其他应用包括SPICE的VLSI电路分析和布线、计算流体动力学、信号/图像/视觉处理和集成、神经网络
41、模拟和连接模型、动态规划，上下文无关文法分析、射线追踪图以及计算几何等问题。第10章 并行处理与互连网络10.4 SIMD计算机的应用计算机的应用10.4.1 计算模型及有限差分计算模型及有限差分哈辛诺在1986年将物理计算模型分成连续模型和离散模型(粒子模型)。连续模型是指所有计算的时间和空间是连续变化的物理量，且这些物理量是一定范围内的平均值。典型的参数如电荷密度、温度和压力等。粒子模型则将世界看成是由离散的粒子组成的，这些物理量反映单个粒子的当前状态，典型的参数如速度、力和动量等。两种模型只是对同一问题的两种不同观察方法而已。第10章 并行处理与互连网络连续模型和离散模型的主要区别是：连
42、续模型符合偏微分方程，按离散形式处理时，方程式中所有变量的变化都是其近邻变量的函数，远程变量没有直接的影响。先通过作用于近邻变量，近邻变量再作用于随后的近邻变量，由此向前非直接地作用于整个媒质，也就是通过局部作用而将作用传送到整个媒质。离散模型(粒子模型)允许粒子受远程粒子的影响。任何粒子在任何时刻都与模型中的其它粒子有关。第10章 并行处理与互连网络应用有限差分方法求解连续模型对于并行计算具有很大的吸引力。有限差分方法是求解偏微分方程的一种有效方法，它把一个有规则的网格履盖在整个模型域上，用网格点上变量值写出差分方程组，以代替连续模型的偏微分方程来进行计算。作为连续模型，在解决物理问题时，我
43、们描述以下平面域的拉普拉斯方程：0yUxU2222第10章 并行处理与互连网络将这个方程离散化，即在x和y方向上每隔一段相同的距离h取一个样值点，这个微分方程就可以用差分方程的形式表示。下面就是二阶偏导数表示为差分形式，式中(x,y)为平面直角坐标，h为网格间距。222222h)hy ,x(U)y ,x(U2)hy,x(UyU h)y ,hx(U)y ,x(U2)y ,hx(UxU第10章 并行处理与互连网络把上述差分方程代入原方程，则可得有限差分计算公式为4)hy ,x(U)y ,hx(U)hy ,x(U)y ,hx(U)y ,x(U第10章 并行处理与互连网络Illiac的阵列结构特别适用
44、于计算在网格上定义的有限差分函数。这是因为，根据拉普拉斯方程，任一网格点(x,y)上的函数值均可由其四周邻近点的函数值计算出来，这一要求正好反映了阵列处理机每个处理单元与其4个近邻连接的性质。实际计算时，应利用张弛法进行。每一网格点上的函数值用求其四邻平均值的方法计算，经多次迭代，逐次逼近其最终的平均值。网格边缘的函数值是已知的，由场域的边界条件决定；而对于内部各点的函数值，开始时可选择为零，然后根据拉普拉依方程多次迭代求U(x,y)值，直至连续二次迭代所求值的差小于规定误差为止(已知迭代过程是收敛的)。第10章 并行处理与互连网络Illiac在计算时，是把内部网格点分配给各个处理单元的。因此
45、，上述计算过程可以并行地完成，从而可成倍地提高处理速度。由于实际问题中所遇到的内部网格点数目很大，因此需将其分成许多子网格，然后才能在Illiac上求解。第10章 并行处理与互连网络10.4.2 阵列处理机的几种基本算法阵列处理机的几种基本算法1矩阵加矩阵加在阵列处理机上，实现矩阵加的算法是最简单的一维数组运算。设A和B是nn阶矩阵，A、B相加的和矩阵为C，它也是nn阶矩阵。矩阵加的算法为A+B=C其中cij=aij+bij。第10章 并行处理与互连网络2矩阵乘矩阵乘设A和B是nn阶矩阵，A、B的乘积矩阵C也是nn阶矩阵。矩阵乘的传统串行算法为AB=C，cij=aikbkj其中，0in-1且0
46、jn-1。1n0k第10章 并行处理与互连网络3累加和累加和累加和并行算法是将N个数的顺序相加过程变为并行相加过程。串行求和的FORTRAN程序如下：C(-1)=0DO 10 I=0，N10 C(I)=C(I-1)+A(I)在并行处理机上，采用递归加法，FORTRAN程序如下：DO 10 I=0，lbN-110 A=A+SRL(A,2*I)；把A向量逻辑右移2i个PE，只需做lbN次加法。第10章 并行处理与互连网络例如，当N=8时，在SISD计算机要用8次加法时间。如果在并行处理机上，采用成对递归相加的算法，则只需lb8=3次加法时间就够了。首先，原始数据A(I)，0I7，存放在8个PEM的
47、a单元中，然后按照下面的步骤求累加和：第一步 置全部PE为活动状态；第二步 全部A(I),0I7,从PE的a单元读到相应PE的RGA中；第三步 令K=0；第四步 全部PE的(RGA)转送到RGR；第五步 全部PE的(RGR)经过互连网络向右传送2k步距；第六步 j=2k-1-1；第七步 置PE0至PEj为不活动状态；第10章 并行处理与互连网络第八步 处于活动状态的PE执行(RGA):=(RGA)+(RGR)操作；第九步 k:=k+1；第十步 若k3，则转回第四步，否则继续往下执行；第十一步 置全部PE为活动状态；第十二步 全部PE的(RGA)存入相应PEM的a+1单元中。采用SIMD并行算法
48、，运算速度提高，加速比为N/lbN倍，运算次数增加。从N次增加到NlbN次，效率降低，实际效率为1/lbN。例如当N=1024，速度提高100倍，运算参数增加10到倍，效率只有1/10。如果N=220，即100万个数求和，速度可以提高5万倍。第10章 并行处理与互连网络10.5 互连网络的概念互连网络的概念互连网络是一种由开关元件按照一定的拓扑结构和控制方式将集中式系统或分布式系统中的结点连接起来所构成的网络，这些结点可能是处理器、存储模块或者其他设备，它们通过互连网络相互连接并进行信息交换。互连网络已成为并行处理系统的核心组成部分，它对并行处理系统的性能起着决定性的作用。第10章 并行处理与
49、互连网络10.5.1 互连网络的基本概念和作用互连网络的基本概念和作用在多计算机系统中，无论是处理机之间，还是处理器与存储器之间，都要通过互连网络实现信息交换。决定互连网络性价比的主要因素是结构复杂性(反应成本)和通信频带及结构灵活性(反应性能)第10章 并行处理与互连网络如果我们把处理单元或存储体看成结点(Node)，互连网络则为输入和输出二组结点之间提供一组互连或映射(Mappings)。对于有N个输入结点和M个输出结点的情况，从输入到输出的映射可定义出NM种映射的互连网络，我们称之为广义互连网络(Generailsed Connection Network)。图10-11画出了3个输入结
50、点和2个输出结点的广义互连网络。它的映射关系可以分为两类：一对多的映射(见图10-11(a)，一是一对一映射(见图10-11(b)。如果只有一对一映射，则共有N！种映射。对于有N！种映射的互连网络，我们称之为连接网络(Connection Network)或全排列网络。第10章 并行处理与互连网络图10-11 3个输入结点和2个输出结点的网络映射第10章 并行处理与互连网络实现广义互连网络的直观方法是全交叉开关网络(Full Crosser Network)。它是互连网络中最通用的一种形式，图10-12显示了具有4个输入和4个输出的全交叉开关网络。对于任一输入和输出之间，都有一个交叉点，每个交
