[科普中国]-有效并行算法

简介

并行计算（parallel computing）一般是指许多指令得以同时进行的计算模式。在同时进行的前提下，可以将计算的过程分解成小部分，之后以并发方式来加以解决。2要真正实现并行计算，必须有有效并行算法。例如现在计算机中CPU都是多核，一个有效并行算法能真正利用这些CPU资源，使计算机多个方面的效率都有明显提升。有效并行算法一般有以下两种解释：1、并行计算机能够正常使用的并行算法；2、并行算法运行时并行且有效的。有效并行算法的性能度量一般是从基本指标、加速比评测、可扩放性标准这三个方面进行。

并行算法并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。总之，并行算法还需要相当多完善的地方。 并行算法与串行算法最大的不同之处在于，并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等等。

常见的非数值算法设计方法举例

并行播送与并行求和

并行排序算法；

并行选择算法：所谓选择问题就是在一给定的序列中选择出某组（个）满足给定条件的元素。

关于图论中的一些并行算法：

图论作为一门到近代才发展起来的科学。在图论中有很多关于如何设计算法的问题，比如求最小生成树，单源最短路径等等。事实上，这些算法中有很多是可以并行化的，而且并行化时运用的思想具有很大的启发性，下面是几个常见的并行图论算法。

关于串处理的并行算法：

KMP算法的并行化。

并行计算机并行处理计算机主要指以下两种类型的计算机：①能同时执行多条指令或同时处理多个数据项的单中央处理器计算机；②多处理机系统。

并行处理计算机的结构特点

随着电子器件的发展 ，计算机的处理能力有显著提高。但是，仅仅依靠器件的进展而达到的速度提高，远不能满足现代科学、技术、工程和其他许多领域对高速运算能力的需要。这就要求人们改进计算机结构，采用各种并行处理技术，以便大幅度地提高处理速度和解题能力。

并行处理计算机的结构特点主要表现在两个方面：①在单处理机内广泛采用各种并行措施；②由单处理机发展成各种不同耦合度的多处理机系统。并行处理的主要目的是提高系统的处理能力。有些类型的并行处理计算机系统（如多处理机系统）还可以提高系统的可靠性。由于器件的发展，并行处理计算机系统具有较好的性能价格比，而且还有进一步提高的趋势。

并行处理计算机的结构主要有流水线方式 、多功能部件方式 、阵列方式、多处理机方式和数据流方式。3

性能度量基本指标执行时间

工作负载

存储性能

加速比评测Amdahl定理

Gastofson定理

Sun-Ni定理

可扩放性标准等效率标准

等速度标准

平均延迟标准4