计算机系统结构 第八章 并行处理机.ppt

8.4 SIMD处理机算法举例 8.4.1 有限差分问题 8.4.2 矩阵乘 8.4.3 求累加和 SIMD处理机特别依赖于并行算法。 并行算法的一个关键是提高向量化的程度。 在设计并行算法时，要特别注意： 数据在多个存储模块之间的分布。 要解决好访问存储器的冲突问题。 互连网络并不能提供所有处理单元之间的连接，因此，并行算法要充分利用互连网络的结构。 8.4.1 有限差分问题 有限差分方法是一种通用和有效方法： 把连续方程变换成离散形式。二阶偏导数表示为差分形式： 并代入原方程，则可得有限差分计算公式： 其中：(x, y)为平面直角坐标， h为网格间距。 IlliacIV的阵列结构特别适合计算这种在网格上定义的有限差分函数。 把内部网格点分配给各个处理单元，计算过程可以并行完成。 运算速度的提高可以与处理机数目成正比。 8.4.2 矩阵乘 矩阵乘是典型的并行程序，非常适合在SIMDSIMD处理机上运行。 例如：A、B、C均为8×8的二维矩阵，则C＝A×B的计算公式为： 在串行机上要用一个三重循环程序，乘法和加法分别为512次。 如果在SIMD处理机上求解，FORTRAN语言程序如下： DO 10 I＝0，7 C(I, J)=0 DO 20 K=0, 7 20 C(I, J)=C (I, J )+A(I, K) * B(K, J) 10 CONTINUE 可以在8个PE的SIMD处理机运行，运算速度可提高8倍。也可在64个PE的SIMD处理机上运行 数据如何分布到各个局部存储器中？ 在SIMD处理机上，J循环只需一次。 PE0：c00＝a00b00＋a01b10＋a02b20……＋a07b70 PE1：c01＝a00b01＋a01b11＋a02b21……＋a07b71 …… PE7：c07＝a00b07＋a01b17＋a02b27……＋a07b77 PE0：c10＝a10b00＋a11b10＋a12b20……＋a17b70 PE1：c11＝a10b01＋a11b11＋a12b21……＋a17b71 …… PE7：c17＝a10b07＋a11b17＋a12b27……＋a17b77 …… PE7：c77＝a70b07＋a71b17＋a72b27……＋a77b77 8.4.3 求累加和 把N个数的顺序相加变为并行相加。 串行求和的 FORTRAN 程序如下： C(-1)＝0 DO 10 I＝0, N 10 C(I)＝C(I-1)＋A(I) 在SIMD处理机上，采用递归加法，FORTRAN 程序如下： DO 10 I=0，log2N－1 10 A＝A＋SRL(A, 2**I) ;A向量右移2i个PE 在SIMD处理机上只需做 log2N 次加法。 递归求和算法的性能分析： 运算速度提高：加速比为N/log2N倍 运算次数增加：从N次增加到N·log2N次 效率降低：实际效率为1/log2N 如：N＝1024，速度提高100倍，运算次数增加10倍，效率只有1/10 如果N＝220，即100万个数求和，速度可以提高5万倍。 这种方法也称为级联求和，或递归求和。 与流水线中采用的方法类似，它利用加法结合律来提高并行度。 本章重点： 1.并行处理的基本结构 2.并行处理的特点 3.典型的SIMD处理机算法 练习题: 8.3 8.6（改为：n个PE） 8.12 * 计算机系统结构 第八章 并行处理机 第8章 SIMD 处理机 8.1 SIMD处理机模型 8.2 SIMD处理机的结构 8.3 SIMD处理机实例 8.4 SIMD处理机算法举例 两种并行性概念： (1)同时性并行Simultaneity：两个或两个以上事件在同一时刻发生。 (2)并发性并行Concurrency：两个或两个以上事件在同一时间间隔内发生。 三条技术途径： (1)资源重复：重复设置多个部件来提高速度。 (2)时间重叠：流水线 (3)资源共享：分时系统，分布式系统 8.1 SIMD处理机模型 1. SIMD处理机的定义： 多个处理部件PU按照一定方式互连，在同一个控制部件CU控制下，对各自的数据完成同一条指令规定的操作。从CU看，指令是串行执行的，从PU看，数据是并行处理的。 按照按照佛林分类法，它属于SIMD处理机。SIMD处理机又称SIMD处理机，也称为阵列处理机。 2. SIMD处理机的主要应用领域： 用于高速向量或矩阵运算。 3. SIMD处