南京大学：《并行处理技术——分布式与并行计算 Distributed and Parallel computing（并行计算——结构、算法、编程）》课程教学资源（课件讲稿）第四章 并行算法的设计基础

第二篇并行算法的设计 Case Study 1.求取最大值算法 2.计算前缀和算法

第二篇 并行算法的设计 Case Study 1.求取最大值算法 2.计算前缀和算法

求取最大值 令n=2m,A是一个2维的数 组，待求最大值的n个数开 始存放在A(n),A(n+1),, K=0 A(2n-1),所求得的最大值 置于A(1)中。 sss--- An2-1 K=m-2 /2 ----D An-l K=m-1 n/2+1 n-2 n/2. A An+2 -“A20-4 A2n-3A2n-2 A2n-1 3 2011/9/27

 令n=2௠ , A是一个2维的数 组，待求最大值的n个数开 始存放在A(n), A(n+1), …, A(2n‐1)，所求得的最大值 置于A(1)中。 求取最大值 3 2011/9/27 A1 An/4 An/2-1 An/2 An/2+1 An-2 An-1 An An+1An+2 An+3 A2n-4 A2n-3A2n-2 A2n-1 K=m-1 K=m-2 P K=0 1 P1 P2 Pn/2-1 Pn/2 P1 Pn/2-1

求最大值 算法4.1：SMD-TCSM①上求最大值算法 输入：n=2m个数存放在A(n,2n-1)中； 输出：求得的最大值置于A(1)中。 Begin for k=m-1 to o do for j=2k to 2k+1-1 par-do A[j]=max{A[2j],A[2j+1]} end for end for end *时间分析 算法的时间：t(n)=m×O(1)=O(Iogn); 总比较次数：O(n); 最大的处理器数：p(n)=n/2 2011/9/27 4

求最大值  算法4.1: SIMD-TC(SM)上求最大值算法 输入： n=2݉ 个数存放在A(n,2n-1)中； 输出：求得的最大值置于A(1)中。 Begin for k=m‐1 to 0 do for j=2k to 2k+1‐1 par‐do A[j]=max{A[2j], A[2j+1]} end for end for end  时间分析 算法的时间：t(n)=m×O(1)=O(logn)； 总比较次数：O(n)； 最大的处理器数：p(n)=n/2 4 2011/9/27

计算前缀和 问题定义 n个元素{区1，X2,…x},前缀和是n个部分和： S=x1*x2*.*x,1≤i≤n这里*可以是十或X *串行算法：S=S-x 计算时间为On) *并行算法：SMD-TC上非递归算法 令A0=x,i=1~n, Bh,j1和Ch,i]为辅助数组h=0~logn,jF1~n/2) 数组B记录由叶到根正向遍历树中各结，点的信息（求和） 数组C记录由根到叶反向遍历树中各结，点的信息（播送前 缀和) 2011/9/27 5

计算前缀和  问题定义 n个元素{x1,x2,…,xn}，前缀和是n个部分和： Si=x1*x2*…*xi, 1≤i≤n 这里*可以是＋或×  串行算法： Si=Si－1*xi 计算时间为 O(n)  并行算法：SIMD-TC上非递归算法 令A[i]=xi, i=1~n, B[h,j]和C[h,j]为辅助数组(h=0~logn, j=1~n/2h) 数组B记录由叶到根正向遍历树中各结点的信息(求和) 数组C记录由根到叶反向遍历树中各结点的信息(播送前 缀和) 5 2011/9/27

计算前缀和 例：1=8，p=8,Co1~C08为前缀和 前半部分和 总和 3 h=3 B31 后半部分和 1 B21 P h=2 B2“ 31 *B13P3 22 j=1~2 h=1 2 13 3 B14 j=1~4 h=0 Bo1 B02 B03 B04 Bos Bo6 B07 Bo3 j=18 P1 P2 P3 P4 Ps P6 P7 P8 A1 A2 A3 A4 As A6 A7 Ag 计算：Ch,1]=B[h.1) j=1 计算：B]=B[h-1,21]*B[h-1,2] C[hj]=C[h+1.j/2] =even 正向遍历（求和） C[h j]=C[h+1.(j-1)/2]*B[h.j]j=odd>1 反向遍历（播送前缀和） 2011/9/27 6

计算前缀和  例：n=8, p=8, C01‾C08为前缀和 6 2011/9/27

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

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

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

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

并行算法的定义和分类 *并行算法的定义刘 *算法 *并行算法：一些可同时执行的诸进程的集合，这些进程 互相作用和协调动作从而达到给定问题的求解。 *并行算法的分类 *数值计算和非数值计算 *同步算法和异步算法 *分布算法 *确定算法和随机算法 10 2011/9/27

 并行算法的定义  算法  并行算法：一些可同时执行的诸进程的集合，这些进程 互相作用和协调动作从而达到给定问题的求解。  并行算法的分类  数值计算和非数值计算  同步算法和异步算法  分布算法  确定算法和随机算法 10 2011/9/27 并行算法的定义和分类

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

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

并行算法的表达 描述语言 *可以使用类Algol、.类Pascal等； *在描述语言中引入并行语句。 *并行语句示例 *Par-do语句 for i=1 to n par-do end for *for all语句 for all Pi,.where o≤i≤k end for 12 2011/9/27

 描述语言  可以使用类Algol、类Pascal等；  在描述语言中引入并行语句。  并行语句示例  Par‐do语句 for i=1 to n par‐do …… end for  for all语句 for all Pi, where 0≤i≤k …… end for 12 2011/9/27 并行算法的表达