Two-stage distributed parallel algorithm with message passing interface for maximum flow problem

详细信息    查看全文

• 作者：Jincheng Jiang ; Lixin Wu
• 关键词：Distributed ; Parallel algorithm ; Maximum flow ; Message passing interface ; Two ; stage strategy
• 刊名：The Journal of Supercomputing
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：71
• 期：2
• 页码：629-647
• 全文大小：1,604 KB
• 参考文献：1. Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms and applications. Prentice-Hall, Englewood Cliffs
  2. Nagy N, Akl SG (2003) The maximum flow problem: a real-time approach. Parallel Comput 6(29):767-94 CrossRef
  3. Dinic EA (1970) Algorithm for the solution of a problem of maximal flow in networks with power estimation. Soviet Math Doklady 11:1277-280
  4. Ahuja RK, Orlin JB (1991) Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems. Nav Res Log 3(38):413-30 CrossRef
  5. Goldberg AV, Tarjan RE (1988) A new approach to the maximum flow problem. J ACM 4(35):921-40 CrossRef
  6. Hochbaum DS (2008) The pseudoflow algorithm: a new algorithm for the maximum-flow problem. Oper Res 4(56):992-009 CrossRef
  7. Boykov Y, Kolmogorov V (2004) An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans Pattern Anal 9(26):1124-137 CrossRef
  8. Dong JY, Li W, Cai CB, Chen Z (2009) Draining algorithm for the maximum flow problem, 2009 WRI International Conference on Communications And Mobile Computing: CMC 2009, Washington DC, IEEE Computer Society, vol 3, pp 197-00
  9. Goldberg AV (2008) The partial augment-relabel algorithm for the maximum flow problem. In: Proceedings 16th annual European symposium. Algorithms-Esa 2008, pp 466-77
  10. Asano T, Asano Y (2000) Recent developments in maximum flow algorithms. J Oper Res Soc Jpn 1(43):2-1 CrossRef
  11. Shiloach Y, Vishkin U (1982) An O(Logn) parallel connectivity algorithm. J Algorithm 1(3):57-7 CrossRef
  12. Johnson DB (1987) Parallel algorithms for minimum cuts and maximum flows in planar networks. J ACM 4(34):950-67 CrossRef
  13. Barbosa VC (1996) An introduction to distributed algorithms. MIT Press, Cambridge
  14. David AB, Vipin S (2005) A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic. In: Proceeding of 18th ISCA international conference on parallel and distributed computing systems. Las Vegas, NV, pp 41-8
  15. Hong B, He ZY (2011) An asynchronous multithreaded algorithm for the maximum network flow problem with nonblocking global relabeling heuristic. IEEE Trans Parallel Distr 6(22):1025-033 CrossRef
  16. Alonso P, Cortina R, Martinez-Zaldivar FJ, Ranilla J (2011) Neville elimination on multi- and many-core systems: OpenMP. MPI CUDA J Supercomput 2(58):215-25 CrossRef
  17. Vineet V, Narayanan PJ (2008) CUDA cuts: fast graph cuts on the GPU. In: 2008 IEEE computer society conference on computer vision and pattern recognition workshops, Anchorage, vols 1-, pp 1070-077
  18. He Z, Hong B (2010) Dynamically tuned push-relabel algorithm for the maximum flow problem on cpu-gpu-hybrid platforms. In: IEEE international symposium on parallel and distributed processing, Atlanta, pp 19-3
  19. Jian LH, Wang C, Liu Y, Liang SS, Yi WD, Shi Y (2013) Parallel data mining techniques on Graphics Processing Unit with Compute Unified Device Architecture (CUDA). J Supercomput 3(64):942-67 CrossRef
  20. Park SY, Hariri S (1997) A high performance message-passing system for network of workstations. J Supercomput 2(11):159-79 CrossRef
  21. Delong A, Boykov Y (2008) A scalable graph-cut algorithm for N–D grids. In: IEEE conference on computer vision and pattern recognition, Anchorage, pp 946-53
  22. Shekhovtsov A, Hlavac V
• 作者单位：Jincheng Jiang (1)
  Lixin Wu (2)
  
  1. Academy of Disaster Reduction and Emergency Management, Beijing Normal University, No. 19, XinJieKouWai St., HaiDian District, Beijing, 100875, China
  2. IoT Perception Mine Research Center, China University of Mining and Technology, No. 1, Daxue Road, Quanshan District, Xuzhou, Jiangsu, 221008, China
  
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers and Interpreters
  Processor Architectures
  Computer Science, general
  
• 出版者：Springer Netherlands
• ISSN：1573-0484

文摘

Maximum flow is one of the important and classical combinatorial optimization problems. However, the time complexity of sequential maximum flow algorithms remains high. In this paper, we present a two-stage distributed parallel algorithm (TSDPA) with message passing interface to improve the computational performance. The strategy of TSDPA has two stages, which push excess flows separately along cheap and expensive paths identified by a new distance estimate function. In TSDPA, stage 1 enhances the parallel efficiency by omitting high-cost paths and decentralizing calculations, and stage 2 guarantees the achievement of an optimal solution through divide-and-conquer method. The experimental test demonstrates that TSDPA runs 1.2-5.5 times faster than sequential algorithms and is faster than or almost as fast as the H_PRF and Q_PRF codes.