并 行 計 算 中國科學技術大學計算機科學與技術系國家高性能計算中心(合肥)2004年12月Date1現(xiàn)代密碼學理論與實踐之五第二篇 并行算法的設計 第四章 并行算法的設計基礎 第五章 并行算法的一般設計方法 第六章 并行算法的基本設計技術 第七章 并行算法的一般設計過程Date2現(xiàn)代密碼學理論與實踐之五第五章 并行算法的一般設計方法 5.1 串行算法的直接并行化 5.2 從問題描述開始設計并行算法 5.3 借用已有算法求解新問題 Date3現(xiàn)代密碼學理論與實踐之五5.1串行算法的直接并行化 5.1.1 設計方法描述 5.1.2 快排序算法的并行化Date4現(xiàn)代密碼學理論與實踐之五 設計方法的描述 方法描述 發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法改造為并行算法 評注 由串行算法直接并行化的方法是并行算法設計的最常用方法之一； 不是所有的串行算法都可以直接并行化的； 一個好的串行算法并不能并行化為一個好的并行算法； 許多數(shù)值串行算法可以并行化為有效的數(shù)值并行算法Date5現(xiàn)代密碼學理論與實踐之五5.1串行算法的直接并行化 5.1.1 設計方法描述 5.1.2 快排序算法的并行化Date6現(xiàn)代密碼學理論與實踐之五 快排序算法的并行化 算法5.2 PRAM-CRCW上的快排序二叉樹構造算法 輸入：序列(A1,An)和n個處理器 輸出：供排序用的一棵二叉排序樹 Begin (1)for each processor i do (2)repeat for each processor iroot do (1.1)root=i if (AiAfi) (Ai=Afiifi) then (1.2)fi=root (2.1)LCfi=i (1.3)LCi=RCi=n+1 (2.2)if i=LCfi then exit else fi=LCfi endif end for else (2.3)RCfi=i (2.4)if i=RCfi then exit else fi=RCfi endif endif end repeat EndDate7現(xiàn)代密碼學理論與實踐之五第五章 并行算法的一般設計方法 5.1 串行算法的直接并行化 5.2 從問題描述開始設計并行算法 5.3 借用已有算法求解新問題 Date8現(xiàn)代密碼學理論與實踐之五 從問題描述開始設計并行算法 方法描述 從問題本身描述出發(fā)，不考慮相應的串行算法，設計一個全新的并行算法。

評注 挖掘問題的固有特性與并行的關系； 設計全新的并行算法是一個挑戰(zhàn)性和創(chuàng)造性的工作； 利用串的周期性的PRAM-CRCW算法是一個很好的范例；Date9現(xiàn)代密碼學理論與實踐之五第五章 并行算法的一般設計方法 5.1 串行算法的直接并行化 5.2 從問題描述開始設計并行算法 5.3 借用已有算法求解新問題 Date10現(xiàn)代密碼學理論與實踐之五5.3 借用已有算法求解新問題 5.3.1 設計方法描述 5.3.2 利用矩陣乘法求所有點對間最短路徑Date11現(xiàn)代密碼學理論與實踐之五 設計方法的描述 方法描述 找出求解問題和某個已解決問題之間的聯(lián)系； 改造或利用已知算法應用到求解問題上 評注 這是一項創(chuàng)造性的工作； 使用矩陣乘法算法求解所有點對間最短路徑是一個很好的范例Date12現(xiàn)代密碼學理論與實踐之五5.3 借用已有算法求解新問題 5.3.1 設計方法描述 5.3.2 利用矩陣乘法求所有點對間最短路徑Date13現(xiàn)代密碼學理論與實踐之五 利用矩陣乘法求所有點對間最短路徑 計算原理 有向圖G=(V,E)，邊權矩陣W=(wij)nn，求最短路徑長度矩陣D=(dij)nn，dij為vi到vj的最短路徑長度。

假定圖中無負權有向回路，記d(k)ij為vi到vj至多有k-1個中間結點的最短路徑長，Dk=(d(k)ij)nn，則 (1) d(1)ij=wij 當 ij (如果vi到vj之間無邊存在記為) d(1)ij=0 當 i=j (2) 無負權回路 dijd(n-1)ij (3) 利用最優(yōu)性原理：d(k)ij=min1lnd(k/2)il+d(k/2)lj 視：”+” “”， “min” “”，則上式變?yōu)?d(k)ij=1lnd(k/2)ild(k/2)lj (4) 應用矩陣乘法：D1 D2 D4 D2logn (= Dn) SIMD-CC上的并行算法：p139算法5.5Date14現(xiàn)代密碼學理論與實踐之五。