算法导论26.1 Exercises 答案

发表于 分类于 阅读次数： 本文字数： 4.2k 阅读时长 ≈ 4 分钟

26.1-1

一个串行算法的运行轨迹是看起来是一个单链表。相比于图26.2和图26.4所展示的运行轨迹，每个节点最多只有一条入边和一条出边。

26.1-2

相比于原来，现在P-FIB变成了P-FIB'，如下：

1
2
3
4
5
6
7
8
P-FIB'(n)
  if n <= 1
    return n
  else 
    x = spawn P-FIB'(n − 1)
    y = spawn P-FIB'(n − 2)
    sync
    return x + y

与原来的区别在于，父线程一进入else就被挂起，并且产生了两个子线程来求解P-FIB'(n − 1)和P-FIB'(n − 2)，父线程会一直等待，直到这两个线程完成执行，最终才返回计算结果。

因此，除了增加了一些线程本身的空间占用，这种做法并不会产生任何的改进，因此其渐进工作量\(T_1'\)仍然为\(\Theta(\phi^n)\)，其持续时间仍然是\(T_{\infty}'=\Theta(n)\)，并行度为\(T_1'/T_{\infty}'=\Theta(\phi^n/n)\)。

26.1-3

如下图所示，为P-FIB(5)的计算有向无环图。可见，图中有\(29\)个节点，因此其工作量为\(29\)。此外，粗线表示这个有向无环图的最长链，其一共有\(10\)个节点，因此其持续时间为\(10\)，最终我们得到并行度为\(2.9\)。

26.1-4

假设这些时间步中，一共有\(x\)个非完全步，一共有\(y\)个完全步。那么必定有\(y\le\lfloor(T_1 - x)/P\rfloor\)。我们通过反证法来证明这个不等式是成立的。

由于每个非完全步至少有\(1\)的工作量，因此至多只有\(T_1-x\)的工作量在完全步完成，也就是说，有\(Py\le T_1-x\)。假设\(y>\lfloor(T_1 - x)/P\rfloor\)，那么有

\(\begin{aligned} Py&\ge P\cdot(\lfloor(T_1 - x)/P\rfloor+1)\\ &=P\cdot\lfloor(T_1 - x)/P\rfloor+P\\ &=P\cdot\left(\dfrac{T_1-x}{P}-((T_1-x)\bmod P)\right) + P\\ &=T_1-x+P-((T_1-x)\bmod P)\\ &>T_1-x \end{aligned}\)

这和\(Py\le T_1-x\)矛盾，因此有\(y\le\lfloor(T_1 - x)/P\rfloor\)。

那么有\(T_p=x+y\le x+\lfloor(T_1 - x)/P\rfloor\)。由于\(x\le T_\infty\)，即\(x\)是所有时间步的一个子集，因此有

\(\begin{aligned} T_p&\le x+\lfloor(T_1 - x)/P\rfloor\\ &\le x+(T_1 - x)/P\\ &\le T_\infty+(T_1 - T_\infty)/P\\ \end{aligned}\)

原结论成立。

26.1-5

假设现在有\(k\)个处理器，\(k+1\)个任务，其中每个串行任务内部一共有\(m\)个节点。那么左图是贪心调度器的一种调度，接下来的\(m\)个时间步它先完成\(k\)个任务的串行节点，然后再花费\(m\)个时间步进行剩下的那一个任务，在这种调度下，花费了\(2m+2\)个时间步完成整个程序的运行（注意，这里加上了开始和结束的时间步）。如左图所示。

另一种调度则是，每次优先选择剩余时间最长的\(k\)个任务运行一个时间步，直到完成所有任务为止。因此，这个过程总共需要\(\left\lceil\dfrac{(k+1)m}{k}\right\rceil+2=\left\lceil m+\dfrac{m}{k}\right\rceil+2\)个时间步进行。如右图所示。

因此，有\(\displaystyle{\lim_{k\rightarrow +\infty}(2m+2)/\left(\left\lceil m+\dfrac{m}{k}\right\rceil+2\right)=2}\)，这时第一种调度所花费的时间步是第二种调度的接近\(2\)倍。

26.1-6

根据工作量定律，有\(T_1\le \min\{4\cdot T_4,10\cdot T_{10},64\cdot T_{64}\}\)，从而得到\(T_1\le 320\)。

根据持续时间定理，有\(T_\infty\le \min\{T_4,T_{10},T_{64}\}\)，从而得到\(T_\infty\le 10\)。

对\(T_{10}\)对应的情况应用不等式26.5，那么有

\(\begin{aligned} T_{10}&\le \dfrac{T_1-T_\infty}{10}+T_\infty\\ &\le \dfrac{T_1+9T_\infty}{10}\\ &\le 32+\dfrac{9T_\infty}{10} \end{aligned}\)

从而得到\(T_\infty>\dfrac{100}{9}\)，这和给出的\(T_{\infty}\le 10\)是矛盾的，因此这个教授是在撒谎。

26.1-7

