并行化程序設(shè)計(jì)的四步走

并行化程序設(shè)計(jì)的四步走并行化程序設(shè)計(jì)的四步走SelwynYou(Intel)星期四,21/05/2009-11:24發(fā)布多核計(jì)算平臺的普及化使得并行（Parallel）或者并發(fā)（Concurrent）程序設(shè)計(jì)（這里不妨稱它們?yōu)椴⑿谢绦蛟O(shè)計(jì)）成為一種編程技術(shù)主流。其實(shí)并行計(jì)算的軟件技術(shù)早已存在了幾十年，然而其原來主要服務(wù)于高性能計(jì)算一類的應(yīng)用，所以并行化編程一直也都為陽春白雪的光環(huán)籠罩?，F(xiàn)在談到多核編程，討論較多的是各種軟件或者并行編程模型的使用；對于初學(xué)者而言卻仍可能難以循其徑而入。其實(shí)，并行化的程序設(shè)計(jì)是有章可循的。按照開發(fā)流程的順序，可以把并行化程序設(shè)計(jì)分為以下四個階段：1.可行算法（解決方案）的描述與分析2.工作分解（Decomposition）--依賴性和同步與通信開銷分析3.選擇編程（實(shí)現(xiàn)）模型4.性能檢查及優(yōu)化在設(shè)計(jì)的初始階段，開發(fā)者應(yīng)當(dāng)針對要解決的問題先找到一個可行的解決方案或者算法。比如，排序問題的解決方案有氣泡排序，快速排序，二叉樹排序等已知可行的方法可以作為并行化的基礎(chǔ)算法。而在進(jìn)行具體的并行化設(shè)計(jì)之前，有一個很重要的分析（或者評估）要做，那就是并行化的必要性分析；即，應(yīng)該估計(jì)一下目標(biāo)問題的計(jì)算量。如果需要解決的問題計(jì)算量并不是很大，比如只需要對30個整數(shù)進(jìn)行排序，即使采用傳統(tǒng)串行程序也不會占用太多時間，那么就可能沒有為之設(shè)計(jì)并行化程序的必要，因?yàn)椴⑿谢彩且冻銎渌?jì)算的代價的。另外，基礎(chǔ)算法的選擇也很有講究。有些算法本身就不具備太多的并行性，比如圖論算法中最小生成樹/MinimumSpanningTree（MST）的Kruskal算法；而有些算法則具有很好的可擴(kuò)展性（Scalability），比如MST的Boruvka算法（關(guān)于MST算法并行化的例子可參見ISN學(xué)術(shù)社區(qū)課件）。為確定算法的并行性，一般需要借助一些理論和工具的幫助。Amdal'slaw是大多數(shù)設(shè)計(jì)者所采用的估計(jì)并行化加速比上限的定理；而Gustafson'slaw則是分析并行程序可擴(kuò)展性的有力理論指導(dǎo)。而為了能夠使用這些定理給出指導(dǎo)，還需要一些軟件工具（ProfilingTools）的輔助，從而確定理論所需的一些參數(shù)（如串行程序的并行量p）。提供這一種功能的常用的工具有Intel性能分析器Vtune，Windows里面的PerfMon等。對于理論和軟件工具的使用可以參照學(xué)術(shù)社區(qū)的課件?；A(chǔ)算