算法导论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)\)。

因此并行度为\(T_1(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)\)。

如果假设\(iter_n(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))\)。

因此并行度为\(T_1(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\{iter_n(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)\)。

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