발간년도 : [2023]
| 논문정보 |
|
| 논문명(한글) |
[Vol.18, No.5] GPU-based Push-Relabel Maximum Flow Computing |
|
| 논문투고자 |
Youngsun Seo, Hyeon-Suk Na |
|
| 논문내용 |
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. |
|
| 첨부논문 |
|
|
|
|
|
자료실 > 논문지 
