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

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

2、增加;例如:紐約市路網(wǎng)地圖就包含了26萬(wàn)個(gè)節(jié)點(diǎn)，73萬(wàn)條邊.面對(duì)大規(guī)模的路網(wǎng)數(shù)據(jù)量，傳統(tǒng)的最短路徑規(guī)劃算法在求解時(shí)耗時(shí)較長(zhǎng)，不能滿足應(yīng)用中的實(shí)時(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)勢(shì)。它與AS

3、IC(Application SpecificIntegrated Circuit，專用集成電路)相比，可重構(gòu)處理器具有靈活多變的硬件架構(gòu)，來(lái)適應(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)為陣列形式，再通過(guò)對(duì)經(jīng)典算法的任務(wù)劃分映射，得到相對(duì)應(yīng)的數(shù)據(jù)流圖和調(diào)度表。這樣就實(shí)現(xiàn)了在可重構(gòu)硬件陣列處理單元上對(duì)算法的映射實(shí)現(xiàn)，最后把優(yōu)化后的算法在

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