bingxin
并行算法研究进展
陈国良
并行算法为并行计算的发展奠定理论基础，是我国高性能计算技术发展的关键之一。要使其研究健康发展必须从学科建设入手，重视人才培养。
引言
什么是并行算法简单地讲，算法就是求解问题的方法和步骤，而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。人们之所以对并行性感兴趣，是因为在现实世界中存在着固有的并行性。其实在日常生活中，你可能自觉或不自觉地都在运用着并行，比如一边听演讲，一边记笔记就是听觉、视觉和手写的并行。这类例子不胜枚举。然而，在处理很多事务时，比如进行推理和计算，人们又习惯用串行方式，在这种情况下，要改用而且要用好并行性也并非易事。同时，就计算科学而言，并行计算理论仍处于发展阶段，特别是早期的并行机均很昂贵，编写并行软件又很难，所以并行性的优点尚未被普遍的认同。
为什么需要并行首先，对于那些要求快速计算的应用问题，单处理机由于器件受物理速度的限制而无法满足要求，所以使用多台处理机联合求解就势在必行了；其次，对于那些大型复杂的科学工程计算问题，为了提高计算精度，往往需要加密计算网格，而细网格的计算也意味着大计算量，它通常需要在并行机上实现；最后，对于那些实时性要求很高的应用问题，传统的串行处理往往难以满足实时性的需要而必须在并行机上用并行算法求解。
并行算法的分类并行算法可以分为数值并行算法和非数值并行算法：前者研究基于代数关系运算的数值计算问题的并行算法，主要包括矩阵运算、方程组的求解和数字信号处理等；后者研究基于比较关系运算的符号处理问题的并行算法，主要包括图论问题、数据库操作和组合优化等。本文重点讨论非数值并行算法。
并行算法研究的层次并行算法的研究可分为并行计算理论、并行算法的设计与分析以及并行算法的实现三个层次。其中并行计算理论主要研究并行计算模型、计算问题的下界、问题的可并行化、NC类问题1和P-完全问题2等。并行算法的设计与分析着重研究计算机科学中那些可用多项式数目的处理器、在对数多项式（Poly-logarithmic）时间内可求解的诸多常用的计算问题的并行算法的设计与分析方法。并行算法的实现主要研究并行算法的硬件实现平台（即并行计算机）和软件支持环境（并行编程）。
并行算法研究的回顾从历史上看，并行算法研究的高峰期似乎在70年代和80年代。这一阶段，在各种不同互连结构的SIMD3模型上和共享存储的SIMD模型上设计出了很多优秀的非数值并行算法，它们在整个并行算法研究历史上占据着辉煌的一页。相应的在80年代中期和90年代初期出版了几部非常优秀的并行算法方面的专著和教材[1-9]。90年代中期以后，并行算法的研究渐渐面向实际而内容有所拓宽。不但研究并行算法的设计与分析，而且也同时兼顾到并行机体系结构和并
1在多项式数目的处理器和对数多项式的并行时间内可计算的问题称为NC类问题
2在计算复杂性理论中将那些可用确定性图灵机在多项式时间内求解的问题称为P类问题，而其中最难有效并行计算的问题称为P完全问题
3Single Instruction Multiple Data (SIMD)单指令多数据流
行程序设计。集中表现在上述几本书的作者，有的在书名中更强调了并行计算而出版了第二版，有的将内容扩充，另出版了新书[10-13]。尽管并行算法的研究历史似乎有些起伏，但一直在前进发展着，而且更面向实用。
并行算法研究的新机遇与新挑战近几年来，随着半导体器件工艺水平的提高，计算技术和通信网络的迅速发展，双CPU或4CPU的高档机已随处可见；而大学和研究所的各专业实验室中，自行用多台PC机搭建的机群系统也越来越多。随着现今并行机的普及，并行机的用户要求学习和使用并行算法也甚为迫切，这就给我们研究并行算法带来新的机遇，它将使并行算法的研究产生一个新的飞跃。与此同时，近几年来由于硬件技术的飞速发展，使得拥有成千上万个CPU的高端并行机相继研制成功。如何充分有效地利用如此巨量的CPU，成为并行算法研究面对的一个极富挑战性的问题。
当今并行算法研究的主要内容
当今并行算法主要研究内容包括并行计算模型、并行算法设计技术和并行复杂性理论等[14]。
并行计算模型并行计算模型是从不同并行计算机体系结构中抽象出来的、供并行算法设计者使用的一种抽象的并行机。任何模型均必须提供为数不多的、能反映并行机计算特性的且可以定量计算出或实际测量出的一组参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。常用的并行计算模型有共享存储的模型，包括共享存储的SIMD同步PRAM4模型和共享存储的MIMD5异步APRAM6模型；分布式存储模型，包括分布存储的MIMD大同步BSP7模型和异步LogP8模型等[15]；分布共享存储模型，包括分布存储的MIMD均匀存储层次UMH9模型和扩充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) 并行随机访存机器
5Multiple Instruction Multiple Data (MIMD) 多指令多数据流
6Asynchronous Parallel Random Access Machine (APRAM) 异步并行随机访存机器
7Bulk Synchronous Parallel (BSP) 大同步并行
8由大卫·库勒（David Culler）、理查德·卡普（Richad M. Karp）等人提出的一种并行计算模型，其特点是考虑并行机的实际参数如延迟（latency）、消息传递开销（overhead）、消息传递间隙（gap）、处理器及内存模块数目（number of processor/memory modules）等
9Uniform Memory Hierarchy
10Distributed Random Access Machine 分布式随机访存机器，h表示存储的层次数目
等都是针对待求解问题本身的特点而采用的一些有效设计方法；迭代法（Iteration ）是求解诸如线性方程组之类问题的常用数值求解方法。
并行复杂性理论 并行复杂性理论中的NC 类问题扮演着串行复杂性理论中的P 类问题的角色。如注释1所述，如果一个问题，在PRAM 模型上，使用多项式数目的处理器、在对数多项式时间内可以求解，则称此问题是NC 类的（Nick ’s Class ）。NC 类问题被认为是可并行化的，而非NC 类问题使用多项式数目的处理器是不可能在对数多项式时间内求解的。严格地讲，如果一个问题P R ∈，且P 中的每个P Q ∈的问题能用多项式数目的处理器、在对数多项式时间内可归约到R ，则称R 是P-完全的。如注释2所述，从有效并行计算的角度，P 完全问题是P 中最难的问题。类似于串行复杂性理论中是否P NP ?，尚无定论；在并行复杂性理论中是否NC P ?，目前也是不知道的。但即使一个问题是P 完全的，也可能存在着有效（未必是对数多项式时间）的并行算法求解，例如网络最大流问题是P 完全的，但存在求解的有效并行算法。
当今并行算法研究的主要方向
最近并行算法的研究更重视理论研究与试验工作互补，更强调算法的设计与实现相结合，更多地集中于应用领域中的并行算法研究上[14]。同时也出现了并行算法研究的一些新方向。
试验研究 并行算法的试验工作渗透到各个方面，包括如何采用试验的方法来分析算法的复杂性；如何利用试验手段来模拟算法的执行；如何通过试验的办法来改进算法的效率；如何使用算法运行的结果来指导并行机的设计等。
并行计算[13,17] 并行算法的设计与具体实现相结合，体现在并行算法的研究目前正向并行计算转移。而并行计算的研究一般包含并行计算机体系结构、并行算法设计、并行程序设计等三个方面的内容[13]。其中并行机体系结构从并行计算的角度主要研究高性能计算机系统的体系结构与存储模型、高速互连网络、通信操作、多级存储及其一致性等；并行算法设计重点研究并行算法的常用设计策略、基本设计技术、一般设计过程、标准性能评测等；并行程序设计主要研究并行程序设计模型、共享存储和分布存储系统的并行编程、并行程序的设计环境与工具以及科学计算可视化等。
并行应用 最近并行算法的研究更讲究实用，更多地集中在应用领域并行算法的研究上，包括计算生物学、计算化学、计算流体动力学、飞行动力学、计算机辅助设计、数据库管理、油藏建模、中长期天气预报、海洋环流和求解N-body 问题等以及面向应用的大型科学与工程问题的并行数值计算，诸如求解大型稀疏方程组、大型非线性方程和有限元分析等。
非传统计算 在交叉学科中出现了一些非传统计算方式，例如分子计算和量子计算等。这些计算本身包含着巨大的并行度，超出了传统的计算模式。分子计算中参与计算的分子数可达1020，我们可以利用大量分子的并行操作能力，以空间换时间的方式提高计算能力，从而可望解决常规计算方式难以解决的问题。量子计算依据量子相干叠加特性，从而使得基于量子位的量子计算具有强大的并行性，在原理上可以完成经典计算机不能胜任的某些计算任务。尽管1994年Shor 提出了大数分解的量子多项式时间算法[18]，但量子计算能否解决NP 完全问题，目前还是不肯定的。
存在的问题与对策
存在问题 传统定义下的并行算法的研究近几年似呈现低潮，一方面在抽象的PRAM 模型上很
多经典的非数值计算问题的并行算法都早已产生；另一方面在更实际的模型上的新算法的设计与分析又很难，更何况目前尚没有一个像PRAM模型那样普遍被采用的模型[15]。并行算法研究的另一个问题是很多理论上很优秀的并行算法只有学术价值而缺乏实用性。最后并行算法的推广应用还不够普及，同时又面临着巨量的CPU难以得到充分利用的新挑战。
建立完整的学科研究体系为了维持并行算法学科的稳定持续发展，必须建立“理论-设计-实现-应用”一套完整的并行算法学科研究体系,而不能只局限于并行算法的设计与分析单一环节的研究。在这一完整体系上的工作将使并行算法的研究得到持续发展。
形成一体化的研究方法为了使并行计算研究更实用化，必须形成“结构-算法-编程”一体化的并行算法研究方法：只有了解当代主流的并行机体系结构，才能设计出工作于其上的高效的并行算法；只有熟悉并行程序设计，才能使所设计的并行算法易于并行编程实现。
重视培养人才并行算法的研究目前已拓宽到并行计算的研究上，而并行计算的最终目的是并行应用，但推广并行应用需要一批高层次的专业人才。所以作者花了十来年的功夫编著了一套并行计算系列从书：《并行计算－结构?算法?编程》[13]、《并行算法的设计与分析》[9]、《并行计算体机系结构》[19]和《并行算法实践》[20]。这套丛书除了供广大科技人员参考外，已经被正式纳入中国科学技术大学计算机系的教学中，希望能为推动我国并行计算学科发展与应用以及培养高层次专业技术人才发挥其应有的作用。
陈国良教授，博士生导师，中国科学院院士，国家高性能计算中心（合肥）
主任，中国科技大学软件学院院长。主要研究方向包括并行计算，并行体系
结构，并行程序设计，自然计算。
参考文献
[1]S. G. Akl.“Parallel Sorting Algorithms”. San Diego, CA, Academic Press,1985
[2]M. J. Quinn. “Designing Efficient Algorithms for Parallel Computers”. McGraw-Hill Book Company,1987
[3] A. Gibbons, W. Rytter. “Efficient Parallel Algorithms”. Cambridge University Press, 1988
[4]S. G. Akl. “The Design and Analysis of Parallel Algorithm s”. Englewood Cliffs, NJ, Prentice-Hall,1989
[5]J. Jaja. “An Introduction to Parallel Algorithms”. Reading MA, Addison-Wesley,1992
[6] F. T. Leighton. “Introduction to Parallel Algorithms and Architectures: Arrays, Trees and Hypercube s”. San
Mateo,CA, Morgan Kaufmann,1992
[7]J. H. Reif, ED.“Synthesis of Parallel Algorithms”. San Mateo, CA, Morgan, Kaufmann, 1993
[8]V. Kumar, A. Gupta, etal. “Introduction to Parallel Computing: Design and Analysis of Algorithm s”.
Benjamin/Cummings Publishing Company, Inc., 1994
[9]陈国良编著. 并行算法的设计与分析. 北京,高等教育出版社，1994（第一版），2002（第二版）
[10]M. J. Quinn. “Parallel Computing: Theory and Practice (Second Edition)”. New York, NY, McGraw-Hill, 1994
[11]S. G. Akl.“Parallel Computation Models and Methods”. Englewood Cliffs, NJ, Prentice-Hall,1997
[12] A. Grama, A. Gupta, etal.“Introduction to Parallel Computing (Second Edition) ”. Benjaming/Cummings Publish
Company, Inc., China Machine Press, 2003
[13]陈国良编著. 并行算法－结构·算法·编程. 北京，高等教育出版社，1999（第一版），2003（第二版）
[14]G.E. Blelloch, B. M. Maggs.“Parallel Algorithms”. ACM Computing Surveys, 1996, V ol. 28, No.1, pp 51-54
[15]陈国良. 更实际的并行计算模型. 小型微型计算机系统，1995，V ol. 16，No. 2, PP 1-9
[16]张云泉. 面向高性能数值计算的并行计算模型DRAM（h）. 计算机学报，2003，V ol. 26，No.12，pp 1660-1670
[17]Thuy Trong Le, Tri Cao Huu. “Advances in Parallel Computing for the Year 2000 and Beyond”. Proc. of
VACETS Technical International Conference (VTIC 97), San Jose State University, July, 1997
[18]P. W. Shor. “Polynomial-time Algorithm for Prime Factorization and Discrete Logarithms on Quantum
Computer”. SIAM Journal on Computing, 1997, V ol. 26, No. 5, pp 1484-1509
[19]陈国良等编著. 并行计算机体系结构. 北京，高等教育出版社，2002
[20]陈国良等编著. 并行算法实践. 北京，高等教育出版社，2004