第6章 单指令流多数据流计算机

华中科技大学出版社计算机系统结构（第二版）华中科技大学出版社华中科技大学出版社计算机系统结构（第二版）目录第6章单指令流多数据流计算机6.1单指令流多数据流计算机的基本结构与特点6.2分布式存储器SIMD计算机实例分析6.3集中式共享存储器SIMD计算机实例分析6.4阵列处理机的算法及性能分析华中科技大学出版社计算机系统结构（第二版）第6章单指令流多数据流计算机华中科技大学出版社计算机系统结构（第二版）6.1单指令流多数据流计算机的基本结构与特点单指令流多数据流（SIMD）计算机的关键特征是它的并行处理机。它的并行处理机是由单一控制部件控制多个处理单元同时进行运算操作，多个处理单元通常通过互连网络连接成阵列结构，故也称为阵列处理机。并行处理机的所有处理单元同时执行从控制部件广播来的同一条指令，但指令使用不同的数据，因此，并行处理机是指令操作级并行的单指令流多数据流处理机。华中科技大学出版社计算机系统结构（第二版）6.1.1单指令流多数据流计算机的两种基本结构根据存储器的组织方式不同，单指令流多数据流计算机的基本结构分为两种：集中式共享存储器型分布式存储器型华中科技大学出版社计算机系统结构（第二版）1.分布式存储器SIMD计算机基本结构采用分布式存储器构型的SIMD计算机的基本结构如图6.1所示。并行处理机的每个处理单元都有自己的局部存储器，存放可直接访问的数据。所有的处理单元通过互连网络互联。阵列控制部件CU是一台功能专用的处理机，它执行程序流控制指令和程序中的标量运算。管理处理机SC运行操作系统，管理系统资源。华中科技大学出版社计算机系统结构（第二版）LM1主机网络控制向量指令指令I/O用户广播总线（指令和常数）数据总线数据寻径网络标量指令PE1LM2PE2LMnPEn大容量存储器控制存储器（程序和数据）标量处理机阵列控制部件PE：处理单元LM：本地存储器…图6.1分布式存储器的SIMD计算机基本结构华中科技大学出版社计算机系统结构（第二版）2.集中式共享存储器SIMD计算机基本结构采用集中式共享存储器构型的SIMD计算机的基本结构如图6.2所示。并行处理机的所有处理单元共享由个存储体组成的并行存储器，个处理单元与个存储体之间通过互连网络互连。CU和SC的功能与采用分布式存储器构型的SIMD计算机没有什么差别。华中科技大学出版社计算机系统结构（第二版）SMm-1主机网络控制I/O用户广播总线（向量指令）数据总线对准网络标量指令PE1SM2PE2SMmPEn大容量存储器标量处理机…控制存储器阵列控制部件SM1…图6.2集中式共享存储器的SIMD计算机基本结构华中科技大学出版社计算机系统结构（第二版）6.1.2单指令流多数据流计算机的主要特点SIMD计算机的效率取决于计算程序向量化的程度。SIMD计算机依靠的并行措施是资源重复。SIMD计算机的互连网络决定了SIMD计算机能适应的算法类别，SIMD计算机的实际有效速度取决于另外两个因素。一是标量运算速度，二是编译过程的时间开销。SIMD计算机是根据功能专用化的原则组成的一种异构型多计算机系统。华中科技大学出版社计算机系统结构（第二版）6.2分布式存储器SIMD计算机实例分析两种典型的SIMD计算机采用分布式存储器结构的并行处理机的ILLIACⅣ计算机。采用集中式共享存储器结构的并行处理机的BSP计算机。华中科技大学出版社计算机系统结构（第二版）1.ILLIACⅣ阵列ILLIACⅣ系统框图如图6.3所示。它是由3种类型处理机组成的一个异构多处理机系统。一是专门用于数组运算的处理单元阵列；二是阵列控制器，它既是处理单元阵列的控制部分，又是一台相对独立的小型标量处理机；三是一台标准的BurroughsB6700计算机，由它担负ILLIACⅣ输入输出系统和操作系统管理功能。华中科技大学出版社计算机系统结构（第二版）CUPE0PE1PE63…PEM0PEM1PEM6364CDBBPE6364×8CU总线模式位线控制线PE0CDC48BIOMDFS12848B6700CPUIOS2562561024I/O总线实时装置1024B6700内存B6700多路开关4848B6700外围设备APPA网接口激光存储器图6.3ILLIACⅣ系统框图华中科技大学出版社计算机系统结构（第二版）1.BSP计算机BSP计算机系统框图如图6.6所示。它由系统管理计算机B7700/B7800和BSP处理机两大部分组成，前者可视为后者的前端机。系统管理机负责BSP程序编译、与远程终端及网络的数据通信、外围设备管理等，大多数BSP作业调度和操作系统活动也是在系统管理机上完成的。BSP处理机又可分为3部分，一是并行处理机，二是控制处理机，三是容量为4~64M字的文件存储器。6.3集中式共享存储器SIMD计算机实例分析华中科技大学出版社计算机系统结构（第二版）图6.6BSP计算机系统框图操作系统和维护信息文件存储器CCD4～64M字文件存储器控制器文件存储器系统指令/控制存储器256K字控制维护单元标量处理单元并行处理机控制器控制处理机并行存储器0.5～8M字入口和出口对准网络16个算术单元并行处理机100M字/s100M字/s12.5M字/s系统管理机B7700/B7800程序和数据250K字/s●●华中科技大学出版社计算机系统结构（第二版）6.4阵列处理机的算法及性能分析阵列处理机的处理器阵列有固定的结构，因此，阵列处理机的性能与算法有很大关系。若问题求解的算法能与阵列处理机的结构相适应，就能获得较高的性能；否则，阵列处理机的实际性能就很低，处理单元的利用率也很低。华中科技大学出版社计算机系统结构（第二版）6.4.1阵列处理机的差分计算描述平面场的拉普拉斯方程：02222yUxU4),(),(),(),(),(hyxUyhxUhyxUyhxUyxU222222),(),(2),(),(),(2),(hhyxUyxUhyxUyUhyhxUyxUyhxUxU将二阶偏导数表示为差分形式:代入原方程，则可得有限差分计算公式：华中科技大学出版社计算机系统结构（第二版）迭代计算开始时，除由边界条件给定的某些边缘点之外，其余网格点的函数值初值均可设为零。若取网格间距为单位1，迭代计算的表达式为：4)(1,)(,1)(1,)(,1)1(,tjitjitjitjitjiUUUUU式中的上标t表示迭代次数。迭代计算直至连续二次迭代所求值的差小于规定误差为止。华中科技大学出版社计算机系统结构（第二版）由于阵列处理机中处理器的数量比网格点数少得多，需要把离散域划分为若干个网格块，一个网格块上的网格点的迭代计算由一个处理器完成。在划分网格块时要注意两点，一是要使网格块的大小相等，二是要使网格块的周长尽可能小，且相邻网格块的邻界边长相等。迭代实现华中科技大学出版社计算机系统结构（第二版）6.4.2阵列处理机的常用算法及性能分析1.矩阵加：把A和B同一位置的一对元素存放在同一个PEM中，那么，64个PE就可以同时并行地完成64对元素的相加。2.矩阵乘：若A和B为两个8×8的矩阵，并行地一次完成8个中间积的运算。最后对8个中间积做7次加法。3.累加和华中科技大学出版社计算机系统结构（第二版）【例6.1】A和B都是元素为浮点表示的64×64的二维数组，一次浮点加法的计算过程可由取数、求阶差、对阶、尾数加、规格化和存数共6个段组成，若每个段的执行时间均为，请分别求出在下列结构不同的处理机上完成C=A+B所需时间及相对于顺序处理方式的加速比。tΔ华中科技大学出版社计算机系统结构（第二版）（1）顺序处理方式的处理机。（2）具有浮点加法流水线的流水处理机，且浮点加法流水线分为6个段，各段执行时间均为。（3）8×8的阵列处理机，且处理阵列上的每个处理器只能顺序处理浮点加运算。（4）8×8的阵列处理机，且处理阵列上的每个处理器均能流水处理浮点加运算。（5）64×64的阵列处理机。tΔ华中科技大学出版社计算机系统结构（第二版）解（1）需要顺序执行的浮点加法次数为，每次浮点加运算所需时间为，则全部运算所需时间为（2）需要流水执行的浮点加法次数为，则一个段的浮点加法流水线处理全部运算所需时间和加速比为40966464ttTΔ57624Δ640961t6ΔtttnkTΔ4101Δ)140966(Δ)1(209646464n6k9.5/212TTS华中科技大学出版社计算机系统结构（第二版）（3）对于8×8的处理阵列，每个处理器需要处理64×64二维数组中的一个的子数组，因此，每个处理器需要执行的浮点加法次数为8×8=64。每次浮点加运算所需时间为。每个处理器顺序执行64次浮点加运算所需时间为。64个处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时间和加速比为t6ΔttΔ384Δ664tTΔ384364/313TTS华中科技大学出版社计算机系统结构（第二版）（4）对于8×8的处理阵列，每个处理器需要流水处理64×64二维数组中的一个8×8的子数组，因此，每个处理器的浮点加法次数为n=8×8=64，k=6段的浮点加法流水线处理64次浮点加运算所需时间为。64个处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时间和加速比为tttnkΔ691)Δ64(6Δ)1(tTΔ6942.356/414TTS华中科技大学出版社计算机系统结构（第二版）（5）对于64×64的处理阵列，每个处理器只需执行一次浮点加法运算，所需时间为，所以，全部运算所需时间和加速比为tΔ6tTΔ654096/515TTS华中科技大学出版社计算机系统结构（第二版）【例6.2】分别计算在下列各处理机中，计算所需的时间及相对于顺序处理方式的加速比。（1）顺序处理方式的处理机。81iiibaS华中科技大学出版社计算机系统结构（第二版）（2）具有一个流水加法器和一个流水乘法器的流水处理机，且加法器和乘法器可以同时工作。（3）8个处理单元之间用双向环互连的并行处理机，相邻PE之间传送一次数据需时。（4）8×8的ILLIACⅣ阵列处理机，且相邻处理单元之间传送一次数据需时。假设各处理机或处理单元取数和存数的时间忽略不计，完成一次加法需时2，完成一次乘法需时4。tttt华中科技大学出版社计算机系统结构（第二版）解计算点积需要做8次乘法和7次加法。（1）顺序执行8次乘法所需时间为再顺序执行7次加法所需时间为故共需时间为81iiibaSttΔ32Δ48ttΔ14Δ27tttTΔ46Δ14Δ321华中科技大学出版社计算机系统结构（第二版）（2）在流水处理机上，8次乘运算分别用1~8表示，7次加运算分别用9~15表示，时空图如图6.10所示图6.10计算S的时空图tTΔ34235.134/46/212TTS华中科技大学出版社计算机系统结构（第二版）（3）由8个PE组成的双向环，每个PE有自己的局部存储器PEM，向量A和B的元素对和存储在相应的中。双向环上的累加和计算过程可以用树形流程图直观地表示，结点表示PE，有向弧箭头表示相应PE之间沿双向环的数据传送，需要特别指出的是：由于SIMD计算机的并行处理机的所有处理单元（PE）只能同时执行同一条指令，因此，SIMD的树形流程图中同一层的所有结点只能执行同一种运算。有向弧的值为数据传送时间，如果两层之间的有向弧的值不等，那么，应取最大值作为层间PE的数据传送时间。iaibiPEM华中科技大学出版社计算机系统结构（第二版）在双向环上完成累加和计算3次传送所需时间:3次加法所需时间:累加和计算需要时间:计算S共需时间:相对于顺序处理方式的加速比为：ttttΔ4ΔΔ2ΔttΔ6Δ23tttΔ10Δ6Δ4tttTΔ14Δ10Δ433.314/46/313TTS图6.11双向环的树形流程图华中科技大学出版社计算机系统结构（第二版）（