基于可重構架構的動態(tài)網(wǎng)絡路徑規(guī)劃算法研究與實現(xiàn).pdf

1、最短路徑規(guī)劃問題是一個經(jīng)典的數(shù)學問題，廣泛應用于多種與路徑規(guī)劃技術相關的領域。例如:科技領域中的無人駕駛汽車、無人機、智能機器人、巡航導彈打擊目標與導彈防御系統(tǒng);日常生活領域中的智能汽車導航、地理信息系統(tǒng);決策調(diào)控領域中的物流規(guī)劃領域邊際問題和資源合理分配問題;通信技術領域中的路由規(guī)劃問題等。隨著人類社會的發(fā)展和科技的不斷進步，社會近百年的科技成就大大超過了人類社會以往幾千年的成就總和。現(xiàn)代城市規(guī)模之巨大，路網(wǎng)之復雜，處理的數(shù)據(jù)量也隨之

2、增加;例如:紐約市路網(wǎng)地圖就包含了26萬個節(jié)點，73萬條邊.面對大規(guī)模的路網(wǎng)數(shù)據(jù)量，傳統(tǒng)的最短路徑規(guī)劃算法在求解時耗時較長，不能滿足應用中的實時性要求?？芍貥嬏幚砥髋cGPP（General Purpose Processor,通用處理器）相比，可重構計算架構的數(shù)據(jù)并行性度高，數(shù)據(jù)處理能力強，它不依賴于指令流的數(shù)據(jù)處理方式，而是基于數(shù)據(jù)流的并行處理，在算法的合適映射下，可以充分挖掘路徑規(guī)劃算法并行度高的特點，發(fā)揮其并行處理的優(yōu)勢。它與AS

3、IC(Application SpecificIntegrated Circuit，專用集成電路)相比，可重構處理器具有靈活多變的硬件架構，來適應軟件層次上改變相關的運算，從而適應不同的算法。
　　本文利用可重構技術的硬件架構，從經(jīng)典的路徑網(wǎng)絡規(guī)劃算法特點出發(fā)，得到可重構體系基本機構為陣列形式，再通過對經(jīng)典算法的任務劃分映射，得到相對應的數(shù)據(jù)流圖和調(diào)度表。這樣就實現(xiàn)了在可重構硬件陣列處理單元上對算法的映射實現(xiàn)，最后把優(yōu)化后的算法在

4、可重構硬件平臺的執(zhí)行，并對其性能進行驗證。這樣設計方式可實現(xiàn)對不同算法的硬件重復利用，而且其設計流程同樣適用于其它的網(wǎng)圖領域。主要內(nèi)容包括：⑴提出基于可重構技術的路徑規(guī)劃算法加速處理方法;利用可重構硬件平臺的動態(tài)可配置性與并行性，分別結合經(jīng)典Dijkstra算法和TSP算法，得到了一種針對路徑規(guī)劃算法的新型加速處理方法。⑵在可重構硬件架構平臺上完成了Dijkstra算法和TSP算法的實現(xiàn)和驗證，與通用計算平臺相比，分別獲得了2.1倍與3