计算机系统结构第6章.ppt

1、第6章阵列处理器，6.1阵列处理器原理，6.2计算机互连网络，6.3共享主存配置的阵列处理器中并行存储器的无冲突访问，6.4脉冲阵列处理器，6.1并行处理器原理，6.1.1阵列处理器的配置和特性，1。阵列处理器的配置阵列处理器有两种配置，区别主要在于不同的内存组成和互连网络的功能。图6-1是使用分布式存储器的阵列处理器配置。图6-1具有分布式内存的阵列处理器配置。为了高效且高速地处理矢量数据，这种配置要求数据能够被合理地预分配给每个处理单元的本地存储器，使得每个处理单元PEi主要使用其自己的本地PEMi中的数据进行操作。分布在每个质子交换膜中的数据可以通过系统数据总线从外部输入，也可以通过控制

2、组件通过控制总线广播。当执行向量指令时，屏蔽位向量控制可用于使一些PEs无效。在操作中，PE可以通过互联网络交换数据(ICN)。互连网络的连接路径选择也由控制单元统一控制。处理单元阵列通过控制单元连接到管理处理器SC。管理处理器是一种通用机器，用于管理系统资源、完成系统维护、输入输出、用户程序汇编和矢量化编译、作业调度、存储分配、设备管理、文件管理等功能。因此，包括处理单元阵列、互连网络和控制部件在内的阵列处理部分可以视为系统的后端处理器。这种配置的阵列处理器是SIMD的主流。典型的机器有伊利亚克、MPP、DAP、CM-2、MP-1、DAP600系列等。图6-2是使用集中式共享内存的阵列处理器

3、配置。系统内存由k个内存分区(MM0MK-1)组成，由所有n个处理单元(PE0PEN-1)通过互连网络ICN共享。为了使每个处理单元同时并行处理长度为n的向量中的每个元素，存储拆分的数量k应该等于或大于处理单元的数量n。当每个处理单元访问主存储器时，为了避免拆分冲突，还需要合适的算法来合理地将数据分配给每个存储拆分。图6-2带有集中式共享内存的阵列处理器配置。与分布式存储器配置的另一个区别是互连网络ICN的不同功能。其互连网络用于在处理单元和存储器之间切换，以形成数据路径。希望每个处理单元能够高速灵活地与不同的内存模块动态连接，以便尽可能多的处理器能够访问共享的主内存模块而不发生冲突。因此，一

4、些阵列处理器称之为阵列网络。具有这种配置的典型机器是BSP。2.并行处理器的特点并行处理器的单指令流和多数据流处理模式及其产生的特殊结构是在有限差分、矩阵、信号处理和线性规划等一系列计算问题的背景下发展起来的。这些计算问题的共同特点是，它们可以通过各种方式转换成数组或向量处理，而并行处理器只是使用多个处理单元来同时计算向量或数组中包含的每个分量，从而获得较高的处理速度。与同样擅长向量处理的流水线处理器相比，并行处理器使用资源复制而不是时间重叠；利用并行的同时性，而不是并发性。每个处理单元必须平等地承担各种计算功能，但其设备利用率可能不如几个单功能流水线组件高。因此，只有当硬件价格大大降低，系统

5、结构大大改善时，并行处理器才能有更好的性能价格比。并行处理器主要依靠增加处理单元的数量来提高运算速度。与主要依靠缩短时钟周期的矢量流水线处理器相比，速度改进的潜力要大得多。另一方面，阵列处理器使用简单和规则的互连网络来确定处理单元之间的连接。互连网络的结构限制了阵列处理器可用的问题解决算法，并且对系统的各种性能指标也有显著影响。因此，互连网络的设计是关键。在机器间互连中，阵列处理器比固定结构的单功能流水线更灵活，这使得许多特殊问题的性能远远高于流水线处理器。如果流水线处理器传统上被分类为通用计算机，那么阵列处理器被认为是基于一定数量的特殊算法的专用计算机。另一方面，由于一直希望阵列处理器的算法

6、具有更强的适应性和更广泛的应用，阵列处理器的结构与并行算法密切相关，这与流水线处理器不同。如上所述，阵列处理器基本上是一台专用于矢量处理的计算机，但不是所有的运算都可以转换成矢量运算，而且总是有许多标量运算。作为整个系统的等效速度，除了矢量运算速度之外，它还在很大程度上受到标量运算速度和编译开销的影响。如果一台机器的向量处理速度极高，甚至没有限制，而标量速度仅为每秒1亿次浮点运算，那么系统的总等效速度最多不会超过每秒10亿次浮点运算。因此，提高标量处理能力非常重要，这就要求阵列处理器系统的控制部件必须是高性能、强功能的标量处理器，以减少标量运算对系统性能的影响。至于编译时间，不仅与数组机的结构

