购买

¥ 30.0

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 并行计算中科大讲义

并行计算中科大讲义.ppt

并行计算中科大讲义

艾尔小茜茜
2018-05-06 0人阅读 举报 0 0 暂无简介

简介:本文档为《并行计算中科大讲义ppt》,可适用于项目管理领域

并行计算mdashmdash结构bull算法bull编程并行计算mdashmdash结构bull算法bull编程第一篇并行计算的基础第一章并行计算机系统及其结构模型第二章当代并行机系统:SMP、MPP和Cluster第三章并行计算性能评测第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程并行计算mdashmdash结构bull算法bull编程第三篇并行数值算法第八章基本通信操作第九章稠密矩阵运算第十章线性方程组的求解第十一章快速傅里叶变换第四篇并行程序设计第十二章并行程序设计基础第十三章并行程序设计模型和共享存储系统编程第十四章分布存储系统并行编程第十五章并行程序设计环境与工具第一章并行计算机系统及结构模型并行计算并行计算与计算科学当代科学与工程问题的计算需求并行计算机系统互连系统互连静态互联网络动态互连网络标准互联网络并行计算机系统结构并行计算机结构模型并行计算机访存模型并行计算并行计算:并行机上所作的计算又称高性能计算或超级计算。计算科学:计算物理、计算化学、计算生物等科学与工程问题的需求:气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。需求类型:计算密集、数据密集、网络密集。美国HPCC计划:重大挑战性课题T性能美国Petaflops研究项目:Pflops。美国ASCI计划:核武器数值模拟。高性能计算机Intel(OptionRed):Tflops,,PentiumProSGI(OptionBlueMountain):Tflops,,MIPSIBM(OptionWhite):Tflops,Top,,Power日本EarthSimulator:Tflops,Top,,VPHewlettPackardASCIQ:Tflops,Top,,,AlphaServer中国联想:Tflops,Top,系统互连不同带宽与距离的互连技术:总线、SAN、LAN、MAN、WAN局部总线、IO总线、SAN和LAN网络性能指标节点度(NodeDegree):射入或射出一个节点的边数。在单向网络中入射和出射边之和称为节点度。网络直径(NetworkDiameter):网络中任何两个节点之间的最长距离即最大路径数。对剖宽度(BisectionWidth):对分网络各半所必须移去的最少边数对剖带宽(BisectionBandwidth):每秒钟内在最小的对剖平面上通过所有连线的最大信息位(或字节)数如果从任一节点观看网络都一样则称网络为对称的(Symmetry)静态互连网络与动态互连网络静态互连网络:处理单元间有着固定连接的一类网络在程序执行期间这种点到点的链接保持不变典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络:用交换开关构成的可按应用程序的要求动态地改变连接组态典型的动态网络包括总线、交叉开关和多级互连网络等。静态互连网络()一维线性阵列(DLinearArray):并行机中最简单、最基本的互连方式每个节点只与其左、右近邻相连也叫二近邻连接N个节点用N条边串接之内节点度为直径为N对剖宽度为当首、尾节点相连时可构成循环移位器在拓扑结构上等同于环环可以是单向的或双向的其节点度恒为直径或为(双向环)或为N(单向环)对剖宽度为静态互连网络()二维网孔(DMesh):每个节点只与其上、下、左、右的近邻相连(边界节点除外)节点度为网络直径为对剖宽度为在垂直方向上带环绕水平方向呈蛇状就变成Illiac网孔了节点度恒为网络直径为而对剖宽度为垂直和水平方向均带环绕则变成了D环绕(DTorus)节点度恒为网络直径为对剖宽度为静态互连网络()二叉树:除了根、叶节点每个内节点只与其父节点和两个子节点相连。节点度为对剖宽度为而树的直径为如果尽量增大节点度为则直径缩小为此时就变成了星形网络其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。静态互连网络()超立方:一个n立方由个顶点组成立方如图(a)所示立方如图(b)所示由两个立方的对应顶点连接而成。n立方的节点度为n网络直径也是n而对剖宽度为。如果将立方的每个顶点代之以一个环就构成了如图(d)所示的立方环此时每个顶点的度为而不像超立方那样节点度为n。嵌入将网络中的各节点映射到另一个网络中去用膨胀(Dilation)系数来描述嵌入的质量它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数如果该系数为则称为完美嵌入。环网可完美嵌入到D环绕网中超立方网可完美嵌入到-D环绕网中嵌入网络名称网络规模节点度网络直径对剖宽度对称链路数线性阵列非环形(双向)是D网孔非Illiac网孔非D环绕是二叉树非星形非超立方nn是立方环是静态互连网络特性比较动态互连网络()总线:PCI、VME、Multics、Sbus、MicroChannel多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等动态互连网络()交叉开关(Crossbar):单级交换网络可为每个端口提供更高的带宽。象电话交换机一样交叉点开关可由程序控制动态设置其处于ldquo开rdquo或ldquo关rdquo状态而能提供所有(源、目的)对之间的动态连接。交叉开关一般有两种使用方式:一种是用于对称的多处理机或多计算机机群中的处理器间的通信另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。动态互联网络()单级交叉开关级联起来形成多级互连网络MIN(MultistageInterconnectionNetwork)动态互连网络()交换开关模块:一个交换开关模块有n个输入和n个输出每个输入可连接到任意输出端口但只允许一对一或一对多的映射不允许多对一的映射因为这将发生输出冲突级间互连(InterstageConnection):均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接n输入的Omega网络需要级开关在Ilinois大学的Cedar多处理机系统中采用了Omega网络CrayYMP多级网络该网络用来支持个向量处理器和个存储器模块之间的数据传输。网络能够避免个处理器同时进行存储器存取时的冲突。动态互连网络比较n,节点规模w数据宽度动态互连网络的复杂度和带宽性能一览表网络特性总线系统多级互连网络交叉开关硬件复杂度每个处理器带宽~报道的聚集带宽SunFire服务器中的Gigaplane总线:GBsIBMSP中的节点的HPS:GBsDigital的千兆开关:GBs标准互联网络()Myrinet:Myrinet是由Myricom公司设计的千兆位包交换网络其目的是为了构筑计算机机群使系统互连成为一种商业产品。Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及在南加州大学开发的ATOMICLAN技术。Myrinet能假设任意拓扑结构不必限定为开关网孔或任何规则的结构。Myrinet在数据链路层具有可变长的包格式对每条链路施行流控制和错误控制并使用切通选路法以及定制的可编程的主机接口。在物理层上Myrinet网使用全双工SAN链路最长可达米峰值速率为(+)Gbps(目前有)Myrinet交换开关:,,端口Myrinet主机接口:位的称作LANai芯片的用户定制的VLSI处理器它带有Myrinet接口、包接口、DMA引擎和快速静态随机存取存储器SRAM。oftheNovemberTOPuseMyrinet,includingofthetopMyrinet连接的LANCluster标准互连网络()高性能并行接口(HiPPI)LosAlamos国家实验室于年提出的一个标准其目的是试图统一来自不同产商生产的所有大型机和超级计算机的接口。在大型机和超级计算机工业界HiPPI作为短距离的系统到系统以及系统到外设连接的高速IO通道。年ANSIXT委员会认可了HiPPI标准它覆盖了物理和数据链路层但在这两层之上的任何规定却取决于用户。HiPPI是个单工的点到点的数据传输接口其速率可达Mbps到Gbps。开发成功了一种能提供潜在的Gbps速率比HiPPI快倍且有很低时延的超级HiPPI技术SGI公司和LosAlamos国家实验室都开发了用来构筑速率高达Gbps的HiPPI交换开关的HiPPI技术。HiPPI通道和HiPPI交换开关被用在SGIPowerChallenge服务器、IBM主机、CrayYMP、C和TDTE等系统使用HiPPI通道和开关构筑的LAN主干网标准互连网络()光纤通道FC(FiberChannel):通道和网络标准的集成光纤通道既可以是共享介质也可以是一种交换技术光纤通道操作速度范围可从到、、和Mbps。FCSI厂商也正在推出未来具有更高速度(、或Gbps)的光纤通道光纤通道的价值已被现在的某些千兆位局域网所证实这些局域网就是基于光纤通道技术的连网拓扑结构的灵活性是光纤通道的主要财富它支持点到点、仲裁环及交换光纤连接FDDI:光纤分布式数据接口FDDI(FiberDistributedDataInterface)FDDI采用双向光纤令牌环可提供Mbps数据传输速率FDDI具有互连大量设备的能力传统的FDDI仅以异步方式操作双向FDDI环作为主干网标准互联网络()ATM(AsynchronousTransferMode):由成立于年的ATM论坛和ITU标准定义。ATM是一种独立于介质的消息传输协议它将消息段变成更短的固定长度为字节的报元进行传输。这种技术是基于报元交换机制。ATM的目的是将实时和突发数据的传输合并成单一的网络技术。ATM网络支持从到、和Mbps不同的速率其速率越低ATM交换器和使用的链路价格越低。香港大学开发的Pearl机群标准互连网络()代别类型以太网BaseT快速以太网BaseT千兆位以太网GB引入年代速度(带宽)MbsMbsGbs最大距离UTR(非屏蔽双扭对)mm-mSTP(屏蔽双扭对)同轴电缆mm-m多模光纤Kmm(半双工)Km(全双工)m单模光纤KmKmKm主要应用领域文件共享打印机共享COW计算CS结构大型数据库存取等大型图像文件多媒体因特网内部网数据仓库等并行计算机结构模型并行计算机体系合一结构SMP、MPP、DSM和COW并行结构渐趋一致。大量的节点通过高速网络互连起来节点遵循Shell结构:用专门定制的Shell电路将商用微处理器和节点的其它部分(包括板级Cache、局存、NIC和DISK)连接起来。优点是CPU升级只需要更换Shell。五种结构特性一览表并行计算机访存模型()UMA(UniformMemoryAccess)模型是均匀存储访问模型的简称。其特点是:物理存储器被所有处理器均匀共享所有处理器访问任何存储字取相同的时间每台处理器可带私有高速缓存外围设备也可以一定形式共享。并行计算机访存模型()NUMA(NonuniformMemoryAccess)模型是非均匀存储访问模型的简称。特点是:被共享的存储器在物理上是分布在所有的处理器中的其所有本地存储器的集合就组成了全局地址空间处理器访问存储器的时间是不一样的访问本地存储器LM或群内共享存储器CSM较快而访问外地的存储器或全局共享存储器GSM较慢(此即非均匀存储访问名称的由来)每台处理器照例可带私有高速缓存外设也可以某种形式共享。并行计算机访存模型()COMA(CacheOnlyMemoryAccess)模型是全高速缓存存储访问的简称。其特点是:各处理器节点中没有存储层次结构全部高速缓存组成了全局地址空间利用分布的高速缓存目录D进行远程高速缓存的访问COMA中的高速缓存容量一般都大于级高速缓存容量使用COMA时数据开始时可任意分配因为在运行时它最终会被迁移到要用到它们的地方。并行计算机访存模型()CCNUMA(CoherentCacheNonuniformMemoryAccess)模型是高速缓存一致性非均匀存储访问模型的简称。其特点是:大多数使用基于目录的高速缓存一致性协议保留SMP结构易于编程的优点也改善常规SMP的可扩放性CCNUMA实际上是一个分布共享存储的DSM多处理机系统它最显著的优点是程序员无需明确地在节点上分配数据系统的硬件和软件开始时自动在各节点分配数据在运行期间高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。并行计算机访存模型()NORMA(NoRemoteMemoryAccess)模型是非远程存储访问模型的简称。NORMA的特点是:所有存储器是私有的绝大数NUMA都不支持远程存储器的访问在DSM中NORMA就消失了。构筑并行机系统的不同存储结构第二章当代并行机系统共享存储多处理机系统对称多处理机SMP结构特性分布存储多计算机系统大规模并行机MPP结构特性机群系统大规模并行处理系统MPP机群SP工作站机群COW对称多处理机SMP()SMP:采用商用微处理器通常有片上和片外Cache基于总线连接集中式共享存储UMA结构例子:SGIPowerChallenge,DECAlphaServer,Dawning对称多处理机SMP()优点对称性单地址空间易编程性动态负载平衡无需显示数据分配高速缓存及其一致性数据局部性硬件维持一致性低通信延迟LoadStore完成问题欠可靠BUS,OS,SM通信延迟(相对于CPU)竞争加剧慢速增加的带宽(MBdouble年,IOB更慢)不可扩放性〉CCNUMA大规模并行机MPP成百上千个处理器组成的大规模计算机系统规模是变化的。NORMA结构高带宽低延迟定制互连。可扩放性:Mem,IO,平衡设计系统成本:商用处理器相对稳定的结构SMP,分布通用性和可用性:不同的应用PVM,MPI,交互批处理互连对用户透明单一系统映象故障通信要求存储器和IO能力例子:IntelOptionRedIBMSPDawning典型MPP系统特性比较MPP所用的高性能CPU特性比较机群型大规模并行机SP设计策略:机群体系结构标准环境标准编程模型系统可用性精选的单一系统映像系统结构:高性能开关HPS多级Omega网络宽节点、窄节点和窄节点工作站机群COW分布式存储MIMD工作站商用互连网络每个节点是一个完整的计算机有自己的磁盘和操作系统而MPP中只有微内核优点:投资风险小系统结构灵活性能价格比高能充分利用分散的计算资源可扩放性好问题通信性能并行编程环境例子:BerkeleyNOWAlphaFarm,FXCOW典型的机群系统SMPMPP机群比较第三章并行计算性能评测并行机的一些基本性能指标加速比性能定律Amdahl定律Gustafson定律Sun和Ni定律可扩放性评测标准并行计算的可扩放性等效率度量标准等速度度量标准平均延迟度量标准CPU的某些基本性能指标工作负载执行时间浮点运算数指令数目并行执行时间Tcomput为计算时间Tparo为并行开销时间Tcomm为相互通信时间Tn=TcomputTparoTcomm例:估计APRAM模型下执行时间存储器性能存储器的层次结构(C,L,B)估计存储器的带宽RISCaddr,r,rrbytesMHzB=***Bs=GBs并行与通信开销并行和通信开销:相对于计算很大。PowerPC(每个周期ns执行flops创建一个进程ms可执行flops)开销的测量:乒乓方法(PingPongScheme)节点发送m个字节给节点节点从节点接收m个字节后立即将消息发回节点。总的时间除以即可得到点到点通信时间也就是执行单一发送或接收操作的时间。可一般化为热土豆法(HotPotato)也称为救火队法(FireBrigade)mdashmdashmdashmdashmdashmdashhellipmdashmdashnmdashmdashPingPongSchemeif(mynodeid=)then*发送者*starttime=second()sendanmbytemessagetonodereceiveanmbytemessagefromnodeendtime=second()totaltime=endtimendashstarttimecommunicationtimei=totaltimeelseif(mynodeid=)then*接收者*receiveanmbytemessagefromnodesendanmbytemessagetonodeendif并行开销的表达式:点到点通信通信开销t(m)=tmrinfin通信启动时间t渐近带宽rinfin:传送无限长的消息时的通信速率半峰值长度m:达到一半渐近带宽所要的消息长度特定性能pi:表示短消息带宽t=mrinfin=pi并行开销的表达式:整体通信典型的整体通信有:播送(Broadcasting):处理器发送m个字节给所有的n个处理器收集(Gather):处理接收所有n个处理器发来在消息所以处理器最终接收了mn个字节散射(Scatter):处理器发送了m个字节的不同消息给所有n个处理器因此处理器最终发送了mn个字节全交换(TotalExchange):每个处理器均彼此相互发送m个字节的不同消息给对方所以总通信量为mn个字节循环移位(Circularshift):处理器i发送m个字节给处理器i处理器n发送m个字节给处理器所以通信量为mn个字节。机器的成本、价格与性价比机器的成本与价格机器的性能价格比PerformanceCostRatio:系指用单位代价(通常以百万美元表示)所获取的性能(通常以MIPS或MFLOPS表示)利用率(Utilization):可达到的速度与峰值速度之比算法级性能评测加速比性能定律并行系统的加速比是指对于一个给定的应用并行算法(或并行程序)的执行速度相对于串行算法(或串行程序)的执行速度加快了多少倍。Amdahl定律Gustafson定律SunNi定律可扩放性评测标准等效率度量标准等速度度量标准平均延迟度量标准Amdahl定律P:处理器数W:问题规模(计算负载、工作负载给定问题的总计算量)Ws:应用程序中的串行分量f是串行分量比例(f=WsWWs=W)WP:应用程序中可并行化部分f为并行分量比例WsWp=WTs=T:串行执行时间Tp:并行执行时间S:加速比E:效率出发点:固定不变的计算负载固定的计算负载分布在多个处理器上的增加处理器加快执行速度从而达到了加速的目的。Amdahl定律(contlsquod)固定负载的加速公式:WsWp可相应地表示为f(f)prarrinfin时上式极限为:S=fWo为额外开销Amdahlrsquoslaw(contrsquod)Gustafson定律出发点:对于很多大型计算精度要求很高即在此类应用中精度是个关键因素而计算时间是固定不变的。此时为了提高精度必须加大计算量相应地亦必须增多处理器数才能维持时间不变除非学术研究在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上增多处理器必须相应地增大问题规模才有实际意义。Gustafson加速定律:并行开销Wo:Gustafson定律(contlsquod)Sun和Ni定律基本思想:只要存储空间许可应尽量增大问题规模以产生更好和更精确的解(此时可能使执行时间略有增加)。假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之此时工作负载W=fW(f)W。在p个节点的并行系统上能够求解较大规模的问题是因为存储容量可增加到pM。令因子G(p)反应存储容量增加到p倍时并行工作负载的增加量所以扩大后的工作负载W=fW(f)G(p)W。存储受限的加速公式:并行开销Wo:Sun和Ni定律(contrsquod)G(p)=时就是Amdahl加速定律G(p)=p变为fp(f)就是Gustafson加速定律G(p)p时相应于计算机负载比存储要求增加得快此时Sun和Ni加速均比Amdahl加速和Gustafson加速为高。加速比讨论参考的加速经验公式:plogpleSleP线性加速比:很少通信开销的矩阵相加、内积运算等plogp的加速比:分治类的应用问题通信密集类的应用问题:S=C(p)超线性加速绝对加速:最佳并行算法与串行算法相对加速:同一算法在单机和并行机的运行时间可扩放性评测标准并行计算的可扩放性(Scalability)也是主要性能指标可扩放性最简朴的含意是在确定的应用背景下计算机系统(或算法或程序等)性能随处理器数的增加而按比例提高的能力影响加速比的因素:处理器数与问题规模求解问题中的串行分量并行处理所引起的额外开销(通信、等待、竞争、冗余操作和同步等)加大的处理器数超过了算法中的并发程度增加问题的规模有利于提高加速的因素:较大的问题规模可提供较高的并发度额外开销的增加可能慢于有效计算的增加算法中的串行分量比例不是固定不变的(串行部分所占的比例随着问题规模的增大而缩小)。增加处理器数会增大额外开销和降低处理器利用率所以对于一个特定的并行系统(算法或程序)它们能否有效利用不断增加的处理器的能力应是受限的而度量这种能力就是可扩放性这一指标。可扩放性评测标准(contlsquod)可扩放性:调整什么和按什么比例调整并行计算要调整的是处理数p和问题规模W两者可按不同比例进行调整此比例关系(可能是线性的多项式的或指数的等)就反映了可扩放的程度。并行算法和体系结构可扩放性研究的主要目的:确定解决某类问题用何种并行算法与何种并行体系结构的组合可以有效地利用大量的处理器对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能对固定的问题规模确定在某类并行机上最优的处理器数与可获得的最大的加速比用于指导改进并行算法和并行机体系结构以使并行算法尽可能地充分利用可扩充的大量处理器目前无一个公认的、标准的和被普遍接受的严格定义和评判它的标准等效率度量标准令tie和tio分别是并行系统上第i个处理器的有用计算时间和额外开销时间(包括通信、同步和空闲等待时间等)Tp是p个处理器系统上并行算法的运行时间对于任意i显然有Tp=tietio且TeTo=pTp问题的规模W为最佳串行算法所完成的计算量W=Te如果问题规模W保持不变处理器数p增加开销To增大效率E下降。为了维持一定的效率(介于与之间)当处理数p增大时需要相应地增大问题规模W的值。由此定义函数fE(p)为问题规模W随处理器数p变化的函数为等效率函数(ISOefficiencyFunction)(Kumar)等效率度量标准(contlsquod)曲线表示算法具有很好的扩放性曲线表示算法是可扩放的曲线表示算法是不可扩放的。优点:简单可定量计算的、少量的参数计算等效率函数缺点:如果To无法计算出(在共享存储并行机中)等速度度量标准p表示处理器个数W表示要求解问题的工作量或称问题规模(在此可指浮点操作个数)T为并行执行时间定义并行计算的速度V为工作量W除以并行时间Tp个处理器的并行系统的平均速度定义为并行速度V除以处理器个数p:W是使用p个处理器时算法的工作量令Wrsquo表示当处理数从p增大到prsquo时为了保持整个系统的平均速度不变所需执行的工作量则可得到处理器数从p到prsquo时平均速度可扩放度量标准公式等速度度量标准(contrsquod)优点:直观地使用易测量的机器性能速度指标来度量缺点:某些非浮点运算可能造成性能的变化平均延迟度量标准Ti为Pi的执行时间包括包括延迟LiPi的总延迟时间为ldquoLi启动时间停止时间rdquo。定义系统平均延迟时间为pTpara=ToTs在p个处理器上求解工作量为W问题的平均延迟在prsquo个处理器上求解工作量为Wrsquo问题的平均延迟当处理器数由p变到prsquo而推持并行执行效率不变则定义平均延迟可扩放性度量标准为平均延迟度量标准(Contrsquod)优点:平均延迟能在更低层次上衡量机器的性能缺点:需要特定的软硬件才能获得平均延迟并行计算中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)年月第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程第四章并行算法的设计基础并行算法的基础知识并行计算模型并行算法的基础知识并行算法的定义和分类并行算法的表达并行算法的复杂性度量并行算法中的同步和通讯并行算法的定义和分类并行算法的定义算法并行算法:一些可同时执行的诸进程的集合这些进程互相作用和协调动作从而达到给定问题的求解。并行算法的分类数值计算和非数值计算同步算法和异步算法分布算法确定算法和随机算法并行算法的基础知识并行算法的定义和分类并行算法的表达并行算法的复杂性度量并行算法中的同步和通讯并行算法的表达描述语言可以使用类Algol、类Pascal等在描述语言中引入并行语句。并行语句示例Pardo语句fori=tonpardohelliphellipendforforall语句forallPi,whereleilekhelliphellipendfor并行算法的基础知识并行算法的定义和分类并行算法的表达并行算法的复杂性度量并行算法中的同步和通讯并行算法的复杂性度量串行算法的复杂性度量最坏情况下的复杂度(WorstCASEComplexity)期望复杂度(ExpectedComplexity)并行算法的几个复杂性度量指标运行时间t(n):包含计算时间和通讯时间分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。处理器数p(n)并行算法成本c(n):c(n)=t(n)p(n)总运算量W(n):并行算法求解问题时所完成的总的操作步数。并行算法的复杂性度量Brent定理令W(n)是某并行算法A在运行时间T(n)内所执行的运算量则A使用p台处理器可在t(n)=O(W(n)pT(n))时间内执行完毕。W(n)和c(n)密切相关P=O(W(n)T(n))时W(n)和c(n)两者是渐进一致的对于任意的pc(n)rsaquoW(n)并行算法的基础知识并行算法的定义和分类并行算法的表达并行算法的复杂性度量并行算法中的同步和通讯并行算法的同步同步概念同步是在时间上强使各执行进程在某一点必须互相等待可用软件、硬件和固件的办法来实现。同步语句示例算法共享存储多处理器上求和算法输入:A=(a,hellip,an),处理器数p输出:S=SigmaaiBegin()S=()lock(S)()forallPiwhereleilepdoS=SL()L=()unlock(S)()forj=itonsteppdoendforL=LajEndendforendfor并行算法的通讯通讯共享存储多处理器使用:globalread(X,Y)和globalwrite(X,Y)分布存储多计算机使用:send(X,i)和receive(Y,j)通讯语句示例算法分布存储多计算机上矩阵向量乘算法输入:处理器数p,A划分为B=An,(i)rir,x划分为w=w(i)rir输出:P保存乘积AXBegin()Computez=Bw()ifi=thenyi=elsereceive(y,left)endif()y=yz()send(y,right)()ifi=thenreceive(y,left)End第四章并行算法的设计基础并行算法的基础知识并行计算模型并行计算模型PRAM模型异步APRAM模型BSP模型logP模型PRAM模型基本概念由Fortune和Wyllie年提出又称SIMDSM模型。有一个集中的共享存储器和一个指令控制器通过SM的RW交换数据隐式同步计算。结构图PRAM模型分类PRAMCRCW并发读并发写CPRAMCRCW(CommonPRAMCRCW):仅允许写入相同数据PPRAMCRCW(PriorityPRAMCRCW):仅允许优先级最高的处理器写入APRAMCRCW(ArbitraryPRAMCRCW):允许任意处理器自由写入PRAMCREW并发读互斥写PRAMEREW互斥读互斥写计算能力比较PRAMCRCW是最强的计算模型PRAMEREW可logp倍模拟PRAMCREW和PRAMCRCWPRAM模型优点适合并行算法表示和复杂性分析易于使用隐藏了并行机的通讯、同步等细节。缺点不适合MIMD并行机忽略了SM的竞争、通讯延迟等因素并行计算模型PRAM模型异步APRAM模型BSP模型logP模型异步APRAM模型基本概念又称分相(Phase)PRAM或MIMDSM。每个处理器有其局部存储器、局部时钟、局部程序无全局时钟各处理器异步执行处理器通过SM进行通讯处理器间依赖关系需在并行程序中显式地加入同步路障。指令类型()全局读()全局写()局部操作()同步异步APRAM模型计算过程由同步障分开的全局相组成异步APRAM模型计算时间设局部操作为单位时间全局读写平均时间为dd随着处理器数目的增加而增加同步路障时间为B=B(p)非降函数。满足关系或令为全局相内各处理器执行时间最长者则APRAM上的计算时间为优缺点易编程和分析算法的复杂度但与现实相差较远其上并行算法非常有限也不适合MIMDDM模型。并行计算模型PRAM模型异步APRAM模型BSP模型logP模型BSP模型基本概念由Valiant()提出的ldquo块rdquo同步模型是一种异步MIMDDM模型支持消息传递系统块内异步并行块间显式同步。模型参数p:处理器数(带有存储器)l:同步障时间(Barriersynchronizationtime)g:带宽因子(timestepspacket)=bandwidthBSP模型计算过程由若干超级步组成每个超级步计算模式为左图优缺点强调了计算和通讯的分离提供了一个编程环境易于程序复杂性分析。但需要显式同步机制限制至多h条消息的传递等。并行计算模型PRAM模型异步APRAM模型BSP模型logP模型logP模型基本概念由Culler()年提出的是一种分布存储的、点到点通讯的多处理机模型其中通讯由一组参数描述实行隐式同步。模型参数L:networklatencyo:communicationoverheadg:gap=bandwidthP:#processors注:L和g反映了通讯网络的容量logP模型优缺点捕捉了MPC的通讯瓶颈隐藏了并行机的网络拓扑、路由、协议可以应用到共享存储、消息传递、数据并行的编程模型中但难以进行算法描述、设计和分析。BSPvsLogPBSPLogP:BSP块同步BSP子集同步BSP进程对同步=LogPBSP可以常数因子模拟LogPLogP可以对数因子模拟BSPBSP=LogPBarriers-OverheadBSP提供了更方便的程设环境LogP更好地利用了机器资源BSP似乎更简单、方便和符合结构化编程并行计算中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)年月第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程第五章并行算法的一般设计方法串行算法的直接并行化从问题描述开始设计并行算法借用已有算法求解新问题串行算法的直接并行化设计方法描述快排序算法的并行化设计方法的描述方法描述发掘和利用现有串行算法中的并行性直接将串行算法改造为并行算法。评注由串行算法直接并行化的方法是并行算法设计的最常用方法之一不是所有的串行算法都可以直接并行化的一个好的串行算法并不能并行化为一个好的并行算法许多数值串行算法可以并行化为有效的数值并行算法。串行算法的直接并行化设计方法描述快排序算法的并行化快排序算法的并行化算法PRAMCRCW上的快排序二叉树构造算法输入:序列(A,hellip,An)和n个处理器输出:供排序用的一棵二叉排序树Begin()foreachprocessorido()repeatforeachprocessorirootdo()root=iif(AiAfi)or(Ai=Afiandifi)then()fi=root()LCfi=i()LCi=RCi=n()ifi=LCfithenexitelsefi=LCfiendifendforelse()RCfi=i()ifi=RCfithenexitelsefi=RCfiendifendifendrepeatEnd第五章并行算法的一般设计方法串行算法的直接并行化从问题描述开始设计并行算法借用已有算法求解新问题从问题描述开始设计并行算法方法描述从问题本身描述出发不考虑相应的串行算法设计一个全新的并行算法。评注挖掘问题的固有特性与并行的关系设计全新的并行算法是一个挑战性和创造性的工作利用串的周期性的PRAMCRCW算法是一个很好的范例第五章并行算法的一般设计方法串行算法的直接并行化从问题描述开始设计并行算法借用已有算法求解新问题借用已有算法求解新问题设计方法描述利用矩阵乘法求所有点对间最短路径设计方法的描述方法描述找出求解问题和某个已解决问题之间的联系改造或利用已知算法应用到求解问题上。评注这是一项创造性的工作使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。借用已有算法求解新问题设计方法描述利用矩阵乘法求所有点对间最短路径利用矩阵乘法求所有点对间最短路径计算原理有向图G=(V,E)边权矩阵W=(wij)ntimesn求最短路径长度矩阵D=(dij)ntimesndij为vi到vj的最短路径长度。假定图中无负权有向回路记d(k)ij为vi到vj至多有k个中间结点的最短路径长Dk=(d(k)ij)ntimesn则()d()ij=wij当ij(如果vi到vj之间无边存在记为infin)d()ij=当i=j()无负权回路dij=d(n)ij()利用最优性原理:d(k)ij=minlellen{d(k)ild(k)lj}视:rdquordquoldquotimesrdquoldquominrdquoldquosumrdquo则上式变为d(k)ij=sumlellen{d(k)iltimesd(k)lj}()应用矩阵乘法:DDDhellipDlogn(=Dn)SIMDCC上的并行算法:p算法并行计算中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)年月第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程第六章并行算法的基本设计技术划分设计技术分治设计技术平衡树设计技术倍增设计技术流水线设计技术划分设计技术均匀划分技术方根划分技术对数划分技术功能划分技术均匀划分技术划分方法n个元素An分成p组每组A(i)npinpi=~p示例:MIMDSM模型上的PSRS排序begin()均匀划分:将n个元素An均匀划分成p段每个pi处理A(i)npinp()局部排序:pi调用串行排序算法对A(i)npinp排序()选取样本:pi从其有序子序列A(i)npinp中选取p个样本元素()样本排序:用一台处理器对p个样本元素进行串行排序()选择主元:用一台处理器从排好序的样本序列中选取p个主元并播送给其他pi()主元划分:pi按主元将有序段A(i)npinp划分成p段()全局交换:各处理器将其有序段按段号交换到对应的处理器中()归并排序:各处理器对接收到的元素进行归并排序end均匀划分技术例PSRS排序过程。N=p=PSRS排序如下:划分设计技术均匀划分技术方根划分技术对数划分技术功能划分技术方根划分技术划分方法n个元素An分成A(i)n^()in^()i=~n^()示例:SIMDCREW模型上的Valiant归并(年发表)有序组Ap、Bq,(假设p=q),处理器数begin()方根划分:A,B分别按()段间比较:A划分元与B划分元比较(至多对)确定A划分元应插入B中的区段()段内比较:A划分元与B相应段内元素进行比较并插入适当的位置()递归归并:B按插入的A划分元重新分段与A相应段(A除去原划分元)构成了成对的段组对每对段组递归执行()~()直至A组为时递归结束各组仍按分配处理器end方根划分技术方根划分技术划分设计技术均匀划分技术方根划分技术对数划分技术功能划分技术对数划分技术划分方法n个元素An分成A(i)lognilogni=~nlogn示例:PRAMCREW上的对数划分并行归并排序()归并过程:设有序组An和Bmji=rank(bilogm:A)为bilogm在A中的位序即A中小于等于bilogm的元素个数()例:A=(,,,,,,,),B=(,,,)n=,m==logm=log==j=rank(blogm:A)=rank(b:A)=rank(:A)=,j=hellip=B:,B:,A:,,A:,,,,A和B归并化为(A,B)和(A,B)的归并划分设计技术均匀划分技术方根划分技术对数划分技术功能划分技术功能划分技术划分方法n个元素An分成等长的p组每组满足某种特性。示例:(m,n)选择问题(求出n个元素中前m个最小者)功能划分:要求每组元素个数必须大于m算法:p算法输入:A=(a,hellip,an)输出:前m个最小者Begin()功能划分:将A划分成g=nm组每组含m个元素()局部排序:使用Batcher排序网络将各组并行进行排序()两两比较:将所排序的各组两两进行比较从而形成MIN序列()排序比较:对各个MIN序列重复执行第()和第()步直至选出m个最小者。End功能划分技术第六章并行算法的基本设计技术划分设计技术分治设计技术平衡树设计技术倍增设计技术流水线设计技术分治设计技术并行分治设计步骤双调归并网络并行分治设计步骤将输入划分成若干个规模相等的子问题同时(并行地)递归求解这些子问题并行地归并子问题的解直至得到原问题的解。分治设计技术并行分治设计步骤双调归并网络双调归并网络双调序列(p定义)(,,,,,,,,)(,,,,,,,,)(,,,,,,,)以上都是双调序列Batcher定理给定双调序列(x,x,hellip,xn),对于si=min{xi,xin}和li=max{xi,xin}则小序列(s,s,hellip,sn)和大序列(l,l,hellip,ln)仍是双调序列双调归并网络(,)双调归并网络双调归并网络Batcher双调归并算法输入:双调序列X=(x,x,hellip,xn)输出:非降有序序列Y=(y,y,hellip,yn)ProcedureBITONICMERG(x)Begin()fori=tonpardo()si=min{xi,xin}()li=max{xi,xin}endfor()RecursiveCall:()BITONICMERG(MIN=(s,hellip,sn))()BITONICMERG(MIN=(l,hellip,ln))()outputsequenceMINfollowedbysequenceMAXEnd第六章并行算法的基本设计技术划分设计技术分治设计技术平衡树设计技术倍增设计技术流水线设计技术平衡树设计技术设计思想求最大值计算前缀和平衡树设计技术设计思想以树的叶结点为输入中间结点为处理结点由叶向根或由根向叶逐层进行并行处理。示例求最大值计算前缀和平衡树设计技术设计思想求最大值计算前缀和求最大值算法:SIMDTC(SM)上求最大值算法Beginfork=mtodoforj=ktokpardoAj=max{Aj,Aj}endforendforend图示时间分析t(n)=mtimesO()=O(logn)p(n)=n平衡树设计技术设计思想求最大值计算前缀和计算前缀和问题定义n个元素{x,x,hellip,xn}前缀和是n个部分和:Si=x*x*hellip*xi,leilen这里*可以是+或times串行算法:Si=Si-*xi计算时间为O(n)并行算法:p算法SIMDTC上非递归算法令Ai=xi,i=~n,Bh,j和Ch,j为辅助数组(h=~logn,j=~nh)数组B记录由叶到根正向遍历树中各结点的信息(求和)数组C记录由根到叶反向遍历树中各结点的信息(播送前缀和)计算前缀和例:n=,p=,C~C为前缀和第六章并行算法的基本设计技术划分设计技术分治设计技术平衡树设计技术倍增设计技术流水线设计技术倍增设计技术设计思想表序问题求森林的根倍增设计技术设计思想又称指针跳跃(pointerjumping)技术特别适合于处理链表或有向树之类的数据结构当递归调用时所要处理数据之间的距离逐步加倍经过k步后即可完成距离为k的所有数据的计算。示例表序问题求森林的根倍增设计技术设计思想表序问题求森林的根表序问题问题描述n个元素的列表L求出每个元素在L中的次第号(秩或位序或rank(k))rank(k)可视为元素k至表尾的距离示例:n=()pa=b,pb=c,pc=d,pd=e,pe=f,pf=g,pg=gra=rb=rc=rd=re=rf=,rg=()pa=c,pb=d,pc=e,pd=f,pe=pf=pg=gra=rb=rc=rd=re=,rf=,rg=()pa=e,pb=f,pc=pd=pe=pf=pg=gra=,rb=,rc=,rd=,re=,rf=,rg=()pa=pb=pc=pd=pe=pf=pg=gra=,rb=,rc=,rd=,re=,rf=,rg=表序问题算法:P算法()并行做:初始化pk和distancekO()()执行次O(logn)()对k并行地做O()如果k的后继不等于k的后继之后继则(i)distancek=distancekdistancepk(ii)pk=ppk()对k并行地做rankk=distancekO()运行时间:t(n)=O(logn)p(n)=n倍增设计技术设计思想表序问题求森林的根求森林的根问题描述一组有向树F中,如果i,j是F中的一条弧则pi=j(即j是i的双亲)若i为根则pi=i。求每个结点j(j=~n)的树根

VIP尊享8折文档

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/617

并行计算中科大讲义

¥30.0

会员价¥24.0

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利