Modular design of data-parallel graph algorithms

Santanu Dash; Sven-Bodo Scholz; B. Christianson

doi:10.1109/HPCSim.2013.6641446

Modular design of data-parallel graph algorithms

Santanu Dash, Sven-Bodo Scholz, B. Christianson

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

724 Downloads (Pure)

Abstract

Amorphous Data Parallelism has proven to be a suitable vehicle for implementing concurrent graph algorithms effectively on multi-core architectures. In view of the growing complexity of graph algorithms for information analysis, there is a need to facilitate modular design techniques in the context of Amorphous Data Parallelism. In this paper, we investigate what it takes to formulate algorithms possessing Amorphous Data Parallelism in a modular fashion enabling a large degree of code re-use. Using the betweenness centrality algorithm, a widely popular algorithm in the analysis of social networks, we demonstrate that a single optimisation technique can suffice to enable a modular programming style without loosing the efficiency of a tailor-made monolithic implementation.

Original language	English
Title of host publication	Procs 2013 Int Conf on High Performance Computing and Simulation
Place of Publication	Helsinki
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	398-404
ISBN (Print)	978-1-4799-0836-3
DOIs	https://doi.org/10.1109/HPCSim.2013.6641446
Publication status	Published - 2013
Event	Procs 2013 Int Conf on High Performance Computing and Simulation - Helsinki, Finland Duration: 1 Jul 2013 → 5 Jul 2013

Conference

Conference	Procs 2013 Int Conf on High Performance Computing and Simulation
Country/Territory	Finland
City	Helsinki
Period	1/07/13 → 5/07/13

Access to Document

10.1109/HPCSim.2013.6641446

apmm2013_submission_5Accepted author manuscript, 194 KB

Cite this

@inproceedings{e1eea30a7c564e6fa033aabfbe9501bd,

title = "Modular design of data-parallel graph algorithms",

abstract = "Amorphous Data Parallelism has proven to be a suitable vehicle for implementing concurrent graph algorithms effectively on multi-core architectures. In view of the growing complexity of graph algorithms for information analysis, there is a need to facilitate modular design techniques in the context of Amorphous Data Parallelism. In this paper, we investigate what it takes to formulate algorithms possessing Amorphous Data Parallelism in a modular fashion enabling a large degree of code re-use. Using the betweenness centrality algorithm, a widely popular algorithm in the analysis of social networks, we demonstrate that a single optimisation technique can suffice to enable a modular programming style without loosing the efficiency of a tailor-made monolithic implementation.",

author = "Santanu Dash and Sven-Bodo Scholz and B. Christianson",

year = "2013",

doi = "10.1109/HPCSim.2013.6641446",

language = "English",

isbn = "978-1-4799-0836-3",

pages = "398--404",

booktitle = "Procs 2013 Int Conf on High Performance Computing and Simulation",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "Procs 2013 Int Conf on High Performance Computing and Simulation ; Conference date: 01-07-2013 Through 05-07-2013",

}

Dash, S, Scholz, S-B & Christianson, B 2013, Modular design of data-parallel graph algorithms. in Procs 2013 Int Conf on High Performance Computing and Simulation. Institute of Electrical and Electronics Engineers (IEEE), Helsinki, pp. 398-404, Procs 2013 Int Conf on High Performance Computing and Simulation, Helsinki, Finland, 1/07/13. https://doi.org/10.1109/HPCSim.2013.6641446

TY - GEN

T1 - Modular design of data-parallel graph algorithms

AU - Dash, Santanu

AU - Scholz, Sven-Bodo

AU - Christianson, B.

PY - 2013

Y1 - 2013

N2 - Amorphous Data Parallelism has proven to be a suitable vehicle for implementing concurrent graph algorithms effectively on multi-core architectures. In view of the growing complexity of graph algorithms for information analysis, there is a need to facilitate modular design techniques in the context of Amorphous Data Parallelism. In this paper, we investigate what it takes to formulate algorithms possessing Amorphous Data Parallelism in a modular fashion enabling a large degree of code re-use. Using the betweenness centrality algorithm, a widely popular algorithm in the analysis of social networks, we demonstrate that a single optimisation technique can suffice to enable a modular programming style without loosing the efficiency of a tailor-made monolithic implementation.

AB - Amorphous Data Parallelism has proven to be a suitable vehicle for implementing concurrent graph algorithms effectively on multi-core architectures. In view of the growing complexity of graph algorithms for information analysis, there is a need to facilitate modular design techniques in the context of Amorphous Data Parallelism. In this paper, we investigate what it takes to formulate algorithms possessing Amorphous Data Parallelism in a modular fashion enabling a large degree of code re-use. Using the betweenness centrality algorithm, a widely popular algorithm in the analysis of social networks, we demonstrate that a single optimisation technique can suffice to enable a modular programming style without loosing the efficiency of a tailor-made monolithic implementation.

U2 - 10.1109/HPCSim.2013.6641446

DO - 10.1109/HPCSim.2013.6641446

M3 - Conference contribution

SN - 978-1-4799-0836-3

SP - 398

EP - 404

BT - Procs 2013 Int Conf on High Performance Computing and Simulation

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Helsinki

T2 - Procs 2013 Int Conf on High Performance Computing and Simulation

Y2 - 1 July 2013 through 5 July 2013

ER -

Modular design of data-parallel graph algorithms

Abstract

Conference

Access to Document

Fingerprint

Cite this