并行算法的设计与分析(1)

《并行算法的设计与分析(1)》由会员分享，可在线阅读，更多相关《并行算法的设计与分析(1)（50页珍藏版）》请在金锄头文库上搜索。

1、并行算法设计与分析钟诚 3236396， 教材 陈国良.并行算法的设计与分析，第3版. 北京:高等教育出版社,2009参考书 1 陈国良. 并行计算结构算法 编程, 第3版. 北京：高等 教育出版社,2011 2 陈国良等. 并行算法实践.北京：高等教育出版社,2004 3 苏德富,钟诚. 计算机算法设计与分析,第2版. 北京：电子工业出版社, 2005 4 C. Xavier, S. S. Iyenger著, 张云泉等译. 并行算法导论.北京：机械工业出版社, 1998 5 Ananth Grama. 并行计算导论, 第2版,英文版. 北京:机械工业出版社,2003为什么需要学习研究并行算法

2、？v 计算机算法+数据结构=计算机程序。 v 计算机程序+文档+控制数据=计算机软件。 v 计算机软件+市场=（精神与物质的）财富。 v 并行计算机、并行算法可以显著加速大规模、复 杂问题的处理（求解）速度，可以获得问题的更 精确（更好）的解。 v 客观世界的一切事物（对象）及其活动都是并发 （并行）进行的，将事物（对象）及其活动映射成计算机软件解时，设计开发的计算机软件（计 算机程序、计算机算法）自然也应当是并行的！版权声明本教学PPT仅供课堂教学教师使用第一章 绪论1.1 引言1. 并行处理 (Parallel Processing)挖掘计算(Computing)过程的并发事件的信息处理.

3、2. 并发性 (Concurrency)并行性(Parallelism) 同时性(Simultaneity) 流水线(Pipelining)3. 并行处理的级别(Parallel Processing Level)指令级并行(Instruction Level Parallelism-ILP, 指令内部并行,指令之间并行) 细粒度并行 (fine grain parallelism/ tiny granularity parallelism )线程级并行(Thread Level Parallelism-TLP)中细粒度并行 (fine- medium grain parallelism)进程

4、级(Process Level Parallelism-PLP)/过程级/算法级并行 中粒度并行 (medium grain parallelism)任务级并行(Task Level Parallel) 粗粒度并行 (coarse grain parallelism)4. 并行计算(Parallel Computing)学科并行计算机体系结构 (Parallel Computer Architectures)并行算法 (Parallel Algorithms)并行程序设计 (Parallel Programming) 5. 多核处理器（Multi-core Processors，又称片上多处理

5、器-Chip Multi-Processor, CMP） 、众核处理器(Many-core Processors, 如GPU)、多线程并行技术(Multi- thread Parallel Techniques) 的出现与应用，使得并行算法的研究与开发显得极其 迫切且富有挑战性。第一章 绪论1.2 并行算法的硬件基础 1.2.1 并行计算机的体系结构: 并行计算机分类 v Flynn分类（1966年）(1) 单指令流单数据流机器SISD，即传统的单处理机(2) 单指令流多数据流机器SIMD-Single Instruction Stream Multiple Data Stream(3) 多指

6、令流单数据流机器MISD （目前无实际的商用机器）(4) 多指令流多数据流机器MIMD-Multiple Instruction Stream Multiple Data Streamv 并行机的结构模型实际的机器体系结构PVP (Parallel Vector Processor, 并行向量机) SIMD 阵列处理器（SIMD PE）SMP (Symmetric Multiprocessor, 对称多处理机)MPP (Massively Parallel Processor, 大规模并行处理机)Clusters ( 工作站机群Workstation-Cluster, PC机群PC-Clust

7、er, SMP机群 SMP-Cluster等)；目前大部分“超级并行计算机”均采用Clusters结构DSM (Distributed Shared Memory, 分布共享存储多处理机) 第一章 绪论1.2.1 并行计算机的体系结构: 并行计算机分类结构模型物理机模型VPVPVP交叉开关SM(a) PVPP/CP/CP/C总线或交叉开关SM(b) SMP, 物理上单一地址空间P/CP/CP/C定制网络LMLMLM虚拟分布共享存储(DSM) (d) DSM (MPP/Cluster), 逻辑上单一地址空间P/CP/CP/C定制网络LMLMLM(c) MPP, 物理/逻辑上多地址空间P/CP/C

8、P/C定制/标准网络LMLMLM(e) Cluster/COW, 物理/逻辑上多地址空间第一章 绪论1.2.1 并行计算机的体系结构: 并行计算机分类结构模型物理机模型SMPSMPSMPSAN/LANSMSMSMMPPMPPMPPSAN/LANDSMDSMDSM(f) SMP-Cluster(g) DSM-ClusterSMPMPPMPPWANLMDSMSM(h) Grid (Cluster of Clusters)1.2.1 并行计算机的互连网络v 静态互连网络(固定连接)connected graph: vertices = processing nodes, edges = commun

