并行计算：第六章 并行算法基本设计策略

并行计算Parallel Computing

主讲人徐云

Spring, 2014

第二篇并行算法的设计

第五章并行算法与并行计算模型第六章并行算法基本设计策略第七章并行算法常用设计技术第八章并行算法一般设计过程

第六章并行算法基本设计策略6.1 串行算法的直接并行化

6.1.1设计方法描述

6.1.2快排序算法的并行化

6.2 从问题描述开始设计并行算法6.3借用已有算法求解新问题

设计方法的描述

方法描述

发掘和利用现有串行算法中的并行性，直接将串行算法

改造为并行算法。

评注

由串行算法直接并行化的方法是并行算法设计的最常用

方法之一；

不是所有的串行算法都可以直接并行化的；

一个好的串行算法并不能并行化为一个好的并行算法；

许多数值串行算法可以并行化为有效的数值并行算法。国家高性能计算中心（合肥）4

第六章并行算法基本设计策略6.1 串行算法的直接并行化

6.1.1设计方法描述

6.1.2快排序算法的并行化

6.2 从问题描述开始设计并行算法6.3借用已有算法求解新问题

快排序算法的并行化（1） SISD上的快排序算法6.1

输入：无序序列（A

q

……Ar）

输出：有序序列（A

q

……Ar）

Procedure Quicrsort(A，q，r);

Begin

if q

(1) x=A

q

(2) s=q

(3) for i=q+1 to r do

if A

i

≤x then

s=s+1

swap(A

s ,A

i

)

end if

endfor

（4）swap(A q，A s)

（5）Quicksort(A，q，s)

（6）Quicksort(A，s+1，r)

end if

end

对于长度为n的序列，在最坏情况下的划分的两个子序别为n-1及1的长度、相应的运行时间为t(n)=t(n-1)+Θ(n)，其解为t(n) =Θ(n2).

理想的情况是所划分的两个子序列等长，相应的运行时间为t(n)=2t(n/2)+Θ(n),其解为

t(n)=Θ(n log n).

国家高性能计算中心（合肥）6

国家高性能计算中心（合肥）7快排序算法的并行化（2）

快排序的并行化 一种自然的并行化方法是并行地调用快排序对两个所划分的子序列进行快排序。这种方法并不改变串行算法本身的属性，很容易改成并行形式。但是，如果用n 个PE 排序n 个数，若用一个PE 将(A 1……A n )划分成(A 1……A s ), (A s+1……A n )是不会得到成本最优算法的，因为单是划分时就有Ω(n ),所以C(n )=p(n)t(n )=Ω(n 2).

可见，只有将划分步并行化，才有可能得到成本最优算法.

PRAM -CRCW 上快排序算法

构造一棵二叉排序树，其中主元是根

小于等于主元的元素处于左子树，大于主元的元素处于右子树 其左、右子树分别也为二叉排序树

快排序算法的并行化（3）

算法6.2 APRAM-CRCW上的快排序二叉树构造算法输入：序列(A1,…,A n)和n个处理器

输出：供排序用的一棵二叉排序树

Begin

(1)for each processor i par-do (2)repeat for each processor i<>root par-do

