并 行 计 算中国科学技术大学计算机科学与技术系国家高性能计算中心 (合肥 )
2003年 9月第二篇 并行算法的设计第四章 并行算法的设计基础第五章 并行算法的一般设计方法第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程第五章 并行算法的一般设计方法
5.1 串行算法的直接并行化
5.2 从问题描述开始设计并行算法
5.3 借用已有算法求解新问题
5.1串行算法的直接并行化
5.1.1 设计方法描述
5.1.2 快排序算法的并行化国家高性能计算中心（合肥） 52009-7-24
设计方法的描述
方法描述
发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。
评注
由串行算法直接并行化的方法是并行算法设计的最常用方法之一；
不是所有的串行算法都可以直接并行化的；
一个好的串行算法并不能并行化为一个好的并行算法；
许多数值串行算法可以并行化为有效的数值并行算法。
5.1串行算法的直接并行化
5.1.1 设计方法描述
5.1.2 快排序算法的并行化国家高性能计算中心（合肥） 72009-7-24
快排序算法的并行化
算法 5.2 PRAM-CRCW上的快排序二叉树构造算法输入：序列 (A1,…,An)和 n个处理器输出：供排序用的一棵二叉排序树
Begin
(1)for each processor i do (2)repeat for each processor i<>root do
(1.1)root=i if (Ai<Afi)∨ (Ai=Afi∧ i<fi) then
(1.2)fi=root (2.1)LCfi=i
(1.3)LCi=RCi=n+1 (2.2)if i=LCfi then exit else fi=LCfi endif
end for else
(2.3)RCfi=i
(2.4)if i=RCfi then exit else fi=RCfi endif
endif
end repeat
End
第五章 并行算法的一般设计方法
5.1 串行算法的直接并行化
5.2 从问题描述开始设计并行算法
5.3 借用已有算法求解新问题国家高性能计算中心（合肥） 92009-7-24
从问题描述开始设计并行算法
方法描述
从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。
评注
挖掘问题的固有特性与并行的关系；
设计全新的并行算法是一个挑战性和创造性的工作；
利用串的周期性的 PRAM-CRCW算法是一个很好的范例；
第五章 并行算法的一般设计方法
5.1 串行算法的直接并行化
5.2 从问题描述开始设计并行算法
5.3 借用已有算法求解新问题
5.3 借用已有算法求解新问题
5.3.1 设计方法描述
5.3.2 利用矩阵乘法求所有点对间最短路径国家高性能计算中心（合肥） 122009-7-24
设计方法的描述
方法描述
找出求解问题和某个已解决问题之间的联系；
改造或利用已知算法应用到求解问题上。
评注
这是一项创造性的工作；
使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。
5.3 借用已有算法求解新问题
5.3.1 设计方法描述
5.3.2 利用矩阵乘法求所有点对间最短路径国家高性能计算中心（合肥） 142009-7-24
利用矩阵乘法求所有点对间最短路径
计算原理有向图 G=(V,E)，边权矩阵 W=(wij)n× n，求最短路径长度矩阵
D=(dij)n× n,dij为 vi到 vj的最短路径长度。假定图中无负权有向回路，
记 d(k)ij为 vi到 vj至多有 k-1个中间结点的最短路径长,Dk=(d(k)ij)n× n，
则
(1) d(1)ij=wij 当 i<>j (如果 vi到 vj之间无边存在记为 ∞)
d(1)ij=0 当 i=j
(2) 无负权回路? dij＝ d(n-1)ij
(3) 利用最优性原理,d(k)ij=min1≤ l≤ n{d(k/2)il+d(k/2)lj}
视：,+”?“×,,“min”?“∑”，则上式变为
d(k)ij=∑1≤ l≤ n{d(k/2)il× d(k/2)lj}
(4) 应用矩阵乘法,D1?D2? D4?…?D2logn (= Dn)
SIMD-CC上的并行算法,p139算法 5.5
2003年 9月第二篇 并行算法的设计第四章 并行算法的设计基础第五章 并行算法的一般设计方法第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程第五章 并行算法的一般设计方法
5.1 串行算法的直接并行化
5.2 从问题描述开始设计并行算法
5.3 借用已有算法求解新问题
5.1串行算法的直接并行化
5.1.1 设计方法描述
5.1.2 快排序算法的并行化国家高性能计算中心（合肥） 52009-7-24
设计方法的描述
方法描述
发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。
评注
由串行算法直接并行化的方法是并行算法设计的最常用方法之一；
不是所有的串行算法都可以直接并行化的；
一个好的串行算法并不能并行化为一个好的并行算法；
许多数值串行算法可以并行化为有效的数值并行算法。
5.1串行算法的直接并行化
5.1.1 设计方法描述
5.1.2 快排序算法的并行化国家高性能计算中心（合肥） 72009-7-24
快排序算法的并行化
算法 5.2 PRAM-CRCW上的快排序二叉树构造算法输入：序列 (A1,…,An)和 n个处理器输出：供排序用的一棵二叉排序树
Begin
(1)for each processor i do (2)repeat for each processor i<>root do
(1.1)root=i if (Ai<Afi)∨ (Ai=Afi∧ i<fi) then
(1.2)fi=root (2.1)LCfi=i
(1.3)LCi=RCi=n+1 (2.2)if i=LCfi then exit else fi=LCfi endif
end for else
(2.3)RCfi=i
(2.4)if i=RCfi then exit else fi=RCfi endif
endif
end repeat
End
第五章 并行算法的一般设计方法
5.1 串行算法的直接并行化
5.2 从问题描述开始设计并行算法
5.3 借用已有算法求解新问题国家高性能计算中心（合肥） 92009-7-24
从问题描述开始设计并行算法
方法描述
从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。
评注
挖掘问题的固有特性与并行的关系；
设计全新的并行算法是一个挑战性和创造性的工作；
利用串的周期性的 PRAM-CRCW算法是一个很好的范例；
第五章 并行算法的一般设计方法
5.1 串行算法的直接并行化
5.2 从问题描述开始设计并行算法
5.3 借用已有算法求解新问题
5.3 借用已有算法求解新问题
5.3.1 设计方法描述
5.3.2 利用矩阵乘法求所有点对间最短路径国家高性能计算中心（合肥） 122009-7-24
设计方法的描述
方法描述
找出求解问题和某个已解决问题之间的联系；
改造或利用已知算法应用到求解问题上。
评注
这是一项创造性的工作；
使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。
5.3 借用已有算法求解新问题
5.3.1 设计方法描述
5.3.2 利用矩阵乘法求所有点对间最短路径国家高性能计算中心（合肥） 142009-7-24
利用矩阵乘法求所有点对间最短路径
计算原理有向图 G=(V,E)，边权矩阵 W=(wij)n× n，求最短路径长度矩阵
D=(dij)n× n,dij为 vi到 vj的最短路径长度。假定图中无负权有向回路，
记 d(k)ij为 vi到 vj至多有 k-1个中间结点的最短路径长,Dk=(d(k)ij)n× n，
则
(1) d(1)ij=wij 当 i<>j (如果 vi到 vj之间无边存在记为 ∞)
d(1)ij=0 当 i=j
(2) 无负权回路? dij＝ d(n-1)ij
(3) 利用最优性原理,d(k)ij=min1≤ l≤ n{d(k/2)il+d(k/2)lj}
视：,+”?“×,,“min”?“∑”，则上式变为
d(k)ij=∑1≤ l≤ n{d(k/2)il× d(k/2)lj}
(4) 应用矩阵乘法,D1?D2? D4?…?D2logn (= Dn)
SIMD-CC上的并行算法,p139算法 5.5
