一種基於MIC協處理器的全網最短路徑規劃並行化方法與流程

2023-06-01 14:34:01

本發明涉及電子地圖導航的路徑規劃方法，尤其涉及一種基於MIC協處理器的全網最短路徑規劃並行化方法。

背景技術：
隨著國內城市化的發展，城市道路縱橫交錯，路網也變得非常的複雜。對於在城市出行的人們來說，如何能快速獲取路程起點和終點的最短路徑成為其迫切的需求。同時，由於通信技術、全球定位技術以及路網數據信息化的不斷發展，為人們的出行電子化導航提供了基本的必要條件。目前地圖導航行業使用的最短路徑規划算法多是基於Dijkstra或是其改進版，相應的時間複雜度為O(N2)或者O(NlogN)。當規劃的節點數N增長到成千上萬時，同時還要相應有大量的路徑規劃請求，實時的線上規劃幾乎變得不可實施。所以一般最短路徑規劃多採用線下的規劃預處理出所有節點之間的最短路徑，當有用戶請求時直接查詢相應的最短路徑。在線下最短路徑預處理過程中，當路網數據之中新增或者刪減一個節點或者一條線路時，都要重新計算全網的最短路徑列表。以四維地圖出品2013年的廣州市地圖為例，其路口數目達到了90000，道路數目達到了120000。根據實際測試每次更新全網節點的最小路徑數據單線程計算大約需要5天的時間。針對路徑規劃的時間效率的問題，王亞文等[一種動態搜索區域的最短路徑規划算法，計算機應用研究，2007]從限制每次動態規劃的區域入手，通過縮小路徑規劃的範圍來實現，不過該種方法只能針對線上實時的路徑規劃實施。對於線下的全網路徑規劃，不能通過限制區域實現。同樣，劉曉軍等[海量道路數據下的 最短路徑規劃效率，計算機系統應用，2010]也是通過估價函數快速過濾無效點和路段，折線簡化等方法來實現線上實時路徑規劃。根據專利文獻檢索，公開號為CN102175252A的專利文獻提出了基於分級道路網數據的分布式多級道路的動態聯合路徑規劃方法；公布號為CN103278168A的專利文獻提出了通過數據挖掘技術，利用新聞、微博、實時上報交通信息以及歷史規律信息挖掘出交通熱點，進而執行交通熱點規避的路徑規劃；公開號為CN101944095A的專利文獻提出了一種優化的Dijkstra方法來實現簡化相應的計算。綜合上述資料，可以看出針對線下全網節點的路徑規劃並行計算方法尚未有被現有技術公開。

