并行算法的设计与分析

并行算法设计与分析钟诚3236396，[e-mail]教材陈国良.并行算法的设计与分析，第3版.北京:高等教育出版社,2009参考书[1]陈国良.并行计算——结构•算法•编程,第3版.北京：高等教育出版社,2011[2]陈国良等.并行算法实践.北京：高等教育出版社,2004[3]苏德富,钟诚.计算机算法设计与分析,第2版.北京：电子工业出版社,2005[4]C.Xavier,S.S.Iyenger著,张云泉等译.并行算法导论.北京：机械工业出版社,1998[5]AnanthGrama.并行计算导论,第2版,英文版.北京:机械工业出版社,2003为什么需要学习研究并行算法？计算机算法+数据结构=计算机程序。计算机程序+文档+控制数据=计算机软件。计算机软件+市场=（精神与物质的）财富。并行计算机、并行算法可以显著加速大规模、复杂问题的处理（求解）速度，可以获得问题的更精确（更好）的解。客观世界的一切事物（对象）及其活动都是并发（并行）进行的，将事物（对象）及其活动映射成计算机软件解时，设计开发的计算机软件（计算机程序、计算机算法）自然也应当是并行的！版权声明本教学PPT仅供课堂教学教师使用第一章绪论1.1引言1.并行处理(ParallelProcessing)挖掘计算(Computing)过程的并发事件的信息处理.2.并发性(Concurrency)并行性(Parallelism)同时性(Simultaneity)流水线(Pipelining)3.并行处理的级别(ParallelProcessingLevel)指令级并行(InstructionLevelParallelism-ILP,指令内部并行,指令之间并行)细粒度并行(finegrainparallelism/tinygranularityparallelism)线程级并行(ThreadLevelParallelism-TLP)中细粒度并行(fine-mediumgrainparallelism)进程级(ProcessLevelParallelism-PLP)/过程级/算法级并行中粒度并行(mediumgrainparallelism)任务级并行(TaskLevelParallel)粗粒度并行(coarsegrainparallelism)4.并行计算(ParallelComputing)学科并行计算机体系结构(ParallelComputerArchitectures)并行算法(ParallelAlgorithms)并行程序设计(ParallelProgramming)5.多核处理器（Multi-coreProcessors，又称片上多处理器-ChipMulti-Processor,CMP）、众核处理器(Many-coreProcessors,如GPU)、多线程并行技术(Multi-threadParallelTechniques)的出现与应用，使得并行算法的研究与开发显得极其迫切且富有挑战性。第一章绪论1.2并行算法的硬件基础1.2.1并行计算机的体系结构:并行计算机分类Flynn分类（1966年）(1)单指令流单数据流机器SISD，即传统的单处理机(2)单指令流多数据流机器SIMD-SingleInstructionStreamMultipleDataStream(3)多指令流单数据流机器MISD（目前无实际的商用机器）(4)多指令流多数据流机器MIMD-MultipleInstructionStreamMultipleDataStream并行机的结构模型－实际的机器体系结构－PVP(ParallelVectorProcessor,并行向量机)－SIMD阵列处理器（SIMDPE）－SMP(SymmetricMultiprocessor,对称多处理机)－MPP(MassivelyParallelProcessor,大规模并行处理机)－Clusters(工作站机群Workstation-Cluster,PC机群PC-Cluster,SMP机群SMP-Cluster等)；目前大部分“超级并行计算机”均采用Clusters结构－DSM(DistributedSharedMemory,分布共享存储多处理机)第一章绪论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/CP/C…定制/标准网络LMLMLM(e)Cluster/COW,物理/逻辑上多地址空间第一章绪论1.2.1并行计算机的体系结构:并行计算机分类结构模型－物理机模型SMPSMPSMP…SAN/LANSMSMSMMPPMPPMPP…SAN/LANDSMDSMDSM(f)SMP-Cluster(g)DSM-ClusterSMPMPPMPP…WANLMDSMSM(h)Grid(ClusterofClusters)1.2.1并行计算机的互连网络静态互连网络(固定连接)connectedgraph:vertices=processingnodes,edges=communicationlinks(1)一维线性连接LA(1-DLinearArray):一维阵列不带环绕的1-DLA，带环绕的1-DLA,通信直径n-1,n处理器数(2)网孔连接MC(MeshConnected):二维阵列互连函数:MC2+1(p)=(p+1)modn,MC2-1(p)=(p-1)modnMC2+n1/2(p)=(p+n1/2)modn,MC2-n1/2(p)=(p-n1/2)modn,p处理器编号不带环绕的MC，带环绕的MC,通信直径n1/2-1,1.2.1并行计算机的互连网络网孔结构的扩展:可重构网孔RMESH(ReconfigurableMesh)网孔+可重构总线动态重新设置并行计算机的互连结构，例如可动态设置成多条行总线、列总线或者对角线总线处理机阵列结构，也可动态将规模n×n的二维RMESH结构设置成n个规模n1/2×n1/2的子MESH结构。每个处理器通过四个端口（N,E,S,W）与总线相连，在处理器内部有6个开关控制这四个端口之间的连接关系，如图a所示。这四个端口之间共有15种连接方式，如图b所示。123123iijP(2,3)NESW:开关NSEWNSEWNSEWNSEWNEW{EWSN}{E,W,SN}{EW,S,N}{E,W,S,N}{EW,SN}NSEWNSEW{EWN,S}{EWS,N}{NWS,E}{W,NES}{NW,SE}NSEWNSEWNSEWNSEW{NE,W,S}{N,W,ES}{WS,N,E}{NW,S,E}{NE,SW}NSEWNSEWNSEWNSEW(a)(b)2D-RMESH结构1.2.1并行计算机的互连网络静态互连网络(3)树形连接TC(TreeConnected)二叉树，通信直径2(logn-1)胖树(X树）根结点处理器负载过重，瓶颈结点要求根结点处理和容错能力强千万亿次神威蓝光超级并行计算机群采用胖树结构连接机群中的处理器结点曙光5000A超级并行计算机群系统机采用树结构连接机群中的处理器结点1.2.1并行计算机的互连网络静态互连网络(4)树网连接MT(Meshoftree)1.2.1并行计算机的互连网络静态互连网络(5)金字塔连接(Pyramid)(6)超立方连接HC(HypercubeConnected)互连函数:CCi(pm-1pm-2…pi+1pipi-1…p1p0)=pm-1pm-2…pi+1~pipi-1…p1p0其中pm-1pm-2…pi+1pipi-1…p1p0为处理器编号的二进制表示,~pi为对pi求反,i=0~m-1,m=log2n,n=2m;通信直径log2n.不易扩展.例:n=16,CC0(0000)=0001,CC0(0001)=0000,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并行计算机的互连网络扩展的超立方结构----光电超立方机器立方体内的结点(处理器)由电信号连接,超立方体之间用光信号(光波)连接.机器规模扩展容易.电信号连接光信号连接1.2.1并行计算机的互连网络静态互连网络(7)立方环连接CCC(CubeConnected-Cycles)(8)洗牌交换连接SE(ShuffleExchange)——物理上是SIMD-SM机器互连函数:SH(pm-1pm-2…p1p0)=pm-2pm-3…p1p0pm-1,循环左移1位,m=lognEX(pm-1pm-2…p1p0)=pm-1pm-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------P3P4-----P5(x)P6------P7特点：位于某个处理器中的数据，连续洗牌m次之后，数据又回到该处理器1.2.1并行计算机的互连网络静态互连网络(9)蝶形连接(ButterflyConnected)对于k×n的蝶形网络,k=log2n,设Pr,i(0≤r≤k,0≤i≤n)表示第r行第i列上的处理器,其中第k行视同第0行.蝶形网络互连函数:Butterfly(Pr,i)=Pr-1,j,r0,j=i,或者j和i的二进制表示从左边数起仅在第r位不同.蝶形网络以2j增长方式展开翅膀,j=0~k-1蝶形网络通信直径:k=log2n蝶形网络特别适用于离散富立页变换FFT的并行处理(做成专用的并行处理器).1.2.1并行计算机的互连网络动态互连网络(非固定连接)(1)总线Bus,主要用于构造规模不大的SMP机器.P.21(2)交叉开关CrossbarSwitcher：一种高带宽网络P.21(3)多级互连网络MultistageInterconnectionNetworkP.21一种大型开关网络.根据算法(应用)的需要,动态地设置多级网络中各端口连通状态,从而使得在任一处理器与某个共享存储器模块之间构成一条路由(链路,通路),该处理器可以访问此共享存储器模块单元中的内容(数据).对于n个处理器、n个共享存储模块的多级互连网络，其互连级数m=logn1.2.2并行计算机的存储组织存储器的层次结构寄存器容量高速缓冲存储器(SRAM)每和一级缓存L1Cache位存二级缓存L2Cache(处理核共享)成取三级缓存L3Cache（CMP共享）本时增间主存储器DRAM加增加硬盘存储器磁带机1.2.2并行计算机的存储组织存储器层次之间的数据传输（P.23图1.21）各层存储器的性能参数容量C：字节数延迟L：读取一个字（Word,32/64位）所需的时间带宽B：1秒钟内各存储层传送的字节数（P.24图1.22）高速缓存一致性问题当某个处理器第一次访问主存某一存储单元时，系统会将其副本同时传给与该处理器相连的高速缓存。以后当此处理器再此访问此数据时，即可直接访问其高速缓存中的副本（数据）。若另一个处理器也访问主存中同一存储单元，则此数据之副本也被传到其高速缓存中。在上述情形下，若一个处理器改写了其高速缓存中（副本）的内容，但另一个处理器的高速缓存中（副本）的内容仍是原来的值，则产生了高速缓存中不一致性的问题。1.3并行计算模型1.3.1引言设计并行算法时，用户可以不关心具体的并行计算机系统结构的细节。将各种并行计算机系统的一些共同属性抽象起来形成“并行计算模型”