(1.1)root=i if (A i

(1.2)f i=root (2.1)LC fi=i

(1.3)LC i=RC i=n+1 (2.2)if i=LC fi then exit else f i=LC fi endif

end for else

(2.3)R C fi=i

(2.4)if i=RC fi then exit else f i=RC fi endif

endif

end repeat

End

注：(1)A i，LC i，RC i，root是SM变量；f i可以是LM变量；

(2)时间为O(logn)

国家高性能计算中心（合肥）8

第六章并行算法基本设计策略6.1 串行算法的直接并行化

6.2 从问题描述开始设计并行算法

6.2.1 设计方法描述

6.2.2 有向环k着色算法的并行化6.3借用已有算法求解新问题

设计方法的描述

方法描述

从问题本身描述出发，不考虑相应的串行算法，设计

一个全新的并行算法。

评注

挖掘问题的固有特性与并行的关系；

设计全新的并行算法是一个挑战性和创造性的工作；

利用串的周期性的PRAM-CRCW算法是一个很好的

范例；

国家高性能计算中心（合肥）10

第六章并行算法基本设计策略6.1 串行算法的直接并行化

6.2 从问题描述开始设计并行算法

6.2.1 设计方法描述

6.2.2 有向环k着色算法的并行化6.3借用已有算法求解新问题

有向环k着色算法的并行化（1）

K着色问题

设有向环G=(V,E)，G的k着色问题：构造映射c:

V {0,1,2,…,k-1}，使得如果 ∈E，则c[i]≠c[j]

3着色串行算法

从一顶点开始，依次给顶点交替用两种颜色着色，如果

顶点数为奇数则需要第3种颜色。

注：该串行算法难以并行化。这时需要将顶点划分为若

干类，每类指派相同颜色，最后再将分类数减为3。

国家高性能计算中心（合肥）12

有向环k着色算法的并行化（2）

基本并行k着色算法

算法: SIMD-EREW模型

//输入初始点着色c(i), 输出最终着色c’(i)

begin

for i=1 to n par-do

(1)令k是c(i)和c(i的后继)的最低的不同二进制位

(2)c’(i)= 2k+c(i)k//c(i)k为c(i)的二进制第k位

end for

end

注: (1)算法的正确性需要证明；

(2)算法的运行时间和工作量？

(3)算法应用的是破对称技术，算法中打破了顶点的对称性，

并对分类进行了压缩；

(4)在此算法的基础上如何构造3着色算法？

国家高性能计算中心（合肥）13

有向环k着色算法的并行化（3）

图例

国家高性能计算中心（合肥）14

第六章并行算法基本设计策略

6.1 串行算法的直接并行化

6.2 从问题描述开始设计并行算法6.3借用已有算法求解新问题

6.3.1设计方法描述

6.3.2利用矩阵乘法求所有点对间最短路径

设计方法的描述

方法描述

找出求解问题和某个已解决问题之间的联系；

改造或利用已知算法应用到求解问题上。

评注

这是一项创造性的工作；

使用矩阵乘法算法求解所有点对间最短路径是一个很好

的范例。

国家高性能计算中心（合肥）16

第六章并行算法基本设计策略

6.1 串行算法的直接并行化

6.2 从问题描述开始设计并行算法6.3借用已有算法求解新问题

6.3.1 设计方法描述

6.3.2利用矩阵乘法求所有点对间最短路径

利用矩阵乘法求所有点对间最短路径（1） 计算原理

有向图G=(V,E)，边权矩阵W=(w ij)n×n，求最短路径长度矩阵

D=(d ij)n×n，d ij为v i到v j的最短路径长度。假定图中无负权有向回路，

记d(k)ij为v i到v j至多有k-1个中间结点的最短路径长，D k=(d(k)ij)n×n，

则

(1) d(1)ij=w ij当i<>j (如果v i到v j之间无边存在记为∞)

d(1)ij=0 当i=j

(2) 无负权回路 d ij＝d(n-1)ij

(3)利用最优性原理：d(k)ij=min1≤l≤n{d(k/2)i l+d(k/2)

l j

}

视：”+” “×”，“min” “∑”，则上式变为

d(k)ij=∑1≤l≤n{d(k/2)i l×d(k/2)

l j }

(4) 应用矩阵乘法：D1 D2 D4 … D2logn (= D n)

SIMD-CC上的并行算法：p183算法6.5

国家高性能计算中心（合肥）18

国家高性能计算中心（合肥）19利用矩阵乘法求所有点对间最短路径（2） 时间分析

每次矩阵乘时间O(logn ), 共作次乘法

==> t(n )=O(log 2n), p(n )=n 3

计算示例

??n log 0 1 2 3 4 5 60 4 1 0 7 0 00 0 8 0 0 0 00 0 0 2 6 0 00 5 0 0 0 0 10 0 0 0 0 0 00 0 0 2 1 0 00 3 0 0 0 1 0

1

2

3

4

5

6(b)

国家高性能计算中心（合肥）

20

利用矩阵乘法求所有点对间最短路径（3）

计算示例

88

8

888888888888

8

888

8888

88888880 1 2 3 4 5 60 4 1 3 7 0 8 7 0 2 6 3 4 0 2 1 0

7 2 1 0 3 3 3 2 1 00123456

(d)

1014

13

11

Activity 5

[Open Problem] 对于一棵有n个节点（元素）的二叉查

找树（BST），如何设计一个有n个处理器的PRAM并行

算法，使得在O(log n)时间内排成一个有序数组。

Tip: 设计合适的BST数据结构，考虑如何将节点分配给相应的处理

器，再进行统计并输出到一个数组。

Homework 3

[6.S1] n个元素x1, x2, …, x n，求S1, S2, …, S n，这里

S i=x1*x2*…*x i 。串行算法为S i=S i-1*x i，其运行时间为O(n)。

试设计一个PRAM-CREW上的O(n2)个处理器的并行算

法，使得并行时间为O(logn)，要求写出SPMD形式的算

法伪代码。

国家高性能计算中心（合肥）21

本文来源：https://www.bwwdw.com/article/cjye.html