单指令流多数据流计算机

1、单指令流多数据流计算机第1页，共46页，2022年，5月20日，2点22分，星期二目 录第6章 单指令流多数据流计算机 6.1 单指令流多数据流计算机的基本结构与特点 6.2 分布式存储器SIMD计算机实例分析 6.3 集中式共享存储器SIMD计算机实例分析 6.4 阵列处理机的算法及性能分析第2页，共46页，2022年，5月20日，2点22分，星期二 第6章 单指令流多数据流计算机 第3页，共46页，2022年，5月20日，2点22分，星期二6.1 单指令流多数据流计算机的基本结构与特点 单指令流多数据流（SIMD）计算机的关键特征是它的并行处理机。它的并行处理机是由单一控制部件控制多个处理

2、单元同时进行运算操作，多个处理单元通常通过互连网络连接成阵列结构，故也称为阵列处理机。 并行处理机的所有处理单元同时执行从控制部件广播来的同一条指令，但指令使用不同的数据，因此，并行处理机是指令操作级并行的单指令流多数据流处理机。第4页，共46页，2022年，5月20日，2点22分，星期二6.1.1 单指令流多数据流计算机的两种基本结构 根据存储器的组织方式不同，单指令流多数据流计算机的基本结构分为两种：集中式共享存储器型分布式存储器型 第5页，共46页，2022年，5月20日，2点22分，星期二1. 分布式存储器SIMD计算机基本结构 并行处理机的每个处理单元都有自己的局部存储器，存放可直接

3、访问的数据。所有的处理单元通过互连网络互联。 阵列控制部件CU是一台功能专用的处理机，它执行程序流控制指令和程序中的标量运算。 管理处理机SC运行操作系统，管理系统资源。 第6页，共46页，2022年，5月20日，2点22分，星期二 图6.1 分布式存储器的SIMD计算机基本结构第7页，共46页，2022年，5月20日，2点22分，星期二 2.集中式共享存储器SIMD计算机基本结构 并行处理机的所有处理单元共享由个存储体组成的并行存储器，处理单元与存储体之间通过互连网络互连。CU和SC的功能与采用分布式存储器构型的SIMD计算机没有什么差别。第8页，共46页，2022年，5月20日，2点22分

4、，星期二图6.2 集中式共享存储器的SIMD计算机基本结构第9页，共46页，2022年，5月20日，2点22分，星期二 6.1.2 单指令流多数据流计算机的主要特点 SIMD的效率取决于计算程序向量化的程度。SIMD计算机依靠的并行措施是资源重复。SIMD计算机的互连网络决定了SIMD计算机能适应的算法类别，SIMD计算机的实际有效速度取决于另外两个因素。一是标量运算速度，二是编译过程的时间开销。SIMD计算机是根据功能专用化的原则组成的一种异构型多计算机系统。 第10页，共46页，2022年，5月20日，2点22分，星期二6.2 分布式存储器SIMD计算机实例分析 两种典型的SIMD计算机采

5、用分布式存储器结构的并行处理机的ILLIAC 计算机。采用集中式共享存储器结构的并行处理机的BSP计算机。第11页，共46页，2022年，5月20日，2点22分，星期二1. ILLIAC 阵列ILLIAC 系统由3种类型处理机组成的一个异构多处理机系统。一是专门用于数组运算的处理单元阵列；二是阵列控制器，它既是处理单元阵列的控制部分，又是一台相对独立的小型标量处理机；三是一台标准的Burroughs B6700计算机，由它担负ILLIAC 输入输出系统和操作系统管理功能。第12页，共46页，2022年，5月20日，2点22分，星期二 图6.3 ILLIAC 系统框图第13页，共46页，2022

6、年，5月20日，2点22分，星期二1. BSP计算机它由系统管理计算机B7700/B7800和BSP处理机两大部分组成，前者可视为后者的前端机。系统管理机负责BSP程序编译、与远程终端及网络的数据通信、外围设备管理等，大多数BSP作业调度和操作系统活动也是在系统管理机上完成的。BSP处理机又可分为3部分，一是并行处理机，二是控制处理机，三是容量为464M字的文件存储器。6.3 集中式共享存储器SIMD计算机实例 第14页，共46页，2022年，5月20日，2点22分，星期二图6.6 BSP计算机系统框图操作系统和维护信息文件存储器CCD464M字文件存储器控制器文件存储器系统指令/控制存储器2

