本文關(guān)鍵詞：基于可重構(gòu)架的動態(tài)網(wǎng)絡(luò)路徑規(guī)劃算法研究與實(shí)現(xiàn)，由筆耕文化傳播整理發(fā)布。

【摘要】：最短路徑規(guī)劃問題是一個經(jīng)典的數(shù)學(xué)問題,廣泛應(yīng)用于多種與路徑規(guī)劃技術(shù)相關(guān)的領(lǐng)域。例如：科技領(lǐng)域中的無人駕駛汽車、無人機(jī)、智能機(jī)器人、巡航導(dǎo)彈打擊目標(biāo)與導(dǎo)彈防御系統(tǒng)；日常生活領(lǐng)域中的智能汽車導(dǎo)航、地理信息系統(tǒng)；決策調(diào)控領(lǐng)域中的物流規(guī)劃領(lǐng)域邊際問題和資源合理分配問題；通信技術(shù)領(lǐng)域中的路由規(guī)劃問題等。隨著人類社會的發(fā)展和科技的不斷進(jìn)步,社會近百年的科技成就大大超過了人類社會以往幾千年的成就總和。現(xiàn)代城市規(guī)模之巨大,路網(wǎng)之復(fù)雜,處理的數(shù)據(jù)量也隨之增加；例如：紐約市路網(wǎng)地圖就包含了26萬個節(jié)點(diǎn),73萬條邊.面對大規(guī)模的路網(wǎng)數(shù)據(jù)量,傳統(tǒng)的最短路徑規(guī)劃算法在求解時耗時較長,不能滿足應(yīng)用中的實(shí)時性要求。可重構(gòu)處理器與GPP (General Purpose Processor,通用處理器)相比,可重構(gòu)計(jì)算架構(gòu)的數(shù)據(jù)并行性度高,數(shù)據(jù)處理能力強(qiáng),它不依賴于指令流的數(shù)據(jù)處理方式,而是基于數(shù)據(jù)流的并行處理,在算法的合適映射下,可以充分挖掘路徑規(guī)劃算法并行度高的特點(diǎn),發(fā)揮其并行處理的優(yōu)勢。它與ASIC (Application Specific Integrated Circuit,專用集成電路)相比,可重構(gòu)處理器具有靈活多變的硬件架構(gòu),來適應(yīng)軟件層次上改變相關(guān)的運(yùn)算,從而適應(yīng)不同的算法。本文利用可重構(gòu)技術(shù)的硬件架構(gòu),從經(jīng)典的路徑網(wǎng)絡(luò)規(guī)劃算法特點(diǎn)出發(fā),得到可重構(gòu)體系基本機(jī)構(gòu)為陣列形式,再通過對經(jīng)典算法的任務(wù)劃分映射,得到相對應(yīng)的數(shù)據(jù)流圖和調(diào)度表。這樣就實(shí)現(xiàn)了在可重構(gòu)硬件陣列處理單元上對算法的映射實(shí)現(xiàn),最后把優(yōu)化后的算法在可重構(gòu)硬件平臺的執(zhí)行,并對其性能進(jìn)行驗(yàn)證。這樣設(shè)計(jì)方式可實(shí)現(xiàn)對不同算法的硬件重復(fù)利用,而且其設(shè)計(jì)流程同樣適用于其它的網(wǎng)圖領(lǐng)域。本文主要特色性研究成果是：(1)提出基于可重構(gòu)技術(shù)的路徑規(guī)劃算法加速處理方法；利用可重構(gòu)硬件平臺的動態(tài)可配置性與并行性,分別結(jié)合經(jīng)典Dijkstra算法和TSP算法,得到了一種針對路徑規(guī)劃算法的新型加速處理方法。(2)在可重構(gòu)硬件架構(gòu)平臺上完成了Dijkstra算法和TSP算法的實(shí)現(xiàn)和驗(yàn)證,與通用計(jì)算平臺相比,分別獲得了2.1倍與3.2倍的加速比。通過對經(jīng)典Dijkstra和TSP算法的并行優(yōu)化,分析其內(nèi)部數(shù)據(jù)結(jié)構(gòu)的依賴關(guān)系,劃分成適合于可重構(gòu)陣列上面執(zhí)行的任務(wù),可大大的降低了原算法的時間復(fù)雜度與空間復(fù)雜度,從而獲得了一定的加速比。
【關(guān)鍵詞】：路徑規(guī)劃算法 可重構(gòu) 并行算法 Dijkstra算法 TSP算法
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP301.6
【目錄】：

