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

并行计算 Parallel Computing 主讲人 徐云 Spring, 2014 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 SISD上的快排序算法6.1 输入：无序序列（A ……Ar ） 输入：无序序列（A ……Ar ） q q 输出：有序序列（A ……Ar ） 输出：有序序列（A ……Ar ） q q endfor endfor Procedure Quicrsort(A，q，r); Procedure Quicrsort(A，q，r); （4）swap(A ，A ) q s q Begin Begin （5）Quicksort(A ，q ，s) if qr then （6）Quicksort(A ，s+1 ，r) if qr then end if (1) x=A end if (1) x=Aq q (2) s=q (2) s=q end (3) for i=q+1 to r do (3) for i=q+1 to r do 对于长度为n的序列，在最坏情况下的划分的