7、56K字控制维护单元标量处理单元并行处理机控制器控制处理机并行存储器0.58M字入口和出口对准网络16个算术单元并行处理机100M字/s100M字/s12.5M字/s系统管理机B7700/B7800程序和数据250K字/s第15页，共46页，2022年，5月20日，2点22分，星期二系统管理机文件存储器控制处理机(指令存储器，标量运算器)17个存储体16算术单元BSP科学处理机系统组成第16页，共46页，2022年，5月20日，2点22分，星期二为了说明BSP并行存储器的地址变换和无冲突访问，下面先看一个较简单的例子。设并行存储器的存储体数m=7(质数)，运算单元数n=6。若有一个45的数组。

8、 a00 a01 a02 a03 a04 a10 a11 a12 a13 a14 a20 a21 a22 a23 a24 a30 a31 a32 a33 a34第17页，共46页，2022年，5月20日，2点22分，星期二 BSP的地址映象关系为：先将二维数组按列或者按行的顺序变换为一维数组，以形成一个一维线性地址空间，地址用a表示。然后将地址a变换成并行存储器地址(j，i)，其中j是存储体体号，i是体内地址： j=a mod m i=an下整存储体数m为一质数，n为无冲突访问的最大存储体数。第18页，共46页，2022年，5月20日，2点22分，星期二3. BSP的数据流水线结构 BSP的1

9、6个AE组成的算术单元阵列、17个存储体组成的并行存储器和2套互连网络(对准网络)形成了一条5级数据流水线，使连续几条向量指令能在时间上重叠起来执行。由17个存储器输出端口并行读出16个操作数。经对准网络NWl将16个操作数重排列成16个算术单元需要的次序。将排列好的16个操作数送到16个算术单元完成操作。所得的16个结果经对准网络NW2重新排列成在17个存储体中存储所需要的次序。写入并行存储器。存储器处理器对准网络2对准网络1第19页，共46页，2022年，5月20日，2点22分，星期二6.4 阵列处理机的算法及性能分析 阵列处理机的处理器阵列有固定的结构，因此，阵列处理机的性能与算法有很大

10、关系。若问题求解的算法能与阵列处理机的结构相适应，就能获得较高的性能；否则，阵列处理机的实际性能就很低，处理单元的利用率也很低。 第20页，共46页，2022年，5月20日，2点22分，星期二6.4.1 阵列处理机的差分计算 描述平面场的拉普拉斯方程： 将二阶偏导数表示为差分形式 :代入原方程，则可得有限差分计算公式： 第21页，共46页，2022年，5月20日，2点22分，星期二迭代计算开始时，除由边界条件给定的某些边缘点之外，其余网格点的函数值初值均可设为零。若取网格间距为单位1，迭代计算的表达式为： 式中的上标 t 表示迭代次数。迭代计算直至连续二次迭代所求值的差小于规定误差为止。 第2

11、2页，共46页，2022年，5月20日，2点22分，星期二由于阵列处理机中处理器的数量比网格点数少得多，需要把离散域划分为若干个网格块，一个网格块上的网格点的迭代计算由一个处理器完成。在划分网格块时要注意两点，一是要使网格块的大小相等，二是要使网格块的周长尽可能小，且相邻网格块的邻界边长相等。迭代实现第23页，共46页，2022年，5月20日，2点22分，星期二6.4.2 阵列处理机的常用算法及性能分析 1. 矩阵加：把A和B同一位置的一对元素存放在同一个PEM中，那么，64个PE就可以同时并行地完成64对元素的相加。 第24页，共46页，2022年，5月20日，2点22分，星期二6.4.2

12、阵列处理机的常用算法及性能分析 2. 矩阵乘：若A和B为两个 88 的矩阵，并行地一次完成8个中间积的运算。最后对8个中间积做7次加法 。 7 cij = aikbkj 0 i , j 7 k=0(1) 顺序执行：每个Cij 需要8次乘法，7次加法，共需要 15*64=960 次加/乘法；第25页，共46页，2022年，5月20日，2点22分，星期二A(4*4)B(4*4)C(4*4)第26页，共46页，2022年，5月20日，2点22分，星期二A(4*4)B(4*4)C(4*4)第27页，共46页，2022年，5月20日，2点22分，星期二(2) 在Illiac 上执行：每列或每排Cij 需

