TY - GEN
T1 - Order or shuffle
T2 - 31st IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
AU - Slota, George M.
AU - Rajamanickam, Sivasankaran
AU - Madduri, Kamesh
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/6/30
Y1 - 2017/6/30
N2 - The in-memory graph layout affects performance of distributed-memory graph computations. Graph layout could refer to partitioning or replication of vertex and edge arrays, selective replication of data structures that hold meta-data, and reordering vertex and edge identifiers. In this work, we consider one-dimensional graph layouts, where disjoint sets of vertices and their adjacencies are partitioned among processors. Using the PuLP graph partitioning method and a breadth-first search (BFS)-based vertex ordering strategy, we empirically evaluate the impact of this graph layout on a collection of five distributed-memory graph computations. Our evaluation considers several objective metrics in addition to execution time, and we observe a considerable performance improvement over randomization.
AB - The in-memory graph layout affects performance of distributed-memory graph computations. Graph layout could refer to partitioning or replication of vertex and edge arrays, selective replication of data structures that hold meta-data, and reordering vertex and edge identifiers. In this work, we consider one-dimensional graph layouts, where disjoint sets of vertices and their adjacencies are partitioned among processors. Using the PuLP graph partitioning method and a breadth-first search (BFS)-based vertex ordering strategy, we empirically evaluate the impact of this graph layout on a collection of five distributed-memory graph computations. Our evaluation considers several objective metrics in addition to execution time, and we observe a considerable performance improvement over randomization.
UR - http://www.scopus.com/inward/record.url?scp=85028043103&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028043103&partnerID=8YFLogxK
U2 - 10.1109/IPDPSW.2017.164
DO - 10.1109/IPDPSW.2017.164
M3 - Conference contribution
AN - SCOPUS:85028043103
T3 - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
SP - 588
EP - 597
BT - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 29 May 2017 through 2 June 2017
ER -