本文關(guān)鍵詞：MPP環(huán)境中面向動(dòng)態(tài)規(guī)劃算法的混合并行系統(tǒng)的研究，由筆耕文化傳播整理發(fā)布。

【摘要】：動(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)規(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)行了封裝，并提供用戶接口供用戶調(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)度策略有著更高的并行效率。
【關(guān)鍵詞】：MPP 動(dòng)態(tài)規(guī)劃 多層次自動(dòng)并行化 DAG數(shù)據(jù)驅(qū)動(dòng)模型
【學(xué)位授予單位】：天津大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：O221.3;TP338.6
【目錄】：

• 摘要4-5
• ABSTRACT5-9
• 第一章 緒論9-13
• 1.1 研究背景9-10
• 1.2 國內(nèi)外研究現(xiàn)狀及趨勢(shì)10-11
• 1.3 本文主要工作和貢獻(xiàn)11
• 1.4 本文的內(nèi)容和結(jié)構(gòu)11-13
• 第二章 相關(guān)工作介紹13-15
• 2.1 并行計(jì)算硬件平臺(tái)13-14
• 2.1.1 對(duì)稱多處理器(Symmetric Multi-Processor)13
• 2.1.2 非一致存儲(chǔ)訪問體系結(jié)構(gòu)(Non-Uniform Memory Access)13
• 2.1.3 大規(guī)模并行處理體系結(jié)構(gòu)(Massive Parallel Processing)13-14
• 2.2 大規(guī)模并行計(jì)算中間件14-15
• 第三章 多層次自動(dòng)并行化系統(tǒng) EasyHPS 框架簡介15-17
• 第四章 DAG 數(shù)據(jù)驅(qū)動(dòng)模型17-23
• 4.1 DAG 模式圖定義17
• 4.2 動(dòng)態(tài)規(guī)劃問題與 DAG 模式圖的關(guān)系17-19
• 4.3 動(dòng)態(tài)規(guī)劃問題的分類與 DAG 模式圖庫19-20
• 4.4 DAG 數(shù)據(jù)驅(qū)動(dòng)模型初始化20-21
• 4.5 運(yùn)行時(shí)系統(tǒng)中 DAG 數(shù)據(jù)驅(qū)動(dòng)模型的解析21-23
• 第五章 EasyHPS 系統(tǒng)子任務(wù)調(diào)度機(jī)制23-27
• 5.1 EasyHPS 動(dòng)態(tài)線程池組件23-24
• 5.1.1 當(dāng)前可計(jì)算子任務(wù)隊(duì)列23
• 5.1.2 完成計(jì)算子任務(wù)隊(duì)列23-24
• 5.2 主模塊動(dòng)態(tài)任務(wù)線程池的任務(wù)調(diào)度24-25
• 5.3 從屬模塊動(dòng)態(tài)任務(wù)線程池的任務(wù)調(diào)度25-27
• 第六章 EasyHPS 系統(tǒng)容錯(cuò)恢復(fù)機(jī)制簡介27-33
• 6.1 常見的容錯(cuò)問題27-28
• 6.2 超時(shí)檢測的容錯(cuò)機(jī)制28-30
• 6.2.1 進(jìn)程級(jí)別的超時(shí)檢測容錯(cuò)機(jī)制28-29
• 6.2.2 線程級(jí)別的超時(shí)檢測容錯(cuò)機(jī)制29-30
• 6.3 日志跟蹤的容錯(cuò)機(jī)制30-33
• 第七章 EasyHPS 系統(tǒng)內(nèi)存接口擴(kuò)展33-38
• 7.1 緩存的組相聯(lián)映射33-34
• 7.2 EasyHPS 系統(tǒng)中內(nèi)存擴(kuò)展接口設(shè)計(jì)34-38
• 第八章 EasyHPS 系統(tǒng)設(shè)計(jì)38-48
• 8.1 EasyHPS 系統(tǒng)主模塊詳細(xì)設(shè)計(jì)38-43
• 8.1.1 主模塊 DAG 數(shù)據(jù)驅(qū)動(dòng)模型詳細(xì)設(shè)計(jì)38-41
• 8.1.2 主模塊調(diào)度模塊詳細(xì)設(shè)計(jì)41-42
• 8.1.3 主模塊容錯(cuò)模塊詳細(xì)設(shè)計(jì)42-43
• 8.2 EasyHPS 從屬模塊詳細(xì)設(shè)計(jì)43-46
• 8.2.1 從屬模塊 DAG 數(shù)據(jù)驅(qū)動(dòng)模型詳細(xì)設(shè)計(jì)43-45
• 8.2.2 從屬模塊調(diào)度模塊詳細(xì)設(shè)計(jì)45-46
• 8.2.3 從屬模塊容錯(cuò)模塊詳細(xì)設(shè)計(jì)46
• 8.3 EasyHPS 系統(tǒng)內(nèi)存擴(kuò)展接口詳細(xì)設(shè)計(jì)46-48
• 第九章 EasyHPS 系統(tǒng)在 MPP 環(huán)境中的實(shí)驗(yàn)設(shè)計(jì)和結(jié)果分析48-57
• 9.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)設(shè)計(jì)48-49
• 9.2 小數(shù)據(jù)規(guī)模下基于 EasyHPS 系統(tǒng)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法49-55
• 9.2.1 小數(shù)據(jù)規(guī)模下基于 EasyHPS 系統(tǒng)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法的實(shí)驗(yàn)設(shè)計(jì)49-51
• 9.2.2 小數(shù)據(jù)規(guī)模下基于 EasyHPS 系統(tǒng)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法的結(jié)果分析51-52
• 9.2.3 小數(shù)據(jù)規(guī)模下容錯(cuò)模塊對(duì)于 EasyHPS 系統(tǒng)性能的影響52-55
• 9.3 小數(shù)據(jù)規(guī)模下 EasyHPS 系統(tǒng)的動(dòng)態(tài)調(diào)度策略與靜態(tài)調(diào)度策略的比較55
• 9.3.1 小數(shù)據(jù)規(guī)模下 EasyHPS 系統(tǒng)的動(dòng)態(tài)調(diào)度策略與靜態(tài)調(diào)度策略的實(shí)驗(yàn)設(shè)計(jì)55
• 9.3.2 小數(shù)據(jù)規(guī)模下 EasyHPS 系統(tǒng)的動(dòng)態(tài)調(diào)度策略與靜態(tài)調(diào)度策略的結(jié)果分析55
• 9.4 大數(shù)據(jù)規(guī)模下基于 EasyHPS 系統(tǒng)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法55-57
• 9.4.1 大數(shù)據(jù)規(guī)模下基于 EasyHPS 系統(tǒng)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法的實(shí)驗(yàn)設(shè)計(jì)56
• 9.4.2 大數(shù)據(jù)規(guī)模下基于 EasyHPS 系統(tǒng)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法的結(jié)果分析56-57
• 第十章 總結(jié)和展望57-59
• 10.1 總結(jié)57
• 10.2 對(duì)未來工作的展望57-59
• 10.2.1 針對(duì) DAG 模式圖庫進(jìn)行改良58
• 10.2.2 對(duì)于異構(gòu)計(jì)算平臺(tái)的研究和完善58
• 10.2.3 對(duì)于超大規(guī)模數(shù)據(jù)集計(jì)算的支持58-59
• 參考文獻(xiàn)59-62
• 發(fā)表論文和參加科研情況說明62-63
• 致謝63

