CCF: AF: Small: Algorithms, Parallelism and Communication Efficiency in Shortest Path Computations

CCF：AF：Small：最短路径计算中的算法、并行性和通信效率

基本信息

批准号：
2008241
负责人：
Vijaya Ramachandran
金额：
$ 35万
依托单位：
University of Texas at Austin
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-08-01 至 2024-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008241&HistoricalAwards=false
关键词：
CCF AF Small Algorithms Parallelism

项目摘要

Computing shortest paths in graphs is one of the most fundamental, widely-studied and widely-used optimization problems on graphs. Classical shortest-path algorithms that have been widely used in the past on smaller graphs are no longer effective on massive graphs that arise in communication, social, and biological networks, the world wide web, and other applications. This project will investigate developing correct and efficient techniques and algorithms for shortest paths to run on currently available parallel-computing systems in a communication-efficient manner. The project will address fundamental and theoretical issues that underpin computation of shortest paths in graphs while also addressing the challenges related to designing correct and efficient algorithms for modern computing platforms. These results will expand the understanding of the algorithmic complexity of this very fundamental problem of computing shortest paths in graphs.In more detail, the project will investigate the design of efficient shortest-path algorithms under settings that include distributed computations with communication along graph edges, parallel shared-memory PRAM computations, and multithreaded computations with caching. The project will study the related problem of developing efficient dynamic algorithms for shortest paths, where the goal is to update shortest paths when the graph changes over time. Massive graphs that arise in practice are almost invariably sparse, where the number of edges is much smaller than quadratic in the number of vertices. For this reason, the project will focus on developing tools and techniques for correct and efficient shortest path algorithms for sparse graphs, and will investigate the design of efficient and scalable data structures to aid the efficient computation of shortest paths on such graphs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

计算图中的最短路径是图上最基本、广泛研究和广泛使用的优化问题之一。过去在较小图上广泛使用的经典最短路径算法对于通信、社交和生物网络、万维网和其他应用程序中出现的大规模图不再有效。该项目将研究开发正确且有效的技术和算法，以实现最短路径，以有效通信的方式在当前可用的并行计算系统上运行。该项目将解决支撑图中最短路径计算的基本和理论问题，同时解决与为现代计算平台设计正确且高效的算法相关的挑战。这些结果将扩展对计算图中最短路径这一非常基本问题的算法复杂性的理解。更详细地说，该项目将研究在包括沿图边缘通信的分布式计算的设置下有效的最短路径算法的设计，并行共享内存 PRAM 计算以及带有缓存的多线程计算。该项目将研究开发有效的最短路径动态算法的相关问题，其目标是当图随时间变化时更新最短路径。实践中出现的大规模图几乎总是稀疏的，其中边的数量远小于顶点数量的二次方。因此，该项目将重点开发用于稀疏图的正确有效的最短路径算法的工具和技术，并将研究高效且可扩展的数据结构的设计，以帮助高效计算此类图上的最短路径。该奖项反映了通过使用基金会的智力价值和更广泛的影响审查标准进行评估，NSF 的法定使命被认为值得支持。