并行计算初探
2019-02-25
90633 字
302 分钟
次

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

如何并行地尽快求解

n
个元素的最大值或排序？

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

朴素的串行算法

遍历即可，时间复杂度

O(n)
，需要一个处理器

一般的并行算法

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

时间复杂度

O(logn)
，需要处理器个数
O(n/logn)

不计代价的并行算法

对于

n
个数的数组
A
，使用
n^2
个处理器：
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]

时间复杂度为

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}
进行检测