Earticle

현재 위치 Home

Poster Session I

Traversing Large Road Networks on GPUs with Breadth-First Search

첫 페이지 보기
  • 발행기관
    한국차세대컴퓨팅학회 바로가기
  • 간행물
    한국차세대컴퓨팅학회 학술대회 바로가기
  • 통권
    The 7th International Conference on Next Generation Computing 2021 (2021.11)바로가기
  • 페이지
    pp.178-181
  • 저자
    Daegun Yoon, Sangyoon Oh
  • 언어
    영어(ENG)
  • URL
    https://www.earticle.net/Article/A448039

원문정보

초록

영어
Breadth-first search (BFS) is one of the most used graph kernels, and substantially affects the overall performance when processing various graphs. Since graph data are frequently used in real life for example road networks in navigation systems, high performance graph processing becomes more critical. In this study, we aim to process BFS algorithm efficiently on road network data. We propose BARON, a BFS algorithm that copes with road networks. To accelerate graph traversal, BARON reduce the occurrence of branch and memory divergences by exploiting warp-cooperative work sharing and atomic operations. With this design approach, BARON outperforms the other BFS kernels of state-of-the-art graph processing frameworks executed stably on the latest GPU architectures. For various graphs, BARON yields speedups of up to 2.88 and 5.43 over Gunrock and CuSha, respectively.

목차

Abstract
I. INTRODUCTION
II. RELATED WORK
III. BARON: BFS ALGORITHM FOR ROAD NETWORKS
IV. EVALUATION
A. Implementation and Hardware Specifications
B. Methodology and Graph Benchmarks
C. BFS Performance Comparison
V. CONCLUSION
ACKNOWLEDGMENT
REFERENCES

키워드

breadth-first search graph road network graphics processing units

저자

  • Daegun Yoon [ dept. of Artificial Intelligence Ajou University ]
  • Sangyoon Oh [ dept. of Artificial Intelligence Ajou University ]

참고문헌

자료제공 : 네이버학술정보

간행물 정보

발행기관

  • 발행기관명
    한국차세대컴퓨팅학회 [Korean Institute of Next Generation Computing]
  • 설립연도
    2005
  • 분야
    공학>컴퓨터학
  • 소개
    본 학회는 차세대 PC 및 그 관련분야의 학술활동을 통하여 차세대 PC의 학문 및 기술발전을 도모하고 산업발전 및 국제협력 증진을 목적으로 한다.

간행물

  • 간행물명
    한국차세대컴퓨팅학회 학술대회
  • 간기
    반년간
  • 수록기간
    2021~2025
  • 십진분류
    KDC 566 DDC 004

이 권호 내 다른 논문 / 한국차세대컴퓨팅학회 학술대회 The 7th International Conference on Next Generation Computing 2021

    피인용수 : 0건 (자료제공 : 네이버학술정보)

    함께 이용한 논문 이 논문을 다운로드한 분들이 이용한 다른 논문입니다.

      출처 : 네이버학술정보

        0개의 논문이 장바구니에 담겼습니다.

        페이지 저장
        소속기관 조회
        이용자님의 소속기관(단체)이 서비스에 가입되어 있는지 확인해 보십시오.
        기관회원에 소속되어 있는 이용자는 원문을 무료로 이용할 수 있습니다.