单指令流多数据流计算机

单指令流多数据流计算机第1页，课件共46页，创作于2023年2月目录第6章单指令流多数据流计算机

6.1单指令流多数据流计算机的基本结构与特点

6.2分布式存储器SIMD计算机实例分析

6.3集中式共享存储器SIMD计算机实例分析

6.4阵列处理机的算法及性能分析第2页，课件共46页，创作于2023年2月

第6章

单指令流多数据流计算机

第3页，课件共46页，创作于2023年2月6.1单指令流多数据流计算机的

基本结构与特点

单指令流多数据流（SIMD）计算机的关键特征是它的并行处理机。它的并行处理机是由单一控制部件控制多个处理单元同时进行运算操作，多个处理单元通常通过互连网络连接成阵列结构，故也称为阵列处理机。并行处理机的所有处理单元同时执行从控制部件广播来的同一条指令，但指令使用不同的数据，因此，并行处理机是指令操作级并行的单指令流多数据流处理机。第4页，课件共46页，创作于2023年2月6.1.1单指令流多数据流计算机的两种基本结构

根据存储器的组织方式不同，单指令流多数据流计算机的基本结构分为两种： 集中式共享存储器型 分布式存储器型

第5页，课件共46页，创作于2023年2月1.分布式存储器SIMD计算机基本结构

并行处理机的每个处理单元都有自己的局部存储器，存放可直接访问的数据。所有的处理单元通过互连网络互联。阵列控制部件CU是一台功能专用的处理机，它执行程序流控制指令和程序中的标量运算。管理处理机SC运行操作系统，管理系统资源。

第6页，课件共46页，创作于2023年2月图6.1分布式存储器的SIMD计算机基本结构第7页，课件共46页，创作于2023年2月2.集中式共享存储器SIMD计算机基本结构

并行处理机的所有处理单元共享由个存储体组成的并行存储器，处理单元与存储体之间通过互连网络互连。CU和SC的功能与采用分布式存储器构型的SIMD计算机没有什么差别。第8页，课件共46页，创作于2023年2月图6.2集中式共享存储器的SIMD计算机基本结构第9页，课件共46页，创作于2023年2月6.1.2单指令流多数据流计算机的主要特点

SIMD的效率取决于计算程序向量化的程度。SIMD计算机依靠的并行措施是资源重复。SIMD计算机的互连网络决定了SIMD计算机能适应的算法类别，SIMD计算机的实际有效速度取决于另外两个因素。一是标量运算速度，二是编译过程的时间开销。SIMD计算机是根据功能专用化的原则组成的一种异构型多计算机系统。

第10页，课件共46页，创作于2023年2月6.2分布式存储器SIMD计算机实例分析

两种典型的SIMD计算机采用分布式存储器结构的并行处理机的ILLIACⅣ计算机。采用集中式共享存储器结构的并行处理机的BSP计算机。第11页，课件共46页，创作于2023年2月1.ILLIACⅣ阵列ILLIACⅣ系统由3种类型处理机组成的一个异构多处理机系统。一是专门用于数组运算的处理单元阵列；二是阵列控制器，它既是处理单元阵列的控制部分，又是一台相对独立的小型标量处理机；三是一台标准的BurroughsB6700计算机，由它担负ILLIACⅣ输入输出系统和操作系统管理功能。第12页，课件共46页，创作于2023年2月

图6.3ILLIACⅣ系统框图第13页，课件共46页，创作于2023年2月1.BSP计算机它由系统管理计算机B7700/B7800和BSP处理机两大部分组成，前者可视为后者的前端机。系统管理机负责BSP程序编译、与远程终端及网络的数据通信、外围设备管理等，大多数BSP作业调度和操作系统活动也是在系统管理机上完成的。BSP处理机又可分为3部分，一是并行处理机，二是控制处理机，三是容量为4~64M字的文件存储器。6.3集中式共享存储器SIMD计算机实例

