并行算法研究进展
免费下载
http://www.ccf.org.cn
1
并行算法研究进展
陈国良
并行算法为并行计算的发展奠定理论基础，是我国高性能计算技术发展的关键之
一。要使其研究健康发展必须从学科建设入手，重视人才培养。
引言
什么是并行算法 简单地讲，算法就是求解问题的方法和步骤，而并行算法就是用多台处理机
联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问
题，然后使用多台计算机同时求解它，从而最终求得原问题的解。人们之所以对并行性感兴趣，是
因为在现实世界中存在着固有的并行性。其实在日常生活中，你可能自觉或不自觉地都在运用着并
行，比如一边听演讲，一边记笔记就是听觉、视觉和手写的并行。这类例子不胜枚举。然而，在处
理很多事务时，比如进行推理和计算，人们又习惯用串行方式，在这种情况下，要改用而且要用好
并行性也并非易事。同时，就计算科学而言，并行计算理论仍处于发展阶段，特别是早期的并行机
均很昂贵，编写并行软件又很难，所以并行性的优点尚未被普遍的认同。
为什么需要并行 首先，对于那些要求快速计算的应用问题，单处理机由于器件受物理速度的
限制而无法满足要求，所以使用多台处理机联合求解就势在必行了；其次，对于那些大型复杂的科
学工程计算问题，为 了提高计算精度，往往需要加密计算网格，而 细网格的计算也意味着大计算量，
它通常需要在并行机上实现；最后，对于那些实时性要求很高的应用问题，传统的串行处理往往难
以满足实时性的需要而必须在并行机上用并行算法求解。
并行算法的分类 并行算法可以分为数值并行算法和非数值并行算法：前者研究基于代数关系
运算的数值计算问题的并行算法，主要包括矩阵运算、方程组的求解和数字信号处理等；后者研究
基于比较关系运算的符号处理问题的并行算法，主要包括图论问题、数据库操作和组合优化等。本
文重点讨论非数值并行算法。
并行算法研究的层次 并行算法的研究可分为并行计算理论、并行算法的设计与分析以及并行
算法的实现三个层次。其中并行计算理论主要研究并行计算模型、计算问题的下界、问题的可并行
化、NC 类问题
1
和 P-完全问题
2
等。并行算法的设计与分析着重研究计算机科学中那些可用多项式数
目的处理器、在对数多项式（Poly-logarithmic）时间内可求解的诸多常用的计算问题的并行算法的
设计与分析方法。并行算法的实现主要研究并行算法的硬件实现平台（即并行计算机）和软件支持
环境（并行编程）。
并行算法研究的回顾 从历史上看，并行算法研究的高峰期似乎在 70 年代和 80 年代。这一阶
段，在各种不同互连结构的 SIMD
3
模型上和共享存储的 SIMD 模型上设计出了很多优秀的非数值并
行算法，它们在整个并行算法研究历史上占据着辉煌的一页。相应的在 80 年代中期和 90 年代初期
出版了几部非常优秀的并行算法方面的专著和教材
[1-9]
。90 年代中期以后，并行算法的研究渐渐面
向实际而内容有所拓宽。不但研究并行算法的设计与分析，而且也同时兼顾到并行机体系结构和并
1
在多项式数目的处理器和对数多项式的并行时间内可计算的问题称为 NC 类问题
2
在计算复杂性理论中将那些可用确定性图灵机在多项式时间内求解的问题称为 P 类问题，而其中最难有效并行计
算的问题称为 P 完全问题
3
Single Instruction Multiple Data (SIMD)单指令多数据流
http://www.ccf.org.cn
2
行程序设计。集中表现在上述几本书的作者，有的在书名中更强调了并行计算而出版了第二版，有
的将内容扩充，另出版了新书
[10-13]
。尽 管 并行算法的研究历史似乎有些起伏，但一直在前进发展着，
而且更面向实用。
并行算法研究的新机遇与新挑战 近几年来，随着半导体器件工艺水平的提高，计算技术和通
信网络的迅速发展，双 CPU 或 4CPU 的高档机已随处可见；而大学和研究所的各专业实验室中，自
行用多台 PC 机搭建的机群系统也越来越多。随着现今并行机的普及，并行机的用户要求学习和使
用并行算法也甚为迫切，这就给我们研究并行算法带来新的机遇，它将使并行算法的研究产生一个
新的飞跃。与此同时，近几年来由于硬件技术的飞速发展，使得拥有成千上万个 CPU 的高端并行机
相继研制成功。如何充分有效地利用如此巨量的 CPU，成为并行算法研究面对的一个极富挑战性的
问题。
当今并行算法研究的主要内容
当今并行算法主要研究内容包括并行计算模型、并行算法设计技术和并行复杂性理论等
[14]
。
并行计算模型 并行计算模型是从不同并行计算机体系结构中抽象出来的、供并行算法设计者
使用的一种抽象的并行机。任何模型均必须提供为数不多的、能反映并行机计算特性的且可以定量
计算出或实际测量出的一组参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复
杂度分析。常用的并行计算模型有共享存储的模型，包括共享存储的 SIMD 同步 PRAM
4
模型和共享
存储的 MIMD
5
异步 APRAM
6
模型；分布式存储模型，包括分布存储的 MIMD 大同步 BSP
7
模型和异
步 LogP
8
模型等
[15]
；分布共享存储模型，包括分布存储的 MIMD 均匀存储层次 UMH
9
模型和扩充 logP
存储 Memory-logP 模型以及分布式存储层次 DRAM（h）
10
模型等
[16]
。其中 PRAM 是算法界最常用
的抽象模型，但不太实用；BSP 和 LogP 等能反映大规模并行机的通信特性；UMH、Memory-logP
和 DRAM（h）等能反映近代主流并行机的多层次存储特性。此外，对于松散耦合的并行系统（如
基于局域网连接的 PC 机群等），也提出了异构非独占使用方式的分时计算模型。至于基于广域网连
接的网格计算系统，目前尚没有像前述那样的计算模型。
基本设计技术 并行算法设计技术尽管理论上不是很成熟，带有一定的技巧性，但也不是无章
可循。经过多年的发展，已经总结出了一些基本的、带有普适性的并行算法设计技术。归纳起来有：
划分法（Partitioning）是设计并行算法最自然朴素的方法，系将一个计算任务分解成若干个规模大
致相等的子任务而并行求解；分治法（Divide-and-Conquer）是求解大型问题的一种策略，系将一个
大而难的问题，逐次化为一些小规模可求解的子问题而递归求解；流水线法（Pipelining）是一种基
于 空 间 并行和时间重叠的问题求解技术，是并行处理技术中普遍使用的方法；随机法
（Randomization）是一种不确定性算法，在算法设计步中引入随机性，从而可望得到平均性能良好、
设计简单的并行算法；平衡树法（Balanced Tree）、倍增法（Doubling）和破对称法（Symmetry Breaking）
4
Parallel Random Access Machine (PRAM) 并行随机访存机器
5
Multiple Instruction Multiple Data (MIMD) 多指令多数据流
6
Asynchronous Parallel Random Access Machine (APRAM) 异步并行随机访存机器
7
Bulk Synchronous Parallel (BSP) 大同步并行
8
由大卫·库勒（David Culler）、理查德·卡普（Richad M. Karp）等人提出的一种并行计算模型，其特点是考虑并
行机的实际参数如延迟（latency）、消息传递开销（overhead）、消息传递间隙（gap）、处理器及内存模块数目（ number
of processor/memory modules）等
9
Uniform Memory Hierarchy
10
Distributed Random Access Machine 分布式随机访存机器，h 表示存储的层次数目
of 5
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论