可以将提供的P-MAT-VEC-RECURSIVE进行改造后，得到如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
P-MAT-VEC-RECURSIVE-AUX'(A, x, n, i, j, j')
  if j == j'
    return a_{i, j} * x_j
  else
    mid = ⌊(j + j') / 2⌋
    l = spawn P-MAT-VEC-RECURSIVE-AUX'(A, x, n, i, j, mid)
    r = P-MAT-VEC-RECURSIVE-AUX'(A, x, n, i, mid + 1, j')
    sync
    return l + r

P-MAT-VEC-RECURSIVE'(A, x, y, n)
  parallel for i = 1 to n
    y_i = P-MAT-VEC-RECURSIVE-AUX'(A, x, n, i, 1, n)

其基本思想在于，对于\(A\)的每一行都和\(x\)独立相乘，得到一个值。然后，先计算这一行左半部分和\(x\)的左半部分点积；右半部分和\(x\)的左半部分点并行进行计算，最终将结果合并。

因此，P-MAT-VEC-RECURSIVE'的工作量为\(T_1(n)=\Theta(n^2)\)，因为它仍然运行了\(n^2\)次乘法运算。

P-MAT-VEC-RECURSIVE'的持续时间\(T_{\infty}(n)\)如下计算。由于P-MAT-VEC-RECURSIVE'中的每次循环都是独立的，因此令\(iter_{\infty}(n,i)\)表示第\(i\)次的循环结果，我们可以得到：

\[T_{\infty}(n)=\Theta(\lg n)+\max\{iter_{\infty}(n,i):1\le i\le n\}\]

对于每一次P-MAT-VEC-RECURSIVE-AUX'的调用，我们可以发现，每一次调用都将求和的范围减小，因此有\(iter_{\infty}(n,i)=iter_{\infty}(n/2,i)+\Theta(1)\)。根据主定理，可以得到：

\[iter_{\infty}(n,i)=\Theta(\lg n)+\Theta(\lg n)\]

因此，我们最终得到\(T_{\infty}(n)=\Theta(\lg n)+\Theta(\lg n)=\Theta(\lg n)\)。

最终我们得到这个算法的并行度为\(T_1(n)/T_\infty(n)=\Theta(n^2/\lg n)\)。

26.1-8

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

接下来求解持续时间\(T_{\infty}(n)\)。令\(iter_1(j)(2\le j\le n)\)表示其外层循环所需要的时间，\(iter_2(i)(1\le j< n)\)表示其内层循环所需要的时间。

如果将内层for循环的parallel关键字转化为spawn ... sync结构后，那么可以得知\(iter_1(i)=\Theta(\lg i)+\max\{iter_2(j):1\le j<i\}\)。可以知道，由于\(iter_2(j)=\Theta(1)\)，因此有\(iter_1(i)=\Theta(\lg i)+\Theta(1)=\Theta(\lg i)\)。

再将外层for循环的parallel关键字转化为spawn ... sync结构后，那么可以得知\(T_{\infty}(n)=\Theta(\lg n)+\max\{iter_1(i):2\le j\le n\}=\Theta(\lg n)+\Theta(\lg n)\)。从而得到\(T_{\infty}(n)=\Theta(\lg n)\)。

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

26.1-9

也就是说，现在的程序转化为P-TRANSPOSE'，即：

1
2
3
4
P-TRANSPOSE(A, n)
  parallel for j = 2 to n
    for i = 1 to j − 1
      exchange a_{ij} with a_{ji}

工作量和题目28.1-8的情况一样，为\(T_1(n)=\Theta(n^2)\)。

接下来求解持续时间\(T_{\infty}(n)\)。令\(iter(j)(2\le j\le n)\)表示其外层循环所需要的时间，由内层循环可以知道，\(iter(j)=\Theta(j)\)。将外层for循环的parallel关键字转化为spawn ... sync结构后，那么可以得知\(T_{\infty}(n)=\Theta(\lg n)+\max\{iter(i):2\le j\le n\}=\Theta(\lg n)+\Theta(n)\)。因此，我们最终得到\(T_{\infty}(n)=\Theta(\lg n)+\Theta(n)=\Theta(n)\)。

因此并行度为\(T_1(n)/T_{\infty}(n)=\Theta(n^2/n)=\Theta(n)\)。

26.1-10

相当于解如下关于未知数\(P,T_P,T_P'\)的方程组：

\[\left \{\begin{aligned} &T_P=\dfrac{T_1}{P}+T_\infty\\ &T_P'=\dfrac{T_1'}{P}+T_\infty'\\ &T_P=T_P'\\ \end{aligned}\right.\]

其中\(T_1=2048,T_{\infty}=1,T_1'=1024,T_{\infty}'=8\)，最终得到解：

\[\left \{\begin{aligned} &P=\dfrac{1024}{7}\\ &T_P=15\\ &T_P'=15\\ \end{aligned}\right.\]

也就是说，只需要约\(146\)或者\(147\)个处理器就能使这两个版本的算法运行时间相同。