cc 15(5): e5

Research Article

An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph

Download855 downloads
  • @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.