A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters

Anand Tripathi; Vinit Padhye; Tara Sasank Sunkara; Jeremy Tucker; Bhagavathidhass Thirunavukarasu; Varun Pandey; Rahul R. Sharma

doi:10.1109/CLOUD.2017.62

A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters

Anand Tripathi, Vinit Padhye, Tara Sasank Sunkara, Jeremy Tucker, Bhagavathidhass Thirunavukarasu, Varun Pandey, Rahul R. Sharma

Computer Science and Engineering

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

4 Scopus citations

Abstract

We present here the results of our investigation of a transactional model of parallel programming on cluster computing systems. This model is specifically targeted for graph applications with the goal of harnessing unstructured parallelism inherently present in many such problems. In this model, tasks for vertex-centric computations are executed optimistically in parallel as serializable transactions. A key-value based globally shared object store is implemented in the main memory of the cluster nodes for storing the graph data. Task computations read and modify data in the distributed global store, without any explicitly programmed message-passing in the application code. Based on this model we developed a framework for parallel programming of graph applications on computing clusters. We present here the programming abstractions provided by this framework and its architecture. Using several graph problems we illustrate the simplicity of the abstractions provided by this model. These problems include graph coloring, k-nearest neighbors, and single-source shortest path computation. We also illustrate how incremental computations can be supported by this programming model. Using these problems we evaluate the transactional programming model and the mechanisms provided by this framework.

Original language	English (US)
Title of host publication	Proceedings - 2017 IEEE 10th International Conference on Cloud Computing, CLOUD 2017
Editors	Geoffrey C. Fox
Publisher	IEEE Computer Society
Pages	431-438
Number of pages	8
ISBN (Electronic)	9781538619933
DOIs	https://doi.org/10.1109/CLOUD.2017.62
State	Published - Sep 8 2017
Event	10th IEEE International Conference on Cloud Computing, CLOUD 2017 - Honolulu, United States Duration: Jun 25 2017 → Jun 30 2017

Publication series

Name	IEEE International Conference on Cloud Computing, CLOUD
Volume	2017-June
ISSN (Print)	2159-6182
ISSN (Electronic)	2159-6190

Other

Other	10th IEEE International Conference on Cloud Computing, CLOUD 2017
Country/Territory	United States
City	Honolulu
Period	6/25/17 → 6/30/17

Bibliographical note

Funding Information:
Acknowledgements: This work was supported by NSF Award 1319333 and computing resources were provided by NSF award 1512877 and the Minnesota Supercomputing Institute.

Publisher Copyright:
© 2017 IEEE.

Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

Keywords

Cluster computing
Concurrency control
Distributed Systems
Graph problems
Parallel computing
Transaction models

Publisher link

10.1109/CLOUD.2017.62

http://hdl.handle.net/11299/200943

Find It

Find It at U of M Libraries

Cite this

Tripathi, A., Padhye, V., Sunkara, T. S., Tucker, J., Thirunavukarasu, B., Pandey, V., & Sharma, R. R. (2017). A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters. In G. C. Fox (Ed.), Proceedings - 2017 IEEE 10th International Conference on Cloud Computing, CLOUD 2017 (pp. 431-438). Article 8030618 (IEEE International Conference on Cloud Computing, CLOUD; Vol. 2017-June). IEEE Computer Society. https://doi.org/10.1109/CLOUD.2017.62

A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters. / Tripathi, Anand; Padhye, Vinit; Sunkara, Tara Sasank et al.
Proceedings - 2017 IEEE 10th International Conference on Cloud Computing, CLOUD 2017. ed. / Geoffrey C. Fox. IEEE Computer Society, 2017. p. 431-438 8030618 (IEEE International Conference on Cloud Computing, CLOUD; Vol. 2017-June).

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

Tripathi, A, Padhye, V, Sunkara, TS, Tucker, J, Thirunavukarasu, B, Pandey, V & Sharma, RR 2017, A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters. in GC Fox (ed.), Proceedings - 2017 IEEE 10th International Conference on Cloud Computing, CLOUD 2017., 8030618, IEEE International Conference on Cloud Computing, CLOUD, vol. 2017-June, IEEE Computer Society, pp. 431-438, 10th IEEE International Conference on Cloud Computing, CLOUD 2017, Honolulu, United States, 6/25/17. https://doi.org/10.1109/CLOUD.2017.62

Tripathi A, Padhye V, Sunkara TS, Tucker J, Thirunavukarasu B, Pandey V et al. A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters. In Fox GC, editor, Proceedings - 2017 IEEE 10th International Conference on Cloud Computing, CLOUD 2017. IEEE Computer Society. 2017. p. 431-438. 8030618. (IEEE International Conference on Cloud Computing, CLOUD). doi: 10.1109/CLOUD.2017.62

