논문 인용하기
각 논문마다 생성되어 있는 BibTeX를 사용하시면 자신이 원하는 스타일의 인용 문구를 생성할 수 있습니다.
생성된 BibTeX 코드를 복사하여 BibTeX Parser를 사용해 일반 문자열로 바꾸십시오. 아래의 사이트와 같이 웹에서 변환할 수도 있습니다.
bibtex.online2022
1.
Yoon, Daegun; Jeong, Minjoong; Oh, Sangyoon
WAVE: designing a heuristics-based three-way breadth-first search on GPUs🌏 InternationalJournal Article
In: The Journal of Supercomputing, 2022, (2).
Abstract | Links | BibTeX | 태그: breath-first search, direction-optimizing BFS, GPU, graph, push-pull
@article{Yoon2022WAVE,
title = {WAVE: designing a heuristics-based three-way breadth-first search on GPUs},
author = {Daegun Yoon and Minjoong Jeong and Sangyoon Oh},
doi = {10.1007/s11227-022-04934-1},
year = {2022},
date = {2022-11-17},
urldate = {2022-11-17},
journal = {The Journal of Supercomputing},
abstract = {Breadth-first search (BFS) is a building block for improving the performance of many iterative graph algorithms. In addition to conventional BFS (push), a novel method that traverses a graph in the reverse direction (pull) has emerged and gained popularity because of its enhanced processing performance. Several frameworks have recently used a hybrid approach known as direction-optimizing BFS, which utilizes both directions. However, these frameworks are mostly interested in optimizing the procedure in each direction, instead of designing sophisticated methods for determining the appropriate direction between push and pull at each iteration. Owing to the lack of in-depth discussion on this decision, state-of-the-art direction-optimizing BFS algorithms cannot demonstrate their comprehensive performance despite improvements in the design of each direction because they select ineffective directions at each iteration. We identified that the current frameworks suffer from high computational overheads for their decisions and make decisions that are overfitted to several graph datasets used for tuning their direction selection process. Based on observations from state-of-the-art limitations, we designed a direction-optimizing method for BFS called WAVE. WAVE minimizes the computational overhead to near zero and makes more appropriate direction selection decisions than the state-of-the-art heuristics based on the characteristics extracted from the input graph dataset. In our experiments on 20 graph benchmarks, WAVE achieved speedups of up to 4.95×, 5.79×, 46.49×, and 149.67× over Enterprise, Gunrock, Tigr, and CuSha, respectively.},
note = {2},
keywords = {breath-first search, direction-optimizing BFS, GPU, graph, push-pull},
pubstate = {published},
tppubtype = {article}
}
Breadth-first search (BFS) is a building block for improving the performance of many iterative graph algorithms. In addition to conventional BFS (push), a novel method that traverses a graph in the reverse direction (pull) has emerged and gained popularity because of its enhanced processing performance. Several frameworks have recently used a hybrid approach known as direction-optimizing BFS, which utilizes both directions. However, these frameworks are mostly interested in optimizing the procedure in each direction, instead of designing sophisticated methods for determining the appropriate direction between push and pull at each iteration. Owing to the lack of in-depth discussion on this decision, state-of-the-art direction-optimizing BFS algorithms cannot demonstrate their comprehensive performance despite improvements in the design of each direction because they select ineffective directions at each iteration. We identified that the current frameworks suffer from high computational overheads for their decisions and make decisions that are overfitted to several graph datasets used for tuning their direction selection process. Based on observations from state-of-the-art limitations, we designed a direction-optimizing method for BFS called WAVE. WAVE minimizes the computational overhead to near zero and makes more appropriate direction selection decisions than the state-of-the-art heuristics based on the characteristics extracted from the input graph dataset. In our experiments on 20 graph benchmarks, WAVE achieved speedups of up to 4.95×, 5.79×, 46.49×, and 149.67× over Enterprise, Gunrock, Tigr, and CuSha, respectively.