算法导论26.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

26.2-1

使用P-MATRIX-MULTIPLY计算$2\times 2$矩阵的轨迹如下图所示：

可见，图中有$13$个节点，因此其工作量为$13$。此外，粗线表示这个有向无环图的最长链，其一共有$6$个节点，因此其持续时间为$6$，最终我们得到并行度为$\dfrac{13}{6}$。

26.2-2

使用P-MATRIX-MULTIPLY-RECURSIVE计算$2\times 2$矩阵的轨迹如下图所示：

可见，图中有$42$个节点，因此其工作量为$42$。此外，粗线表示这个有向无环图的最长链，其一共有$23$个节点，因此其持续时间为$23$，最终我们得到并行度为$\dfrac{42}{23}$。

26.2-3

对P-MATRIX-MULTIPLY修改后，由P-MATRIX-MULTIPLY'给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
P-MATRIX-MULTIPLY-AUX'(A, B, i, j, k, k')
  if k == k'
    return a_{ik} * b_{kj}
  else
    mid = ⌊(k + k') / 2⌋
    l = spawn P-MATRIX-MULTIPLY-AUX'(A, B, i, j, k, mid)
    r = P-MATRIX-MULTIPLY-AUX'(A, B, i, j, mid, k')
    sync
    return l + r

P-MATRIX-MULTIPLY'(A, B, C, n)
  parallel for i = 1 to n
    parallel for j = 1 to n
      C_{ij} = P-MATRIX-MULTIPLY-AUX'(A, B, i, j, 1, n)

可以知道其工作量为$T_1(n)=\Theta(n^3)$。

对程序P-MATRIX-MULTIPLY-AUX'的分析和对题目26.1-7中对P-MAT-VEC-RECURSIVE-AUX'的分析完全一致。因此，假设$iter_n(i,j)$表示外层循环为$i$，内层循环为$j$时的运行时间，那么有$iter_n(i,j)=O(\lg n)$。

由于P-MATRIX-MULTIPLY'首先沿着parallel for循环$i$的递归树的路径向下，然后沿着内层循环parallel for循环$j$的递归树的路径向下，因此这个算法的持续时间为$T_{\infty}(n)=\Theta(\lg n)+\Theta(\lg n)+\max{iter_n(i,j):1\le i,j\le n}=\Theta(\lg n)$。

因此并行度为$T1(n)/T{\infty}(n)=\Theta(n^3/\lg n)$。

26.2-4

考虑对题目26.2-3的代码P-MATRIX-MULTIPLY'进行修改，最终由P-MATRIX-MULTIPLY''给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
P-MATRIX-MULTIPLY-AUX''(A, B, i, j, k, k')
  if k == k'
    return a_{ik} * b_{kj}
  else
    mid = ⌊(k + k') / 2⌋
    l = spawn P-MATRIX-MULTIPLY-AUX'(A, B, i, j, k, mid)
    r = P-MATRIX-MULTIPLY-AUX'(A, B, i, j, mid, k')
    sync
    return l + r

P-MATRIX-MULTIPLY''(A, B, C, p, q, r)
  parallel for i = 1 to p
    parallel for j = 1 to r
      C_{ij} = P-MATRIX-MULTIPLY-AUX'(A, B, i, j, 1, q)

使用和题目26.2-3一样的分析方式，我们可以知道这个算法的工作量为$T_1(n)=\Theta(pqr)$。

如果假设$itern(i,j)$表示外层循环为$i$，内层循环为$j$时的运行时间，那么有$iter_n(i,j)=O(\lg q)$。那么这个算法的持续时间为$T{\infty}(n)=\Theta(\lg p)+\Theta(\lg r)+\max{iter_n(i,j):1\le i\le p,1\le j\le r}=\Theta(\lg (pqr))$。

因此并行度为$T1(n)/T{\infty}(n)=\Theta(pqr/\lg (pqr))$。

26.2-5

修改后的可并行化的Floyd-Warshall算法由P-FLOYD-WARSHALL'给出（使用题目23.2-4的Floyd-Warshall算法伪代码FLOYD-WARSHALL'进行修改）：

1
2
3
4
5
6
7
P-FLOYD-WARSHALL'(W, n)
  D = W
  for k = 1 to n
    parallel for i = 1 to n
      parallel for j = 1 to n
        d_{ij} = min {d_{ij}, d_{ik} + d_{kj} }
6 return D

首先说明一下这样修改的正确性。可见，在第$k$轮循环中，P-FLOYD-WARSHALL'的第5行只会使用$D$的第$k$行和第$k$列中的元素进行读取，并对其它元素进行修改。由于原来的图是一个非负边权的图，因此哪怕对$d{ik},d{kj}$这样的元素进行更新，也不会对原本的值进行改变。因此。这个算法通过如此并行化完成是正确的。

这个程序的串行投影需要花费$\Theta(n^3)$的时间完成，因此其工作量为$T_1(n)=\Theta(n^3)$。

接下来求解持续时间$T{\infty}(n)$。假设$iter_n(i,j)$表示外层parallel for循环为$i$，内层parallel for循环为$j$时的运行时间，那么有$iter_n(i,j)=O(1)$，因为接下来只有一个较小值更新操作和加法操作。将两层循环中的parallel关键字转化为spawn ... sync结构后，那么可以得知$T{\infty}(n)=\Theta(\lg n)+\Theta(\lg n)+\max{itern(i,j):1\le i,j\le n}=\Theta(\lg n)$。由于这个两层parallel for循环需要串行地执行$k$次，因此我们可以求出$T{\infty}(n)=n\cdot \Theta(\lg n)=\Theta(n\lg n)$。

最终并行度为$T1(n)/T{\infty}(n)=\Theta(n^3/(n\lg n))=\Theta(n^2/\lg n)$。