第九章 并行处理技术
本章讲述的重点内容就是阵列处理机和多处理机，对阵列机的基本结构、主要特点、以及阵列机的互连网络和并行存储器的无冲突访问等内容要加强理解。本章应掌握的概念有：阵列处理机、网络拓扑结构、单级立方体网络、多级立方体网等。
一、并行处理技术（识记）：
并行性主要是指同时性或并发性，并行处理是指对一种相对于串行处理的处理方式，它着重开发计算过程中存在的并发事件。
并行性通常划分为作业级、任务级、例行程序或子程序级、循环和迭代级以及语句和指令级。作业级的层次高，并行处理粒度粗。粗粒度开并行性开发主要采用MIMD方式，而细粒度并行性开发则主要采用SIMD方式。
开发计算机并行性的方法主要有：资源重复、时间重叠和资源共享三种方法。
二、SIMD并行计算机（阵列处理机）
阵列机也称并行处理机。它将大量重复设置的处理单元按一定方式互连成阵列，在单一控制部件CU（Contrul Unit）控制下对各自所分配的不同数据并行执行同一指令规定的操作，是操作并行的SIMD计算机。它采用资源重复的措施开发并行性。是以SIMD（单指令流多数据流）方式工作的。
1、阵列机的基本结构（识记）
阵列机通常由一个控制器CU、N个处理器单元PE（Processing Element）、M个存储模块以及一个互连网络部件（IN）组成。根据其中存储器模块的分布方式，阵列机可分为两种基本结构：分布式存储器的阵列机和共享存储器的阵列机（理解二者不同之处）。
阵列机的主要特点：
它采用资源重复的方法引入空间因素，这与利用时间重叠的流水线处理机是不一样的。它是利用并行性中的同时性而不是并发性，所有的处理单元必须同时进行相同操作（资源重复同时性）（我们想象一下亚运会的开幕式大型团体操表演，每个人就是一个PE，他们听从一个总指挥的指令，同时进行自己的操作，很快地就能"计算"出一个结果（队形）来。）
它是以某类算法为背景的专用计算机，基本上是专用于向量处理的计算机（某类算法专用机）。
阵列机的研究必须与并行算法研究密切结合，以使它的求解算法适应性更强一些，应用面更广一些（并行算法合研究）。
陈列机实质上是由专门对付数据组运算的处理单元阵列组成的处理机（M个PE）、专门从事处理单元阵列的控制及标量处理机（控制器CU）和专门从事系统输入输出操作及操作系统管理的处理机三部分构成的一个异构型多处理机系统（三个部分成异构）。
2、阵列机的并行算法（领会）
阵列机的算法是与结构紧密联系在一起的，阵列机上常用的算法有矩阵计算、图象处理等，我们对教材中举的两种算法要领会，特别是累加和递归操作，不难理解。它就是使各个处理器同时进行加的操作，但并不是全部处理器都参加运算，在处理时，根据累加计算的需要，由控制器CU借助屏蔽的方式将一部分PE设置成不活动的状态。这种累加操作的速度提高倍数是N/log2N倍。
3.典型的SIMD计算机
对图9.6要加以领会，对于ILLIAC-IV的互连方式，若给你N个PE，请你画出各个PE 的连接，行不行？这种阵列中，任意两个单元之间的最短距离不超过根号N减去1步。这种计算机就是前面说的分布式存储器了阵列处理机。
另一种典型结构BSP结构。它的主要特点是将资源重复和时间重复结合起来开发并行性。这种结构就是集中式共享存储器的阵列处理机。
4.SIMD计算机的互连网络（简单应用）
在阵列机中，各个处理单元和存储模块之间都要经过网络交换信息。衡量互连网络性能好坏的主要因素是它的连接度、延时性、带宽、可靠性和成本。好象我们现在用的互联网，没有一项性能指标令人满意呀。
设计互连网时应考虑的四个特征是：
通信工作方式：有同步、异步及同/异步组合等三种。阵列机都采用同步工作方式，也就是各种命令的广播和并行操作都由统一的时钟加以同步控制。
控制策略：集中和分散两种。SIMD阵列机一般采用集中控制。
交换方式：线路交换和分组交换（又称包交换）以及线路/包交换组合三种。SIMD一般采用线路交换方式。而我们现在用的互联网多采用分组交换方式。我们的互联网可算是一个MIMD多机系统。
网络拓扑：指的是互连网络入、出端可以实现的连接的模式，有静态和动态两种。在阵列机中，采用的是动态拓扑。
动态网络有单级和多级两类。动态单级网络只有有限几种连接，必须经循环多次通过，才能实现任意两个处理单元之间的信息传送，故称此动态单级网络为循环网络。动态多级网络是由多个单级网络串联组成，以实现任意两个处理单元之间的连接。将多级互连网络循环使用可实现复杂的互连。
现在的绝大多数阵列机都采用多级互连网络或多级循环互连网络。为反映互连特性，每种互连网络可用一组互连函数定义。
首先学习3种基本的单级互连网络。它们是立方体、PM2I和混洗交换单级网络。
1.立方体单级网络（交换互连网络）
立方体的每一个顶点代表一个处理单元，共有8个处理单元，用直角坐标系上zyx三位二进制码编号。
互连函数E（X）k=（bn-1……~bk……b0 ） 即把二进制编码的第k位变反就可得到，它共有n=log2N种互连函数，当n=3时，就得到上面的立方体单级互连网络。从一个结点到另一个结点的最大距离为n.（教材p193称"最短距离"应改为"最大距离"）
2.PM2I互连网络（加减2i单级互连网络，即（Plus-Minums2i）
又称循环移数网，它的互连函数是：
PM2+i（j）=j+2i mod N
PM2-i（j）=j-2i mod N
其中0<=i<=n-1 0<=j<=N-1 n=log2N ，N是结点数。PM2I网络的最大距离为<=log2N/2
3.混洗交换单级网络
这种互连网络由全混洗和交换两种互连函数组成：
全混Shuffle（bn-1bn-2……b1b0）=（bn-2……b0bn-1）
相当于将处理单元的进制地址位中的最左位移到最右位的循环移位。由于全混洗互连网络不能实现全0和全1单元与其他单元的连接，因此引入交换网络中的Cube0函数，两函数复合后为：
Exchange[Shuffle（bn-1bn-2……b1b0）]=（bn-2……b0~bn-1）
（教材中图9.17中除节点上方和下方的连线应改为虚线）
在混洗交换网络中，最大距离为2n-1.最远的两个PE连接需要n次交换和n-1次混洗。
4.蝶形网络，即将二进制地址的最高位与最低位互换位置。
对于以上几种单级互连网络，应能根据其函数求得入端与出端的关系。
多级互连网络：
将前面几种单级互连网络重复连接，就形成了最基本的多级互连网络。决定多级互连网络的特性的主要因素有以下三个方面：交换开关、拓扑结构和控制方式。交换开关有直通、交换、上播、下播四种功能；控制方式则有级控、单元控制、部分极控三种方式。
常用的多级互连网络有：
1、多级立方体网络：通常是采用交换互连单级网络串接起来构成的。STARAN多级互连网络就是将Cube0，Cube1，Cube2三种互连函数的三个单级立方体网串接起来的。（教材中p197第12行开关的"110"应更正为"101"）在采用不同的级控信号时，可以实现任一输入端到任一输出端的直接连接。
2、多级混洗交换网络：又称OMEGA网络。这种网络的交换开关单元是四功能的。这种网络可以实现一个输入端与多个出端的连接。
3、多级PM2I互连网络
4、全排列网络
三、并行存储器的无冲突访问
为保证对存储器的并行无冲突访问，可采用的方法有，数据交叉存储在m个存储体中，并且使存储体M大于每次要访问的全部向量元素N，且为质数。将数组按行或列变换成一维数组，形成一个给维线性地址空间，地址用a表示，然后，将地址a所对应的元素存放在体号地址j=a |_a/n_|的单元中，就可以满足无冲突访问的要求。（教材中p199图9.26中块内地址应从0开始排列而不是从1开始）。
给出一个线性地址，应能求出其在存储器中的模块号和块内偏移。
四、多处理机（识记）
多处理机具有两台以上的处理机，在操作系统控制下通过共享的主存或输入输出子系统或高速通讯网络进行通讯。多处理机属MIMD系统。
多处理机与SIMD相比有较大不同，表现在：
结构灵活性：MIMD机结构上具有更大灵活性和更强的通用性；程序并行性：前者是作业级并行，后者则是操作级并行。
并行任务派生：前者需要由专用语句显式指明是否派生并行任务，而后者则不需要专门指令进程同步：MIMD机中各进程的同步需要采取特殊措施来保证，而SIMD机则由于受同一控制器控制，自然是同步的。
资源分配和调度：MIMD机任务调度要采用软件手段，而SIMD机中，只需用屏蔽来控制实际参加并行操作的处理单元数目。
多处理机在系统结构上分为两类：紧耦合和松耦合系统。
紧耦合是通过共享主存实现处理机间的互相通信，处理机间的相互联系比较紧密。按所用处理机类型是否相同及对称，又可分为同构或异构及对称或非对称的形式。常见组合是同构对称式和异构非对称式多机系统。
松耦合是通过消息传递方式来实现处理机间的相互通信，而每个处理机是由一个独立性较强的计算机模块组成。
为了解决多系统中的cache一致性问题，可采用的方法有（1）软件方法、（2）采用总线监听机制、（3）目录表法。
多处理机系统中，机间互连主要采用以下几种方式。
总线方式纵横交叉开关互连方式多端口存储器互连方式多级网络互连方式虫孔互连和寻径技术多处理机中并行性的开发第一步是要对程序中存在的并行性进行分析，主要分析其中的数据相关、数据反相关及数据输入相关，其次是用伯恩斯坦准则来分析哪些部分是可以并行执行的。
并行的程序设计语言常用FORK-JOIN原语及块结构语言Cobegin-Coend语言来表示程序中可并行执行部分及相互之间的同步关系。
多处理机操作系统除了完成通常单机操作系统的资源分配和管理、存储管理和保护、死锁防止、异常里程终止或例外处理等功能外，还必须具有以下特点和功能：
支持多个任务的并行执行支持处理机同步和通信管理提供系统结构重构运动系统降级使用自动支持硬件并行性和程序并行性的开发多处理机操作系统主要分成三类结构：主从结构、独立监控结构和浮动监控结构。其中主从结构适用于系统负载固定以及主机功能较强、从机功能较弱的非对称多处理机系统；独立监控结构适用于松耦合多处理机系统；第三种结构则适用于对称紧耦全多处理机系统。
衡量多处理机调度性能好坏的主要参数通常有：
完成所有任务所需最少时间；完成所有任务所需最少处理机数；最小平均流时间即执行每个任务所需平均时间；处理机的最大利用率或最小空闲时间并行机按系统结构划分可分为以下五类：向量流水巨型机、SIMD阵列机、共享主存多处理机、分布存储多计算机和联网计算机。