Techniques for solving large-scale graph problems on heterogeneous platforms

Ilya Afanasyev; Alexander Daryin; Jack Dongarra; Dmitry Nikitenko; Alexey Teplov; Vladimir Voevodin

doi:10.1007/978-3-319-55669-7_25

Techniques for solving large-scale graph problems on heterogeneous platforms

Ilya Afanasyev, Alexander Daryin, Jack Dongarra, Dmitry Nikitenko, Alexey Teplov, Vladimir Voevodin

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The paper introduces techniques for solving various large-scale graph problems on hybrid architectures. The proposed approach is illustrated on the computation of minimum spanning tree and shortest paths. We provide a precise mathematical description accompanied by the information structure of required algorithms. Efficient parallel implementations of several graph algorithms are proposed based on this analysis. Hybrid computations allow using all the available resources on both multi-core CPUs and GPUs. Our implementation uses out-of-core memory algorithms to handle graphs that don’t fit in the main memory. Experimental results confirm high performance and scalability of the proposed solutions. Moreover, the proposed approach can be applied to other graph processing problems, which have recently rapidly increased in demand.

Original language	English
Title of host publication	Supercomputing - 2nd Russian Supercomputing Days, RuSCDays 2016, Revised Selected Papers
Editors	Vladimir Voevodin, Sergey Sobolev
Publisher	Springer Verlag
Pages	318-332
Number of pages	15
ISBN (Print)	9783319556680
DOIs	https://doi.org/10.1007/978-3-319-55669-7_25
State	Published - 2016
Externally published	Yes
Event	2nd Russian Supercomputing Days, RuSCDays 2016 - Moscow, Russian Federation Duration: Sep 26 2016 → Sep 27 2016

Publication series

Name	Communications in Computer and Information Science
Volume	687
ISSN (Print)	1865-0929

Conference

Conference	2nd Russian Supercomputing Days, RuSCDays 2016
Country/Territory	Russian Federation
City	Moscow
Period	09/26/16 → 09/27/16

Funding

This study was financially supported by the Russian Science Foundation, agreement N14-11-00190 except mathematical problem statement (Sects. and ).

Funders	Funder number
Russian Science Foundation	N14-11-00190

Keywords

APSP
All pairs of shortest paths
CUDA
GPU
Graph algorithms
Hybrid computations
Large-scale graph processing
MST
Minimum spanning tree

Access to Document

10.1007/978-3-319-55669-7_25

Cite this

Afanasyev, I., Daryin, A., Dongarra, J., Nikitenko, D., Teplov, A., & Voevodin, V. (2016). Techniques for solving large-scale graph problems on heterogeneous platforms. In V. Voevodin, & S. Sobolev (Eds.), Supercomputing - 2nd Russian Supercomputing Days, RuSCDays 2016, Revised Selected Papers (pp. 318-332). (Communications in Computer and Information Science; Vol. 687). Springer Verlag. https://doi.org/10.1007/978-3-319-55669-7_25

@inproceedings{394e3276e10641b2864e043e29c7b1a0,

title = "Techniques for solving large-scale graph problems on heterogeneous platforms",

abstract = "The paper introduces techniques for solving various large-scale graph problems on hybrid architectures. The proposed approach is illustrated on the computation of minimum spanning tree and shortest paths. We provide a precise mathematical description accompanied by the information structure of required algorithms. Efficient parallel implementations of several graph algorithms are proposed based on this analysis. Hybrid computations allow using all the available resources on both multi-core CPUs and GPUs. Our implementation uses out-of-core memory algorithms to handle graphs that don{\textquoteright}t fit in the main memory. Experimental results confirm high performance and scalability of the proposed solutions. Moreover, the proposed approach can be applied to other graph processing problems, which have recently rapidly increased in demand.",

keywords = "APSP, All pairs of shortest paths, CUDA, GPU, Graph algorithms, Hybrid computations, Large-scale graph processing, MST, Minimum spanning tree",

author = "Ilya Afanasyev and Alexander Daryin and Jack Dongarra and Dmitry Nikitenko and Alexey Teplov and Vladimir Voevodin",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 2nd Russian Supercomputing Days, RuSCDays 2016 ; Conference date: 26-09-2016 Through 27-09-2016",

year = "2016",

doi = "10.1007/978-3-319-55669-7_25",

language = "English",

isbn = "9783319556680",

series = "Communications in Computer and Information Science",

publisher = "Springer Verlag",

pages = "318--332",

editor = "Vladimir Voevodin and Sergey Sobolev",

booktitle = "Supercomputing - 2nd Russian Supercomputing Days, RuSCDays 2016, Revised Selected Papers",

}

