《並行系統上大規模圖中最短路徑實時計算研究》是依託中國科學技術大學，由周英華擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：並行系統上大規模圖中最短路徑實時計算研究
- 項目類別：青年科學基金項目
- 項目負責人：周英華
- 依託單位：中國科學技術大學
中文摘要,結題摘要,
中文摘要
計算圖上兩點間的最短路徑問題是計算機學科里一個經典問題，在許多問題中有著重要套用, 如物流規劃、交通模擬、行車導航、社交網路等。隨著套用需求和信息技術的發展，對於求解最短路徑問題提出了新的要求。這些要求體現在以下三個方面：(1) 大規模圖數據處理；(2) 圖數據的動態性；(3) 計算的實時性要求。本項目針對最短路徑問題求解的最新需求，結合併行計算平台的發展，在並行計算的系統平台上（包含共享存儲的多核系統、分布存儲的機群系統），設計、分析並實現新型高效並行算法。通過並行系統建模和應用程式建模的手段，分析並行系統與套用特性之間的關聯關係，建立定量化性能模型，更好的指導並行算法的設計、實現和最佳化。本項目的研究成果將為大規模圖中具有實時性要求的最短路徑問題求解相關套用提供有效的支持。
結題摘要
針對大規模圖上最短路徑問題的最新求解需求，結合當前研究現狀和自身的研究基礎，為得到高效的問題求解算法，項目組開展了三個方面的研究工作：(1) 新型最短路徑算法的計算特性建模研究；(2) 高效並行算法的設計、分析與實現；(3)並行程式的性能分析與定量化建模。項目在兩個方面取得了階段性的進展。(1)在對最短路徑求解算法的串列算法進行充分調研的基礎上，利用圖中代表元的系列處理方法，改進了目前已知的最好的同類算法。在基於壓縮技術的路徑查詢問題研究中，通過採用新的壓縮技術，將之前路徑數據的壓縮比進行進一步的最佳化，為在實際套用中套用提供了基礎，有可能在特定計算平台上達到實時性的性能要求。(2)在傳統集群系統的平台和多核平台上上進行了路徑計算問題的研究，開展了時間限制下動態路網路徑規划算法的研究與實現。對於基於圖劃分的路徑計算方法，開展並行化和最佳化的研究，通過實驗驗證和理論分析說明了新方法的有效性。對於基於預處理的路徑計算方法，通過並行化的技術，有效減少了預處理部分的計算時間，達到了接近線性的加速比。項目研究成果已發表學術論文13篇（其中EI索引10篇、SCI索引2篇），申請國家發明專利5項，培養研究生8名。對於路徑計算研究的部分成果，已經在中國科學技術大學智慧校園建設得到套用。有關並行系統性能建模的部分，有望在進一步完善後，在中國科學技術大學超級計算中心進行套用，以最佳化計算系統的整體性能。
