多线程算法分析

这一章节的内容主要是关于对分支递归的并行性分析 🥵

算法回顾，分治递归的并行性

首先我们来看递归树，可以知道深度为 $\log_{b}n$ ，并且我们可以计算出来每一层的时间复杂度为 $O(n^{\log_{b}a})$ ，所以我们可以得到总的时间复杂度为 $O(n^{\log_{b}a})$ 。上述 $T(n)=aT(\frac{n}{b})+f(n)$ ，其中 $a$ 是子问题的个数， $b$ 是每个子问题的规模， $f(n)$ 是合并子问题的时间复杂度。并且 $n^{\log_{b}a}$ 与$ a^{\log_{b}n} $是等价的，只需要对两个式子取对数即可得到（取log以b为底的对数）。

现在有一个问题：这些级别的工作量是多少？——我们要比较 $f(n)$ 与 $n^{\log_{b}a}$ 的大小：

上述符号中，Big O符号表示的是一个上界，Big $\Omega$ 符号表示的是一个下界，Big $\Theta$ 符号表示的是一个确切的界。我们可以看到，如果 $f(n)$ 与 $n^{\log_{b}a}$ 相比， $f(n)$ 的增长速度更快，那么我们就可以认为 $f(n)$ 是主导的，反之， $n^{\log_{b}a}$ 是主导的。同时，当 $f(n)$ 与 $n^{\log_{b}a}$ 相等时，该工作量为 $\Theta(n^{\log_{b}a}lg^{k+1}n)$ ，注意，这里的K是要大于等于0的。

以下是一个应用上述公式的例子：

如图所示，这里的第二个式子，k=0，符合要求，而对于第四个式子，这里的，k=-1，不符合要求。

Cilk loop parallelism

外层循环cilk

上节课关于矩阵的转置代码，我们都知道，可以通过cilk_for来实现并行性，具体cilk是怎么实现再循环中并行呢？实际上还是用的分治递归的思想：

我们可以看到，如果仅仅针对外层循环做cilk操作，那么实际上就是对i做了一个分治递归，那么我们可以绘制出这样的DAG图像：

现在问题来了，上一节课我们学习到了如何进行计算并行度，主要是两个公式：Work和Span。只不过这里不再是具体的数字，而是一个Big O符号。

上述图中的相关量计算如下：

Work： $T_1(n)=\Theta(n^2)$ （很明显，双重循环）
Span： $T_{\infty}(n)=\Theta(n+lgn)=\Theta(n)$ （这里关于循环控制的span是lgn，但是关于最大的span还是n，因为这里我只是把外层循环进行了分治，所以内部要走的最长路径仍然是n，因此关于这条最长的路径，一去一回，去是N，回来是lgn）
Parallelism： $T_1(n)/T_{\infty}(n)=\Theta(n)$ （这里的Parallelism是Work/Span，也就是说，这里的并行度是n）

双层循环cilk

如果我们对双层循环都进行cilk操作，那么现在，我们的work和span是多少呢？

其实很简单，我们可以看到，我们的work是不变的，即 $T_1(n)=\Theta(n^2)$ ，而对于span，已经发生了改变，外层循环控制是lgn，内层循环也变成了lgn，最内层叶子节点的操作变成了 $\Theta(1)$ ，所以我们可以得到 $T_{\infty}(n)=\Theta(lgn)$ ，那么我们可以得到并行度为 $\Theta(n^2/lgn)$ 。