资源预览内容
第1页 / 共29页
第2页 / 共29页
第3页 / 共29页
第4页 / 共29页
第5页 / 共29页
第6页 / 共29页
第7页 / 共29页
第8页 / 共29页
第9页 / 共29页
第10页 / 共29页
亲,该文档总共29页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
并 行 计 算中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥)2004年12月Date1现代密码学理论与实践之五第二篇 并行算法的设计第四章 并行算法的设计基础第五章 并行算法的一般设计方法第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程Date2现代密码学理论与实践之五第四章 并行算法的设计基础4.1 并行算法的基础知识4.2 并行计算模型Date3现代密码学理论与实践之五4.1 并行算法的基础知识4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3 并行算法的复杂性度量4.1.4 并行算法中的同步和通讯Date4现代密码学理论与实践之五并行算法的定义和分类 并行算法的定义 算法 并行算法:一些可同时执行的诸进程的集合,这些进 程互相作用和协调动作从而达到给定问题的求解。 并行算法的分类 数值计算和非数值计算 同步算法和异步算法 分布算法 确定算法和随机算法Date5现代密码学理论与实践之五4.1 并行算法的基础知识4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3 并行算法的复杂性度量4.1.4 并行算法中的同步和通讯Date6现代密码学理论与实践之五并行算法的表达 描述语言 可以使用类Algol、类Pascal等; 在描述语言中引入并行语句。 并行语句示例 Par-do语句for i=1 to n par-doend for for all语句for all Pi, where 0ikend for Date7现代密码学理论与实践之五4.1 并行算法的基础知识4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3 并行算法的复杂性度量4.1.4 并行算法中的同步和通讯Date8现代密码学理论与实践之五并行算法的复杂性度量 串行算法的复杂性度量 最坏情况下的复杂度(Worst-CASE Complexity) 期望复杂度(Expected Complexity) 并行算法的几个复杂性度量指标 运行时间t(n):包含计算时间和通讯时间,分别用计算 时间步和选路时间步作单位。n为问题实例的输入规模 。 处理器数p(n) 并行算法成本c(n): c(n)=t(n)p(n) 总运算量W(n): 并行算法求解问题时所完成的总的操 作步数。Date9现代密码学理论与实践之五并行算法的复杂性度量 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)Date10现代密码学理论与实践之五4.1 并行算法的基础知识4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3 并行算法的复杂性度量4.1.4 并行算法中的同步和通讯Date11现代密码学理论与实践之五并行算法的同步 同步概念 同步是在时间上强使各执行进程在某一点必须互相等待; 可用软件、硬件和固件的办法来实现。 同步语句示例 算法4.1 共享存储多处理器上求和算法输入:A=(a0,an-1),处理器数p输出:S=aiBegin (1)S=0 (2.3) lock(S) (2)for all Pi where 0ip-1 do S=S+L(2.1) L=0 (2.4) unlock(S)(2.2) for j=i to n step p do end forL=L+aj Endend forend for Date12现代密码学理论与实践之五并行算法的通讯 通讯 共享存储多处理器使用:global read(X,Y)和global write(X,Y) 分布存储多计算机使用:send(X,i)和receive(Y,j) 通讯语句示例 算法4.2 分布存储多计算机上矩阵向量乘算法输入:处理器数p, A划分为B=A1n,(i-1)r+1ir, x划分为w=w(i-1)r+1;ir 输出:P1保存乘积AXBegin (1) Compute z=Bw(2) if i=1 then yi=0 else receive(y,left) endif(3) y=y+z(4) send(y,right)(5) if i=1 then receive(y,left)End Date13现代密码学理论与实践之五第四章 并行算法的设计基础4.1 并行算法的基础知识4.2 并行计算模型Date14现代密码学理论与实践之五4.2 并行计算模型4.2.1 PRAM模型4.2.2 异步APRAM模型4.2.3 BSP模型4.2.4 logP模型Date15现代密码学理论与实践之五Date16现代密码学理论与实践之五PRAM模型 基本概念 由Fortune和Wyllie1978年提出,又称SIMD-SM模型 。有一个集中的共享存储器和一个指令控制器,通过 SM的R/W交换数据,隐式同步计算。 结构图Control UnitInterconnection NetworkPLMPLMPLMPLMShared MemoryDate17现代密码学理论与实践之五PRAM模型 分类 PRAM-CRCW并发读并发写 CPRAM-CRCW(Common PRAM-CRCW):仅允许写入相同数据 PPRAM-CRCW(Priority PRAM-CRCW):仅允许优先级最高的处理器写入 APRAM-CRCW(Arbitrary PRAM-CRCW):允许任意处理器自由写入 PRAM-CREW并发读互斥写 PRAM-EREW互斥读互斥写 计算能力比较 PRAM-CRCW是最强的计算模型,PRAM-EREW可logp倍模拟 PRAM-CREW和PRAM-CRCW Date18现代密码学理论与实践之五PRAM模型 优点 适合并行算法表示和复杂性分析,易于使用,隐藏了 并行机的通讯、同步等细节。 缺点 不适合MIMD并行机,忽略了SM的竞争、通讯延迟 等因素Date19现代密码学理论与实践之五4.2 并行计算模型4.2.1 PRAM模型4.2.2 异步APRAM模型4.2.3 BSP模型4.2.4 logP模型Date20现代密码学理论与实践之五异步APRAM模型 基本概念 又称分相(Phase)PRAM或MIMD-SM。每个处理 器有其局部存储器、局部时钟、局部程序;无全局时 钟,各处理器异步执行;处理器通过SM进行通讯; 处理器间依赖关系,需在并行程序中显式地加入同步 路障。 指令类型(1)全局读 (2)全局写 (3)局部操作 (4)同步 Date21现代密码学理论与实践之五异步APRAM模型 计算过程 由同步障分开的全局相组成 Date22现代密码学理论与实践之五异步APRAM模型 计算时间设局部操作为单位时间;全局读/写平均时间为d,d随着处理器数 目的增加而增加;同步路障时间为B=B(p)非降函数。满足关系 ; 或令 为全局相内各处理器执行时间最长者,则APRAM上的计算时 间为 优缺点易编程和分析算法的复杂度,算法的正确性容易保证;但与现实相 差较远,其上并行算法非常有限,也不适合MIMD-DM模型。Date23现代密码学理论与实践之五4.2 并行计算模型4.2.1 PRAM模型4.2.2 异步APRAM模型4.2.3 BSP模型4.2.4 logP模型Date24现代密码学理论与实践之五BSP模型 基本概念 由Valiant(1990)提出的,“块”同步模型,是一种异步 MIMD-DM模型,支持消息传递系统,块内异步并行 ,块间显式同步。 模型参数 p:处理器数(带有存储器) l:同步障时间(Barrier synchronization time) g:带宽因子(time steps/packet)=1/bandwidth Date25现代密码学理论与实践之五BSP模型 计算过程 由若干超级步组成, 每个超级步计算模式为左图 优缺点强调了计算和通讯的分离,提供了一个编程环境,易于程序复杂性分析。但需要显式同步机制,限制至多h条消息的传递等。Date26现代密码学理论与实践之五4.2 并行计算模型4.2.1 PRAM模型4.2.2 异步APRAM模型4.2.3 BSP模型4.2.4 logP模型Date27现代密码学理论与实践之五logP模型 基本概念 由Culler(1993)年提出的,是一种分布存储的、点到 点通讯的多处理机模型,其中通讯由一组参数描述, 实行隐式同步。 模型参数 L:network latency o:communication overhead g:gap=1/bandwidth P:#processors 注:L和g反映了通讯网络的容量 Date28现代密码学理论与实践之五logP模型 优缺点捕捉了MPC的通讯瓶颈,隐藏了并行机的网络拓扑、路由、协议 ,可以应用到共享存储、消息传递、数据并行的编程模型中;但难 以进行算法描述、设计和分析。 BSP vs. LogP BSPLogP:BSP块同步BSP子集同步BSP进程对同步 LogP BSP可以常数因子模拟LogP,LogP可以对数因子模拟BSP BSPLogP+BarriersOverhead BSP提供了更方便的程设环境,LogP更好地利用了机器资源 BSP似乎更简单、方便和符合结构化编程 Date29现代密码学理论与实践之五
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号