第14页，课件共46页，创作于2023年2月图6.6BSP计算机系统框图操作系统和维护信息文件存储器CCD4～64M字文件存储器控制器文件存储器系统指令/控制存储器256K字控制维护单元标量处理单元并行处理机控制器控制处理机并行存储器0.5～8M字入口和出口对准网络16个算术单元并行处理机100M字/s100M字/s12.5M字/s系统管理机B7700/B7800程序和数据250K字/s●●第15页，课件共46页，创作于2023年2月系统管理机文件存储器控制处理机(指令存储器，标量运算器)17个存储体16算术单元BSP科学处理机系统组成第16页，课件共46页，创作于2023年2月为了说明BSP并行存储器的地址变换和无冲突访问，下面先看一个较简单的例子。设并行存储器的存储体数m=7(质数)，运算单元数n=6。若有一个45的数组。

a00a01a02a03a04

a10a11a12a13a14a20a21a22a23a24a30a31a32a33a34第17页，课件共46页，创作于2023年2月

BSP的地址映象关系为：先将二维数组按列或者按行的顺序变换为一维数组，以形成一个一维线性地址空间，地址用a表示。然后将地址a变换成并行存储器地址(j，i)，其中j是存储体体号，i是体内地址：

j=amodmi=[a／n]下整存储体数m为一质数，n为无冲突访问的最大存储体数。第18页，课件共46页，创作于2023年2月3.BSP的数据流水线结构

BSP的16个AE组成的算术单元阵列、17个存储体组成的并行存储器和2套互连网络(对准网络)形成了一条5级数据流水线，使连续几条向量指令能在时间上重叠起来执行。①由17个存储器输出端口并行读出16个操作数。②经对准网络NWl将16个操作数重排列成16个算术单元需要的次序。③将排列好的16个操作数送到16个算术单元完成操作。④所得的16个结果经对准网络NW2重新排列成在17个存储体中存储所需要的次序。⑤写入并行存储器。存储器处理器对准网络2对准网络1第19页，课件共46页，创作于2023年2月6.4阵列处理机的算法及性能分析

阵列处理机的处理器阵列有固定的结构，因此，阵列处理机的性能与算法有很大关系。若问题求解的算法能与阵列处理机的结构相适应，就能获得较高的性能；否则，阵列处理机的实际性能就很低，处理单元的利用率也很低。

第20页，课件共46页，创作于2023年2月6.4.1阵列处理机的差分计算

描述平面场的拉普拉斯方程：

将二阶偏导数表示为差分形式:代入原方程，则可得有限差分计算公式：

第21页，课件共46页，创作于2023年2月迭代计算开始时，除由边界条件给定的某些边缘点之外，其余网格点的函数值初值均可设为零。若取网格间距为单位1，迭代计算的表达式为：式中的上标t表示迭代次数。迭代计算直至连续二次迭代所求值的差小于规定误差为止。

第22页，课件共46页，创作于2023年2月由于阵列处理机中处理器的数量比网格点数少得多，需要把离散域划分为若干个网格块，一个网格块上的网格点的迭代计算由一个处理器完成。在划分网格块时要注意两点，一是要使网格块的大小相等，二是要使网格块的周长尽可能小，且相邻网格块的邻界边长相等。迭代实现第23页，课件共46页，创作于2023年2月6.4.2阵列处理机的常用算法及性能分析

1.矩阵加：把A和B同一位置的一对元素存放在同一个PEM中，那么，64个PE就可以同时并行地完成64对元素的相加。

第24页，课件共46页，创作于2023年2月6.4.2阵列处理机的常用算法及性能分析

2.矩阵乘：若A和B为两个8×8的矩阵，并行地一次完成8个中间积的运算。最后对8个中间积做7次加法。

7cij=∑aikbkj0≤i,j≤7

k=0(1)顺序执行：每个Cij需要8次乘法，7次加法，共需要15*64=960次加/乘法；第25页，课件共46页，创作于2023年2月A(4*4)B(4*4)C(4*4)第26页，课件共46页，创作于2023年2月A(4*4)B(4*4)C(4*4)第27页，课件共46页，创作于2023年2月(2)在Illiac上执行：每列或每排Cij需要1次乘法，3次加法，共需要4*8=32次加/乘法；求8×8的矩阵乘法，显然每列或每排Cij需要1次乘法，7次加法，共需要8*8=64次加/乘法；书中说每个Cij需要1次乘法，7次加法，共需要

8*64=512次加、乘法。显然有问题，没有充分利用64个运算器。第28页，课件共46页，创作于2023年2月6.4.2阵列处理机的常用算法及性能分析