Afanasyev, I, Daryin, A, Dongarra, J, Nikitenko, D, Teplov, A & Voevodin, V 2016, Techniques for solving large-scale graph problems on heterogeneous platforms. in V Voevodin & S Sobolev (eds), Supercomputing - 2nd Russian Supercomputing Days, RuSCDays 2016, Revised Selected Papers. Communications in Computer and Information Science, vol. 687, Springer Verlag, pp. 318-332, 2nd Russian Supercomputing Days, RuSCDays 2016, Moscow, Russian Federation, 09/26/16. https://doi.org/10.1007/978-3-319-55669-7_25

Techniques for solving large-scale graph problems on heterogeneous platforms. / Afanasyev, Ilya; Daryin, Alexander; Dongarra, Jack et al.
Supercomputing - 2nd Russian Supercomputing Days, RuSCDays 2016, Revised Selected Papers. ed. / Vladimir Voevodin; Sergey Sobolev. Springer Verlag, 2016. p. 318-332 (Communications in Computer and Information Science; Vol. 687).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Techniques for solving large-scale graph problems on heterogeneous platforms

AU - Afanasyev, Ilya

AU - Daryin, Alexander

AU - Dongarra, Jack

AU - Nikitenko, Dmitry

AU - Teplov, Alexey

AU - Voevodin, Vladimir

N1 - Publisher Copyright: © Springer International Publishing AG 2016.

PY - 2016

Y1 - 2016

N2 - The paper introduces techniques for solving various large-scale graph problems on hybrid architectures. The proposed approach is illustrated on the computation of minimum spanning tree and shortest paths. We provide a precise mathematical description accompanied by the information structure of required algorithms. Efficient parallel implementations of several graph algorithms are proposed based on this analysis. Hybrid computations allow using all the available resources on both multi-core CPUs and GPUs. Our implementation uses out-of-core memory algorithms to handle graphs that don’t fit in the main memory. Experimental results confirm high performance and scalability of the proposed solutions. Moreover, the proposed approach can be applied to other graph processing problems, which have recently rapidly increased in demand.

AB - The paper introduces techniques for solving various large-scale graph problems on hybrid architectures. The proposed approach is illustrated on the computation of minimum spanning tree and shortest paths. We provide a precise mathematical description accompanied by the information structure of required algorithms. Efficient parallel implementations of several graph algorithms are proposed based on this analysis. Hybrid computations allow using all the available resources on both multi-core CPUs and GPUs. Our implementation uses out-of-core memory algorithms to handle graphs that don’t fit in the main memory. Experimental results confirm high performance and scalability of the proposed solutions. Moreover, the proposed approach can be applied to other graph processing problems, which have recently rapidly increased in demand.

KW - APSP

KW - All pairs of shortest paths

KW - CUDA

KW - GPU

KW - Graph algorithms

KW - Hybrid computations

KW - Large-scale graph processing

KW - MST

KW - Minimum spanning tree

UR - http://www.scopus.com/inward/record.url?scp=85015961670&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-55669-7_25

DO - 10.1007/978-3-319-55669-7_25

M3 - Conference contribution

AN - SCOPUS:85015961670

SN - 9783319556680

T3 - Communications in Computer and Information Science

SP - 318

EP - 332

BT - Supercomputing - 2nd Russian Supercomputing Days, RuSCDays 2016, Revised Selected Papers

A2 - Voevodin, Vladimir

A2 - Sobolev, Sergey

PB - Springer Verlag

T2 - 2nd Russian Supercomputing Days, RuSCDays 2016

Y2 - 26 September 2016 through 27 September 2016

ER -

Afanasyev I, Daryin A, Dongarra J, Nikitenko D, Teplov A, Voevodin V. Techniques for solving large-scale graph problems on heterogeneous platforms. In Voevodin V, Sobolev S, editors, Supercomputing - 2nd Russian Supercomputing Days, RuSCDays 2016, Revised Selected Papers. Springer Verlag. 2016. p. 318-332. (Communications in Computer and Information Science). doi: 10.1007/978-3-319-55669-7_25

Techniques for solving large-scale graph problems on heterogeneous platforms

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this