7、有关，还与机器语言的并行性有关。特别是为了提高阵列处理器的通用性，有必要建立一个具有向量化功能的高级语言编译器。因此，阵列处理器还必须使用高性能的单个处理器作为管理计算机，以协同工作并运行系统的所有管理程序。因此，阵列处理器本质上是一个异构多处理器系统，由专门从事阵列操作的处理器、专门从事阵列控制和标量处理的处理器以及专门从事系统输入/输出和操作系统管理的处理器组成。6 . 1 . 2 ILLIAC处理单元阵列结构由于阵列处理器上的并行算法研究与该结构密切相关，因此首先介绍了ILIAC阵列处理器上处理单元的互连结构。伊利亚克采用如图6-1所示的分布式内存配置，其处理单元阵列结构如图6-3所示。

8、PUi是一个处理单元，它包括一个64位算术处理单元PEi、一个本地存储器PEMi和一个存储逻辑单元MLU。64个处理单元PU0PU63排列成88的正方形阵列，并且任何PUi与其四个邻居PUi-8(mod64)、PUi-8(mod 64)、PUi-1(mod64)和PUi-1(mod 64)直接相连。同一列两端的聚氨酯连接成一个环，左右各排右端的聚氨酯与下一排左端的聚氨酯连接，最下面一排右端的聚氨酯与最上面一排左端的聚氨酯连接，形成一个封闭的螺旋形状，称为封闭螺旋阵列。在这个阵列中，任何步距不等于1或8的单元都可以用软件找到最短的通信路径，最短距离不超过7步。例如，从PU63发送到PU10的信息

9、可以通过PU63PU7PU8PU9PU104步骤实现，从PU9发送到PU45的信息可以通过PU9 Pu1 Pu57 Pu56 Pu48 Pu47 Pu46 Pu457步骤实现。一般来说，由12个处理单元组成的阵列中任意两个处理单元之间的最短距离不超过步数。图6-3 ILIAC处理单元的互连结构。Illiac处理单元是一个累加器型运算符，它对累加寄存器RGA中的数据和来自存储器的数据进行运算，并将结果保存在累加寄存器RGA中。每个处理单元都有一个数据传输寄存器RGR，用于发送和接收数据，以实现处理单元之间的数据传输，以及一个屏蔽触发器，用于控制PUi是否被屏蔽，以便它不参与矢量指令的操作。6 .

10、 1 . 3 LLIAC并行算法示例1。矩阵加法阵列处理器是最简单的一维情况。将88的两个矩阵A和B相加，得到的矩阵C也是88的矩阵。只有在相应位置的a、b和c的组件需要存储在相同的PEM中，并且在所有64个PEM中，a、b和c的组件的地址应该是相同的地址1和2，如图6-4所示。这样，实现矩阵加法只需要以下三个ILLIAC汇编指令：所有()都由PEMi发送到PEi的蓄能器RGaI ADRN ALPHA 1；将所有(1)和(RGAi)浮点相加，并将结果发送给RGAi STA ALPHA 2；所有(RGAi)均由PEi发送至2台PEMi，其中0i63。图6-4矩阵加法的内存分配示例。2.矩阵乘法是

11、二维数组运算，比矩阵加法更复杂。假设甲、乙、丙是三个88的二维矩阵。给定A和B，C=AB的64个分量可以通过公式计算，其中0i7和0j7。可以执行用FORTRAN语言编写的下列程序：do10i=0，7do10j=0，7c (I，j)=0d10k=0，710c (I，j)=c (I，j) a (I，k) * b (k，j)。每个循环执行8次总共需要512次乘法和加法，每次还包括执行其他操作(如循环控制判别)所需的时间。如果在SIMD阵列处理器上运行，可以用8个处理单元并行计算矩阵C(I，J)的某一行或某一列，即将J循环或I循环转换为一维向量处理，从而消除了双循环。以J循环消除为例，可以执行用FO

12、RTRAN语言编写的下列程序：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矩阵乘法器程序执行流程每次控制单元执行的PE类指令表面上是标量指令，实际上等价于矢量指令，如矢量取值、矢量存储、矢量加法、矢量乘法等。并且八个PEs并行执行相同的指令。在每次广播时，阵列处理器的广播功能用于通过控制单元(CU)将处理单元PEK中的累积寄存器RGAK的内容广播到所有八个处理单元的RGA。然而，为了使每个处理单元PEi尽可能只访问本地存储器PEMi以确保高速处理，有必要采用图6-6所示的方案来分配本地存储器中矩阵