9、ication links(1) 一维线性连接LA(1-D Linear Array): 一维阵列不带环绕的1-D LA，带环绕的1-D LA, 通信直径n-1, n处理器数 (2) 网孔连接MC (Mesh Connected): 二维阵列互连函数: MC2+1(p)=(p+1) mod n, MC2-1(p)=(p-1) mod nMC2+n 1/2(p)=(p+n1/2) mod n, MC2-n 1/2(p)=(p-n1/2) mod n, p处理器编号不带环绕的MC，带环绕的MC , 通信直径n1/2-1,1.2.1 并行计算机的互连网络v 网孔结构的扩展: 可重构网孔 RMESH

10、(Reconfigurable Mesh)网孔+可重构总线动态重新设置并行计算机的互连结构，例如可动态设置成多条行总线、列总 线或者对角线总线处理机阵列结构，也可动态将规模n n的二维RMESH结 构设置成n个规模n1/2 n1/2的子MESH结构。每个处理器通过四个端口（ N,E,S,W）与总线相连，在处理器内部有6个开关控制这四个端口之间的连 接关系，如图a所示。这四个端口之间共有15种连接方式，如图b所示。 123123iijP(2,3)NESW: 开关NSEWNSEWNSEWNSEWNEWEWSNE,W,SNEW,S,NE,W,S,NEW,SNNSEWNSEWEWN,SEWS,NNWS

11、,EW,NESNW,SENSEWNSEWNSEWNSEWNE,W,SN,W,ESWS,N,ENW,S,ENE,SWNSEWNSEWNSEWNSEW(a)(b)2D-RMESH结构1.2.1 并行计算机的互连网络v 静态互连网络(3) 树形连接TC(Tree Connected)二叉树，通信直径2(logn-1) 胖树(X树）根结点处理器负载过重，瓶颈结点 要求根结点处理和容错能力强千万亿次神威蓝光超级并行计算机群采用胖树结构连接机群中的处理器结点曙光5000A超级并行计算机群系统机采用树结构连接机群中的处理器结点1.2.1 并行计算机的互连网络v 静态互连网络(4) 树网连接MT(Mesh o

12、f tree) 1.2.1 并行计算机的互连网络v 静态互连网络 (5) 金字塔连接 (Pyramid) (6) 超立方连接HC (Hypercube Connected)互连函数: CCi(pm-1 pm-2 pi+1 pi pi-1 p1 p0 )= pm-1 pm-2 pi+1 pi pi-1 p1 p0 其中pm-1 pm-2 pi+1 pi pi-1 p1 p0为处理器编号的二进制表示, pi 为对pi 求 反, i=0m-1, m=log2n, n=2m ; 通信直径log2n. 不易扩展. 例: n=16, CC0(0000 )= 0001, CC0(0001 )= 0000,

13、CC0(0010 )= 0011, CC0(0011 )= 0010, CC0(0100 )= 0101, CC0(0101 )= 0100, CC0(0110 )= 0111, CC0(0111 )= 0110, CC0(1000 )= 1001, CC0(1001 )= 1000, 3立方 4立方1.2.1 并行计算机的互连网络v 扩展的超立方结构-光电超立方机器立方体内的结点(处理器)由电信号连接, 超立方体之间用光 信号(光波)连接. 机器规模扩展容易.电信号连接 光信号连接1.2.1 并行计算机的互连网络v 静态互连网络(7)立方环连接CCC (Cube Connected-Cycl

14、es)(8)洗牌交换连接SE(Shuffle Exchange)物理上是SIMD-SM机器互连函数: SH(pm-1 pm-2 p1 p0 )= pm-2 pm-3 p1 p0 pm-1 ,循环左移1位, m=lognEX(pm-1 pm-2 p1 p0 )= pm-1 pm-2 p1 p0 , 奇偶相邻处理器交换数据例: n=8个处理器的洗牌和交换函数:SH(p)=(0) (1,2,4) (3,6,5 ) (7); EX(p)=(0,1) (2,3) (4,5) (6,7)P0 - P1 (y) P2 - P3 P4 - P5(x) P6-P7特点：位于某个处理器中的数据，连续洗牌m次之后，

15、数据又回到该处理器1.2.1 并行计算机的互连网络v 静态互连网络 (9) 蝶形连接(Butterfly Connected)对于k n的蝶形网络, k=log2n, 设Pr,i (0 r k, 0 i n)表示第r 行 第i 列上的处理器,其中第k 行视同第0行. 蝶形网络互连函数:Butterfly(Pr,i )= Pr-1,j , r 0, j= i ,或者 j和 i的二进制表示从左边数 起仅在第r 位不同.蝶形网络以2j增长方式展开翅膀, j=0k-1 蝶形网络通信直径: k=log2n蝶形网络特别适用于离散富立页变换FFT的并行处理(做成专用的 并行处理器).1.2.1 并行计算机的互连网络v 动态互连网络(非固定连接) (1) 总线Bus, 主要用于构造规模不大的SMP机器. P.21(2) 交叉开关Crossbar Switcher：一种高带宽网络 P.21(3) 多级互连网络Multistage Interconnection Network P.21一种大型开关网络. 根据算法(应用)的需要, 动态地设置多级网络中各端口连通状 态, 从而使得在任一处理器与