[科普中国]-可扩展并行处理

并行处理（Parallel Processing）是计算机系统中能同时执行两个或多个处理机的一种计算方法。可扩展并行处理是指并行计算性能随着问题规模和并行处理系统规模的增加而提升。可扩展并行处理是设计并行算法和高性能并行机所追求的一个重要目标，即缩短计算时间（计算复杂性）。

简介对于并行处理系统来说，可扩展并行处理可以从以下几点来解释：对于体系结构来说，就是在确定的应用背景下，随着处理机数目的增加，计算机系统的性能能相应提高；对于并行算法来说，就是它能处理的问题规模随处理机数目的增长呈比例增长；对于并行算法和并行机组合体来说，就是当问题规模增长时，适当增加处理机数目，该组合体能够获得某种指定的性能。

可扩展性可扩展性是随着问题规模和计算资源的增加，对算法执行时间的一种定量描述，或指某个算法在某个机器上的可扩放性反映该算法是否能有效利用不断增加的CPU。研究可扩展性的目的就是要使算法尽可能的利用最多的处理器，并且也可以预测当某个算法移植到大规模处理机上后的运行效果（即问题规模扩大时对处理器的利用情况）。一个好的可扩展度量方法可以反映算法和机器组合体匹配程度的信息，也可以预测并行系统的性能。可扩展性度量方法的基本要求有：它必须提供系统规模如何影响性能的信息；它必须是描述并行算法与机器组合的函数。这是因为系统规模增加了，并行开销也会增加，使得性能降低。引起性能降低的原因在于算法与机器两个方面，如算法中负载不平衡、处理机通信费用增加等；它是可评估的、可比较的、定量的性能度量。为了尽可能最优地匹配实际的并行体系结构，通常采用与体系结构相结合的算法设计。相同的算法在不同体系结构上的性能是不同的。因此，在可扩展性研究方面，通常研究的是这两者相结合的可扩展性1。

计算复杂性对于同一个问题往往可以用许多算法求解。由于各种算法对同一个问题都有可能求出最优解，怎样衡量一个算法的效率怎样判定一个问题是否可计算，如果这个问题可计算，则该问题的难易程度如何，都涉及到计算复杂性理论的有关知识。计算复杂性理论是用于研究算法有效性和问题难度的一种工具，是提高问题的计算效率的前提条件。一个算法复杂性的高低体现为运行该算法所需要的计算机资源即时间和空间资源的多少上。所需的资源越多，说明该算法的复杂性越高所需的资源越少，该算法的复杂性便越低。一般来说，一个问题的复杂度可以用计算该问题所耗费的时间和空间资源的多少来衡量，亦即算法的时间复杂度和空间复杂度。我们可以定义一个以数据量如问题的规模大小为输入，时间或空间占据量为输出的函数，用来度量算法的时间或空间复杂度。其形式的定义可以用图灵机的计算模型描述。

并行算法并行计算（parallel computing）一般是指许多指令得以同时进行的计算模式。在同时进行的前提下，可以将计算的过程分解成小部分，之后以并发方式来加以解决。计算机软件可以被分成数个运算步骤来运行。为了解决某个特定问题，软件采用某个算法，以一连串指令运行来完成。传统上，这些指令都被送至单一的中央处理器，以循序方式运行完成。在这种处理方式下，单一时间中，只有单一指令被运行(processor level: 比较微处理器，CISC, 和RISC，即流水线Pipeline的概念，以及后来在Pipeline基础上以提高指令处理效率为目的的硬件及软件发展，比如branch-prediction, 比如forwarding，比如在每个运算单元前的指令堆栈，汇编程序员对programm code的顺序改写)。并行运算采用了多个运算单元，同时运行，以解决问题。

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

并行处理系统并行处理系统是利用多个功能部件或多个处理机同时工作来提高系统性能或可靠性的计算机系统。任何一个计算机系统都包含某种程度的并行性，但如果只具有硬件基本操作的并行性，如一个数据的所有位同时传送，许多门电路同时工作等，不能认为是并行处理系统。并行处理系统至少应包含指令级或指令级以上的并行。

并行处理系统可以在4个级别上实现并行处理：指令内部、指令之间、任务或过程之间和作业或程序之间。采用多个功能单元并行实现一条指令中的不同操作属于指令内部并行，超长指令字( VLIW) 计算机是实现指令内部并行的典型例子。同一时间执行两条以上指令称为指令间并行，超标量计算机中有多条指令流水线，这是指令间并行的实例。一个程序往往可以分解成多个任务、子程序或过程，同一程序内多个任务或过程可以在一个系统的不同处理机中同时运行，以缩短计算时间，称为任务级并行。多个作业或大型计算问题的多个独立的程序，在并行处理系统的不同的处理机或计算机中同时运行，以提高系统的吞吐量或有效地利用系统资源，称为作业级并行。并行处理系统的研究与发展涉及计算理论、算法、计算机体系结构、硬件、软件 (包括操作系统、编译、编程环境与程序语言等)以及性能评价等方面。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学