• 致謝5-6
• 摘要6-7
• ABSTRACT7-11
• 1 引言11-19
• 1.1 論文研究背景及其意義11-12
• 1.2 可重構(gòu)計(jì)算系統(tǒng)簡介12-16
• 1.2.1 重構(gòu)計(jì)算系統(tǒng)概述13-14
• 1.2.2 可重構(gòu)計(jì)算體系的國內(nèi)外研究現(xiàn)狀14-15
• 1.2.3 可重構(gòu)計(jì)算系統(tǒng)的優(yōu)勢15-16
• 1.3 本文研究內(nèi)容和創(chuàng)新工作16-17
• 1.4 論文組織結(jié)構(gòu)17-19
• 2 可重構(gòu)硬件架構(gòu)技術(shù)研究19-27
• 2.1 可重構(gòu)硬件結(jié)構(gòu)綜述19-20
• 2.2 可重構(gòu)處理硬件架構(gòu)20-22
• 2.2.1 可重構(gòu)陣列執(zhí)行流程21-22
• 2.2.2 可重構(gòu)架構(gòu)存儲22
• 2.3 可重構(gòu)處理陣列PEA22-25
• 2.3.1 執(zhí)行流程23
• 2.3.2 陣列單元Router23-24
• 2.3.3 可重構(gòu)陣列PE執(zhí)行流程24-25
• 2.4 ALU概述25-26
• 2.5 本章小結(jié)26-27
• 3 基于可重構(gòu)硬件架構(gòu)的動態(tài)路徑規(guī)劃算法的加速研究27-39
• 3.1 路徑規(guī)劃算法的可重構(gòu)并行技術(shù)實(shí)現(xiàn)27-30
• 3.1.1 并行算法基礎(chǔ)概述28-29
• 3.1.2 可重構(gòu)計(jì)算框架基本原理29
• 3.1.3 可重構(gòu)任務(wù)并行過程29-30
• 3.2 可重構(gòu)的動態(tài)路徑技術(shù)實(shí)現(xiàn)框架30-31
• 3.3 可重構(gòu)的動態(tài)路徑規(guī)劃算法與其他優(yōu)化算法的比較31
• 3.4 DIJKSTRA算法的可重構(gòu)架構(gòu)設(shè)計(jì)31-35
• 3.4.1 DIJKSTRA算法原理31-34
• 3.4.2 基于可重構(gòu)架構(gòu)的DIJKSTRA算法并行化分析34-35
• 3.5 TSP算法的可重構(gòu)架構(gòu)設(shè)計(jì)35-37
• 3.5.1 TSP算法原理35-37
• 3.5.2 基于可重構(gòu)架構(gòu)的TSP算法并行化分析37
• 3.6 本章小結(jié)37-39
• 4 基于可重構(gòu)架構(gòu)的動態(tài)路徑規(guī)劃算法優(yōu)化與實(shí)現(xiàn)39-49
• 4.1 算法映射概念39-40
• 4.2 驗(yàn)證工具鏈及平臺40-42
• 4.3 基于可重構(gòu)硬件架構(gòu)的DIJKSTRA算法優(yōu)化與實(shí)現(xiàn)42-45
• 4.3.1 可重構(gòu)硬件架構(gòu)的DIJKSTRA算法優(yōu)化42-43
• 4.3.2 可重構(gòu)硬件架構(gòu)的DIJKSTRA算法的映射實(shí)現(xiàn)43-45
• 4.4 基于可重構(gòu)硬件架構(gòu)的TSP算法優(yōu)化與實(shí)現(xiàn)45-48
• 4.4.1 可重構(gòu)硬件架構(gòu)的TSP算法的優(yōu)化45-46
• 4.4.2 可重構(gòu)硬件架構(gòu)的TSP算法的實(shí)現(xiàn)46-48
• 4.5 本章小結(jié)48-49
• 5 可重構(gòu)硬件架構(gòu)的路徑規(guī)劃算法性能分析與比較49-64
• 5.1 實(shí)驗(yàn)驗(yàn)證平臺49-51
• 5.2 實(shí)驗(yàn)研究方法51-53
• 5.3 基于可重構(gòu)硬件架構(gòu)下的DIJKSTRA算法性能驗(yàn)證53-59
• 5.3.1 實(shí)驗(yàn)驗(yàn)證步驟53-56
• 5.3.2 實(shí)驗(yàn)結(jié)果分析與比較56-59
• 5.4 基于可重構(gòu)硬件架構(gòu)的TSP算法性能驗(yàn)證59-63
• 5.4.1 實(shí)驗(yàn)驗(yàn)證步驟59-61
• 5.4.2 實(shí)驗(yàn)結(jié)果分析與比較61-63
• 5.5 本章小結(jié)63-64
• 6 結(jié)束語64-66
• 6.1 論文工作總結(jié)64-65
• 6.2 問題與展望65-66
• 參考文獻(xiàn)66-69
• 作者簡歷69-71
• 學(xué)位論文數(shù)據(jù)集71

【相似文獻(xiàn)】

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

1 禹建麗,VALERIKroumov,成久洋之;機(jī)器人路徑規(guī)劃算法及其應(yīng)用(英文)[J];數(shù)學(xué)季刊;2002年03期

