1 / 41
文档名称:

并行算法抽象模型.ppt

格式:ppt   大小:424KB   页数:41页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

并行算法抽象模型.ppt

上传人:85872037 2017/10/17 文件大小:424 KB

下载得到文件列表

并行算法抽象模型.ppt

文档介绍

文档介绍:并行算法的抽象模型
并行算法的定义和分类
并行算法的定义
算法
并行算法:一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。
并行算法的分类
数值计算和非数值计算
同步算法和异步算法
分布算法
确定算法和随机算法
并行算法的表达
描述语言
可以使用类Algol、类Pascal等;
在描述语言中引入并行语句。
并行语句示例
Par-do语句(Do in parallle)算法要并行执行
for i=1 to n par-do
……
end for
for all语句(几个处理器同时执行相同的操作)
for all Pi, where 0≤i≤k
……
end for
并行算法的复杂性度量
串行算法的复杂性度量
最坏情况下的复杂度(Worst-plexity)
期望复杂度(plexity)
并行算法的几个复杂性度量指标
运行时间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)
一个算法在运行过程中,不一定都能充分地利用有效地处理器去工作。
并行算法的同步
同步概念
同步是在时间上强使各执行进程在某一点必须互相等待;
可用软件、硬件和固件的办法来实现。
同步语句示例
共享存储多处理器上求和算法
输入:A=(a0,…,an-1),处理器数p
输出:S=Σai
Begin
(1)S=0 () lock(S)
(2)for all Pi where 0≤i≤p-1 do S=S+L
() L=0 () unlock(S)
() for j=i to n step p do end for
L=L+aj End
end for
end for
并行算法的通信
通信(使用通信原语)
共享存储多处理器使用:global read(X,Y)和global write(X,Y)
分布存储多计算机使用:send(X,i)和receive(Y,j)
通信语句示例
分布存储多计算机上矩阵向量乘算法
输入:处理器数p, A划分为B=A[1..n,(i-1)r+1..ir],
x划分为w=w[(i-1)r+1;ir]
输出:P1保存乘积AX
Begin
(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
抽象模型的概念
并行计算模型通常指从并行算法的设计和分析出发,将各种并行计算机(至少某一类并行计算机)的基本特征抽象出来,形成一个抽象的计算模型。从更广的意义上说,并行计算模型为并行计算提供了硬件和软件界面,在该界面的约定下,并行系统硬件设计者和软件设计者可以开发对并行性的支持机制,从而提高系统的性能。
并行计算机的抽象模型
并行计算机的理论模型是从物理模型抽象的;
为开发并行算法提供了一种方便的框架;
用这些模型可求得并行计算机的理论性能界限;
可在芯片制作前估算芯片区的VLSI复杂性和执行时间。
一、时间与空间复杂性
计算机求解一个规模为s的问题的算法复杂性取决于:
执行时间
存储空间

最近更新

小学六年级上册数学期末测试卷(精选题)word版.. 8页

青岛版六年级下册数学第二单元-冰淇淋盒有多大.. 6页

部编版小学四年级上册道德与法治期中测试卷带.. 7页

部编版四年级下册道德与法治期末卷附答案【基.. 8页

部编版四年级上册道德与法治期末测试卷精品【.. 8页

部编版六年级下册道德与法治期中卷一套及答案.. 10页

部编版五年级下册道德与法治第二单元测试卷含.. 7页

部编版五年级下册道德与法治期中测试卷含答案.. 10页

部编版二年级下册道德与法治期中测试卷精品(典.. 7页

高中物理第十三章光本章整合课件新人教版 14页

部编版三年级上册道德与法治期中测试卷带下载.. 5页

2025年三年级语文上册第三单元7大地巨人第2课.. 2页

道德与法治五年级下册第1单元我们是一家人测试.. 6页

西师大版数学五年级上册期末测试卷(培优a卷) 6页

现代三项治疗腰椎间盘突出症 40页

2025年七年级地理上册2.2海陆的变迁同步练习新.. 5页

特灵螺杆式冷水机组介绍 56页

最新小学一年级上册数学填空题附完整答案(历年.. 13页

新部编版小学二年级上册道德与法治期末测试卷.. 6页

教科版四年级上册科学-期末测试卷附参考答案(.. 9页

小学六年级下册数学应用题50道精品【易错题】.. 18页

精神发育迟缓诊疗常规 4页

安全设施设计合同 4页

关键控制点与关键限值判定与控制培训教材 32页

2025年度防水堵漏工程定额 21页

起重吊装作业专项施工方案 20页

云南初中生成长记录手册 22页

中药不良反应影响因素概述 72页

基本素质发展云南省普通高中学生成长记录 25页

大蒙山施食 18页