设计并行算法的思路(1)

1. 模型抽象

一般来说如果一个问题可以被抽象为一个 DAG(有向无环图)那么这个问题都可以用来并行计算。常见问题可以抽象下面两种模型。

1） for 循环的展开。

for(int i = 0 ; i < N ; i++)
  work(i);

这种问题可以分解为 N 个问让 p 个 cpu 同时计算。

2）divide and conquer, 分治算法。

int work(int start, int end){
  if(end -  start  < N){
    //do some thing
  }
  work(start, (star+end) / 2 );
  work((star+end) / 2+1, end );
}

通过divide 的方式将问题划归为一列不相关的子问题，这些子问题可以同时被顺序解决。这样也提高了工作效率。常见的例子为，快速排序和归并排序。

2. 问题分析

对于样的模型，我们如何对它们进行量化分析呢？在这里需要定义两个指标 work 与 span。

Work 是在顺序执行的情况下的总计算复杂度。也就是我们常说的计算复杂度。

Depth(span) 是指每个处理器被分配的任务。通常情况下是一个 DAG 图中最长的路径(如如图中的黄色的路径)。

image

几条定律

在分析时间复杂度的时候，我们暂时抛开内存和通信上面的开销。

1 speed up

2 时间复杂度的下界

其中 p 是处理器的数量，D是上面提到的 span

3 时间复杂度的上界

image

为了证明上界，我们讲将整个 DGA 图转换为上图的的模式。可以分割为一个个的 phase（图中的黄色分割线），中间的蓝色点就是 critical path，也就是我们之前讲的 D 。这个新的图有如下性质：

1. 每一个critical 路径上的一个节点就是一个 phase。
2. 同一层上左右两边的非关键路径上的node代表一组task，他们之间没有相互依赖。
3. DAG 图中的每一个点都会出现在一个 phase中。

代表每一个phase里面的work数目。 。

这里有由 ceilling 的转化公式 转化而得。

其实直观的理解这个就是阿达姆法则 是可并行化的部分而 是不可并行化的。

所以增速

1. if （work optimality）串行与并行的work是一样的。

3. 设计并行算法

那么为了设计并行算法要实现的目标是 Work 与 span 都要小。

Work efficiency: A parallel algorithm is work efficient if it performs asymptotically the same work as the best known sequential algorithm for that problem.

需要遵循两条原则

1. work optimality: w = w1 = O(n) if possible
2. low span,

对于 divide and conquer 的问题的理论上最优是

对于 for 循环