第六章-并行算法的基本设计技术课件.ppt

1、第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术 6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术国家高性能计算中心（合肥）42022-3-27 均匀划分技术国家高性能计算中心（合肥）52022-3-27 均匀划分技术6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根

2、划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术国家高性能计算中心（合肥）72022-3-27 方根划分技术pqk pqk ）、分成若干段（和qjpiqjpi11 qp pqk 国家高性能计算中心（合肥）82022-3-27 方根划分技术国家高性能计算中心（合肥）92022-3-27 方根划分技术6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术国家高性能计算中心（合肥）112022-3-27 对数划分技术6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.

3、1.4 功能划分技术国家高性能计算中心（合肥）132022-3-27 功能划分技术国家高性能计算中心（合肥）142022-3-27 功能划分技术第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术 6.2 分治设计技术 6.2.1 并行分治设计步骤 6.2.2 双调归并网络国家高性能计算中心（合肥）172022-3-27 并行分治设计步骤6.2 分治设计技术 6.2.1 并行分治设计步骤 6.2.2 双调归并网络国家高性能计算中心（合肥）192022-3-27 双调归并网络国家高性能计算中心（合肥）20

4、2022-3-27 双调归并网络国家高性能计算中心（合肥）212022-3-27 双调归并网络第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术 6.3 平衡树设计技术 6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和国家高性能计算中心（合肥）242022-3-27 平衡树设计技术6.3 平衡树设计技术 6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和国家高性能计算中心（合肥）262022-3-27 求最大值 t(n)=mO(1)=O(logn) p(n)=n/2A

5、1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An+3A2n-4A2n-3A2n-2A2n-1K=m-1K=m-2K=0P1P1P2Pn/2-1Pn/2P1Pn/2-16.3 平衡树设计技术 6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和国家高性能计算中心（合肥）282022-3-27 计算前缀和国家高性能计算中心（合肥）292022-3-27 计算前缀和第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术 6.4 倍增设计技术 6.4.1 设计思想

6、6.4.2 表序问题 6.4.3 求森林的根国家高性能计算中心（合肥）322022-3-27 倍增设计技术6.4 倍增设计技术 6.4.1 设计思想 6.4.2 表序问题 6.4.3 求森林的根国家高性能计算中心（合肥）342022-3-27 表序问题国家高性能计算中心（合肥）352022-3-27 表序问题nlog6.4 倍增设计技术 6.4.1 设计思想 6.4.2 表序问题 6.4.3 求森林的根国家高性能计算中心（合肥）372022-3-27 求森林的根 初始时初始时 P1=p2=5 p3=p4=p5=6 P1=p2=5 p3=p4=p5=6 P6=p7=8 p8=8 P9=10 P6

7、=p7=8 p8=8 P9=10 p10=11 p11=12 p12=13 p13=13 p10=11 p11=12 p12=13 p13=13 si=pi si=pi国家高性能计算中心（合肥）382022-3-27 求森林的根 第一次迭代后第一次迭代后 第二次迭代后第二次迭代后第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术 6.5 流水线设计技术 6.5.1 设计思想 6.5.2 5-point DFT的计算 国家高性能计算中心（合肥）412022-3-27 流水线设计技术6.5 流水线设计技术 6.5.1 设计思想 6.5.2 5-point DFT的计算 国家高性能计算中心（合肥）432022-3-27 5-point DFT的计算04142434440313233343021222324201112131410010203040021426316444021426312433021426384220112233441100102030400)()()()()(aaaaayaaaaayaaaaayaaaaayaaaaayaaaaabyaaaaabyaaaaabyaaaaabyaaaaaby国家高性能计算中心（合肥）442022-3-27 5-point DFT的计算