05-第05章-并行算法的一般设计方法-并行算法的设计-并行计算(共15章)

并行计算中国科学技术大学计算机科学与技术系中国科学技术大学计算机科学与技术系国家高性能计算中心国家高性能计算中心((合肥合肥))20042004年年1212月月第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程第五章并行算法的一般设计方法5.1串行算法的直接并行化5.2从问题描述开始设计并行算法5.3借用已有算法求解新问题5.1串行算法的直接并行化5.1.1设计方法描述5.1.2快排序算法的并行化国家高性能计算中心（合肥）52013/7/24Wednesday设计方法的描述方法描述方法描述发掘和利用现有串行算法中的并行性，直接将串行算法发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。改造为并行算法。评注评注由串行算法直接并行化的方法是并行算法设计的最常用由串行算法直接并行化的方法是并行算法设计的最常用方法之一；方法之一；不是所有的串行算法都可以直接并行化的；不是所有的串行算法都可以直接并行化的；一个好的串行算法并不能并行化为一个好的并行算法；一个好的串行算法并不能并行化为一个好的并行算法；许多数值串行算法可以并行化为有效的数值并行算法。许多数值串行算法可以并行化为有效的数值并行算法。5.1串行算法的直接并行化5.1.1设计方法描述5.1.2快排序算法的并行化国家高性能计算中心（合肥）72013/7/24Wednesday快排序算法的并行化算法算法5.2PRAM5.2PRAM--CRCWCRCW上的快排序二叉树构造算法上的快排序二叉树构造算法输入：序列输入：序列(A(A11,,……,A,Ann))和和nn个处理器个处理器输出：供排序用的一棵二叉排序树输出：供排序用的一棵二叉排序树BeginBegin(1)foreachprocessorido(1)foreachprocessorido(2)repeatforeachprocessorirootdo(2)repeatforeachprocessorirootdo(1.1)root=i(1.1)root=iif(Aif(AiiAAfifi))∨∨((AAii==AAfifi∧∧iiffii)then)then(1.2)f(1.2)fii=root(2.1)LC=root(2.1)LCfifi=i=i(1.3)LC(1.3)LCii==RCRCii=n+1(2.2)ifi==n+1(2.2)ifi=LCLCfifithenexitelsethenexitelseffii==LCLCfifiendifendifendforelseendforelse(2.3)R(2.3)RCCfifi=i=i(2.4)ifi=(2.4)ifi=RCRCfifithenexitelsethenexitelseffii==RCRCfifiendifendifendifendifendrepeaendrepeattEndEnd第五章并行算法的一般设计方法5.1串行算法的直接并行化5.2从问题描述开始设计并行算法5.3借用已有算法求解新问题国家高性能计算中心（合肥）92013/7/24Wednesday从问题描述开始设计并行算法方法描述方法描述从问题本身描述出发，不考虑相应的串行算法，设计从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。一个全新的并行算法。评注评注挖掘问题的固有特性与并行的关系；挖掘问题的固有特性与并行的关系；设计全新的并行算法是一个挑战性和创造性的工作；设计全新的并行算法是一个挑战性和创造性的工作；利用串的周期性的利用串的周期性的PRAMPRAM--CRCWCRCW算法是一个很好的算法是一个很好的范例；范例；第五章并行算法的一般设计方法5.1串行算法的直接并行化5.2从问题描述开始设计并行算法5.3借用已有算法求解新问题5.3借用已有算法求解新问题5.3.1设计方法描述5.3.2利用矩阵乘法求所有点对间最短路径国家高性能计算中心（合肥）122013/7/24Wednesday设计方法的描述方法描述方法描述找出求解问题和某个已解决问题之间的联系；找出求解问题和某个已解决问题之间的联系；改造或利用已知算法应用到求解问题上。改造或利用已知算法应用到求解问题上。评注评注这是一项创造性的工作；这是一项创造性的工作；使用矩阵乘法算法求解所有点对间最短路径是一个很好使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。的范例。5.3借用已有算法求解新问题5.3.1设计方法描述5.3.2利用矩阵乘法求所有点对间最短路径国家高性能计算中心（合肥）142013/7/24Wednesday利用矩阵乘法求所有点对间最短路径计算原理计算原理有向图有向图G=(V,E)G=(V,E)，边权矩阵，边权矩阵W=(W=(wwijij))nn××nn，求最短路径长度矩阵，求最短路径长度矩阵D=(D=(ddijij))nn××nn，，ddijij为为vvii到到vvjj的最短路径长度。假定图中无负权有向回路，的最短路径长度。假定图中无负权有向回路，记记dd(k)(k)ijij为为vvii到到vvjj至多有至多有kk--11个中间结点的最短路径长，个中间结点的最短路径长，DDkk=(=(dd(k)(k)ijij))nn××nn，，则则(1)d(1)d(1)(1)ijij==wwijij当当ij(ij(如果如果vvii到到vvjj之间无边存在记为之间无边存在记为∞∞))dd(1)(1)ijij=0=0当当i=ji=j(2)(2)无负权回路无负权回路ddijij＝＝dd(n(n--1)1)ijij(3)(3)利用最优性原理：利用最优性原理：dd(k)(k)ijij=min=min11≤≤ll≤≤nn{{dd(k/2)(k/2)iill++dd(k/2)(k/2)lljj}}视：视：””++””““××””，，““minmin””““∑∑””，则上式变为，则上式变为dd(k)(k)ijij==∑∑11≤≤ll≤≤nn{{dd(k/2)(k/2)iill××dd(k/2)(k/2)lljj}}(4)(4)应用矩阵乘法：应用矩阵乘法：DD11DD22DD44……DD22lognlogn(=(=DDnn))SIMDSIMD--CCCC上的并行算法：上的并行算法：p139p139算法算法5.55.5