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

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

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

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第四章并行算法的设计基础 4.1并行算法的基础知识 4.2并行计算模型

第四章 并行算法的设计基础 4.1 并行算法的基础知识 4.2 并行计算模型

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 4.1并行算法的基础知识 41.1并行算法的定义和分类 4.1.2并行算法的表达 4.1.3并行算法的复杂性度量 4.1.4并行算法中的同步和通讯

4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯

中国料学火计算机科学与波术系 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 4.1并行算法的基础知识 41.1并行算法的定义和分类 4.1.2并行算法的表达 4.1.3并行算法的复杂性度量 4.1.4并行算法中的同步和通讯

4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯

中国料学火计算机科学与波术系 riversity of Science and Technolocy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 并行算法的表达 ■描述语言 ■可以使用类 Algol、类 Pascal等 在描述语言中引入并行语句。 并行语句示例 Par-do语句 for i=1 to n par-do end for ford川语句 for all Pi, where≤i≤k end for 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 7 2021/2/19 并行算法的表达 ▪ 描述语言 ▪ 可以使用类Algol、类Pascal等； ▪ 在描述语言中引入并行语句。 ▪ 并行语句示例 ▪ Par-do语句 for i=1 to n par-do …… end for ▪ for all语句 for all Pi, where 0≤i≤k …… end for

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 4.1并行算法的基础知识 41.1并行算法的定义和分类 4.1.2并行算法的表达 4.1.3并行算法的复杂性度量 4.1.4并行算法中的同步和通讯

4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 并行算法的复杂性度量 串行算法的复杂性度量 ■最坏情况下的复杂度( Worst- CASE Complexity) 期望复杂度( Expected Complexity 并行算法的几个复杂性度量指标 运行时间t(n):包含计算时间和通讯时间,分别用计算时 间步和选路时间步作单位。η为问题实例的输入规模。 处理器数p(n) 并行算法成本c(n):c(n)=tn)p(n) 总运算量W(n):并行算法求解问题时所完成的总的操作 步数。 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 9 2021/2/19 并行算法的复杂性度量 ▪ 串行算法的复杂性度量 ▪ 最坏情况下的复杂度(Worst-CASE Complexity) ▪ 期望复杂度(Expected Complexity) ▪ 并行算法的几个复杂性度量指标 ▪ 运行时间t(n):包含计算时间和通讯时间，分别用计算时 间步和选路时间步作单位。n为问题实例的输入规模。 ▪ 处理器数p(n) ▪ 并行算法成本c(n): c(n)=t(n)p(n) ▪ 总运算量W(n): 并行算法求解问题时所完成的总的操作 步数

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 并行算法的复杂性度量 Brent定理 令W(n)是某并行算法A在运行时间T(n)内所执行的运算 量,则A使用p台处理器可在t(n)=O(W(n)/p+T(n)时间 内执行完毕。 W(n)和c(n)密切相关 POW(n)/T(n)时,W(n)和c(n)两者是渐进一致的 对于任意的p,c(n)W(n) 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 10 2021/2/19 并行算法的复杂性度量 ▪ Brent定理 令W(n)是某并行算法A在运行时间T(n)内所执行的运算 量，则A使用p台处理器可在t(n)=O(W(n)/p+T(n))时间 内执行完毕。 ▪ W(n)和c(n)密切相关 ▪ P=O(W(n)/T(n))时，W(n)和c(n)两者是渐进一致的 ▪ 对于任意的p，c(n)›W(n)

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 4.1并行算法的基础知识 41.1并行算法的定义和分类 4.1.2并行算法的表达 4.1.3并行算法的复杂性度量 4.1.4并行算法中的同步和通讯

4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