指令流多数据流计算机.ppt

计算机系统结构（第二版）,目录,第6章单指令流多数据流计算机6.1单指令流多数据流计算机的基本结构与特点6.2分布式存储器SIMD计算机实例分析6.3集中式共享存储器SIMD计算机实例分析6.4阵列处理机的算法及性能分析,第6章单指令流多数据流计算机,6.1单指令流多数据流计算机的基本结构与特点,单指令流多数据流（SIMD）计算机的关键特征是它的并行处理机。,它的并行处理机是由单一控制部件控制多个处理单元同时进行运算操作，多个处理单元通常通过互连网络连接成阵列结构，故也称为阵列处理机。,并行处理机的所有处理单元同时执行从控制部件广播来的同一条指令，但指令使用不同的数据，因此，并行处理机是指令操作级并行的单指令流多数据流处理机。,6.1.1单指令流多数据流计算机的两种基本结构,根据存储器的组织方式不同，单指令流多数据流计算机的基本结构分为两种：集中式共享存储器型分布式存储器型,1.分布式存储器SIMD计算机基本结构,并行处理机的每个处理单元都有自己的局部存储器，存放可直接访问的数据。所有的处理单元通过互连网络互联。阵列控制部件CU是一台功能专用的处理机，它执行程序流控制指令和程序中的标量运算。管理处理机SC运行操作系统，管理系统资源。,图6.1分布式存储器的SIMD计算机基本结构,2.集中式共享存储器SIMD计算机基本结构,并行处理机的所有处理单元共享由个存储体组成的并行存储器，处理单元与存储体之间通过互连网络互连。CU和SC的功能与采用分布式存储器构型的SIMD计算机没有什么差别。,图6.2集中式共享存储器的SIMD计算机基本结构,6.1.2单指令流多数据流计算机的主要特点,SIMD的效率取决于计算程序向量化的程度。SIMD计算机依靠的并行措施是资源重复。SIMD计算机的互连网络决定了SIMD计算机能适应的算法类别，SIMD计算机的实际有效速度取决于另外两个因素。一是标量运算速度，二是编译过程的时间开销。SIMD计算机是根据功能专用化的原则组成的一种异构型多计算机系统。,6.2分布式存储器SIMD计算机实例分析,两种典型的SIMD计算机采用分布式存储器结构的并行处理机的ILLIAC计算机。采用集中式共享存储器结构的并行处理机的BSP计算机。,1.ILLIAC阵列,ILLIAC系统由3种类型处理机组成的一个异构多处理机系统。一是专门用于数组运算的处理单元阵列；二是阵列控制器，它既是处理单元阵列的控制部分，又是一台相对独立的小型标量处理机；三是一台标准的BurroughsB6700计算机，由它担负ILLIAC输入输出系统和操作系统管理功能。,图6.3ILLIAC系统框图,1.BSP计算机,它由系统管理计算机B7700/B7800和BSP处理机两大部分组成，前者可视为后者的前端机。系统管理机负责BSP程序编译、与远程终端及网络的数据通信、外围设备管理等，大多数BSP作业调度和操作系统活动也是在系统管理机上完成的。BSP处理机又可分为3部分，一是并行处理机，二是控制处理机，三是容量为464M字的文件存储器。,6.3集中式共享存储器SIMD计算机实例,图6.6BSP计算机系统框图,系统管理机,文件存储器,控制处理机(指令存储器，标量运算器),17个存储体16算术单元,BSP科学处理机系统组成,为了说明BSP并行存储器的地址变换和无冲突访问，下面先看一个较简单的例子。设并行存储器的存储体数m=7(质数)，运算单元数n=6。若有一个45的数组。a00a01a02a03a04a10a11a12a13a14a20a21a22a23a24a30a31a32a33a34,BSP的地址映象关系为：先将二维数组按列或者按行的顺序变换为一维数组，以形成一个一维线性地址空间，地址用a表示。然后将地址a变换成并行存储器地址(j，i)，其中j是存储体体号，i是体内地址：j=amodmi=an下整存储体数m为一质数，n为无冲突访问的最大存储体数。,3.BSP的数据流水线结构BSP的16个AE组成的算术单元阵列、17个存储体组成的并行存储器和2套互连网络(对准网络)形成了一条5级数据流水线，使连续几条向量指令能在时间上重叠起来执行。由17个存储器输出端口并行读出16个操作数。经对准网络NWl将16个操作数重排列成16个算术单元需要的次序。将排列好的16个操作数送到16个算术单元完成操作。所得的16个结果经对准网络NW2重新排列成在17个存储体中存储所需要的次序。写入并行存储器。,存储器,处理器,对准网络2,对准网络1,6.4阵列处理机的算法及性能分析,阵列处理机的处理器阵列有固定的结构，因此，阵列处理机的性能与算法有很大关系。若问题求解的算法能与阵列处理机的结构相适应，就能获得较高的性能；否则，阵列处理机的实际性能就很低，处理单元的利用率也很低。,6.4.1阵列处理机的差分计算,描述平面场的拉普拉斯方程：,将二阶偏导数表示为差分形式:,代入原方程，则可得有限差分计算公式：,迭代计算开始时，除由边界条件给定的某些边缘点之外，其余网格点的函数值初值均可设为零。若取网格间距为单位1，迭代计算的表达式为：,式中的上标t表示迭代次数。迭代计算直至连续二次迭代所求值的差小于规定误差为止。,由于阵列处理机中处理器的数量比网格点数少得多，需要把离散域划分为若干个网格块，一个网格块上的网格点的迭代计算由一个处理器完成。在划分网格块时要注意两点，一是要使网格块的大小相等，二是要使网格块的周长尽可能小，且相邻网格块的邻界边长相等。,迭代实现,6.4.2阵列处理机的常用算法及性能分析,1.矩阵加：把A和B同一位置的一对元素存放在同一个PEM中，那么，64个PE就可以同时并行地完成64对元素的相加。,6.4.2阵列处理机的常用算法及性能分析,2.矩阵乘：若A和B为两个88的矩阵，并行地一次完成8个中间积的运算。最后对8个中间积做7次加法。7cij=aikbkj0i,j7k=0,(1)顺序执行：每个Cij需要8次乘法，7次加法，共需要15*64=960次加/乘法；,A(4*4),B(4*4),C(4*4),A(4*4),B(4*4),C(4*4),(2)在Illiac上执行：每列或每排Cij需要1次乘法，3次加法，共需要4*8=32次加/乘法；求88的矩阵乘法，显然每列或每排Cij需要1次乘法，7次加法，共需要8*8=64次加/乘法；书中说每个Cij需要1次乘法，7次加法，共需要8*64=512次加、乘法。显然有问题，没有充分利用64个运算器。,6.4.2阵列处理机的常用算法及性能分析,3.累加和7S=aii=0,如果在阵列处理机上采用成对递归相加的算法，则只需log28=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的(RGA)存入相应PEM的a+1单元中。,0,1,2,3,4,5,6,7,RGA,0,1,2,3,4,5,6,7,RGR,K=0,0,1,2,3,4,5,6,RGR,7,0,0-1,1-2,2-3,3-4,4-5,5-6,6-7,RGA,0,0-1,1-2,2-3,3-4,4-5,5-6,6-7,RGR,K=1,0,0-1,1-2,2-3,3-4,4-5,5-6,6-7,0,0-1,0-2,0-3,1-4,2-5,3-6,4-7,RGA,RGR,0,0-1,0-2,0-3,1-4,2-5,3-6,4-7,RGR,K=2,1-4,2-5,3-6,4-7,0,0-1,0-2,0-3,RGR,0,0-1,0-2,0-3,0-4,0-5,0-6,0-7,RGA,【例6.1】A和B都是元素为浮点表示的6464的二维数组，一次浮点加法的计算过程可由取数、求阶差、对阶、尾数加、规格化和存数共6个段组成，若每个段的执行时间均为，请分别求出在下列结构不同的处理机上完成C=A+B所需时间及相对于顺序处理方式的加速比。,（1）顺序处理方式的处理机。（2）具有浮点加法流水线的流水处理机，且浮点加法流水线分为6个段，各段执行时间均为。（3）88的阵列处理机，且处理阵列上的每个处理器只能顺序处理浮点加运算。（4）88的阵列处理机，且处理阵列上的每个处理器均能流水处理浮点加运算。（5）6464的阵列处理机。,解（1）需要顺序执行的浮点加法次数为，每次浮点加运算所需时间为，则全部运算所需时间为（2）需要流水执行的浮点加法次数为，则一个段的浮点加法流水线处理全部运算所需时间和加速比为,（3）对于88的处理阵列，每个处理器需要处理6464二维数组中的一个的子数组，因此，每个处理器需要执行的浮点加法次数为88=64。每次浮点加运算所需时间为。每个处理器顺序执行64次浮点加运算所需时间为。64个处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时间和加速比为,（4）对于88的处理阵列，每个处理器需要流水处理6464二维数组中的一个88的子数组，因此，每个处理器的浮点加法次数为n=88=64，k=6段的浮点加法流水线处理64次浮点加运算所需时间为64个处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时间和加速比为,（5）对于6464的处理阵列，每个处理器只需执行一次浮点加法运算，所需时间为，所以，全部运算所需时间和加速比为,【例6.2】分别计算在下列各处理机中，计算所需的时间及相对于顺序处理方式的加速比。（1）顺序处理方式的处理机。,（2）具有一个流水加法器和一个流水乘法器的流水处理机，且加法器和乘法器可以同时工作。（3）8个处理单元之间用双向环互连的并行处理机，相邻PE之间传送一次数据需时。（4）88的ILLIAC阵列处理机，且相邻处理单元之间传送一次数据需时。假设各处理机或处理单元取数和存数的时间忽略不计，完成一次加法需时2，完成一次乘法需时4。,解计算点积需要做8次乘法和7次加法。（1）顺序执行8次乘法所需时间为再顺序执行7次加法所需时间为故共需时间为,（2）在流水处理机上，8次乘运算分别用18表示，7次加运算分别用915表示,图6.10计算S的时空图,（3）由8个PE组成的双向环，每个PE有自己的局部存储器PEM，向量A和B的元素对ai和bi存储在相应的PEMi中。双向环上的累加和计算过程可以用树形流程图直观地表示，结点表示PE，有向弧箭头表示相应PE之间沿双向环的数据传送，需要特别指出的是：由于SIMD计算机的并行处理机的所有处理单元（PE）只能同时执行同一条指令，因此，SIMD的树形流程图中同一层的所有结点只能执行同一种运算。有向弧的值为数据传送时间，如果两层之间的有向弧的值不等，