Accelerating All-Pairs Shortest Path Problem Using CUDA

  • OKUYAMA TOMOHIRO
    Department of Information and Computer Sciences, School of Engineering Science, Osaka University
  • INO FUMIHIKO
    Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
  • HAGIHARA KENICHI
    Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Bibliographic Information

Other Title
  • CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))

Search this article

Description

This paper presents acceleration results of the all-pairs shortest path (APSP) problem on a graphics processing unit (GPU). The proposed method is implemented using compute unified device architecture (CUDA), which offers the development environment for GPUs. The method is based on an iterative algorithm that repeatedly computes single-source shortest paths (SSSPs). In order to obtain a higher speedup, we decrease the sequential part of the algorithm by processing SSSP problems in parallel. Furthermore, we reduce the access to global memory by using shared memory, which allows tasks to share data between them. As a result, our method is 3.5-18 times faster than an existing method. We also show that the iterative method varies the performance depending on the characteristic of the graph.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 2008 (19), 145-150, 2008-03-05

    Information Processing Society of Japan (IPSJ)

Details 詳細情報について

  • CRID
    1574231877019766400
  • NII Article ID
    110006828689
  • NII Book ID
    AN10463942
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top