技術實現要素：
針對現有技術的缺點，本發明的目的是提供一種基於MIC協處理器的全網最短路徑規劃並行化方法，解決了現有的最短路徑規劃線下預處時間效率低，不能及時響應城市快速擴張以及城市交通意外等帶來的路網連結規律的變化的問題。為了實現上述目的，本發明的技術方案為：一種基於MIC協處理器的全網最短路徑規劃並行化方法，所述全網包括N個節點，該方法包括如下步驟：（1）將每個節點相對全網其他節點定義為一個不可再分的單元，N個節點構成的全網有N個單元任務；（2）以K個單元任務為一個任務包，可以創建P=N/K個任務包，對於N不能被K整除的情況，創建P=[N/K]+1個任務包，[N/K]表示取整數部分，每個線程在拿到某一任務包後，將分成K次循環依次執行其中的K個單元任務；（3）對於所創建的P個任務包在L個線程之間進行任務調度時，L個線程初始會依次各拿到一個任務包，此時未處理的任務包為P-L個，當其中的某個線程處理完自己的任務包時，則會請求新的任務包；調度時利用全局變量g_num來表徵目前未處理任務包數目，每個線程通過互斥鎖的方式來爭搶任務包資源，當某個線程互斥鎖加鎖成功則表示其搶到了相應序號的任務包，同時將任務包數目g_num減一，再解除互斥鎖，完成一次加解鎖過程的線程根據 自己所搶到的序號，在相應內存地址上讀取數據，依次執行完該任務包中的K個單元任務，當線程檢查到任務包數目g_num變成0時，則表示所有任務包都已經處理完畢，相應線程執行退出操作；（4）當全網節點都處理完畢時，輸出路徑規劃的結果並下傳全網路徑規劃數據到主機系統，以供路徑規劃在線服務程序查詢。與現有技術相比，本發明利用大量的線程加速全網路徑規划算法的執行，同時本發明提出了全網路徑規劃並行化實現動態任務調度的方式，進一步的優化了程序的執行過程，提升了並行化執行的效率，最後本發明又利用MIC的native執行模式，在路網數據以及路徑規劃結果不超過MIC的內存時，可以比較方便的應用MIC協處理器實施相應的加速，很好的滿足了中小城市城域內智能交通的路徑規劃需求。附圖說明下面結合附圖對本發明作進一步的詳細說明。圖1為本發明在在MIC上執行的程序流程圖；圖2為本發明的動態任務調度示意圖；圖3為MIC線程內動態任務調度流程。具體實施方式MIC是由Intel公司於2012年12月發布的基於x86架構的協處理器，其由60顆處理核心構成，雙精度計算峰值計算能力達到1TFlops，其採用了與CPU相同的x86架構，支持的offload、native等執行模式。本發明以Dijkstra最短路徑規划算法為基礎，下面是Dijkstra的全網節點的路徑規劃說明：Dijkstra每次計算解決的路網中某個節點A到其他節點的最短路徑；對於全網N個節點之間的最短路徑規劃需要調用N次的Dijkstra計算；由於現實路網中有道路單行限制，使得每個節點到其他節點的最短路徑需要重新計算，而不能直接利用之前的已經優化過的結果來降低相應的計算量。本發明的全網最短路徑規劃的並行化方法包括如下步驟：（1）全網節點最短路徑規劃並行化設計。以N個節點構成的路網為例，將每個節點相對全網其他節點基於Dijkstra算法的最短路徑規劃定義為一個不可再分的單元，每個單元任務的執行都需要一個MIC的線程去完成；N個節點構成的路網圖就有N個單元任務需要完成，將K個單元任務合成一個任務包交給MIC的一個線程去執行。（2）任務包的創建。對於N個節點的路網，當以K個執行單元為一個任務包，共計可以創建P=N/K個任務包，對於N不能被K整除的情況，創建P=[N/K]+1個任務包，[N/K]表示取整數部分，每個MIC的線程在拿到某個任務包後，將會分成K次循環依次執行其中的K個單元任務。（3）任務包的調度。對於所創建的P個任務包在L個MIC線程之間進行任務調度時，將按照動態任務調度的原則執行調度,L個MIC線程初始會依次各拿到一個任務包，共計L個任務包，此時未處理的任務包為P-L，當其中的某個MIC線程處理完自己的任務包時，則會請求新的任務包。調度的具體實現是利用全局變量g_num來表徵目前未處理任務包數目，每個線程通過互斥鎖的方式來爭搶任務包資源。當某個線程互斥鎖加鎖成功則表示其搶到了相應序號的任務包，同時將任務包數目g_num減一，再解除互斥鎖。完成一次加解鎖過程的MIC線程就會根據自己所搶到的序號，在相應內存地址上讀取數據，依次執行完該任務包中的K個單元任務。當MIC線程檢查到任務包數目g_num變成0時，則表示所有任務包都已經處理完畢了，相應MIC線程就會執行退出操作。（4）MIC的native模式執行。由於MIC是帶有自己作業系統的協處理器，其可以作為一個節點來執行並行計算。在MIC的native執行模式中，將編譯完成的全網路徑規劃程序以及路網數據上傳到MIC的tmp目錄，然後啟動相應程序，等全網路徑規劃程序計算完成後，下傳全網路徑規劃數據到主機系統，以供路徑規劃在線服務程序查詢。請參閱圖1，當將源程序利用intel編譯器的-mmic選項編譯後，上傳可執行程序以及相應數據到MIC上，執行流程解釋如下：（1）讀入路網數據。該模塊將貯存在MIC設備內存中的數據讀到程序可見的內存空間中，同時將路網原始數據轉換成鄰接表存儲。（2）創建線程。利用pthread庫創建線程，此處根 據MIC卡的具體型號不同，可以創建不同量的線程數。以XeonPhi3110為例，最多可以創建224個線程。線程創建的pthread庫必須是也經過了-mmic重新編譯的針對MIC架構的庫，否則程序運行將會失敗。（3）調度任務。主要是實現線程之間動態任務調度過程，在任務調度過程中會創建全局變量來表徵未處理的任務包數目，動態任務調度過程代碼則是根據該全局變量實現對未完成任務數的監測，任務調度室利用互斥鎖來實現線程之間計算任務的動態分配。（4）完成所有節點的計算。針對全網的每個節點都計算其到其他節點的最短路徑，當全網節點都計算完畢時，則可以退出任務調度循環，執行線程退出模塊，最後輸出路徑規劃的結果。（5）當程序執行完畢時則下傳全網路徑規劃結果，以供線上查詢使用。請參閱圖2，此處以3個線程9個任務的調度為例詳細說明該動態的調度過程，圖中箭頭表示時間軸，初始時刻線程T0/T1/T2分別爭搶到了任務包1/2/3。在執行過程中由於每個線程的執行任務時間並不是精確相等，故而完成任務的時間有先後。T2線程優先完成任務，其就搶到了任務包4，T0/T2的情況同理。相比靜態的任務劃分而言，當調度任務成本小於線程等待成本時，動態劃分的方式能相對提升並行化的效率。同時動態的任務劃分方式對於程序的擴展性也非常有利，它能根據實際運行情況自動調整。請參閱圖3，在,每個線程的內部，首先通過互斥鎖來鎖定全局變量，待到計算出其所爭搶到的任務再將互斥鎖解鎖。當捕獲計算任務後，調用Dijkstra循環處理。最後再次檢查是否還有未處理完的計算任務：如果還有未處理完成的任務，則跳轉到爭搶任務的部分，繼續加鎖捕獲計算任務；如果沒有剩餘任務了，則執行線程退出。雖然本發明以較佳實施例揭露如上，但並非用以限定本發明實施的範圍。任何本領域的普通人員，在不脫離本發明的範圍內，作些改進，即凡是依照本發明所做的同等改進，應為本發明的範圍所涵蓋。