并行算法概要

4.1.1　并行算法概要

20世纪70年代初，各国计算机科学家逐渐认识到，在“计算机硬件技术进步速度的远跟不上软件技术进步的发展与需要速度”的阶段性强约束条件下，传统计算机的串行结构是阻碍其运算速度进一步提高的关键因素，必须另行寻找可大幅提高电脑计算速度的新路。以此为开端，世界各国开始了旨在超越串行算法（Serial Algorithm）计算速度极限的并行算法（Parallel Algorithm）的探索与研究。

21世纪以来，以并行计算（含并行系统、网格计算等）为核心的高性能计算，已经成为一个引人入胜、意义重大、影响深远的计算机科学的高技术研究领域。人们越来越认同，并行计算的根本出路和发展前景绝不仅仅在于并行机硬件系统的研制，而应在很大程度上倚重于并行算法的研究、设计与实现。随着资源信息化、经济知识化、全球网络化的迅猛发展，当今计算机技术与通信技术正在使能把遍布各地、幅域广袤、方便快捷的网络资源组合、联合、综合、整合为一体的分布式计算，并成为越来越值得高度重视的并行计算研究与发展的高性能计算新领域。

并行算法（包括其程序）设计方法，不同于传统的串行算法设计方法，其主要区别在于对计算机解决问题采取何种看法。早期的非结构化算法设计方法、中期的结构化算法设计方法，都把所处理事务的变化发展看成是单线程的，任何两种事务之间必然存在因果关系，从而把一系列相关事务看成是一个不可分割的串行整体；中后期的对象化算法设计，把一个所处理的复杂事务分解成多个简单事务，或者把一个所设计的系统看成是多个相互联系的实体构成。后者对事务（或系统，下同，略）联系本质特征的新理念，是对前两者就事务认识的突破性历史进展，尽管它仍只是对事务结构的静态分拆，而尚未涉及事务行为的动态分解。从事务行为上来看，无论是非结构化、结构化，还是对象化的算法设计方法，其共同的本质局限性都是串行，因为它们都把所处理的事务看成是一致串接的，或者是先后相继的，相互之间不存在并发干扰现象，更不会有可同时发生且相互作用的事务行为。

并行算法设计方法的最基本观点，就是把一个事务的行为看成是多个事务互相作用的结果。这是对串行算法设计方法的事务认识的根本性观念创新与转变飞跃。根据这个创新观点，并行算法设计方法的核心内容就是并行划分与算法映射。其理论基础是并行计算模型。并行计算模型决定了并行语义，并行语义决定了可并行执行的准则，从而决定了并行划分的原则。

定义4.1　并行算法，是一些同时执行、相互作用、彼此协调、目标统一、协同一致地完成给定问题求解的多个进程的集合。

定义4.2　采用同步方式（指算法的诸进程的执行必须相互等待）、异步方式（指算法的诸进程的执行不必相互等待）、分布方式（指由通信链路连接的多个场点size或节点node来协同完成问题求解）进行并行处理的并行算法，分别称为同步并行算法（Synchronized Algorithm）、异步并行算法（Asynchronized Algorithm）、分布并行算法（Distributed Algorithm）。