并行系统上大规模图中最短路径实时计算研究

项目名称： 并行系统上大规模图中最短路径实时计算研究

项目编号： No.61303047

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 周英华

作者单位： 中国科学技术大学

项目金额： 25万元

中文摘要： 计算图上两点间的最短路径问题是计算机学科里一个经典问题，在许多问题中有着重要应用, 如物流规划、交通模拟、行车导航、社交网络等。随着应用需求和信息技术的发展，对于求解最短路径问题提出了新的要求。这些要求体现在以下三个方面：(1) 大规模图数据处理；(2) 图数据的动态性；(3) 计算的实时性要求。本项目针对最短路径问题求解的最新需求，结合并行计算平台的发展，在并行计算的系统平台上（包含共享存储的多核系统、分布存储的机群系统），设计、分析并实现新型高效并行算法。通过并行系统建模和应用程序建模的手段，分析并行系统与应用特性之间的关联关系，建立定量化性能模型，更好的指导并行算法的设计、实现和优化。本项目的研究成果将为大规模图中具有实时性要求的最短路径问题求解相关应用提供有效的支持。

中文关键词： 实时；路径；并行；建模；图

英文摘要： Computing shortest paths in graphs is one of the most fundamental and well-studied problems in computer science. There are classical applications for this problem including logistics planning, finding routes in road and public transportation networks, social networks and so on. These applications raise new requirements as the rising of technical development. These new requirements motivate the problem from the following three aspects: (1) large scale graph data processing, (2) dynamical graph data, (3) real-time computing. This proposal will focus on real-time computing of shortest path problem on parallel computing platform(including multi-core with shared memory and cluster with distributed memory). We will design, analyze and implement new high efficient parallel algorithms. By modelling of parallel systems and application program, we will build quantitative performance model based on parallel system and application, analyze the relationship between parallel system and application characters. The performance model will be beneficial to the design, implementation and optimization of related parallel algorithms. Our research output can be applied usefully in practical applications related to the real-time computing of shortest path problem in large-scale graph.

英文关键词： real-time；path；parallel；modelling；graph