13、要1次乘法，3次加法，共需要 4*8=32 次加/乘法； 求88的矩阵乘法，显然每列或每排Cij 需要1次乘法，7次加法，共需要 8*8=64 次加/乘法；书中说每个Cij需要1次乘法，7次加法，共需要 8*64=512次加、乘法。 显然有问题，没有充分利用64个运算器。第28页，共46页，2022年，5月20日，2点22分，星期二6.4.2 阵列处理机的常用算法及性能分析 3. 累加和 7 S = ai i=0第29页，共46页，2022年，5月20日，2点22分，星期二第30页，共46页，2022年，5月20日，2点22分，星期二 如果在阵列处理机上采用成对递归相加的算法，则只需log28

14、 = 3次加法时间。 首先，8个原始数据A(i)，0i7，存放在8个PEM的a单元中，然后按下述步骤求累加和。第1步 置全部PE为活跃状态；第2步 全部A(I)，0I7，从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步 若K3，则转第四步；否则，继续往下执行；第11步 置全部PE为活跃状态；第12步 全部PE的(R

15、GA)存入相应PEM的a+1单元中。第31页，共46页，2022年，5月20日，2点22分，星期二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页，2022年，5月20日，2点22分，星期二【例6

16、.1】 A和B都是元素为浮点表示的6464的二维数组，一次浮点加法的计算过程可由取数、求阶差、对阶、尾数加、规格化和存数共6个段组成，若每个段的执行时间均为 ，请分别求出在下列结构不同的处理机上完成C=A+B所需时间及相对于顺序处理方式的加速比。 第33页，共46页，2022年，5月20日，2点22分，星期二（1）顺序处理方式的处理机。（2）具有浮点加法流水线的流水处理机，且浮点加法流水线分为6个段，各段执行时间均为 。（3）88的阵列处理机，且处理阵列上的每个处理器只能顺序处理浮点加运算。（4）88的阵列处理机，且处理阵列上的每个处理器均能流水处理浮点加运算。（5）6464的阵列处理机。 第

17、34页，共46页，2022年，5月20日，2点22分，星期二解 （1）需要顺序执行的浮点加法次数为 ，每次浮点加运算所需时间为 ，则全部运算所需时间为（2）需要流水执行的浮点加法次数为 ，则一个 段的浮点加法流水线处理全部运算所需时间和加速比为第35页，共46页，2022年，5月20日，2点22分，星期二（3）对于88的处理阵列，每个处理器需要处理6464二维数组中的一个的子数组，因此，每个处理器需要执行的浮点加法次数为88=64。每次浮点加运算所需时间为 。每个处理器顺序执行64次浮点加运算所需时间为 。64个处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时间和加速比为第

18、36页，共46页，2022年，5月20日，2点22分，星期二（4）对于88的处理阵列，每个处理器需要流水处理6464二维数组中的一个88的子数组，因此，每个处理器的浮点加法次数为n=88=64，k=6段的浮点加法流水线处理64次浮点加运算所需时间为 64个处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时间和加速比为第37页，共46页，2022年，5月20日，2点22分，星期二（5）对于6464的处理阵列，每个处理器只需执行一次浮点加法运算，所需时间为 ，所以，全部运算所需时间和加速比为第38页，共46页，2022年，5月20日，2点22分，星期二【例6.2】 分别计算在下列

19、各处理机中，计算所需的时间及相对于顺序处理方式的加速比。（1）顺序处理方式的处理机。第39页，共46页，2022年，5月20日，2点22分，星期二（2）具有一个流水加法器和一个流水乘法器的流水处理机，且加法器和乘法器可以同时工作。（3）8个处理单元之间用双向环互连的并行处理机，相邻PE之间传送一次数据需时 。（4）88的ILLIAC 阵列处理机，且相邻处理单元之间传送一次数据需时 。假设各处理机或处理单元取数和存数的时间忽略不计，完成一次加法需时2 ，完成一次乘法需时4 。第40页，共46页，2022年，5月20日，2点22分，星期二解 计算点积 需要做8次乘法和7次加法。（1）顺序执行8次乘法所需时间为再顺序执行7次加法所需时间为故共需时间为第41页，共46页，2022年，5月20日，2点22分，星期二（2）在流水处理机上，8次乘运算分别用18表示，