About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
cc 15(5): e5

Research Article

An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph

Download1422 downloads
Cite
BibTeX Plain Text
  • @ARTICLE{10.4108/eai.17-12-2015.150810,
        author={Amirreza Abdolrashidi and Lakshmish Ramaswamy},
        title={An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph},
        journal={EAI Endorsed Transactions on Collaborative Computing},
        volume={1},
        number={5},
        publisher={EAI},
        journal_a={CC},
        year={2015},
        month={12},
        keywords={Distributed Vertex-Centric Graph Processing, Performance Modeling, Parallel Processing, Graph Partitioning.},
        doi={10.4108/eai.17-12-2015.150810}
    }
    
  • Amirreza Abdolrashidi
    Lakshmish Ramaswamy
    Year: 2015
    An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph
    CC
    EAI
    DOI: 10.4108/eai.17-12-2015.150810
Amirreza Abdolrashidi1,*, Lakshmish Ramaswamy1
  • 1: Department of Computer Science, The University of Georgia, Athens, Georgia, USA
*Contact email: ara@cs.uga.edu

Abstract

Distributed vertex-centric graph processing systems such as Pregel, Giraph and GPS have acquired significant popularity in recent years. Although the manner in which graph data is partitioned and placed on the computational nodes has considerable impact on the performance of the vertex-centric graph processing cluster, there are very few comprehensive studies on this topic. Towards enhancing our understanding of this important factor, in this paper, we propose a novel model for analyzing the performance of such clusters. Using three graph algorithms as case studies, we also characterize the inherent tradeoff between the computational load distribution and the communication overheads of a BSP cluster. This paper also reports a detailed experimental study investigating the performance of commonly-used graph partitioning mechanisms with respect to their computational load distribution characteristics and the associated communication overheads.

Keywords
Distributed Vertex-Centric Graph Processing, Performance Modeling, Parallel Processing, Graph Partitioning.
Received
2015-02-18
Accepted
2015-07-04
Published
2015-12-17
Publisher
EAI
http://dx.doi.org/10.4108/eai.17-12-2015.150810

Copyright © 2015 Amirreza Abdolrashidi and Lakshmish Ramaswamy, licensed to EAI. This is an open access article distributed under the terms of the Creative Commons Attribution license (http://creativecommons.org/licenses/ by/3.0/), which permits unlimited use, distribution and reproduction in any medium so long as the original work is properly cited.

EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL