并行算法设计及编程基本方法

《并行算法设计及编程基本方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2卷第4期零陵学院学报(教育科学)Vol.2No.42004年8月JournalofLinglingUniversityAug.2004并行算法设计及编程基本方法孙兴文(永州职业技术学院,湖南永州,425006)摘要:并行算法是指一次可执行多个操作的算法。对并行算法的研究现在已发展为一个独立的研究领域。很多用串行算法解决的问题也已经有了相应的并行算法。在本文，我们阐述了一些简单的并行计算以说明并行算法的一些基本概念、应用和编程方法。*关键词:并行算法;效率;编程中图分类号:TP311文献标识码:A文章编号：1671-9697(2004)04-0182-031.并行算法设计1.1并行算法的

2、基本概念所谓并行，是只有一个以上的事件在同一时刻伙同时间段内发生，有人把并行分为几类：数据并性行，分布式并性行与人的并行性，世界上客观事物的发展过程很多是并行的，彼此相对独立，相互又有一定的联系和制约。1.2并行算法的目标从计算复杂性的角度来看，一个算法的复杂性表示为空间复杂性和时间复杂性两个方面。并行算法的目标是尽可能减少时间复杂性，通常是增加空间复杂性（如增加空间的维数及增加处理器的台数）来实现。从算法树的结构来看，通常的串行算法树“深而窄”。递推算法是串行算法本质上是为一维问题设计的，而不少高维问题的计算本质上仍借助一维的张量积形式。体现在矩阵计算则是70年代稀疏矩阵技术的广发应用。

3、并行算法树的结构则截然不同，为达到把时间复杂性转化为时间复杂性的目的，并行算法树采用“浅而宽”的结构，即每时刻可容纳的计算量相应增加，使整个算法的步数尽可能减少。适当增加空间复杂性（如引入较复杂的基底，增加空间维数等），是不少并行算法所实际采用的有效的方法。1.3加速比定率与可扩展性顾名思义，并行加速比是表示采用多个矗立起计算速度所能得到的加速的倍数。设tseq表示用串行机求解某个计算问题所需的时间，tP是用p个处理器求解该问题所需的时间。定义1.1p个处理器加速比．SP=t1/t2（１.１）这里t1是用但处理求解统一问题所需的时间。定义1.2并行加速比ŝP＝tsep/tp（１.２）这里

4、tsep是表示用串行机求解该问题所需的时间。应该指出，一般情况下ŝp

5、dahl定律或者称Ware定律。在理想情况下，该程序的每一部分如能完全并行，那是p个处理器的加速比似乎应该等于p。一般情况下，这是不可能的。一个并行程序加速比接近于p,就称为很好的，是高度并行。若Sp＝o(p)，则称为具有线性加速笔；若Sp>p，则称为超线性加速比。根据Amdahl定律，严格的线性加速比似乎是不可能达到的，更不用说超线性加速比了。但是在某些实用程序算法中，可能出现这种现象。例如，某些并行搜索技术允许每个处理器在不同的方向上搜索，一旦某个进程找到了一个结果，它就向其它处理器发出信号中止搜索，这样就会比串行机的相应算法提前取消那些无谓的搜索分支。因而出现超线性加速比。但在一般情

6、况下，当并行计算机结果出现超线性加速比，就要很慎重地分析原因。并行计算机系统中各个处理器的存储方式不同，高速缓存的影响，以及并行操作系统开销的均摊都有出现超线性加速比的假象。并行效率是与加速比相关联的概念，一个并行的效率定义为Ep=Sp/p(1.4)其中p微处理器个数，当加速比Sp接近p时，效率Ep接近于1。影响并行效率的因素很多。首先，不能期望一个程序的所有部分都完全并行。例如，输入，输出部分。输出部分通常是用单处理机完成的，处理器之间的通信与同步都需要时间开销，各个处理器中所执行的运算量也是不可能完全精确相同，总会出现某些处理器的负载不均衡甚至是处于闲置等待状态。1.4并行算法的分类算

7、法是解题方法的描述，以确定解决某一特征类型问题的运算顺序与规则。根据所解决问题的类型不同或者计算模型不同，相应的计算方法应有所不同。并行算法有以下几类：1）数值并行算法，主要为数值计算方法而设计的并行算法。2）非熟制并行算法，如神经网络算法，演化算法，遗传算法，格子气算法，以及为符号计算设计的并行算法。3）同步并行算法，是指某些进程必须等待其他进程的一种并行算法。要求所有进程必须在一个给定时刻同步。SIMD以及共享型的M