Parallelresearch And Implement Of Network Maximun Flow Algorithm Based On BSP Model

Maximum flow problem is a very important basic problem in graph theory and has very important application in many areas such as the basic theory of graph theory selecting express corporate center traffic assignment image segmentation and finding social networking web communities. However,the arriving of the internet area of big date brings new difficulties and challenges for many traditional computing problems.the traditional serial solving network maximum flow algorithm is now difficult to meet the new computing requirements.Finding the parallel algorithm for computing the maximum flow is a new topic which the development of the internet brings us.BSP parallel computing model is a simple, practical and very important computing model in the field of parallel computing.BSPparallel computing model has good usability, scalability and reliability. BSP model is a clear and logical framework and has a good application in the IT industry.So BSP parallel computing model is a simple, practical and very important computing model.In the boom of cloud computing research,BSP model has a new application direction.In this thesis,we have a depth and fruitful research in parallel computing maximum flow based on BSP parallel computing model. The main research work is as follows.First,we conducted in-depth research on the basis algorithms ofnetwork maximum flow.We select the push-relabel algorithm as the basic algorithm. BSP model is selected as the base model of parallel computation.Second,based on BSP parallel computing model,through the modular programming we designed and implementedparallel calculation engine suitable for graph computing.We decomposed the data on parallel for computing and proposed a new data partitioning strategy by two phases and a new strategy in processing cross boundary.Third,we designed the calculation stepsin superstep and optimized the calculation steps for the algorithm.Based on the BSP model we implemented the push-relabel algorithm in parallel.In this thesis,we tested the results on the parallel computing in two aspects under laboratory conditions.First,we contrasted the result for subgraph segmentation on two phase diagram data partitioning strategy and hash strategy.The result reflected that the two phase diagram data partitioning strategy is better than the hash strategy.Second,we tested the parallel implementation in speed ratio and parallelism.We proved the correctness of the parallel computing and it has good speedup and parallelism on the performance.