基于分布式层次图的最大流混合并行算法研究

The maximum flow problem is a class of important combinatorial optimization problem in large-scale graphs, and the existing parallel algorithms do not make full use of the context information of multiple computing steps, resulting in limited acceleration. .Concentrating on maximum flow oriented graph partitioning and preprocessing, our research leverages multiple parallel computing models and frameworks, focuses on distributed hierarchical graph based parallel algorithms for maximum flow problem. It includes: distributed hierarchical graph oriented preprocessing, which constructs effective hierarchical structure upon graph partitions, thus reduces computational complexity of following steps; the acceleration methods for offline maximum flow problem, which pre-calculate and store historical results of sub-graph into index structure, leverage multiple parallel computing models to get efficient hybrid parallel algorithms; the acceleration methods for online maximum flow problem, which efficiently adjust the index structure to respond to local graph changes, use incremental calculation to ensure online computing efficiency..Our research is expected to obtain innovative acceleration methods for maximum flow preprocess and hybrid parallel algorithm. The research results will be used to accelerate the solving of maximum flow problem in large-scale graph, and provide basic models and algorithms for Big Data analysis and processing.

最大流问题是大规模图上一类重要的组合优化问题，现有并行算法未充分利用多个计算环节中的上下文信息，加速效果受限。本项目以面向最大流的图划分和预处理为突破点，组合利用多种并行计算模型和框架，研究基于分布式层次图的最大流混合并行算法，具体内容包括：结合分布式层次图的大规模图预处理，构建层次化图结构并进行有效划分，降低后续处理的计算复杂度；最大流离线处理加速方法，利用索引存储局部图的历史计算结果，并结合多种计算模型设计高效混合并行算法；最大流在线处理加速方法，针对局部图变化高效调整索引，增量求解保证在线计算效率。本项目预期在最大流预处理和并行算法设计上有关键方法的创新，研究成果有助于提高大规模图上最大流问题族的求解效率，并为相关的大数据分析处理提供基础模型和算法支撑。

本项目主要研究大规模图上一类重要的组合优化问题-最大流问题，现有并行加速算法仅使用通用的图划分原则，主要集中于已有串行算法的并行化，加速效果受限。本项目以面向最大流的图划分和预处理为突破点，充分挖掘最大流问题和已有计算过程的特点，研究适用于分布式环境的最大流混合并行算法，具体内容包括基于双连通分量的最大流计算加速方法、基于简单路径局域性的最大流计算加速方法、基于贝尔曼优化原则的最短路径计算加速方法、基于树割映射的最小割计算加速方法、基于二界图的最大流计算加速方法以及最大流求解相关的底层计算资源调度方法。最后基于真实和仿真的数据及实验平台，评价和完善相关理论和算法实现。