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

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

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

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