串行算法并行化
并行计算，是将一个计算任务分摊到多个处理器上并同时运行的计算方法。由于单个CPU 的运行速度难以显著提高，所以计算机制造商试图将多个CPU 联合起来使用。在巨型计算机上早已采用专用的多处理器设计，多台计算机通过网络互联而组成的并行工作站也在专业领域被广泛使用。台式机和笔记本电脑现在也已广泛地采用了双核或多核CPU。双核CPU 从外部看起来是一个CPU，但是内部有两个运算核心，它们可以独立进行计算工作。在同时处理多个任务的时候，多核处理器可以自然地将不同的任务分配给不同的核心。但只运行一个以常规的串行代码写成的程序时，如何将计算任务拆分成多个部分并分解到多个核心上同时运行，是很困难的事情。有时甚至需要人工来读懂原来代码的含义，并以适合并行计算的语言重写程序。这需要耗费大量的人力物力。最容易被并行化的计算任务称为“易并行”1的，它可以直观地立即分解成为多个独立的部分，并同时执行计算。例如将一个数组里的所有元素求和。我们可以先将数组分成两段，对每段各自求和，最后再把结果相加。如果两段的大小划分得当，我们可以让双核CPU 的每个核心的运算量相当，在数组规模很大时，总的运算速度比单核CPU 能提高接近一倍。但并不是所有程序都能够分解成这种效果。在软件行业中很自然地提出这个问题：希望设计一种方法，能够将一个常规的串行程序分解成两个部分，使之能够在CPU 的两个核心上并行运算，并且希望能够尽量发挥双核心的计算能力。一般来说，如果两个核心的运算量
//1有时也称作“自然并行”。
//1基本相当，那么总的运算效率较高2。如果出现某个核心空闲等待的状态，双核CPU 的运算力就没有被充分的利用起来。