《并行程序的设计Chapter优秀PPT.ppt》由会员分享，可在线阅读，更多相关《并行程序的设计Chapter优秀PPT.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+
6、a2,2x2 +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)P
13、artition(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)、博弈、最优解查找、博弈、最优解查找、此类问题大多属于此类问
16、题大多属于NP-完全问题，即没有比完全问题，即没有比穷举查找更优的算法穷举查找更优的算法状态空间树状态空间树(state space tree)树的根表示搜寻的起点树的根表示搜寻的起点从根结点到下一层表示朝问题求解方向的各从根结点到下一层表示朝问题求解方向的各种选择种选择叶子节点表示问题的一种解，非叶子节点表叶子节点表示问题的一种解，非叶子节点表示部分解示部分解经典的树搜寻算法经典的树搜寻算法广度优先搜寻广度优先搜寻(breadth-first)深度优先搜寻深度优先搜寻(depth-first)5.4树树 搜搜 索索二、分支限界搜寻二、分支限界搜寻随着问题规模增大，其状态空间树过于浩大，随着问
17、题规模增大，其状态空间树过于浩大，导致穷举搜寻代价过大导致穷举搜寻代价过大分支限界的思路分支限界的思路在状态空间树中搜寻时，假如依据一条搜寻在状态空间树中搜寻时，假如依据一条搜寻路径不行能找到比现有解更好的解，就不路径不行能找到比现有解更好的解，就不再向前搜寻，即对树进行修剪再向前搜寻，即对树进行修剪限界函数限界函数(bounding function)/修剪函数修剪函数(cut-off function)作用：为问题的一个解或者部分解计算出量作用：为问题的一个解或者部分解计算出量化评估值化评估值当搜寻到一个结点时，为该结点计算评估值，当搜寻到一个结点时，为该结点计算评估值，与当前已获得的最优
18、评估值进行比较与当前已获得的最优评估值进行比较如优于现有解的评估值，则接着对该结点的如优于现有解的评估值，则接着对该结点的子树进行搜寻子树进行搜寻如差于现有解的评估值，则放弃对该结点的如差于现有解的评估值，则放弃对该结点的子树进行搜寻子树进行搜寻5.4树树 搜搜 索索三、并行分支限界搜寻三、并行分支限界搜寻状态空间树的搜寻比较适合于并行化状态空间树的搜寻比较适合于并行化对子树的搜寻相对独立，可以并行进行对子树的搜寻相对独立，可以并行进行假如一个深度优先搜寻被分解成多个独立的假如一个深度优先搜寻被分解成多个独立的深度优先搜寻时，就称为并行深度优先搜深度优先搜寻时，就称为并行深度优先搜寻寻可能影响
19、树并行搜寻性能的问题可能影响树并行搜寻性能的问题搜寻过程中，当前最优评估值动态更新，且搜寻过程中，当前最优评估值动态更新，且必需通知到每一个并行任务，以便其进行必需通知到每一个并行任务，以便其进行修剪，并且在发觉更优评估值时，需更新修剪，并且在发觉更优评估值时，需更新当前最优评估值当前最优评估值问：在共享存储系统和消息传递系统中，将问：在共享存储系统和消息传递系统中，将产生怎样的影响？产生怎样的影响？搜寻过程中子树可能被修剪：搜寻过程中子树可能被修剪：假如接受静态任务安排，则可能导致负载均假如接受静态任务安排，则可能导致负载均衡问题衡问题假如安排给某一任务的子树被修剪，该任务假如安排给某一任务的子树被修剪，该任务将变为空闲将变为空闲假如接受动态任务安排，任务安排队列成为假如接受动态任务安排，任务安排队列成为共享数据结构共享数据结构