GPU-기반 MPM 최대 유량 계산
GPU-based MPM Maximum Flow Computing
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
최대유량 계산은 대표적인 그래프 최적화문제로서, 교통, 통신, 전기 네트워크, 병렬기기 스케쥴링, 이미지 프로세싱 등에서 활용되고 있는 문제이다. 최대유량 계산은 높은 시간복잡도가 불가피하기 때문에 그래프 크기가 커질수록 효율성 향상은 중요한 이슈이다. 하지만 현재까지 개발된 소수의 GPU 기반 병렬 처리 연구들조차 로컬 연산 기반의 Push-Relabel 알고리즘 및 휴리스틱 개발에만 집중되어 왔다. 본 논문은 대표적인 유량 증가 알고리즘인 MPM 알고리즘의 병렬 구현 기법을 제안한다. Solomon이 구현한 GPU 기반 MPM 알고리즘을 개선하기 위해 두 가지 병렬 처리 기법-워프(Warp) 단위 구현 기법과 레벨별 정점 리스트를 활용한 CPU 컨트롤의 효율적 감소-을 구현했으며, 이를 통해 대부분의 입력 데이터에서 성능이 크게 향상되었음을 보인다.
Abstract
The maximum flow problem is a problem of obtaining the maximum flow amount that can be sent from a start point to an end point in a flow network given capacity for each edge. In many application areas such as transportation, communication, electric networks, parallel device scheduling and image processing, many problems can be modeled as optimization problems in flow networks. Thus the maximum flow problem is a representative graph optimization problem and is used as a subroutine in various minimum cost maximum flow problems. Since the calculation of the maximum flow inevitably requires high time-complexity, efficiency improvement becomes more and more important issue as the graph size increases and the graph structure becomes more complex. However, even few GPU-based parallel processing studies developed so far have focused only on the development of local-computation-based Push-Relabel algorithm and its heuristics. To our best knowledge, the only GPU-based study on augmenting flow approaches is the Solomon’s implementation of MPM algorithm. Therefore we propose two parallel computing techniques for optimizing the GPU-based MPM algorithm implemented by Solomon: implementation technique based on WARP unit for graph algorithms and CPU control reduction using a vertex list per level. By performance comparison on 13 types of experimental graph data sets, we empirically prove that the proposed parallel processing techniques improve the Solomon’s MPM implementation significantly.
참고문헌 (20)
- R. Ahuja, "Network flows: theory, algorithms, and applications" (1993), Prentice Hall
- L. R. Ford, "Maximal flow through a network", Canadian Journal of Mathematics, 8, pp.399~404 (1956)
- J. Edmonds, "Theoretical improvements in algorithmic efficiency for network flow problems", Journal of ACM, 19(2), pp.248~264 (1972)
- E. A. Dinic, "Algorithm for solution of a problem of maximal flow in a network with power estimation", Soviet Mathematics, Doklady, 11, pp.1277~1280 (1970)
- V. M. Malhotra, "An OV algorithm for finding maximum flows in networks", Information Processing Letters, 7, pp.277~278 (1978)
- A. V. Goldberg, "Efficient graph algorithms for sequential and parallel computers", Ph.D. Dissertation, pp.1987
- Y. Boykov, "An experimental comparison of min-cut", max-flow algorithms for energy minimization in vision, 2004, pp.26(9), 1124~1137
- S. Solomon, "Parallel algorithm design and implementation of regular", irregular problems: an in-depth performance study on GPU, University of Manitoba, 2012
- N. Sakharnykh, "Efficient maximum flow algorithm", Presentation-Slide at GPU Technology Conference (2017)
- "LEMON—Library for Efficient Modeling and Optimization in Networks" (2012)[URL]
- 류승택, "GPU 기반 비디오 코덱을 이용한 실시간 스마트 영상 믹싱 시스템의 개발", 한국지식정보기술학회 논문지, 11(6), pp.617~624 (2016), 한국지식정보기술학회
- 이정웅, "국방시스템 내에서의 GPU 기반 병렬처리 방법에 대한 연구", 한국지식정보기술학회 논문지, 12(5), pp.661~675 (2017), 한국지식정보기술학회[DOI]
- R. Anderson, "A parallel implementation of the push–relabel algorithm for the maximum flow problem", Journal of Parallel Distribution Computing, 29(1), pp.17~26 (1995)
- A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic, "D. Bader", Georgia Institute of Technology, ~ (2006)
- B, Hong, "An asynchronous multithreaded algorithm for the maximum network flow problem with non-blocking global relabeling heuristic", IEEE Transactions on Parallel and Distributed Systems, 22(6), pp.1025~1033 (2011)
- B, Hong, "Dynamically tuned push-relabel algorithm for the maximum flow problem on CPU-GPU hybrid platforms", Proceedings of IEEE International Symposium on Parallel Distributed Processing, pp.1~10 (2010)
- N. Baumstark, "Efficient implementation of a synchronous parallel push-relabel algorithm", Proceedings of the Embedded Systems and Applications Conference, pp.106~117 (2015)
- G. Kara, "Algorithm 1002 : graph coloring based parallel push-relabel algorithm for the maximum flow problem", ACM Transactions on Mathematical Software, 45(4), pp.1~28 (2019)
- P. Kovács, "Minimum-cost flow algorithms : an experimental evaluation", Optimization Methods and Software, 30(1), pp.94~127 (2015)