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
(4)
allpairs shortest path
Data Communication
Matrix Multiplication
APSP
Subscribe
Academic
Publications
Blocked AllPairs Shortest Paths Algorithm for Hybrid CPUGPU System
Blocked AllPairs Shortest Paths Algorithm for Hybrid CPUGPU System,10.1109/HPCC.2011.28,Kazuya Matsumoto,Naohito Nakasato,Stanislav G. Sedukhin
Edit
Blocked AllPairs Shortest Paths Algorithm for Hybrid CPUGPU System
BibTex

RIS

RefWorks
Download
Kazuya Matsumoto
,
Naohito Nakasato
,
Stanislav G. Sedukhin
This paper presents a blocked algorithm for the allpairs shortest paths (APSP) problem for a hybrid CPUGPU system. In the blocked
APSP
algorithm, the amount of
data communication
between CPU (host) memory and GPU memory is minimized. When a problem size (the number of vertices in a graph) is large enough compared with a blocking factor, the blocked algorithm virtually requires CPUGPU exchanging of two block matrices for a block computation on the GPU. We also estimate a required memory/communication bandwidth to utilize the GPU efficiently. On a system containing an Intel Westmere CPU (Core i7 970) and an AMD Cypress GPU (Radeon HD 5870), our implementation of the blocked
APSP
algorithm achieves the performance up to 1 TFlop/s in single precision.
Conference:
High Performance Computing and Communications  HPCC
, 2011
DOI:
10.1109/HPCC.2011.28
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
)
(
ieeexplore.ieee.org
)
References
(17)
Introduction to Algorithms, Second Edition
(
Citations: 12540
)
Thomas H. Cormen
,
Charles E. Leiserson
,
Ronald L. Rivest
,
Clifford Stein
Published in 2001.
Path Problems in Graphs
(
Citations: 54
)
Gunter Rote
Published in 1990.
A block algorithm for the algebraic path problem and its execution on a systolic array
(
Citations: 9
)
Fernando J. Nunez
,
Mateo Valero
Conference:
Proceedings of the International Conference on Systolic Arrays  ARRAYS
, 1988
A blocked allpairs shortestpaths algorithm
(
Citations: 24
)
Gayathri Venkataraman
,
Sartaj Sahni
,
Srabani Mukhopadhyaya
Journal:
ACM Journal of Experimental Algorithms  JEA
, vol. 8, pp. 2.2es, 2003
CacheFriendly implementations of transitive closure
(
Citations: 3
)
Michael Penner
,
Viktor K. Prasanna
Journal:
ACM Journal of Experimental Algorithms  JEA
, vol. 11, pp. 1.3es, 2006