并行编程的步骤

可以把并行编程分为下图中的四个步骤：

Decmposition

把问题分解为能够并行化的任务，Amdahl定律指出，程序的串行部分制约着并行程序的加速比。

要将一张照片的每个象素的亮度翻倍、计算所有象素的平均值，由于这两部分都是可并行化的，所以加速比可以接近理想情况：

Assignment这一步是将由上一步得到的任务分配给线程，这一步的目标是平衡各线程的负载，降低线程通信的开销。

Assignment有2种方式，一种是程序员负责分配（静态），一种是由语言在运行时分配（动态），这两种方式在ISPC中均有体现：

Orchestration这一步的目标是减少线程间通信、同步的成本，保护数据的局部性。

这一步不需要程序员负责:

对一个二维矩阵进行扫描并更新，直到满足收敛条件：

红色箭头标记出了元素间的依赖关系，蓝色的线是一种划为问题的方式，每条蓝线都是对角线，每条对角线之间都不存在依赖。

改变算法，现在把矩阵各元素用红黑染色，这时红色元素的更新只依赖于黑色，更新完红色后，可以并行地更新黑色。

这里会用到锁和屏障：

上图的程序可以优化，该程序使用lock来保护变量diff同一时刻只被一个线程访问。这里的优化思路是：不再维护一个全局的diff，各个进程拥有各自的myDiff，最后相加得到diff。

还可以注意到共享空间程序中有三个barrier来同步线程，这里也可以优化，每个线程的局部变量myDiff都被累加到全局变量diff[index]中，之后如果还要继续while循环，index会被+1，这样下一轮的diff[index]就不会依赖这一轮。