13、A、B和C的分量。图6-6。以矩阵乘法的内存分配为例，如果要使用ILLIAC的全部64个处理单元进行并行操作，即把K-loop的操作改为并行，这样可以进一步提高速度，但是需要在数组内存中适当地重新分配数据。同时，八个中间乘积A(I，K)B(K，J)可以并行相加(0K7)，这需要以下累加和并行算法。即便如此，就k并行性而言，速度提高不是8倍，而是8/log28，接近2.7倍。这是一个把N个数的顺序相加转化为并行相加的问题。为了获得每个项目的累积部分和以及最终和，使用处理单元中的有效标志位。只有活动的处理单元可以执行相应的操作。为了描述方便，N=8，即8个数字A(1)按顺序累加，其中0I7。下列F

14、ORTRAN程序可以在SISD计算机上编写：C=0 DO10I=0，7 10 C=C A(1)。这是一个串行程序，需要8次加法。在阵列处理器上，使用成对递归加法算法，它只需要log28=3次加法。首先，原始数据A(1)分别存储在8个质子交换膜单元中，其中0I7。然后，按照以下步骤进行总结：(1)将所有PEi设置为活动状态，0i7(2)所有的A(I)从PEMi单元读入相应的PEi，0i7的累加寄存器RGAi；(3)假设K=0；(4)将所有PEi转移到转移寄存器RGRi，0i7(5)通过互连网络将PEi的所有(RGRi)向右转移2K步，0i7；(6)让j=2K-1；(7)将PE0PEj设置为非活动

15、状态；(8)处于活动状态的所有PEi执行(RGAI) :=(RGAI) (RGRI)，Ji7(9)K:=k1；(10)如果K3，转回(4)，否则继续执行；(11)将所有PEi设置为活动状态，0i7(12)将所有Pei的累计寄存器内容(RGAi)存储在相应PEmi 0i 7的单元1中。图6-7描述了阵列处理器上累加和的计算过程。框中的数字表示每个周期后添加每个处理单元的结果。在图中，A(0)A(7)用数字0 7表示。阴影处理单元表示它们此时不活动。另外，在上面的步骤(5)中向右移动时PE的(RGRi)超过PE7的内容没有在图中显示，因为如果向右移动的步距是2K(mod8)，它应该被移动到PE0P

16、Ej中，并且这些pes在步骤(7)中将是无效的，所以不管它的RGR接收到什么内容，它都不会影响执行结果。图6-7阵列处理器累加和的计算过程，6.2 SIMD计算机互连网络，6.2.1互连网络的设计目标和互连功能在SIMD计算机中，处理单元之间或处理单元与存储单元之间应通过互连网络进行信息交换。随着大规模集成电路和微处理器的快速发展，构建一个具有多达214，216个处理单元的阵列处理器已经成为现实。然而，如果在任何两个处理单元之间有直接的路径，将会有太多的互连网络。因此，相邻处理单元之间只有有限数量的直接连接，任何两个处理单元之间完成问题求解算法的信息传输可以在一步或几步传输后实现。SIMD系统

17、互联网络的设计目标是：结构不要过于复杂，以降低成本；互连应该灵活，以满足算法和应用的需要；处理单元之间信息交换所需的传输步骤数量应尽可能少，以提高速度性能；它可以与常规的单个基本组件相结合，也可以通过多通道或多级连接实现复杂的互连，具有良好的模块化，便于超大规模集成电路的实现，满足系统的可扩展性。为了反映互连的特性，每个互连网络可以由一组互连函数来定义。如果互连网络的N个输入端和N个输出端(N=2n)由整数0、1和N-1表示，则互连函数表示互连网络的输出端号码和输入端号码之间的一一对应关系。对于所有输入端0、1、j和N-1，互连网络的互连功能被定义为输入端j和输出端f(j)之间的功能对应。当实

18、现处理单元之间的互连时，互连网络的输入和输出实际上是同一组处理单元的输出和输入，它们是互连网络的同一个节点。互连函数可以直接用节点间的连接图来表示，但有时很繁琐，难以反映连接的内在规律。因此，通常使用另一个简单的函数表达式，即所有的输入端x和输出端f(x)都用二进制编码，它们的函数规则从两者的二进制代码中找出。这种表示的例子将在下面看到。6.2.2互连网络中应选择的几个问题在确定电力公司间通信的互连网络时，有必要对运行模式、控制策略、交换方法和网络拓扑结构进行选择。有三种运行模式：同步、异步以及同步和异步的结合。根据其SIMD特性，现有的阵列处理器都采用同步运行模式，使得所有的处理器都按照时钟同步运行。异步或组合操作模式通常用于多