【共引文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 楊澤民;謝數(shù)濤;章群;張俊彬;;RNA二級(jí)結(jié)構(gòu)預(yù)測及其在分子分類研究中的應(yīng)用[J];安徽農(nóng)業(yè)科學(xué);2012年07期

2 張偉;金萍;侯林;馬飛;;海鞘(Ciona intestinalis)新microRNA基因的識(shí)別及其靶標(biāo)預(yù)測[J];安徽農(nóng)業(yè)大學(xué)學(xué)報(bào);2010年04期

3 付昊月;張祥德;薛定宇;;粗糙集算法在預(yù)測RNA保守功能二級(jí)結(jié)構(gòu)中的應(yīng)用[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年10期

4 ;Prediction of miRNA Based on miRNA Biogenesis via One-class SVM[J];Chemical Research in Chinese Universities;2010年05期

5 ;Identification of MicroRNA Precursors with Support Vector Machine and String Kernel[J];Genomics Proteomics & Bioinformatics;2008年02期

6 ;A Method for Identification of Selenoprotein Genes in Archaeal Genomes[J];Genomics Proteomics & Bioinformatics;2009年Z1期

7 ;Characterization of Evolutionarily Conserved MicroRNAs in Amphioxus[J];Genomics Proteomics & Bioinformatics;2010年01期

8 劉文遠(yuǎn);劉麗云;王常武;王寶文;;基于二階馬爾科夫模型預(yù)測可趨近性靶基因[J];燕山大學(xué)學(xué)報(bào);2012年04期

9 ;Predicting sRNAs and Their Targets in Bacteria[J];Genomics, Proteomics & Bioinformatics;2012年05期

10 夏飛;朱強(qiáng)華;金國慶;;基于CPU-GPU混合計(jì)算平臺(tái)的RNA二級(jí)結(jié)構(gòu)預(yù)測算法并行化研究[J];國防科技大學(xué)學(xué)報(bào);2013年06期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前1條

1 蘇光龍;黃旭慧;丁凡;蔣曉舟;駱志剛;;基于堆積能量和協(xié)變信息的RNA二級(jí)結(jié)構(gòu)預(yù)測算法[A];中國通信學(xué)會(huì)第六屆學(xué)術(shù)年會(huì)論文集（下）[C];2009年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 王鑫;Pre-mRNA選擇性剪接調(diào)控機(jī)制研究[D];哈爾濱工程大學(xué);2009年

2 靳宇;RNA帶扭結(jié)結(jié)構(gòu)的組合研究[D];南開大學(xué);2010年

3 秦晶;核糖核酸結(jié)構(gòu)：三級(jí)聯(lián)接與相互作用[D];南開大學(xué);2010年

4 夏飛;生物序列分析算法硬件加速器關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2011年

5 賈孟文;mRNA序列、結(jié)構(gòu)、能量和蛋白質(zhì)二級(jí)結(jié)構(gòu)的相關(guān)性[D];內(nèi)蒙古大學(xué);2004年

6 金偉波;基于支持向量機(jī)方法的植物miRNA預(yù)測及小麥miRNA的克隆[D];西北農(nóng)林科技大學(xué);2007年

7 劉娜;生物序列/結(jié)構(gòu)的比較及進(jìn)化樹的構(gòu)建[D];大連理工大學(xué);2007年

8 王師;櫛孔扇貝遺傳圖譜的構(gòu)建及重復(fù)元件的進(jìn)化分析[D];中國海洋大學(xué);2007年

9 李校;組合多重證據(jù)促進(jìn)真核生物基因結(jié)構(gòu)預(yù)測[D];四川大學(xué);2007年

10 舒文杰;RNA二級(jí)結(jié)構(gòu)拓?fù)涮卣骰P(guān)鍵技術(shù)及其應(yīng)用研究[D];國防科學(xué)技術(shù)大學(xué);2007年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 張偉;海鞘MicroRNA基因的識(shí)別及其靶標(biāo)預(yù)測[D];遼寧師范大學(xué);2011年

