没有合适的资源?快使用搜索试试~ 我知道了~
首页并行计算在三对角线性方程与偏微分方程求解中的应用研究
并行计算在三对角线性方程与偏微分方程求解中的应用研究
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 86 浏览量
更新于2024-07-02
收藏 1.27MB PDF 举报
"云计算-三对角系统与偏微分方程若干并行计算问题的研究.pdf" 该研究主要探讨了在云计算环境中,如何利用并行计算技术高效地解决三对角线性方程组以及处理偏微分方程(PDE)的若干问题。全文分为三个部分,共七章。 第一部分(第1、2章)主要介绍了论文的内容概要以及并行计算的架构和编程。这部分详细阐述了并行计算的基本概念,包括并行计算的历史、重要性以及MPI(Message Passing Interface)编程模型。同时,这部分还提供了本研究的数值实验环境背景,为后续的分析和实验奠定了基础。 第二部分(第3、4章)集中讨论了求解三对角线性方程组的直接方法。作者首先总结了在并行计算中解决这类问题的通用研究状况,接着深入探讨了递归加倍、循环减量以及基于矩阵分解的并行算法的思想方法。在此基础上,他们提出了一种结合循环减量和分而治之策略的最优化大步交替循环减量法。此外,引入了流水线技术,并讨论了其在基于矩阵分解的并行算法中的应用,以提高计算效率和并行度。 第三部分(第5章及以后章节)则转向偏微分方程的并行有限差分方案。这部分可能涉及了多种PDE的数值解法,如有限差分法、谱方法等,并探讨了如何在云计算平台上实现这些方法的并行化,以解决大规模的科学计算问题。可能涵盖了误差分析、稳定性研究以及性能优化等内容。 通过这样的研究,作者旨在利用云计算的强大计算能力,为解决复杂的科学计算问题提供更快速、更有效的解决方案。这些研究成果对于推动科学计算领域的进步,尤其是在处理大规模数据和复杂模型时,具有重要的理论价值和实际应用前景。
资源详情
资源推荐
第二章 并行计算概要和 MPI 程序设计
9
大而复杂的问题分解成若干特性相同的子问题分而治之。若所得的子问题规模仍嫌过
大,可反复使用分治策略,直至很容易求解诸子问题为止。使用分治法时,子问题的
类型通常和原问题的类型相同,因此分治法很自然的导致递归(Recursion)过程。
一般而言,并行分治法分为三步:①将输入划分成若干规模近于相等的子问题;
②同时递归的求解各个子问题;③归并各子问题的解成为原问题的解。
一个问题能否使用分治策略,主要看能否有效地执行上述问题分解和归并。如果
归并开销过大,可使用流水线技术进行归并。
(3) 平衡树设计技术
平衡树(Balanced Tree)方法是将输入元素作为叶节点构成一棵平衡二叉树,
然后自叶向根往返遍历。此方法成功的部分原因是在树中能快速的存取所需要的信
息。平衡二叉树的方法可以推广到内结点的子节点的数目不止两个的任意平衡树。这
种方法对数据的播送、压缩、抽取和前缀计算等甚为有效。
(4) 倍增设计技术
倍增技术(Doubling Technique)又称指针跳跃(Pointer Jumping)技术,特
别适合处理链表或有向有根树之类表示的数据结构,在图论和链表算法中有着广泛的
应用。每当递归调用时,所要处理的数据之间的距离将逐步加倍,经过
k
步后就可完
成距离为
k
2
的所有数据的计算。
(5) 流水线设计技术
在并行处理中,流水线(Pipelining)技术是一项重要的并行技术。其基本思想
是将一个计算任务
t
分成一系列子任务
12
, , ,
m
t t t
,使得一旦
1
t
完成,后继的子任务就
可立即开始,并以同样的速度进行计算。流水线并行,是指一些进程形成流水线作业
法,诸进程在流水线的不同地段同时重叠地执行操作以达到整体并行的效果。
§2.1.2.3 并行算法的一般设计过程
设计并行算法是一件复杂的事,而并行算法的设计这门学科还属于发展中的一门
学科,目前尚无一套普遍适用的、系统的设计方法学。
要从给定问题的描述出发,通过一系列步骤,最终设计出一个展示并发性、可扩
放性、局部性和模块性的并行算法,此过程可分为四步,即任务划分(Partitioning)、
通信(Communication)分析、任务组合(Agglomeration)和处理器映射(Mapping),
简称 PCAM 设计过程。
PCAM 是一种设计方法学。其在设计的前期主要考虑并发性等与机器无关的特性,
在设计的后期才考虑与机器有关的特性。也就是说,在设计的第一和第二阶段,关注
的是并发性和可扩放性,并寻求开发出具有这些特性的并行算法。在设计的第三和第
四阶段才把注意力转移到局部性和别的与性能有关的问题上。并行算法的整个过程可
概括于图 2.1 中。它从给定设计问题的说明开始,寻找一种计算任务的划分方法,确
万方数据
第二章 并行计算概要和 MPI 程序设计
10
定诸任务的通信要求,组合可能的计算任务,最后将优化了的诸任务指派给实际的处
理器。
图 2.1 并行算法的 PCAM 设计过程
上述各阶段可简述如下:
① 划分:将整个计算分解成一些小的任务,其目的是尽量开拓并行执行的机会。
② 通信:确定诸任务执行中所需交换的数据和协调诸任务的执行,由此可检测
上述划分的合理性。
③ 组合:按性能要求和实现的代价来考察前两阶段的结果,必要时可将一些小
的任务组合成更大的任务以提高性能或减少通信开销。
④ 映射:将每个任务分配到一个处理器上,其目的是最小化全局执行时间和通
信成本以及最大化处理器的利用率。
虽然上述的设计过程是一步一步进行的,但实际上它们可以同时一并考虑;同样,
虽然我们希望一个算法能用上述四步一次设计成功,但实际上设计过程的回溯反复总
是难免的。
§2.1.3 并行算法的性能评测
并行计算的性能评测与并行计算机体系结构、并行算法和并行程序设计一起构成
了“并行计算”研究的四大分支。
并行计算的性能评测,大致可分为机器级的性能评测、算法级的性能评测和程序
级的性能评测。机器级的性能评测主要包括 CPU 和存储器的某些基本性能指标,并行
问题
划分
映射
组合
通信
万方数据
第二章 并行计算概要和 MPI 程序设计
11
通信开销以及机器的成本、价格和性/价比等;算法级的性能评测主要包括加速、效
率和可扩放性等;程序级的性能评测主要包括基本测试程序、数学库测试程序和并行
测试程序等。
在并行系统上进行计算的主要目的就是加速整个计算的过程,所以研究并行算法
的加速比性能是必要的也是根本的;随着计算机负载的增加和机器规模的扩大,研究
算法的性能能否随着处理器数目的增加而按比例的增加也是很重要的,这就是并行计
算的可扩展性问题。
加速比和并行效率是最传统的并行算法评价标准,它体现在并行机上运用并行算
法解决实际问题所能获得的好处。对求解具有相同规模的同一应用问题,最基本的并
行算法加速比可定义为
poptp
/TTS
(2.1)
式中:
opt
T
-最优串行算法在单处理机上的运行时间
p
T
-并行算法在并行机上使用
p
台处理机所需时间
从问题规模上,并行加速比可分为固定规模问题的加速比模型和可变规模问题的
加速比模型。设处理器数
p
,问题的串行部分所占比例为
f
,则并行所占比例为
fN 1
。1967 年 Amdahl 推导出了如下固定负载的加速公式:
(1 )
1
1 ( 1)
p
f f p
S
f
fp
f
p
(2.2)
这就是著名的 Amdahl 加速定律,它意味着随着处理器数目的无限增加,并行系
统所能达到的加速比上限为
/f1
,这是一个很悲观的结论。
对于扩充问题规模的加速比模型又称为 Gustafson 加速比模型。它是对 Amdahl
模型的修正。其加速比为:
(1 )
(1 )
(1 )
p
f f p
S f f p
fp
f
p
(2.3)
上式表明,要获得较高的加速比,应随着处理机数目的增加而相应的增加问题规
模,而不是固定问题规模。它意味着随着处理机数目的增加,加速几乎与处理器数目
成比例的线性增加。串行比例
f
不再是程序的一个瓶颈,这对并行系统的发展是一个
非常乐观的结论。
固定存储容量的加速比模型是 X.H.Sun 和 L.Ni 在研究同构并行机的加速比时提
出的。其基本思想是在并行机有限存储空间的条件下求解尽可能大的应用问题,以获
得较高加速比、较高精度的解和较好的资源利用率。
§2.1.4 并行算法的可扩展性
万方数据
第二章 并行计算概要和 MPI 程序设计
12
并行计算的可扩放性(Scalability)也是并行算法评测的主要性能指标。增加
处理器数会增大额外开销和降低处理器利用率,所以对于一个特定的并行系统(算法
或程序),它们能否有效利用不断增加的处理器的能力应是受限的,而度量这种能力
就是可扩放性这一指标。
可扩放性最简朴的含意是在确定的应用背景下,计算机系统(或算法或程序等)
性能随处理器数的增加而按比例提高的能力。虽然已经提出了很多可扩放性度量标
准,但尚无一个公认的、标准的和被普遍接受的严格定义和评判它的标准。目前主要
有等效率、等速度和平均延迟等度量标准。
§2.1.5 并行算法的效率
并行算法的效率定义为:
p
p
S
E
p
(2.4)
它反映了并行系统中处理器的利用情况。因为有时候一个并行算法虽然有好的加
速比,但处理器的利用率可能很低。特别是处理器个数
p
不固定时,
p
S
不是一个最
好的评价标准。不难推知,
10
p
E
。
§2.2 MPI 程序设计
§2.2.1 MPI 概述
§2.2.1.1 什么是 MPI
消息传递界面MPI
[1]-[5]
(Message Passing Interface)是1994年5月发布的一种
消息传递接口。它实际上是一个消息传递函数库的标准说明,吸取了众多消息传递系
统的优点,是目前国际上最流行的并行编程环境之一。MPI提供了一种与语言和平台
无关,可以被广泛使用的编写消息传递程序的标准。
①MPI是一个库而不是一门语言。可在FORTRAN70、FORTRAN90、C和C++语言中调
用。它遵守所有对库函数过程的调用规则,和一般的函数/过程没有什么区别
②MPI是一种标准或规范的代表,而不特指某一个对它的具体实现。
③MPI是一种消息传递编程模型并成为这种编程模型的代表和事实上的标准。
消息传递方式是广泛应用于多类并行机的一种模式,特别是那些分布存储并行
机,尽管在具体的实现上有许多不同,但通过消息完成进程通信的基本概念是容易理
解的。十多年来,这种模式在重要的计算应用中已取得了实质进步。有效和可移植地
实现一个消息传递系统是可行的,因此通过定义核心库程序的语法、语义,这将在大
范围计算机上可有效实现,将有益于广大用户,这是MPI产生的重要原因。
万方数据
剩余79页未读,继续阅读
programxh
- 粉丝: 17
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 构建Cadence PSpice仿真模型库教程
- VMware 10.0安装指南:步骤详解与网络、文件共享解决方案
- 中国互联网20周年必读:影响行业的100本经典书籍
- SQL Server 2000 Analysis Services的经典MDX查询示例
- VC6.0 MFC操作Excel教程:亲测Win7下的应用与保存技巧
- 使用Python NetworkX处理网络图
- 科技驱动:计算机控制技术的革新与应用
- MF-1型机器人硬件与robobasic编程详解
- ADC性能指标解析:超越位数、SNR和谐波
- 通用示波器改造为逻辑分析仪:0-1字符显示与电路设计
- C++实现TCP控制台客户端
- SOA架构下ESB在卷烟厂的信息整合与决策支持
- 三维人脸识别:技术进展与应用解析
- 单张人脸图像的眼镜边框自动去除方法
- C语言绘制图形:余弦曲线与正弦函数示例
- Matlab 文件操作入门:fopen、fclose、fprintf、fscanf 等函数使用详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功