并行计算 第二篇 并行算法的设计.ppt

并行计算 2009年3月10日 第二篇并行算法的设计 第四章并行算法的设计基础第五章并行算法的一般设计策略第六章并行算法的基本设计技术第七章并行算法的一般设计过程 第四章并行算法的设计基础 4 1并行算法的基础知识4 2并行计算模型 4 1并行算法的基础知识 4 1 1并行算法的定义和分类4 1 2并行算法的表达4 1 3并行算法的复杂性度量4 1 4并行算法中的同步和通信 并行算法的定义和分类 并行算法的定义算法并行算法 一些可同时执行的诸进程的集合 这些进程互相作用和协调动作从而达到给定问题的求解 并行算法的分类数值计算和非数值计算同步算法和异步算法分布算法确定算法和随机算法 并行算法的表达 描述语言可以使用类Algol 类Pascal等 在描述语言中引入并行语句 并行语句示例Par do语句fori 1tonpar do endforforall语句forallPi where0 i k endfor 并行算法的复杂性度量 串行算法的复杂性度量最坏情况下的复杂度 Worst CASEComplexity 期望复杂度 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 p T n 时间内执行完毕 W n 和c n 密切相关P O W n T n 时 W n 和c n 两者是渐进一致的对于任意的p c n W n 并行算法的同步 同步概念同步是在时间上强使各执行进程在某一点必须互相等待 可用软件 硬件和固件的办法来实现 同步语句示例算法4 1共享存储多处理器上求和算法输入 A a0 an 1 处理器数p输出 S aiBegin 1 S 0 2 3 lock S 2 forallPiwhere0 i p 1doS S L 2 1 L 0 2 4 unlock S 2 2 forj itonsteppdoendforL L ajEndendforendfor 并行算法的通信 通信共享存储多处理器使用 globalread X Y 和globalwrite X Y 分布存储多计算机使用 send X i 和receive Y j 通信语句示例算法4 2分布存储多计算机上矩阵向量乘算法输入 处理器数p A划分为B A 1 n i 1 r 1 ir x划分为w w i 1 r 1 ir 输出 P1保存乘积AXBegin 1 Computez Bw 2 ifi 1thenyi 0elsereceive y left endif 3 y y z 4 send y right 5 ifi 1thenreceive y left End 4 2并行计算模型 4 2 1PRAM模型4 2 2异步APRAM模型4 2 3BSP模型4 2 4logP模型 PRAM模型 基本概念由Fortune和Wyllie1978年提出 又称SIMD SM模型 有一个集中的共享存储器和一个指令控制器 通过SM的R W交换数据 隐式同步计算 结构图 PRAM模型 分类PRAM CRCW并发读并发写CPRAM CRCW CommonPRAM CRCW 仅允许写入相同数据PPRAM CRCW PriorityPRAM CRCW 仅允许优先级最高的处理器写入APRAM CRCW ArbitraryPRAM CRCW 允许任意处理器自由写入PRAM CREW并发读互斥写PRAM EREW互斥读互斥写计算能力比较PRAM CRCW是最强的计算模型 PRAM EREW可logp倍模拟PRAM CREW和PRAM CRCW PRAM模型 优点适合并行算法表示和复杂性分析 易于使用 隐藏了并行机的通讯 同步等细节 缺点不适合MIMD并行机 忽略了SM的竞争 通讯延迟等因素 异步APRAM模型 基本概念又称分相 Phase PRAM或MIMD SM 每个处理器有其局部存储器 局部时钟 局部程序 无全局时钟 各处理器异步执行 处理器通过SM进行通讯 处理器间依赖关系 需在并行程序中显式地加入同步路障 指令类型 1 全局读 2 全局写 3 局部操作 4 同步 异步APRAM模型 计算过程由同步障分开的全局相组成 异步APRAM模型 计算时间设局部操作为单位时间 全局读 写平均时间为d d随着处理器数目的增加而增加 同步路障时间为B B p 非降函数 满足关系 或令为全局相内各处理器执行时间最长者 则APRAM上的计算时间为优缺点易编程和分析算法的复杂度 但与现实相差较远 其上并行算法非常有限 也不适合MIMD DM模型 BSP模型 基本概念由Valiant 1990 提出的 块 同步模型 是一种异步MIMD DM模型 支持消息传递系统 块内异步并行 块间显式同步 模型参数p 处理器数 带有存储器 l 同步障时间 Barriersynchronizationtime g 带宽因子 timesteps packet 1 bandwidth BSP模型 计算过程由若干超级步组成 每个超级步计算模式为左图优缺点强调了计算和通讯的分离 提供了一个编程环境 易于程序复杂性分析 但需要显式同步机制 限制至多h条消息的传递等 logP模型 基本概念由Culler 1993 年提出的 是一种分布存储的 点到点通讯的多处理机模型 其中通讯由一组参数描述 实行隐式同步 模型参数L networklatencyo communicationoverheadg gap 1 bandwidthP processors注 L和g反映了通讯网络的容量 logP模型 优缺点捕捉了MPC的通讯瓶颈 隐藏了并行机的网络拓扑 路由 协议 可以应用到共享存储 消息传递 数据并行的编程模型中 但难以进行算法描述 设计和分析 BSPvs LogPBSP LogP BSP块同步 BSP子集同步 BSP进程对同步 LogPBSP可以常数因子模拟LogP LogP可以对数因子模拟BSPBSP LogP Barriers OverheadBSP提供了更方便的程设环境 LogP更好地利用了机器资源BSP似乎更简单 方便和符合结构化编程 作业 1 TOP500综述应用举例 新闻报道等选择某个型号的高性能计算机 撰写调研报告顾乃杰等 基于斐波那契序列的多播算法Brent定理的证明和意义BSP编程方法调研 23 模型与下界 不同的PRAM模型的相互模拟下界NP完全理论P完全理论 不同的PRAM模型的相互模拟 不同的PRAM模型PRAM EREWPRAM CREWPRAM CRCWCPRAM CRCWAPRAM CRCWPPRAM CRCW计算能力是相当的 PRAM EREW模拟PPRAM CRCW 定理1 一条p 处理器PPRAM CRCW模型上的指令 可在p 处理器PRAM EREW模型上用O logp 的时间实现 证明思路 并发读指令和并发写指令 PPRAM CRCW 并发读指令 处理器Qi读取Mi单元中的内容 PRAM EREW 处理器Pi设置数对按照字典序排序 时间O logp 第一分量相同的数对组成块 通过树播送数据 完成数据分布 Pi读取对于的数据 时间O 1 并发写指令 使用三元组推论 TEREW O TPCRCWlogp PRAM CRCW之间的模拟 CPRAM CRCW上算法可在APRAM CRCW上正确执行APRAM CRCW上算法可在PPRAM CRCW上正确执行似乎计算能力是按CPRAM CRCW APRAM CRCW PPRAM CRCW依次增强的 在对处理器数目或对共享存储的容量不加限制时 三个模型是等效的 最左俘获问题 p个处理器 活跃 或者 非活跃 每个活跃的处理器有标记 值为0或1 当且仅当处理器是编号最小的活跃处理器 标记为1 CPRAM CRCW模拟PPRAM CRCW 定理2运行在p 处理器PPRAM CRCW上时间为T的算法 可在plogp 处理器CPRAM CRCW上运行时间为O T 证明思路 对于PPRAM CRCW中每个参与写操作的处理器 使用logp个辅助处理器 构造一个完全二叉树来选取标号最小的活跃处理器 定理3p 处理器PPRAM CRCW上的一条并发写指令 可在p 处理器CPRAM CRCW模型上用O logp loglogp 时间实现 证明思路 归纳法 APRAM CRCW模拟PPRAM CRCW 定理4p 处理器PPRAM CRCW上的一条并发写指令 可在p 处理器APRAM CRCW模型上用O loglogp 时间实现 证明思路 方根划分技术 递归求解时间 模拟的意义 算法研究的两个方向 优化寻找更好的算法设计技巧一个新的算法 上界 可能性说明难以得到更好的算法证明技巧对模型 问题的更好认识 下界 Gates WilliamH andChristosH Papadimitriou Boundsforsortingbyprefixreversal DiscreteMathematics27 1979 47 57 HarvardUniversity 1973 Microsoft 1975 PrincetonUniversity MS1974andPhD1976 上界与下界 问题描述 仅通过前缀翻转 prefixreversal 操作对n个大小不同的序列排序 前缀翻转 将包含首个元素的子序列进行翻转结果 给出算法 证明至多 5n 5 3次操作可以排序完成给出例子 证明17n 16次操作无法完成排序改进 1995年 新的下界结果 PRAM模型的下界 理想的PRAM模型n个处理器可访问无限的共享存储单元每个处理器有无限的私有存储单元一步计算分为三个阶段 读阶段 计算阶段 写阶段每一步计算允许任意数量的局部计算理想PRAM模型反映了通信的限制理想PRAM模型的下界对于标准PRAM模型同样成立 PRAM模型的下界 PRAM CREW的下界无论多少处理器 计算n变元的布尔或需要 logn 的时间PRAM EREW的下界p个处理器 计算长度为n的计数零问题需要 logn logp 的时间PRAM CRCW的下界计算n变量奇偶函数 使用多项式数目的处理器需要 logn loglogn 的时间 NP完全理论导引 计算复杂性理论中最重要的理论在工作中 遇到一个问题 找不到好的算法来解决 怎么办 算法与好的算法 算法 为实现某个任务而构成的简单指令集有穷的计算良过程通过有限多次运算可以决定的过程图灵机好的算法 多项式时间算法指数时间算法往往在实际中不可接受各种串行计算模型是多项式时间等价的是否所有的问题都有好的算法 SAT问题TSP Travelingsalesmanproblem 猜测TSP没有多项式时间算法 J Edmonds1965 图灵机 带子可读可写无限长的带子读写头可左移右移 图灵机 实际的 的图灵机模型单带图灵机 1TM 多带图灵机 kTM 随机存取机 RAM 实际的 单位时间内完成的工作量有一个多项式上界所有 实际的 计算模型多项式时间等价 非确定型图灵机 NTM 不现实的计算现实中的计算方式都是确定的解SAT问题的一个非确定型算法第一步 猜测一个变量的真值赋值 第二步 检查该赋值是否满足非确定型算法的计算时间 各种可能的计算过程的最短时间 非确定型图灵机 NTM 猜想模块 猜想阶段验证阶段 NTM计算树 计算过程 从根到叶节点的路径 P类与NP类 判定问题 只有肯定和否定两种答案优化问题可以化作判定问题处理P类 Polynomial 具有多项式时间算法的判定问题形成的计算复杂性类NP问题 在非确定型图灵机上多项式时间可解的问题在确定型图灵机上多项式时间可验证的问题P类包含于NP类中NP类问题在确定图灵机上指数时间可解非确定型图灵机和确定型图灵机的计算能力相当 计算难度的比较 归约 多项式时间归约 Karp归约1972 问题A的实例I多项式时间内转化为问题B的实例f I 对于A的输入I的回答与其对应的B的输入f I 一致 则称A可多项式归约于B 记为如果B可以多项式时间求解 则A也可以多项式时间求解 NP完全问题 NP完全问题是NP问题中 最难 的问题 NP完全问题 第一个NP完全问题 Cook levin定理1971 可满足性问题是NP完全问题如果一个NP完全问题karp归约到另一个NP问题 则该问题也是NP完全的六个NP完全问题 Karp1972 3SAT 3DM VC 团 HC 划分更多的NP完全问题1979年 300多个1998年 2000多个 P NP P NP问题 现在的估计 如果 则NPC问题无有效算法 P NP 如何处理NP完全问题 实际中的NP完全问题不会消失证明难度并不会使问题得到解决近似算法随机算法 并行计算理想的PRAM模型上可多项式时间解决NP完全问题 P完全理论导引 计算模型 PRAMP类NC Nick sClass 类 在PRAM上 使用多项式数目的处理器 在多对数时间内可求解的问题 NC类在P类中有些问题难以在使用多项式数目的处理器 在多对数时间