并行计算 Parallel Computing 主讲人 孙广中 Spring, 2018 2019/5/11

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

第六章 并行算法基本设计策略 6. 1 串行算法的直接并行化 6. 1. 1 设计方法描述 6. 1. 2 快排序算法的并行化 6 第六章 并行算法基本设计策略 6.1 串行算法的直接并行化 6.1.1 设计方法描述 6.1.2 快排序算法的并行化 6.2 从问题描述开始设计并行算法 6.3 借用已有算法求解新问题

设计方法的描述 方法描述 评注 发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。 由串行算法直接并行化的方法是并行算法设计的最常用方法之一； 不是所有的串行算法都可以直接并行化的； 一个好的串行算法并不能并行化为一个好的并行算法； 许多数值串行算法可以并行化为有效的数值并行算法。

第六章 并行算法基本设计策略 6. 1 串行算法的直接并行化 6. 1. 1 设计方法描述 6. 1. 2 快排序算法的并行化 6 第六章 并行算法基本设计策略 6.1 串行算法的直接并行化 6.1.1 设计方法描述 6.1.2 快排序算法的并行化 6.2 从问题描述开始设计并行算法 6.3 借用已有算法求解新问题

快排序算法的并行化（1） SISD上的快排序算法6.1 end 输入：无序序列（Aq……Ar） 输出：有序序列（Aq……Ar） Procedure Quicrsort(A，q，r); Begin if q<r then (1) x=Aq (2) s=q (3) for i=q+1 to r do if Ai≤x then s=s+1 swap(As,Ai) end if endfor （4）swap(Aq，As) （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)=Θ(nlogn).

快排序算法的并行化（2） 快排序的并行化 一种自然的并行化方法是并行地调用快排序对两个所划分的子序列进行快排序。这种方法并不改变串行算法本身的属性，很容易改成并行形式。但是，如果用n个PE排序n个数，若用一个PE将(A1……An)划分成(A1……As), (As+1……An)是不会得到成本最优算法的，因为单是划分时就有Ω(n),所以C(n)=p(n)t(n)=Ω(n2). 可见，只有将划分步并行化，才有可能得到成本最优算法. PRAM-CRCW上快排序算法 构造一棵二叉排序树，其中主元是根 小于等于主元的元素处于左子树，大于主元的元素处于右子树 其左、右子树分别也为二叉排序树

快排序算法的并行化（3） 算法6.2 APRAM-CRCW上的快排序二叉树构造算法 输入：序列(A1,…,An)和n个处理器 输出：供排序用的一棵二叉排序树 Begin (1)for each processor i par-do (2)repeat for each processor i<>root par-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 注：(1)Ai，LCi，RCi，root是SM变量；fi可以是LM变量； (2)时间为O(logn)

第六章 并行算法基本设计策略 6. 1 串行算法的直接并行化 6. 2 从问题描述开始设计并行算法 6. 2. 1 设计方法描述 6. 2 第六章 并行算法基本设计策略 6.1 串行算法的直接并行化 6.2 从问题描述开始设计并行算法 6.2.1 设计方法描述 6.2.2 有向环k着色算法的并行化 6.3 借用已有算法求解新问题

设计方法的描述 方法描述 评注 从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。 挖掘问题的固有特性与并行的关系； 设计全新的并行算法是一个挑战性和创造性的工作； 利用串的周期性的PRAM-CRCW算法是一个很好的范例；

第六章 并行算法基本设计策略 6. 1 串行算法的直接并行化 6. 2 从问题描述开始设计并行算法 6. 2. 1 设计方法描述 6. 2 第六章 并行算法基本设计策略 6.1 串行算法的直接并行化 6.2 从问题描述开始设计并行算法 6.2.1 设计方法描述 6.2.2 有向环k着色算法的并行化 6.3 借用已有算法求解新问题

K着色问题 3着色串行算法 有向环k着色算法的并行化（1） 设有向环G=(V,E)，G的k着色问题：构造映射c: V{0,1,2,…,k-1}，使得如果<i, j> ∈E，则c[i]≠c[j] 3着色串行算法 从一顶点开始，依次给顶点交替用两种颜色着色，如果顶点数为奇数则需要第3种颜色。 注：该串行算法难以并行化。这时需要将顶点划分为若干类，每类指派相同颜色，最后再将分类数减为3。

有向环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着色算法？

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

第六章 并行算法基本设计策略 6.1 串行算法的直接并行化 6.2 从问题描述开始设计并行算法 6.3 借用已有算法求解新问题 6.3.1 设计方法描述 6.3.2 利用矩阵乘法求所有点对间最短路径

设计方法的描述 方法描述 评注 找出求解问题和某个已解决问题之间的联系； 改造或利用已知算法应用到求解问题上。 这是一项创造性的工作； 使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。

第六章 并行算法基本设计策略 6.1 串行算法的直接并行化 6.2 从问题描述开始设计并行算法 6.3 借用已有算法求解新问题 6.3.1 设计方法描述 6.3.2 利用矩阵乘法求所有点对间最短路径

利用矩阵乘法求所有点对间最短路径（1） 计算原理 SIMD-CC上的并行算法：p183算法6.5 有向图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上的并行算法：p183算法6.5

利用矩阵乘法求所有点对间最短路径（2） 时间分析 计算示例 每次矩阵乘时间O(logn), 共作 次乘法 ==> t(n)=O(log2n), p(n)=n3 计算示例

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

1. A是一个大小为n的布尔数组，欲求出最小的下标i且A[i]为真，试设计一个常数时间的PRAM-CRCW并行算法。如果使用PRAM-CREW模型，运行时间如何？ Hint: 1. copy A[1..n] to B[1..n] 3. for i=1 to n par-do 2. for i=1 to n par-do if B[i]=true then if B[i]=true then return i for j=i+1 to n par-do endif B[j]=false endfor endfor endif 2.在PRAM-CREW模型上，用n个处理器在O(1)时间内求出数组 A[1..n]={0,…,0,1,…,1}，最先为1值的下标。