《并行程序的设计Chapter5.ppt》由会员分享，可在线阅读，更多相关《并行程序的设计Chapter5.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章 并行算法及应用并行算法及应用刘刘 轶轶北京航空航天大学北京航空航天大学 计算机学院计算机学院5.1 矩阵乘法矩阵乘法5.1 矩阵乘法矩阵乘法一、简介一、简介nn矩阵乘法矩阵乘法:for(i=0;i n;i+)for(j=0;j n;j+)cij=0;for(k=0;k n;k+)cij=cij+aik*bkj;顺序代码顺序代码顺序代码的时间复杂性：顺序代码的时间复杂性：O(n3)两个外层循环没有相关性，可并两个外层循环没有相关性，可并行执行行执行如用如用n个处理器，时间复杂性个处理器，时间复杂性O(n2)如用如用n2个处理器，时间复杂性个处理器，时间复杂性O(n)如用如用n3个处
2、理器，可减为个处理器，可减为O(logn)优化内层循环，使用树结构优化内层循环，使用树结构仅为理想状态，未考虑通信仅为理想状态，未考虑通信5.1 矩阵乘法矩阵乘法二、块矩阵乘法二、块矩阵乘法通常所使用的处理器个数远小于通常所使用的处理器个数远小于n，每个处理器要处理一组数据，每个处理器要处理一组数据矩阵可以被划分成若干子矩阵矩阵可以被划分成若干子矩阵设设nn矩阵的行、列均被矩阵的行、列均被s等分，则矩阵被划分为等分，则矩阵被划分为s2个子矩阵，每个子矩阵个子矩阵，每个子矩阵有有n/sn/s个元素个元素设设m=n/s，则子矩阵元素个数为，则子矩阵元素个数为mm块块矩矩阵阵乘法乘法for(p=0;
3、p s;p+)for(q=0;q s;q+)Cp,q=0;for(r=0;r m;r+)Cp,q=Cp,q+Ap,r*Br,q;块矩阵乘法代码块矩阵乘法代码5.1 矩阵乘法矩阵乘法44矩阵乘法矩阵乘法将将44矩阵划矩阵划分为四个分为四个22矩阵矩阵块矩阵块矩阵乘法乘法5.1 矩阵乘法矩阵乘法并行算法分析并行算法分析(不考不考虑虑子矩子矩阵阵划分划分)设设nn矩矩阵阵，使用，使用n2个个处处理器，每个理器，每个处处理器需收到理器需收到1行和行和1列列元素，并把元素，并把计计算算结结果果(cij)返回返回给给主主处处理器，理器，则则通信通信时间时间：每个每个处处理器需理器需进进行行n次乘法和次乘法
4、和n次加法，次加法，计计算算时间时间：使用使用树结树结构可在构可在n台台处处理器上用理器上用logn时间时间完成完成n个元素的加法个元素的加法 因此，关于因此，关于计计算复算复杂杂性有：性有：如使用如使用n2处处理器，理器，O(n)如使用如使用n3处处理器，理器，O(logn)5.1 矩阵乘法矩阵乘法并行算法分析并行算法分析(考考虑虑子矩子矩阵阵划分划分)设矩阵的行、列被设矩阵的行、列被s等分等分(划分为划分为s2个子矩阵个子矩阵)，设，设m=n/s，子矩，子矩阵元素个数为阵元素个数为mm 使用使用s2个个处处理器，每个理器，每个处处理器需接收理器需接收1行和行和1列元素，每个元素列元素，每个
5、元素为为的的mm子矩子矩阵阵，则则通信通信时间时间：注：注：一行/列的元素个数=s(mm)=nm 每个每个处处理器需理器需进进行行s次子矩次子矩阵阵乘法和乘法和s次子矩次子矩阵阵加法，加法，顺顺序序执执 行一次子矩行一次子矩阵阵乘法需乘法需m3次乘法和次乘法和m3次加法，次加法，执执行一次子矩行一次子矩阵阵加法又需要加法又需要m2次加法，因此次加法，因此计计算算时间时间：5.2 求解线性方程组求解线性方程组一、简介一、简介假设有线性方程组：假设有线性方程组：an-1,0 x0+an-1,1x1+an-1,2x2 +an-1,n-1xn-1=bn-1 a2,0 x0+a2,1x1+a2,2x2
6、+a2,n-1xn-1 =b2a1,0 x0+a1,1x1+a1,2x2 +a1,n-1xn-1 =b1a0,0 x0+a0,1x1+a0,2x2 +a0,n-1xn-1 =b0 可将其写成矩阵形式：可将其写成矩阵形式：Ax=b两种不同的求解方法：两种不同的求解方法：稀疏矩阵稀疏矩阵(矩阵中大部分元素为矩阵中大部分元素为0)：迭代方法：迭代方法稠密矩阵稠密矩阵(矩阵中大部分元素为非矩阵中大部分元素为非0)：数学方法直接求解：数学方法直接求解用高斯消去法转换为三角矩阵用高斯消去法转换为三角矩阵用逐级回代的方法求解三角方程组用逐级回代的方法求解三角方程组二、求解三角方程组二、求解三角方程组线性方程
7、组的特殊形式线性方程组的特殊形式-三角方程组的求解方法三角方程组的求解方法an-1,0 x0+an-1,1x1+an-1,2x2 +an-1,n-1xn-1=bn-1 a2,0 x0+a2,1x1+a2,2x2 =b2a1,0 x0+a1,1x1 =b1a0,0 x0 =b0 可采用逐级回代的方法求解：可采用逐级回代的方法求解：x0=b0/a00;for(i=1;i n;i+)sum=0;for(j=0;j i;j+)sum=sum+aij*xj;xi=(bi sum)/aii;顺序顺序代码代码注意前后循环之间注意前后循环之间有数据相关性有数据相关性三、高斯消去法三、高斯消去法(又称高斯消元法
8、又称高斯消元法)一般线性方程组的求解一般线性方程组的求解先用高斯消去法转换为三角方程组，再求解三角方程组先用高斯消去法转换为三角方程组，再求解三角方程组高斯消去法高斯消去法线性方程组的一个基本特征：任一行可由该行加上另一行乘以一个常数线性方程组的一个基本特征：任一行可由该行加上另一行乘以一个常数代替代替这一过程从第一行开始，向下进行这一过程从第一行开始，向下进行例如第例如第1行以下，每一行的第行以下，每一行的第1列系列系数可以被下式清零数可以被下式清零在第在第i行，第行，第i行以下的每一行行以下的每一行j都将都将被被(第第i行行)+(第第j行行)(-aj,i/ai,i)所替换所替换高斯消去法高
9、斯消去法在考虑第在考虑第i行的情况下，行行的情况下，行i被称为主元行被称为主元行(pivot row)当当ai,i为为0或接近于或接近于0时，无法计算时，无法计算-aj,i/ai,i此时需考虑局部选主元此时需考虑局部选主元(partial pivoting)：交换第：交换第i行和它下面的行，以使行和它下面的行，以使第第i行下面所有行的第行下面所有行的第i列中绝对值最大的元素交换到第列中绝对值最大的元素交换到第i行上。交换过后，行上。交换过后，再进行高斯消去再进行高斯消去高斯消去法并行性讨论高斯消去法并行性讨论各行的处理可以并行进行各行的处理可以并行进行数据划分方案一：条状划分数据划分方案一：条
10、状划分p个处理器，每个处理器负责个处理器，每个处理器负责n/p行行负载均衡性不好负载均衡性不好数据划分方案二：循环带状划分数据划分方案二：循环带状划分p个处理器个处理器处理器处理器0负责第负责第0,n/p,2n/p,行行数据划分方案三：块状划分数据划分方案三：块状划分for(i=0;i n-1;i+)for(j=i+1;j n;j+)m=aji/aii;for(k=i;k n;k+)ajk=ajk aik*m;bj=bj bi*m;不考虑局部选主元的顺序代码不考虑局部选主元的顺序代码5.2 求解线性方程组求解线性方程组5.3 快速排序快速排序5.3快速排序快速排序一、可能的加速比一、可能的加速
11、比基于比较的排序算法基于比较的排序算法在比较数对的基础上排序在比较数对的基础上排序归并排序归并排序和和快速排序快速排序的时间复杂性：的时间复杂性：O(nlogn)在基于比较的排序算法中，如果不使用数字的特殊属在基于比较的排序算法中，如果不使用数字的特殊属性，性，O(nlogn)实际上是最好的时间复杂性实际上是最好的时间复杂性如果使用如果使用p个处理器，个处理器，最好的时间复杂性最好的时间复杂性：总的来说，用总的来说，用n个处理器达到个处理器达到O(logn)并不容易并不容易5.3快速排序快速排序二、快速排序算法二、快速排序算法快速排序算法由快速排序算法由Hoare于于1962年提出，时间复杂度
12、年提出，时间复杂度O(nlogn)快速排序算法流程快速排序算法流程从数组序列中选出一个元素，称为中间值从数组序列中选出一个元素，称为中间值(pivot)把数组序列分成两个子序列，比中间值小的元素放在一个子序列，比中把数组序列分成两个子序列，比中间值小的元素放在一个子序列，比中间值大的元素放在另一个子序列。该操作称为分割间值大的元素放在另一个子序列。该操作称为分割(partition)递归地对两个子序列分别重复上述操作，直到子序列中元素个数为递归地对两个子序列分别重复上述操作，直到子序列中元素个数为1Quicksort(list,start,end)if (start end)Partition
13、(list,start,end,pivot);Quicksort(list,start,povit-1)Quicksort(list,povit+1,end);递归形式的顺序代码递归形式的顺序代码5.3快速排序快速排序三、快速排序的并行化三、快速排序的并行化典型的并行化方法典型的并行化方法从一个处理器开始，递归产生的两个子序列中，一个留给自从一个处理器开始，递归产生的两个子序列中，一个留给自己处理，另一个传递给另一个处理器己处理，另一个传递给另一个处理器由此产生一个树结构由此产生一个树结构5.3快速排序快速排序三、快速排序的并行化三、快速排序的并行化时间复杂度时间复杂度并行时间复杂度与中间值的
14、选择密切相关并行时间复杂度与中间值的选择密切相关在理想状况下，每次选择的中间值都将序列等分成两个相等在理想状况下，每次选择的中间值都将序列等分成两个相等的子序列，则时间复杂度可达到的子序列，则时间复杂度可达到O(logn)在最差情况下，每次选择的中间值都是序列中的最大值，时在最差情况下，每次选择的中间值都是序列中的最大值，时间复杂度达到间复杂度达到O(n2)并行快速排序的工作划分并行快速排序的工作划分回忆第回忆第4章介绍的动态为进程分配工作方法章介绍的动态为进程分配工作方法快速排序过程中，后续的工作来自前面的处理结果，难以进快速排序过程中，后续的工作来自前面的处理结果，难以进行静态工作划分行静
15、态工作划分由一个处理器将序列分为由一个处理器将序列分为2个子序列，自己处理一个子序列，个子序列，自己处理一个子序列，将另一个子序列放入工作队列，由其他处理器进行类似处理将另一个子序列放入工作队列，由其他处理器进行类似处理能够较好地实现负载均衡，但工作队列是共享数据能够较好地实现负载均衡，但工作队列是共享数据5.4 树树 搜搜 索索5.4树树 搜搜 索索一、树搜索简介一、树搜索简介许多问题都可以归结为树搜索许多问题都可以归结为树搜索旅行商问题旅行商问题(Traveling Salesperson Problem,TSP)、博弈、最、博弈、最优解查找、优解查找、此类问题大多属于此类问题大多属于NP
16、-完全问题，即没有比穷举查找更优的完全问题，即没有比穷举查找更优的算法算法状态空间树状态空间树(state space tree)树的根表示搜索的起点树的根表示搜索的起点从根结点到下一层表示朝问题求解方向的各种选择从根结点到下一层表示朝问题求解方向的各种选择叶子节点表示问题的一种解，非叶子节点表示部分解叶子节点表示问题的一种解，非叶子节点表示部分解经典的树搜索算法经典的树搜索算法广度优先搜索广度优先搜索(breadth-first)深度优先搜索深度优先搜索(depth-first)5.4树树 搜搜 索索二、分支限界搜索二、分支限界搜索随着问题规模增大，其状态空间树过于庞大，导致穷随着问题规模增
17、大，其状态空间树过于庞大，导致穷举搜索代价过大举搜索代价过大分支限界的思路分支限界的思路在状态空间树中搜索时，如果按照一条搜索路径不可能找到在状态空间树中搜索时，如果按照一条搜索路径不可能找到比现有解更好的解，就不再向前搜索，即对树进行比现有解更好的解，就不再向前搜索，即对树进行修剪修剪限界函数限界函数(bounding function)/修剪函数修剪函数(cut-off function)作用：为问题的一个解或者部分解计算出量化评估值作用：为问题的一个解或者部分解计算出量化评估值当搜索到一个结点时，为该结点计算评估值，与当前已获得当搜索到一个结点时，为该结点计算评估值，与当前已获得的最优评
18、估值进行比较的最优评估值进行比较如优于现有解的评估值，则继续对该结点的子树进行搜索如优于现有解的评估值，则继续对该结点的子树进行搜索如差于现有解的评估值，则放弃对该结点的子树进行搜索如差于现有解的评估值，则放弃对该结点的子树进行搜索5.4树树 搜搜 索索三、并行分支限界搜索三、并行分支限界搜索状态空间树的搜索比较适合于并行化状态空间树的搜索比较适合于并行化对对子树的搜索相对独立子树的搜索相对独立，可以并行进行，可以并行进行如果一个深度优先搜索被分解成多个独立的深度优先如果一个深度优先搜索被分解成多个独立的深度优先搜索时，就称为并行深度优先搜索搜索时，就称为并行深度优先搜索可能影响树并行搜索性能
19、的问题可能影响树并行搜索性能的问题搜索过程中，当前最优评估值动态更新，且必须通知到每一搜索过程中，当前最优评估值动态更新，且必须通知到每一个并行任务，以便其进行修剪，并且在发现更优评估值时，个并行任务，以便其进行修剪，并且在发现更优评估值时，需更新当前最优评估值需更新当前最优评估值问：在共享存储系统和消息传递系统中，将产生怎样的影响？问：在共享存储系统和消息传递系统中，将产生怎样的影响？搜索过程中子树可能被修剪：搜索过程中子树可能被修剪：如果采用静态任务分配如果采用静态任务分配，则可能，则可能导致负载均衡导致负载均衡问题问题如果如果分配给某分配给某一任务的子一任务的子树被修剪，该任务将变为空闲树被修剪，该任务将变为空闲如果采用动态任务分配，任务分配队列成为共享数据结构如果采用动态任务分配，任务分配队列成为共享数据结构