并行计算初探

今天是并行计算的第一节课，在介绍完重要性和历史后，老师提了一个问题，作为我们了解并行计算的开始

如何并行地尽快求解$n$个元素的最大值或排序？

老师讲解了求最大值的方法，我觉得挺有趣的，在此做个记录

朴素的串行算法

遍历即可，时间复杂度$O(n)$，需要一个处理器

一般的并行算法

类似淘汰赛的方式，每两个数用一个处理器进行比较，选出较大的数，在所有选出的数中重复该操作

时间复杂度$O(logn)$，需要处理器个数$O(n/logn)$

不计代价的并行算法

对于$n$个数的数组$A$，使用$n^2$个处理器：

• 第1步， 每个处理器$p_{ij}, i \in [0, n - 1], j \in [0, n - 1]$，比较第$i$和第$j$个数的大小，得到结果方阵$B$

$$
B_{ij} =
\begin{align}
1 && if \ A_i \ge A_j \
0 && if \ A_i \lt A_j \
\end{align}
\ ， i \in [0, n - 1]，j \in [0, n - 1]
$$

• 第2步， 再使用一个列向量$M$，处理器$p_{i1}, i \in [0, n - 1]$初始化每个分量为$1$

• 第3步， 如果$B_{ij} = 0，i \in [0, n - 1]，j \in [0, n - 1]$ ，处理器$p_{ij}$置$M_i = 0$ （此处可能有写冲突，但不影响结果）

• 第4步，处理器$p_{i1}$对$M$的对应分量$M_i$进行检测。如此，只有最大的那个数对应$B$的行全为$1$，即对应$M$的分量为$1$

时间复杂度为$O(1)$

伪代码如下

begin
    for 1 ≤ i, j ≤ p par-do //工作量O(p2); 时间O(1),因为允许同时读
        if A[i] ≥ A[j] then 
             B[i, j]=1 
         else 
             B[i, j]=0
         end if
    end for
    for 1 ≤ i ≤ p par-do //工作量O(p2); 时间O(1),因为允许同时写
        M[i] = B[i,1] ∧ B[i,2] ∧ … ∧ B[i,p]
    end for
end

举例如下：

A
3	5	8	4

B
1	0	0	0
1	1	0	1
1	1	1	1
1	0	0	1

M
0
0
1
0

最大数为$A_2 = 8$

---

更新

布置了作业

改写求最大值问题的并行算法，要求不使用数组M。

很简单，不使用$M$数组，就直接在$B$上修改

第3步，处理器$p_{ij}$置$M_i = 0$ ，修改为置$B_{i0} = 0$

第4步，处理器$p_{i1}$对$M_i$进行检测，修改为对$B_{i0}$进行检测