MPP環(huán)境中面向動態(tài)規(guī)劃算法的混合并行系統(tǒng)的研究.pdf

1、動態(tài)規(guī)劃是一種將復雜問題分解成若干個子問題進行計算的問題解決方案,在科學計算中有著廣泛的應用。然而隨著計算中數(shù)據(jù)量的增大,解決問題的時間代價已經(jīng)不能滿足人們的需求。多核多處理器等硬件技術(shù)的發(fā)展為科學計算并行化提供了良好的環(huán)境和平臺,使得降低科學計算的時間代價成為可能。與其他科學計算問題相比,動態(tài)規(guī)劃問題具有很強的數(shù)據(jù)依賴性。這給并行程序設計帶來困難,并使得并行程序設計過程容易出錯。
　　本文針對以上問題,提出了MPP環(huán)境下針對動態(tài)

2、規(guī)劃并行化的多層次混合并行系統(tǒng)EasyHPS并對動態(tài)規(guī)劃問題的并行化進行了研究。對于動態(tài)規(guī)劃問題,我們根據(jù)其特點總結(jié)出動態(tài)規(guī)劃計算方程?；诖朔匠?我們在EasyHPS系統(tǒng)中建立起DAG數(shù)據(jù)驅(qū)動模型并為動態(tài)規(guī)劃問題進行建模。以DAG數(shù)據(jù)驅(qū)動模型為基礎(chǔ),EasyHPS實現(xiàn)了MPP環(huán)境下動態(tài)規(guī)劃問題多層次自動并行化的系統(tǒng)框架。在EasyHPS系統(tǒng)中,DAG數(shù)據(jù)驅(qū)動模型對并行計算過程中的子任務劃分,調(diào)度及消息通信等功能模塊進行了封裝,并提供用

3、戶接口供用戶調(diào)用,從而實現(xiàn)了動態(tài)規(guī)劃問題在MPP環(huán)境下的自動并行化,降低程序設計人員的并行程序設計難度。動態(tài)規(guī)劃并行化過程中的容錯問題進行研究。EasyHPS系統(tǒng)通過超時檢查和日志跟蹤兩種方式對于運行過程進行容錯檢查,并實現(xiàn)了斷電重啟后繼續(xù)計算的功能。最后通過生物信息學中的基因匹配算法對于系統(tǒng)的可行性及并行效率進行驗證。通過基于波陣的Block-Cyclic的靜態(tài)任務調(diào)度算法的實驗對比,EasyHPS的多層次動態(tài)調(diào)度策略有著更高的并行效