Introduction to Algorithm-08-Parallel

在现在的计算机中，多核处理器使用的是共享存储器架构。并行计算的目标是将计算任务分解为多个子任务，并在多个处理器上同时执行这些子任务，以提高计算效率。

动态多线程：在动态多线程中，处理器可以根据需要动态地分配任务。这种方法可以更好地利用处理器资源，但也可能导致任务之间的依赖关系和竞争条件。

多线程模型具有如下几个重要的优点：它是串行编程模型的一个简单扩展。通过在伪代码中加入三个”并发“关键词 (parallel 、 spawn 和 sync) 来描述一个多线程算法。此外，如果从多线程伪代码中删除这些并

Fork-join Parallelism

在计算斐波那契数列中，我们可以使用分治法来实现并行计算。具体来说，我们可以将计算任务分解为两个子任务：计算 fib(n-1) 和 fib(n-2)，然后在不同的线程中并行执行这两个子任务。

在上面的算法中，即使是理想无穷多核心的计算机，仍然不能在常数时间内完成完成计算。绘制出上面的并行计算的计算题，求出对应的关键路径

上面的斐波那契数的计算是一个线性时间的时间的计算

$$T_{\infty}(n) = T_{\infty}(n-1) + O(1)$$

Definition

• 多线程计算的工作量是指在一个处理器上执行整个计算的总时间。换句话说，工作量就是每个链消耗时间的总和。如果计算有向无环图中的每个链耗费单位时间，那么工作量正是图中的顶点数
• work law: $T_p\geq \frac{T_1}{P}$
  • 使用P个处理器的工作量至少需要$T_1/P$的时间
• span law: $T_p \geq T_{\infty}$
• speed up:（加速比） $\frac{T_1}{T_p}$
• Linear Speedup: $\frac{T_1}{T_p} = \Theta(P)$
• perfect linear speedup: $\frac{T_1}{T_p} = P$
• parallelism（并行度）： $\frac{T_1}{T_{\infty}}$
  • 作为一个比值，并行度表示沿着关键路径每一步可被并行执行的平均合计工作扯。作为一个上界，并行度给出了最大的可能加速比，这是在任何数目的处理器上所能达到的。最后，也许是最重要的，并行度给出了获得完美线性加速的一个限制。
  • 一般而言处理器数目超过并行数时，无法获得完美线性加速。
• 松弛度（relaxation）： $\frac{T_1}{ P T_{\infty}}$
  • 如果松弛度小于1，就得不到完美线性加速。
  • 接近0时，越来越偏离完美线性加速

Scheduling

在并行计算中，调度是一个重要的概念。调度的目标是将计算任务分配到多个处理器上，以最大化并行度和效率。

Greedy Scheduling：贪心调度是一种简单的调度策略，它在每个时间步选择当前可用的任务，并将其分配给空闲的处理器。贪心调度的优点是简单易实现，但可能无法达到最优的并行度。

Complete Step : 是指并行程序执行过程中，所有可运行任务都被分配到处理器并同时执行的一次时间步。即所有的核心都在工作的一个时间步。
Incomplete Step : 是指并行程序执行过程中，并非所有可运行任务都被分配到处理器并同时执行的一次时间步。即有些核心没有工作。

Multiplying Matrix by and vector

在计算一个矩阵和向量的乘法中，我们可以使用并行计算来加速这个过程。具体来说，我们可以将矩阵的每一行与向量进行乘法运算，并行地计算出结果。

在上面的算法中，实际执行时使用的是分治算法来执行的，将所有的任务分发给不同的处理器使用的时间为$O(\lg n)$。在分发之后在处理器上执行基本任务需要的时间为$O(n)$，
注意，最后的基本操作是同时进行的。算法的复杂度为$O(n) + O(\lg n) = O(n)$
上面代码中第7行的同步是必须的，否则，可能其中某一个函数运行结束后就会提前返回，导致结果不正确。

计算并行度为$\frac{\Theta(n^2)}{\Theta(n)} = \Theta(n)$

Race conditions

当两个逻辑上并行的运算在相同的内存中写数据时可能发生，

在上面的算法的最后一行如果也使用并行则会产生运行冲突

Parallel Matrix Multiplication

可以直接使用矩阵乘法的计算方式进行计算。即将行列乘法并行计算。

时间复杂度分析得到并行算法的无穷核心时间复杂度分析为

Divide-and-conquer

将矩阵计算分解为8个子问题，这些计算是可以并行计算的，然后再进行相加。

初始化时间开销为$O(\lg n) + O(\lg n)$

Parallel merge sort

在并行归并排序中，我们可以将数组分成多个子数组，然后对每个子数组进行排序，最后将排序后的子数组合并起来。

使用标准的合并算法得到的并行度为$\frac{T_1}{T_{\infty}} = \Theta(\lg n)$

考虑使用并行的合并算法：

对于两个有序数组，可以将其中一个数组的中点作为划分点，并且在第二个数组中使用二分查找找到第一个大于等于中点的元素。然后将两个数组分成四个部分，分别进行并行合并。