@inproceedings{7fffbadeec8d45ca9a21e73448e40c5b,

title = "A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters",

abstract = "We present here the results of our investigation of a transactional model of parallel programming on cluster computing systems. This model is specifically targeted for graph applications with the goal of harnessing unstructured parallelism inherently present in many such problems. In this model, tasks for vertex-centric computations are executed optimistically in parallel as serializable transactions. A key-value based globally shared object store is implemented in the main memory of the cluster nodes for storing the graph data. Task computations read and modify data in the distributed global store, without any explicitly programmed message-passing in the application code. Based on this model we developed a framework for parallel programming of graph applications on computing clusters. We present here the programming abstractions provided by this framework and its architecture. Using several graph problems we illustrate the simplicity of the abstractions provided by this model. These problems include graph coloring, k-nearest neighbors, and single-source shortest path computation. We also illustrate how incremental computations can be supported by this programming model. Using these problems we evaluate the transactional programming model and the mechanisms provided by this framework.",

keywords = "Cluster computing, Concurrency control, Distributed Systems, Graph problems, Parallel computing, Transaction models",

author = "Anand Tripathi and Vinit Padhye and Sunkara, {Tara Sasank} and Jeremy Tucker and Bhagavathidhass Thirunavukarasu and Varun Pandey and Sharma, {Rahul R.}",

note = "Funding Information: Acknowledgements: This work was supported by NSF Award 1319333 and computing resources were provided by NSF award 1512877 and the Minnesota Supercomputing Institute. Publisher Copyright: {\textcopyright} 2017 IEEE. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.; 10th IEEE International Conference on Cloud Computing, CLOUD 2017 ; Conference date: 25-06-2017 Through 30-06-2017",

year = "2017",

month = sep,

day = "8",

doi = "10.1109/CLOUD.2017.62",

language = "English (US)",

series = "IEEE International Conference on Cloud Computing, CLOUD",

publisher = "IEEE Computer Society",

pages = "431--438",

editor = "Fox, {Geoffrey C.}",

booktitle = "Proceedings - 2017 IEEE 10th International Conference on Cloud Computing, CLOUD 2017",

}

TY - GEN

T1 - A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters

AU - Tripathi, Anand

AU - Padhye, Vinit

AU - Sunkara, Tara Sasank

AU - Tucker, Jeremy

AU - Thirunavukarasu, Bhagavathidhass

AU - Pandey, Varun

AU - Sharma, Rahul R.

N1 - Funding Information: Acknowledgements: This work was supported by NSF Award 1319333 and computing resources were provided by NSF award 1512877 and the Minnesota Supercomputing Institute. Publisher Copyright: © 2017 IEEE. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2017/9/8

Y1 - 2017/9/8

N2 - We present here the results of our investigation of a transactional model of parallel programming on cluster computing systems. This model is specifically targeted for graph applications with the goal of harnessing unstructured parallelism inherently present in many such problems. In this model, tasks for vertex-centric computations are executed optimistically in parallel as serializable transactions. A key-value based globally shared object store is implemented in the main memory of the cluster nodes for storing the graph data. Task computations read and modify data in the distributed global store, without any explicitly programmed message-passing in the application code. Based on this model we developed a framework for parallel programming of graph applications on computing clusters. We present here the programming abstractions provided by this framework and its architecture. Using several graph problems we illustrate the simplicity of the abstractions provided by this model. These problems include graph coloring, k-nearest neighbors, and single-source shortest path computation. We also illustrate how incremental computations can be supported by this programming model. Using these problems we evaluate the transactional programming model and the mechanisms provided by this framework.

AB - We present here the results of our investigation of a transactional model of parallel programming on cluster computing systems. This model is specifically targeted for graph applications with the goal of harnessing unstructured parallelism inherently present in many such problems. In this model, tasks for vertex-centric computations are executed optimistically in parallel as serializable transactions. A key-value based globally shared object store is implemented in the main memory of the cluster nodes for storing the graph data. Task computations read and modify data in the distributed global store, without any explicitly programmed message-passing in the application code. Based on this model we developed a framework for parallel programming of graph applications on computing clusters. We present here the programming abstractions provided by this framework and its architecture. Using several graph problems we illustrate the simplicity of the abstractions provided by this model. These problems include graph coloring, k-nearest neighbors, and single-source shortest path computation. We also illustrate how incremental computations can be supported by this programming model. Using these problems we evaluate the transactional programming model and the mechanisms provided by this framework.

KW - Cluster computing

KW - Concurrency control

KW - Distributed Systems

KW - Graph problems

KW - Parallel computing

KW - Transaction models

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

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

U2 - 10.1109/CLOUD.2017.62

DO - 10.1109/CLOUD.2017.62

M3 - Conference contribution

AN - SCOPUS:85032191009

T3 - IEEE International Conference on Cloud Computing, CLOUD

SP - 431

EP - 438

BT - Proceedings - 2017 IEEE 10th International Conference on Cloud Computing, CLOUD 2017

A2 - Fox, Geoffrey C.

PB - IEEE Computer Society

T2 - 10th IEEE International Conference on Cloud Computing, CLOUD 2017

Y2 - 25 June 2017 through 30 June 2017

ER -

A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this