并行算法范例及其设计模型

并行程序设计不同于顺序程序设计，主要在于对问题采取何种看法。顺序程序设计是把事物的变化发展看成单线程的，按先后顺序发展。并行程序设计是把一个事物的行为看成多个事物互相作用的结果，多个事物可以并行发展。这是一个观念上的根本转变，根据这个观点，并行程序设计的核心内容就是并行划分与算法映射。要研究并行程序设计，就需要了解并行算法的结构和设计模型。

由于并行算法设计的不同，可能对程序的执行效率有很大的影响，不同的算法产生几倍、几十倍甚至上百倍性能差异也是完全有可能的。并行算法范例是指构造算法方法以使其能在并行机系统上运行。最常见的并行算法范例有如下4类。

阶段并行：并行程序由一些超步组成，每一超步分为两阶段。在计算阶段，多个进程中的每一个都完成一个独立计算。此后是交互阶段，在这一阶段，这些进程完成一个或多个同步交互操作。

分而治之：父进程将其工作负载分成若干个较小的子块，并将它们分派给一些子进程。这些子进程并行地计算它们的工作负载，所产生的结果由父进程进行合并。分割和合并以递归方式进行。(www.xing528.com)

进程农庄：主进程执行并行程序中基本的顺序部分，并派生出一些从进程去执行并行的工作负载。当一个从进程完成其工作时通知主进程，让其分派一个新的工作负载，由主进程完成协调 工作。

工作池：工作池以全局数据结构方式实现，将创建一些进程。开始时，池中只有一件工作，空闲进程可从池中获取一件工作并加以执行，执行后可能产生新的多个工作件并将顺承地放入工作池中。当工作池为空时，并行程序结束。