3.累加和

7S

=∑ai

i=0第29页，课件共46页，创作于2023年2月第30页，课件共46页，创作于2023年2月

如果在阵列处理机上采用成对递归相加的算法，则只需log28=3次加法时间。首先，8个原始数据A(i)，0≤i≤7，存放在8个PEM的a单元中，然后按下述步骤求累加和。第1步置全部PE为活跃状态；第2步全部A(I)，0≤I≤7，从PE的a单元读到相应PE的

RGA中；第3步令K:=0；第4步全部PE的(RGA)转送到RGR；第5步全部PE的(RGR)经过互连网络向右传送2k步距；第6步令j=2k-1；第7步置PE0至PEj为不活跃状态；第8步处于活跃状态的PE执行(RGA):=(RGA)+(RGR)

的操作；第9步K:=K+1；第10步若K<3，则转第四步；否则，继续往下执行；第11步置全部PE为活跃状态；第12步全部PE的(RGA)存入相应PEM的a+1单元中。第31页，课件共46页，创作于2023年2月01234567RGA01234567RGRK=00123456RGR700-11-22-33-44-55-66-7RGA00-11-22-33-44-55-66-7RGRK=100-11-22-33-44-55-66-700-10-20-31-42-53-64-7RGARGR00-10-20-31-42-53-64-7RGRK=21-42-53-64-700-10-20-3RGR00-10-20-30-40-50-60-7RGA第32页，课件共46页，创作于2023年2月【例6.1】A和B都是元素为浮点表示的64×64的二维数组，一次浮点加法的计算过程可由取数、求阶差、对阶、尾数加、规格化和存数共6个段组成，若每个段的执行时间均为，请分别求出在下列结构不同的处理机上完成C=A+B所需时间及相对于顺序处理方式的加速比。

第33页，课件共46页，创作于2023年2月（1）顺序处理方式的处理机。（2）具有浮点加法流水线的流水处理机，且浮点加法流水线分为6个段，各段执行时间均为。（3）8×8的阵列处理机，且处理阵列上的每个处理器只能顺序处理浮点加运算。（4）8×8的阵列处理机，且处理阵列上的每个处理器均能流水处理浮点加运算。（5）64×64的阵列处理机。

第34页，课件共46页，创作于2023年2月解（1）需要顺序执行的浮点加法次数为，每次浮点加运算所需时间为，则全部运算所需时间为（2）需要流水执行的浮点加法次数为，则一个段的浮点加法流水线处理全部运算所需时间和加速比为第35页，课件共46页，创作于2023年2月（3）对于8×8的处理阵列，每个处理器需要处理64×64二维数组中的一个的子数组，因此，每个处理器需要执行的浮点加法次数为8×8=64。每次浮点加运算所需时间为。每个处理器顺序执行64次浮点加运算所需时间为。64个处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时间和加速比为第36页，课件共46页，创作于2023年2月（4）对于8×8的处理阵列，每个处理器需要流水处理64×64二维数组中的一个8×8的子数组，因此，每个处理器的浮点加法次数为n=8×8=64，k=6段的浮点加法流水线处理64次浮点加运算所需时间为

64个处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时间和加速比为第37页，课件共46页，创作于2023年2月（5）对于64×64的处理阵列，每个处理器只需执行一次浮点加法运算，所需时间为，所以，全部运算所需时间和加速比为第38页，课件共46页，创作于2023年2月【例6.2】

分别计算在下列各处理机中，计算所需的时间及相对于顺序处理方式的加速比。（1）顺序处理方式的处理机。第39页，课件共46页，创作于2023年2月（2）具有一个流水加法器和一个流水乘法器的流水处理机，且加法器和乘法器可以同时工作。（3）8个处理单元之间用双向环互连的并行处理机，相邻PE之间传送一次数据需时。（4）8×8的ILLIACⅣ阵列处理机，且相邻处理单元之间传送一次数据需时。假设各处理机或处理单元取数和存数的时间忽略不计，完成一次加法需时2，完成一次乘法需时4。第40页，课件共46页，创作于2023年2月解

计算点积需要做8次乘法和7次加法。（1）顺序执行8次乘法所需时间为再顺序执行7次加法所需时间为故共需时间为第41页，课件共46页，创作于2023年2月（2）在流水处