设计并行算法的思路(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

$S_{p} =\frac{W}{T_{p}}$

2 时间复杂度的下界

$T_{p} \geq \frac{W}{p}, \ \ T_{p} \geq D \rarr T_{p} \geq \max\{ \frac{W}{p}, D \}$ 其中 p 是处理器的数量，D是上面提到的 span

3 时间复杂度的上界

image

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

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

$W_{i}$ 代表每一个phase里面的work数目。 $T_{i} = \lceil \frac{W_{i}}{p}\rceil$ 。 $T_{D} = \sum ^{D}_{i=1}\ \lceil \frac{W_{i}}{p}\rceil =T_{D} = \sum ^{D}_{i=1}\ \lfloor \frac{W_{i} - 1}{p}\rfloor + 1$

这里有由 ceilling 的转化公式 $\lceil \frac{a}{b}\rceil = \lfloor \frac{a-1}{b}\rfloor + 1$ 转化而得。

$\sum ^{D}_{i=1}\ \lfloor \frac{W_{i} - 1}{p}\rfloor + 1 \leq \sum ^{D}_{i=1}\ \frac{W_{i} - 1}{p} + 1 = \frac{W-D}{p} + D$

其实直观的理解这个就是阿达姆法则 $\frac{W-D}{p}$ 是可并行化的部分而 $D$ 是不可并行化的。

所以增速 $speed \geq \frac{W_{1}}{\frac{W-D}{p} + D } = \frac{p}{\frac{W-D + pD}{W_{1}}} \$

$= \frac{p}{\frac{W}{W_{1}}+\frac{p-1}{W_{1}/D}}$

if $W= W_1$ （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.

需要遵循两条原则