并行编程的步骤
可以把并行编程分为下图中的四个步骤:
Decmposition
把问题分解为能够并行化的任务,Amdahl定律指出,程序的串行部分制约着并行程序的加速比。
要将一张照片的每个象素的亮度翻倍、计算所有象素的平均值,由于这两部分都是可并行化的,所以加速比可以接近理想情况:
Assignment
Assignment这一步是将由上一步得到的任务分配给线程,这一步的目标是平衡各线程的负载,降低线程通信的开销。
Assignment有2种方式,一种是程序员负责分配(静态),一种是由语言在运行时分配(动态),这两种方式在ISPC中均有体现:
Orchestration
Orchestration这一步的目标是减少线程间通信、同步的成本,保护数据的局部性。
Mapping to hardware
这一步不需要程序员负责:
并行程序实例
对一个二维矩阵进行扫描并更新,直到满足收敛条件:
红色箭头标记出了元素间的依赖关系,蓝色的线是一种划为问题的方式,每条蓝线都是对角线,每条对角线之间都不存在依赖。
改变算法,现在把矩阵各元素用红黑染色,这时红色元素的更新只依赖于黑色,更新完红色后,可以并行地更新黑色。
数据并行程序
共享空间程序
这里会用到锁和屏障:
上图的程序可以优化,该程序使用lock来保护变量diff
同一时刻只被一个线程访问。这里的优化思路是:不再维护一个全局的diff
,各个进程拥有各自的myDiff
,最后相加得到diff
。
还可以注意到共享空间程序中有三个barrier来同步线程,这里也可以优化,每个线程的局部变量myDiff
都被累加到全局变量diff[index]
中,之后如果还要继续while
循环,index
会被+1
,这样下一轮的diff[index]
就不会依赖这一轮。