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

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.

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

针对大规模图上最短路径问题的最新求解需求，结合当前研究现状和自身的研究基础，为得到高效的问题求解算法，项目组开展了三个方面的研究工作：(1) 新型最短路径算法的计算特性建模研究；(2) 高效并行算法的设计、分析与实现；(3)并行程序的性能分析与定量化建模。项目在两个方面取得了阶段性的进展。(1)在对最短路径求解算法的串行算法进行充分调研的基础上，利用图中代表元的系列处理方法，改进了目前已知的最好的同类算法。在基于压缩技术的路径查询问题研究中，通过采用新的压缩技术，将之前路径数据的压缩比进行进一步的优化，为在实际应用中应用提供了基础，有可能在特定计算平台上达到实时性的性能要求。(2)在传统集群系统的平台和多核平台上上进行了路径计算问题的研究，开展了时间限制下动态路网路径规划算法的研究与实现。对于基于图划分的路径计算方法，开展并行化和优化的研究，通过实验验证和理论分析说明了新方法的有效性。对于基于预处理的路径计算方法，通过并行化的技术，有效减少了预处理部分的计算时间，达到了接近线性的加速比。项目研究成果已发表学术论文13篇（其中EI索引10篇、SCI索引2篇），申请国家发明专利5项，培养研究生8名。对于路径计算研究的部分成果，已经在中国科学技术大学智慧校园建设得到应用。有关并行系统性能建模的部分，有望在进一步完善后，在中国科学技术大学超级计算中心进行应用，以优化计算系统的整体性能。