《计算机系统结构第6章》由会员分享，可在线阅读，更多相关《计算机系统结构第6章（112页珍藏版）》请在金锄头文库上搜索。
1、第6章 阵列处理机,6.1 阵列处理机的原理 6.2 SIMD计算机的互连网络 6.3 共享主存构形阵列处理机中并行存储器的无冲突访问 6.4 脉动阵列处理机,6.1 并行处理机原理,6.1.1阵列处理机的构形和特点 1.阵列处理机的构形 阵列处理机有两种构形，差别主要在于存储器的组成方式和互连网络的作用不同。 图6-1是采用分布式存储器的阵列处理机构形。,图6-1具有分布式存储器的阵列处理机构形,为了高速有效地处理向量数据，这种构形要求能把数据合理地预分配到各个处理单元的局部存储器中，使各处理单元PEi主要用自己的局存PEMi中的数据运算。分布于各PEM的数据，可以经系统数据总线从外部输入，
2、也可以用控制总线经控制部件播送。在执行向量指令时，可使用屏蔽位向量控制，让某些PE不工作(不活跃)。运算中，PE间可通过互连网络(InterconnectionNetwork,ICN)来交换数据。互连网络的连通路径选择也由控制部件统一控制。,处理单元阵列通过控制部件接到管理处理机SC上。管理处理机是一种通用机，用于管理系统资源，完成系统维护、输入/输出、用户程序的汇编及向量化编译、作业调度、存储分配、设备管理、文件管理等操作的功能。因此包括处理单元阵列、互连网络和控制部件在内的阵列处理部分，可以看成是系统的后端处理机。 采用这种构形的阵列处理机是SIMD的主流。典型机器有ILLIAC、MPP、
3、DAP、CM-2、MP-1、DAP600系列等。,图6-2是采用集中式共享存储器的阵列处理机构形。系统存储器是由K个存储分体(MM0MMK-1)集中组成，经互连网络ICN为全部N个处理单元(PE0PEN-1)所共享。为使各处理单元对长度为N的向量中各个元素都能同时并行处理，存储分体个数K应等于或多于处理单元数N。各处理单元在访主存时，为避免发生分体冲突，也要求有合适的算法能将数据合理地分配到各个存储分体中。,图6-2具有集中式共享存储器的阵列处理机构形,与分布式存储器构形不同的另一个地方是互连网络ICN的作用不同。其互连网络是用于在处理单元与存储器分体之间进行转接构成数据通路，希望各处理单元能
4、高速灵活地动态与不同的存储分体相连，使尽可能多的PE能无冲突地访问共享的主存模块。因此有的阵列处理机称它为对准网络(AlignmentNetwork)。 采用这种构形的典型机器有BSP。,2. 并行处理机的特点 并行处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列计算问题为背景发展起来的。这些计算问题的共同特点是可以通过各种途径把它们转化成为对数组或向量的处理，而并行处理机正好利用多个处理单元对向量或数组所包含的各个分量同时计算， 从而获得很高的处理速度。与同样擅长于向量处理的流水线处理机相比，并行处理机利用的是资源重复，而不是时间重叠；利
5、用并行性中的同时性，而不是并发性。它的每个处理单元要同等地担负起各种运算功能，但其设备利用率却可能没有多个单功能流水线部件那样高。因此，只有在硬件价格有了大幅度下降及系统结构有了较大改进的情况下，并行处理机才能具有较好的性能价格比。并行理机主要是靠增大处理单元个数来提高运算速度，比起向量流水线处理机主要依靠缩短时钟周期来说， 速度提高的潜力要大得多。,与流水线处理机不同的另一方面是阵列处理机使用简单规整的互连网络来确定处理单元间的连接。互连网络的结构形式限定了阵列处理机可用的解题算法，也会对系统多种性能指标产生显著影响，因此，互连网络的设计是重点。 阵列处理机在机间互连上比固定结构的单功能流水
6、线灵活，使相当一部分专门问题上的工作性能比流水线处理机高得多，专用性强得多。如果习惯上把流水线处理机归属于通用计算机的话，阵列处理机则被看成是一种专用计算机，它是以一定数量的专门算法为背景的。另一方面，由于总希望阵列处理机解题算法的适应性更强一些，应用面更广一些，因此，与流水线处理机不同，阵列处理机的结构是和采用的并行算法紧密联系在一起的。,如上所述，阵列处理机基本上是一台专用于向量处理的计算机，但并不是所有的运算都可以转化为向量运算，总有不少标量运算。作为整个系统的等效速度来讲，除向量运算速度外，在很大程度上还受标量运算速度和编译开销的大小所影响。如果一台机器的向量处理速度极高，甚至不受限制
7、，而标量速度只是每秒一亿次浮点运算，那么对于标量运算占10%的题目来讲，系统总的等效速度最多也不会超过每秒十亿次浮点运算。所以，提高标量的处理能力是很重要的，这就要求阵列处理机系统的控制部件必须是一台具有高性能、强功能的标量处理机，减少标量运算对系统性能的影响。,至于编译时间的多少，则不仅与阵列机结构有关，也与机器语言的并行性程度有关，特别是想要提高阵列处理机的通用性，建立一个有向量化功能的高级语言编译程序就是非常必要的了。正因为如此，阵列处理机还必须用一台高性能单处理机作为管理计算机来配合工作，运行系统的全部管理程序。所以，阵列处理机实质上是由专门对付数组运算的处理单元阵列组成的处理机、专门
8、从事处理单元阵列的控制及标量处理的处理机和专门从事系统输入/输出及操作系统管理的处理机组成的一个异构型多处理机系统。,6.1.2 ILLIAC的处理单元阵列结构 由于阵列处理机上的并行算法的研究是与结构紧密联系在一起的，因此，下面先介绍一下ILLIAC阵列机上处理单元的互连结构。ILLIAC是采用如图6-1所示的分布存储器构形，其处理单元阵列结构如图6-3所示。其中，PUi为处理部件，包含64位的算术处理单元PEi、所带的局部存储器PEMi和存储逻辑部件MLU。64个处理部件PU0PU63排列成88的方阵，任何一个PUi只与其上、下、左、右4个近邻PUi-8(mod64)、PUi+8(mod6
9、4)、PUi-1(mod64)和PUi+1(mod64)直接相连。,上下同一列两端的PU连成环，左右每一行右端的PU与下一行左端的PU相连，最下面一行右端的PU与最上面一行左端的PU相连，从而形成一个闭合的螺线形状，所以称其为闭合螺线阵列。在这个阵列中，步距不等于1或8的任意单元之间可以用软件寻找最短路径进行通信，其最短距离不超过7步。例如，信息由PU63送PU10,可经PU63PU7PU8PU9PU104步实现，信息由PU9送PU45可经PU9PU1PU57PU56PU48PU47PU46PU457步实现。普遍来讲， 个处理单元组成的阵列中，任意两个处理单元之间的最短距离不超过 步。,图6-
10、3 ILLIAC处理单元的互连结构,ILLIAC的处理单元是累加器型运算器，把累加寄存器RGA中的数据和存储器中来的数据进行运算，结果保留在累加寄存器RGA中。每个处理单元内有一个数据传送寄存器RGR收发数据，实现数据在处理单元之间的传送，并有一个屏蔽触发器，用来控制让该PUi是否被屏蔽掉，使之不参与向量指令的操作。,6.1.3ILLIAC的并行算法举例 1.矩阵加 阵列处理机解决矩阵加是最简单的一维情况。两个88的矩阵A、B相加，所得的结果矩阵C也是一个88的矩阵。只需把A、B、C居于相应位置的分量存放在同一个PEM内，且在全部64个PEM中，让A、B和C的各分量地址均对应取相同的地址、+1
11、和+2，如图6-4所示。这样，实现矩阵加只需用下列三条ILLIAC汇编指令：,LDA ALPHA ;全部()由PEMi送PEi的累加器RGAi ADRN ALPHA+1 ;全部(+1)与(RGAi)浮点加，结果送 RGAi STA ALPHA+2 ;全部(RGAi)由PEi送PEMi的+2单元 其中，0i63。,图6-4矩阵相加的存储器分配举例,2.矩阵乘 矩阵乘是二维数组运算，比矩阵加要复杂。设A、B和C为3个88的二维矩阵，给定A和B，计算C=AB的64个分量可用公式,其中，0i7且0j7。,在SISD计算机上求解，可执行FORTRAN语言编写的下列程序： DO10I=0,7 DO10J=
12、0,7 C(I,J)=0 DO10K=0,7 10 C(I,J)=C(I,J)+A(I,K)*B(K,J),需经I、J、K三重循环完成。每重循环执行8次，共需512次乘、加的时间，且每次还要包括执行循环控制判别等其它操作所需的时间。如果在SIMD阵列处理机上运算，可用8个处理单元并行计算矩阵C(I,J)的某一行或一列，即将J循环或I循环转化成一维的向量处理，从而消去了一重循环。以消去J循环为例，可执行用FORTRAN语言编写的下列程序：,DO10I=0,7 C(I,J)=0 DO10K=0,7 10 C(I,J)=C(I,J)+A(I,K)*B(K,J),图6-5矩阵乘程序执行流程图,需要说明
13、的是其执行过程虽与SISD的类似，但实际的解决方式是不同的。每次控制部件执行的PE类指令表面上是标量指令，实际上已等效于向量指令，如向量取、向量存、向量加、向量乘等，是8个PE并行地执行同一条指令。每次播送时，利用阵列处理机的播送功能将处理单元PEK中累加寄存器RGAK的内容经控制部件(CU)播送到全部8个处理单元的RGA中去。 然而为了让各个处理单元PEi尽可能只访问所带局部存储器PEMi，以保证高速处理，就必须要求对矩阵A、B、C各分量在局部存储器中的分布采用如图6-6所示的方案。,图6-6 矩阵乘的存储器分配举例,如果想把ILLIAC的64个处理单元全部利用起来并行运算，即把K循环的运算
14、也改为并行，还可进一步提高速度，但需要在阵列存储器中重新恰当地分配数据。同时还要使8个中间积A(I,K)B(K,J)能够并行相加(其中0K7)，这就要用到下面的累加和并行算法。即使如此，就K的并行来说，速度的提高也不是8倍，而只是8/log28，接近于2.7倍。,3.累加和 这是一个将N个数的顺序相加转为并行相加的问题。为得到各项累加的部分和与最后的总和，要用到处理单元中的活跃标志位。只有处于活跃状态的处理单元才能执行相应的操作。为叙述方便取N=8，即有8个数A(I)顺序累加，其中0I7。 在SISD计算机上可以写成下列FORTRAN程序： C=0 DO 10 I=0,7 10 C=C+A(I
15、) 这是一个串行程序，需要8次加法时间。,在阵列处理机上用成对递归相加算法，只需log28=3次加法时间即可。首先，原始数据A(I)分别存放在8个PEM的单元中，其中，0I7。然后，按下面的步骤求累加和： (1)置全部PEi为活跃状态,0i7; (2)全部A(I)从PEMi的单元读到相应PEi的累加寄存器 RGAi中，0i7； (3)令K=0; (4)将全部PEi的(RGAi)转送到传送寄存器RGRi,0i7;,(5)将全部PEi的(RGRi)经过互连网络向右传送2K步距， 0i7； (6)令j=2K-1; (7)置PE0PEj为不活跃状态； (8)处于活跃状态的所有PEi执行(RGAi):=
16、(RGAi)+(RGRi),ji7； (9)K:=K+1； (10)如K3，则转回(4)，否则往下继续执行； (11)置全部PEi为活跃状态，0i7; (12)将全部PEi的累加寄存器内容(RGAi)存入相应PEMi的+1单元中，0i7。,图6-7描绘了阵列处理机上累加和的计算过程。框中的数字表明各处理单元每次循环后相加的结果。图中用数字0 7分别代表A(0)A(7)。画有阴影线的处理单元表示此时不活跃。另外，图中对上述第(5)步中PE的(RGRi)在右移时超出PE7的内容没有表示出来，这是因为若右移步距为2K(mod8)，应移入PE0PEj，而这些PE在第(7)步将要置为不活跃，所以无论它的RGR接收什么内容都不会对执行结果有影响。,图6-7阵列处理机上累加和的计算过程,6.2 SIMD计算机的互连网络,6.2.1互连网络的设计目标与互
