中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（PPT课件讲稿）第二篇 并行算法的设计 第五章 并行算法的一般设计方法

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第二篇并行算法的设计 第四章并行算法的设计基础 第五章并行算法的一般设计方法 第六章并行算法的基本设计技术 第七章并行算法的一般设计过程

第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第五章并行算法的一般设计方法 5.1串行算法的直接并行化 5.2从问题描述开始设计并行算法 53借用已有算法求解新问题

第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 5.1串行算法的直接并行化 5.1.1设计方法描述 51.2快排序算法的并行化

5.1串行算法的直接并行化 5.1.1 设计方法描述 5.1.2 快排序算法的并行化

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 设计方法的描述 方法描述 发掘和利用现有串行算法中的并行性,直接将串行算法 改造为并行算法 评注 由串行算法直接并行化的方法是并行算法设计的最常用 方法之一; ■不是所有的串行算法都可以直接并行化的; 个好的串行算法并不能并行化为一个好的并行算法 ■许多数值串行算法可以并行化为有效的数值并行算法。 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 5 2021/2/19 设计方法的描述 ▪ 方法描述 ▪ 发掘和利用现有串行算法中的并行性，直接将串行算法 改造为并行算法。 ▪ 评注 ▪ 由串行算法直接并行化的方法是并行算法设计的最常用 方法之一； ▪ 不是所有的串行算法都可以直接并行化的； ▪ 一个好的串行算法并不能并行化为一个好的并行算法； ▪ 许多数值串行算法可以并行化为有效的数值并行算法

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 5.1串行算法的直接并行化 51.1设计方法描述 5.1.2快排序算法的并行化

5.1串行算法的直接并行化 5.1.1 设计方法描述 5.1.2 快排序算法的并行化

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 快排序算法的并行化 ■算法52PRAM-CRCW上的快排序二叉树构造算法 输入:序列(A1A和n个处理器 输出:供排序用的一棵二叉排序树 gin (1)for each processor i do(2)repeat for each processor i>root do (1.)roo+=i f(AAf)V(A=A∧f)then (1.2) root (21儿LC1 (13儿LC=RC1=n+1 (2.2)if i=LCfi then exit else fi LCfi endif end for else (23)RC (2. 4)if i=RCfi then exit else fi=Rcfi endif endif end repeat End 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 7 2021/2/19 快排序算法的并行化 ▪ 算法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

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第五章并行算法的一般设计方法 5.1串行算法的直接并行化 5.2从问题描述开始设计并行算法 5.3借用已有算法求解新问题

第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 从问题描述开始设计并行算法 方法描述 从问题本身描述出发,不考虑相应的串行算法,设计 个全新的并行算法 评注 挖掘问题的固有特性与并行的关系 ■设计全新的并行算法是一个挑战性和创造性的工作; 利用串的周期性的PRAM-CRCW算法是一个很好的 范例; 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 9 2021/2/19 从问题描述开始设计并行算法 ▪ 方法描述 ▪ 从问题本身描述出发，不考虑相应的串行算法，设计 一个全新的并行算法。 ▪ 评注 ▪ 挖掘问题的固有特性与并行的关系； ▪ 设计全新的并行算法是一个挑战性和创造性的工作； ▪ 利用串的周期性的PRAM-CRCW算法是一个很好的 范例；

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第五章并行算法的一般设计方法 5.1串行算法的直接并行化 5.2从问题描述开始设计并行算法 5.3借用已有算法求解新问题

第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 5.3借用已有算法求解新问题 5.31设计方法描述 532利用矩阵乘法求所有点对间 最短路径

5.3 借用已有算法求解新问题 5.3.1 设计方法描述 5.3.2 利用矩阵乘法求所有点对间 最短路径