GPU-기반 Push-Relabel 최대 유량 계산
GPU-based Push-Relabel Maximum Flow Computing
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
그래프 이론에서 유량 네트워크란 각 간선에 용량이 주어진 방향 그래프를 말하는데, 각 간선 위의 유량은 용량을 넘어서는 안된다. 최대 유량 문제는 유량 네트워크의 시점에서 종점까지 보낼 수 있는 최대 유량을 구하는 문제로서, Push-Relabel 알고리즘은 가장 효율적이고 병렬처리에 적합한 접근법으로서 연구되어 왔다. 특히 최근 개발된 Kara와 Özturan의 CPU 멀티코어 기반 그래프 색칠 Push-Relabel 병렬 알고리즘은 그래프 색칠로 구한 비인접 정점집합(독립집합, Independent Set)에서 Push 연산으로 동시에 유량을 흘려보내면 병렬 처리로 인한 경쟁 상태가 최소화되어 현재까지 개발된 어떤 알고리즘보다도 더 효율적임이 입증된 바 있다. 본 논문에서는 이 CPU 멀티코어 기반 알고리즘을 GPU 기반으로 병렬 처리하는 효율적 기법들을 제안했다. 제안된 세 가지 기법들-정점별 워프 할당, Grid 단위 동기화, 거대 정점의 별도 처리-는 분기가 많고 복잡한 그래프 알고리즘에서 병렬 처리로 인해 발생하는 호스트-디바이스 간의 실행 오버헤드 및 지연시간을 효율적으로 해결한다. 그래프 색칠 루틴으로, Kara와 Özturan이 사용한 탐욕적 순차 알고리즘을 Gebremedhin과 Manne의 병렬 알고리즘으로 대체하는데, 이는 근사값(색칠 수)은 더 나쁠 수 있으나 수행시간이 더 짧다. 다양한 실험 데이터에서의 성능 비교를 통해 본 논문의 GPU 기반 구현이 Kara와 Özturan의 구현보다 더 효율적임을 보이고, 거대 정점의 별도 처리 및 그래프 색칠 루틴의 GPU 기반 병렬 처리의 유의미성도 확인한다.
Abstract
In graph theory, flow network is a directed graph with edge having capacity, meaning that the amount of flow on an edge cannot exceed its capacity. Maximum flow problem is the problem of finding the maximum value of flow that can be sent from a starting point to a target point in a flow network. Push-Relabel algorithm is one of the most efficient and popular algorithms for the maximum flow problem and is regarded as the most suitable approach for parallel processing. Recently, Kara and Özturan developed a graph-coloring-based Push-Relabel parallel algorithm and empirically showed that their algorithm is more efficient than any algorithms developed so far. The key idea is to avoid conflicts and synchronization problems due to simultaneous flow-pushing at vertices, by using sets of non-adjacent vertices (independent sets) obtained by graph coloring. In this paper, we propose efficient methods for GPU-based parallel processing of their algorithm. The proposed techniques-warp assignment per vertex, processing separately of huge-degree vertices, and synchronization in grid units-efficiently resolve the execution-overhead between host and device and latency problem, caused by parallel processing in complex graph algorithms with many branches. As a graph-coloring routine, we replace the greedy sequential algorithm used by Kara and Özturan with the graph coloring parallel algorithm of Gebremedhin and Manne which might give a worse approximation value (number of colors) but in shorter execution time. By the performance comparison in various experimental data, we show that our GPU-based algorithm is more efficient than that of Kara and Özturan, and confirm the significance of exceptional handling of huge-degree vertices and of using the GPU-based parallel graph coloring routine.
참고문헌 (22)
- R. Ahuja, "Network flows: theory, algorithms, and applications" (1993), Prentice Hall
- A. V. Goldberg, "A new approach to the maximum flow problem", Proc. of the 18th annual ACM symposium on Theory of computing (STOC '86), pp.136~146 (1986)
- 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)
- A. H. Gebremedhin, "Scalable parallel graph coloring algorithms", Concurrency : Practice and Experience, 12, pp.1131~1146 (2000)
- 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 ximum flows in networks", Information Processing Letters, 7, pp.277~278 (1978)
- A. V. Goldberg, "Efficient graph algorithms for sequential and parallel computers", Ph.D., pp.1987
- U. Derigs, "Implementing Goldberg's max-flow-algorithm — A computational investigation", Zeitschrift für Operations Research, 33(6), pp.383~403 (1989)
- 류승택, "GPU 기반 비디오 코덱을 이용한 실시간 스마트 영상 믹싱 시스템의 개발", 한국지식정보기술학회 논문지, 11(6), pp.617~624 (2016), 한국지식정보기술학회
- S. Solomon, "Parallel algorithm design and implementation of regular", irregular problems:an in-depth performance study on GPU, University of Manitoba, 2012
- 서영선, "GPU-기반 MPM 최대 유량 계산", 한국지식정보기술학회 논문지, 18(2), pp.377~388 (2023), 한국지식정보기술학회[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 nonblocking global relabeling heuristic", IEEE Transactions on Parallel and Distributed Systems, 22(6), pp.1025~1033 (2011)
- N. Baumstark, "Efficient implementation of a synchronous parallel push-relabel algorithm", Proc. of the Embedded Systems and Applications Conference, pp.106~117 (2015)
- D. W. Matula, "Graph coloring algorithms", pp.109~122 (1972), Graph Theory and Computing
- M. T. Jones, "A parallel graph coloring heuristic", SIAM J. Sci. Comput, 14(3), pp.654~669 (1993)
- M. Luby, "A simple parallel algorithm for the maximal independent set problem", SIAM J. on Computing, 15(4), pp.1036~1053 (1986)
- "NVIDIA’s Next Generation CUDA Compute Architecture: Kepler TM GK110/210" (2014)[URL]
- P. Kovács, "Minimum-cost flow algorithms : an experimental evaluation", Optimization Methods and Software, 30(1), pp.94~127 (2015)