Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
allpairs shortest path
Development Environment
Iterative Algorithm
Parallel Algorithm
APSP
Compute Unified Device Architecture
Single Source Shortest Path
Subscribe
Academic
Publications
A Task Parallel Algorithm for Computing the Costs of AllPairs Shortest Paths on the CUDACompatible GPU
A Task Parallel Algorithm for Computing the Costs of AllPairs Shortest Paths on the CUDACompatible GPU,10.1109/ISPA.2008.40,Tomohiro Okuyama,Fumihik
Edit
A Task Parallel Algorithm for Computing the Costs of AllPairs Shortest Paths on the CUDACompatible GPU
(
Citations: 3
)
BibTex

RIS

RefWorks
Download
Tomohiro Okuyama
,
Fumihiko Ino
,
Kenichi Hagihara
Abstract This paper proposes a fast method,for computing,the costs of allpairs shortest paths (APSPs) on the graph ics processing unit (GPU). The proposed method is imple mented using
compute unified device architecture
(CUDA), which offers us a development,environment for performing generalpurpose computation on the GPU. Our method is based on Harish’s
iterative algorithm
that computes,the cost of the singlesource
shortest path
(SSSP) for every source vertex. We present that exploiting task parallelism in the
APSP
problem allows us to efficiently use onchip mem ory in the GPU, reducing the amount of data being trans ferred from relatively slower offchip memory.,Further more, our task parallel scheme is useful to exploit a higher parallelism, increasing the efficiency with highly threaded code. As a result, our method is 3.4‐15 times faster than the prior method. Using onchip memory, our method elim inates approximately 20% of data loads from offchip mem ory.
Conference:
IEEE International Symposium on Intelligent Signal Processing  WISP
, pp. 284291, 2008
DOI:
10.1109/ISPA.2008.40
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
ieeexplore.ieee.org
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(3)
...For example, task parallelism is exploited in [
22
] to efficiently use the onchip memory on the GPU...
Long Chen
,
et al.
Dynamic load balancing on single and multiGPU systems
...In [
21
] task parallelism is exploited to efficiently use the onchip memory on the GPU...
Jakob Siegel
,
et al.
Efficient sparse matrixmatrix multiplication on heterogeneous high pe...
...Recently, Okuyama et al. [
22
] improved this GPU implementation, which leads to an efficient use of onchip shared memory and hides the latencies by generating many threads...
Hiroki Yanagisawa
.
A multisource labelcorrecting algorithm for the allpairs shortest p...
References
(7)
Hardware/Software Integration for FPGAbased AllPairs ShortestPaths
(
Citations: 6
)
Uday Bondhugula
,
Ananth Devulapalli
,
James Dinan
,
Joseph Fernando
,
Pete Wyckoff
,
Eric Stahlberg
,
P. Sadayappan
Conference:
FieldProgrammable Custom Computing Machines  FCCM
, pp. 152164, 2006
Accelerating large graph algorithms on the GPU using CUDA
(
Citations: 64
)
Pawan Harish
,
P. J. Narayanan
Published in 2007.
General Parallel Computation on Commodity Graphics Hardware: Case Study with the AllPairs Shortest Paths Problem
(
Citations: 7
)
Paulius Micikevicius
Conference:
Parallel and Distributed Processing Techniques and Applications  PDPTA
, pp. 13591365, 2004
Extraction of Correlated Gene Clusters by Multiple Graph Comparison
(
Citations: 22
)
Akihiro Nakaya
,
Susumu Goto
,
Minoru Kanehisa
Published in 2001.
A scalable parallelization of allpairs shortest path algorithm for a high performance cluster environment
(
Citations: 1
)
Thanukrishnan Srinivasan
,
R. Balakrishnan
,
S. A. Gangadharan
,
V. Hayawardh
Conference:
International Conference on Parallel and Distributed Systems  ICPADS
, vol. 2, pp. 18, 2007
Sort by:
Citations
(3)
Dynamic load balancing on single and multiGPU systems
(
Citations: 4
)
Long Chen
,
Oreste Villa
,
Sriram Krishnamoorthy
,
Guang R. Gao
Published in 2010.
Efficient sparse matrixmatrix multiplication on heterogeneous high performance systems
Jakob Siegel
,
Oreste Villa
,
Sriram Krishnamoorthy
,
Antonino Tumeo
,
Xiaoming Li
Conference:
IEEE International Conference on Cluster Computing Workshops and Posters  CLUSTER WORKSHOPS
, 2010
A multisource labelcorrecting algorithm for the allpairs shortest paths problem
Hiroki Yanagisawa
Conference:
International Parallel and Distributed Processing Symposium/International Parallel Processing Symposium  IPDPS(IPPS)
, pp. 110, 2010