基于BSP模型的网络最大流算法的并行化研究与实现

发布时间：2018-04-28 17:36

本文选题：网络最大流 + 并行计算　；参考：《电子科技大学》2014年硕士论文

【摘要】：网络最大流问题是图论有向图部分的一个非常重要的基本问题,在图论研究领域有着非常重要的理论意义。同时网络最大流在快递企业中心选址、交通分配、图像分割、社交网络Web社团发现等方面也有非常重要的实际应用。互联网大数据时代的到来给很多传统的计算问题带来了新的困难和挑战,传统的求解网络最大流的串行算法目前已经难以适应当前计算数据与应用的要求。研究网络最大流算法的并行化求解是互联网发展对我们提出的新要求。BSP并行计算模型是并行计算领域的一个简洁,实用且非常重要的计算模型。其具有清晰的逻辑组成结构,严谨的并行控制机制和良好的实用性,可扩展性与可靠性。在云计算的研究热潮下,BSP模型在云计算领域又有了新的应用方向。本文对基于BSP模型实现并行化求解网络最大流问题进行了深入且卓有成效的研究。主要的研究工作如下:①对求解网络最大流的基础算法进行了广泛深入的研究,并选取Push-Relabel算法作为并行化实现的基础算法,选定BSP并行计算模型作为并行计算的基础模型。②基于BSP并行计算模型,通过模块化编程设计并实现了一个适用于图计算问题的并行计算引擎。③对Push-Relabel算法,在计算的数据上进行了并行化设计,提出了一种新的两阶段图数据划分策略和图分割跨界边处理策略。④对Push-Relabel算法,在计算步骤上进行了超步化设计,优化了超步中的算法计算步骤,并基于BSP并行计算引擎,编程实现了并行化求解网络最大流。本文最后在实验室条件下,通过仿真实验测试对并行化求解网络最大流进行了两个方面的结果测试。①对两阶段图数据划分策略与Hash图分割的子图分割效果进行了对比测试,测试结果良好反应了两阶段图数据划分策略在图分割结果上的改进效果。②对并行计算实现在加速比和并行度等方面进行了性能测试,通过理论和数据两个方面对测试数据进行了分析和论证,验证了该并行化计算在实验室环境下的良好计算性能。
[Abstract]:The maximum flow problem of network is a very important basic problem in graph theory digraph. It has very important theoretical significance in the field of graph theory research. At the same time, the maximum flow of network has very important practical applications in the location of the express enterprise center, traffic assignment, image segmentation, and the discovery of social network Web community. According to the arrival of the times, new difficulties and challenges have been brought to many traditional computing problems. The traditional serial algorithm for solving the maximum flow of network is difficult to meet the requirements of current computing data and applications. The parallel computing of the maximum flow algorithm of the network is a new.BSP parallel computing model proposed by the Internet development. It is a concise, practical and very important computing model in the field of parallel computing. It has a clear logical structure, strict parallel control mechanism and good practicability, scalability and reliability. In the upsurge of cloud computing, the BSP model has a new application direction in the field of cloud computing. This paper is based on the BSP model. The main research work is as follows: (1) the basic algorithm for solving the maximum flow of the network is studied extensively, and the Push-Relabel algorithm is selected as the basic algorithm of the parallel implementation, and the BSP parallel computing model is selected as the basis of parallel computing. Based on the BSP parallel computing model, a parallel computing engine is designed and implemented by modularized programming. (3) a parallel design for the Push-Relabel algorithm is carried out on the calculated data, and a new two stage graph data partition strategy and a Graph Segmentation cross boundary processing strategy are proposed. (4) to Push-Rel The Abel algorithm has carried out the super step design in the calculation step, optimized the algorithm calculation steps in the super step, and based on the BSP parallel computing engine, the programming realized the parallelization to solve the maximum flow of the network. Finally, in the laboratory conditions, the results of two aspects of the maximum flow of the parallel computing network were tested by the simulation test. (1) the comparison test of the two stage map data partition strategy and the sub graph segmentation effect of the Hash graph segmentation is carried out. The test results well reflect the improvement effect of the two stage map data partition strategy on the image segmentation results. Secondly, the performance test is carried out on the speedup ratio and the parallelism of parallel computing, through two parties of theory and data. The analysis and demonstration of the test data verify the good computing performance of the parallel computing in the laboratory environment.

【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：O157.5;TP338.6

【参考文献】