2 王明浩;序列結(jié)構(gòu)二聯(lián)語法識(shí)別miRNA前體[D];南京航空航天大學(xué);2010年

3 白楊;基于隨機(jī)森林的外顯子剪接增強(qiáng)子識(shí)別[D];哈爾濱工業(yè)大學(xué);2010年

4 米少華;基于機(jī)器學(xué)習(xí)的microRNA基因預(yù)測[D];河北工業(yè)大學(xué);2011年

5 賈啟東;農(nóng)業(yè)昆蟲中微RNA基因的生物信息學(xué)預(yù)測[D];南京農(nóng)業(yè)大學(xué);2010年

6 楊澤民;金藻類部分類群的分子系統(tǒng)學(xué)研究[D];暨南大學(xué);2005年

7 婁紹科;反義寡核苷酸的計(jì)算機(jī)輔助設(shè)計(jì)[D];中國人民解放軍軍事醫(yī)學(xué)科學(xué)院;2006年

8 李培芳;基因組中核苷酸序列的字頻和回文結(jié)構(gòu)[D];內(nèi)蒙古大學(xué);2006年

9 王義;支持向量機(jī)在醫(yī)學(xué)及生物方面的應(yīng)用[D];華東師范大學(xué);2007年

10 謝福亮;油菜microRNA和靶基因的預(yù)測與鑒定[D];南京農(nóng)業(yè)大學(xué);2007年

  本文關(guān)鍵詞：MPP環(huán)境中面向動(dòng)態(tài)規(guī)劃算法的混合并行系統(tǒng)的研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：431362