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