2 王力虎,張海洪;一種室內(nèi)自主清掃機(jī)器人的路徑規(guī)劃算法[J];機(jī)床與液壓;2005年07期

3 劉海;郭小勤;余得貴;;清潔機(jī)器人全覆蓋路徑規(guī)劃算法綜述[J];機(jī)電產(chǎn)品開發(fā)與創(chuàng)新;2008年06期

4 楊志曉;郭勝國;;基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃算法[J];微計(jì)算機(jī)信息;2008年20期

5 孫立光;史其信;;基于離散勢能場的行人路徑規(guī)劃算法研究[J];交通標(biāo)準(zhǔn)化;2009年23期

6 馬文輝;崔瑩;;云模型在機(jī)器人路徑規(guī)劃算法中的研究[J];知識經(jīng)濟(jì);2010年14期

7 馬占春;寧小美;;云進(jìn)化機(jī)器人路徑規(guī)劃算法[J];科技通報;2012年10期

8 陳書光;;機(jī)器人路徑規(guī)劃算法探討[J];商;2012年15期

9 王偉，儲林波，馬玉林;一種改進(jìn)的機(jī)器人路徑規(guī)劃算法[J];哈爾濱工業(yè)大學(xué)學(xué)報;1998年02期

10 寧志剛;;一種高效的機(jī)器人路徑規(guī)劃算法[J];科技致富向?qū)?2011年18期

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

1 汪永紅;劉小春;張有為;侯一凡;;嵌入式GIS中大區(qū)域路徑規(guī)劃算法研究[A];《測繪通報》測繪科學(xué)前沿技術(shù)論壇摘要集[C];2008年

2 原曉偉;任雪梅;;參數(shù)自調(diào)整的機(jī)器人路徑規(guī)劃算法[A];第二十三屆中國控制會議論文集（下冊）[C];2004年

3 涂自然;王維;梁以業(yè);禹建麗;;基于強(qiáng)化學(xué)習(xí)的自適應(yīng)變步長機(jī)器人路徑規(guī)劃算法[A];2003年中國智能自動化會議論文集（上冊）[C];2003年

4 雷東升;諸彤宇;;一種基于實(shí)時路況信息的動態(tài)路徑規(guī)劃算法[A];2008'中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（一）[C];2008年

5 史久根;徐勝生;;基于文化-粒子群算法的機(jī)器人路徑規(guī)劃算法[A];2011中國儀器儀表與測控技術(shù)大會論文集[C];2011年

6 王仲賓;魏闖先;田衛(wèi)東;周紅娟;;一種改進(jìn)的基于切線的機(jī)器人路徑規(guī)劃算法[A];計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展——全國第17屆計(jì)算機(jī)科學(xué)與技術(shù)應(yīng)用（CACIS）學(xué)術(shù)會議論文集（上冊）[C];2006年

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

1 彭飛;約束條件下的船舶裝配拆卸隨機(jī)采樣路徑規(guī)劃研究[D];華中科技大學(xué);2013年

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

1 王亞春;移動機(jī)器人路徑規(guī)劃算法研究[D];天津理工大學(xué);2015年

2 杜沅澤;人群動畫中融入情緒模型的實(shí)時路徑規(guī)劃算法研究[D];鄭州大學(xué);2015年

3 李駿豪;針對復(fù)雜環(huán)境的室內(nèi)路徑規(guī)劃算法的設(shè)計(jì)與實(shí)現(xiàn)[D];電子科技大學(xué);2014年

4 謝娟;路徑規(guī)劃算法的研究及應(yīng)用[D];電子科技大學(xué);2015年

5 劉軍強(qiáng);一種飛行器導(dǎo)航算法研究及其系統(tǒng)設(shè)計(jì)[D];西安電子科技大學(xué);2014年

6 張琪;分隊(duì)?wèi)?zhàn)術(shù)CGF路徑規(guī)劃算法研究[D];國防科學(xué)技術(shù)大學(xué);2013年

7 孫首兵;基于RFID技術(shù)的倉庫數(shù)字貨架的研究與開發(fā)[D];合肥工業(yè)大學(xué);2014年

8 王騰飛;3D打印技術(shù)中分層與路徑規(guī)劃算法的研究及實(shí)現(xiàn)[D];河北工業(yè)大學(xué);2015年

9 柏強(qiáng);基于可重構(gòu)架的動態(tài)網(wǎng)絡(luò)路徑規(guī)劃算法研究與實(shí)現(xiàn)[D];北京交通大學(xué);2016年

10 陳峰;環(huán)境搜索與路徑規(guī)劃算法的研究[D];吉林大學(xué);2012年

  本文關(guān)鍵詞：基于可重構(gòu)架的動態(tài)網(wǎng)絡(luò)路徑規(guī)劃算法研究與實(shí)現(xiàn)，，由筆耕文化傳播整理發(fā)布。

本文編號：329691