An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
European Alliance for Innovation (EAI)
2015-12-01
|
| Series: | EAI Endorsed Transactions on Collaborative Computing |
| Subjects: | |
| Online Access: | http://eudl.eu/doi/10.4108/eai.17-12-2015.150810 |
| _version_ | 1819171024032235520 |
|---|---|
| author | Amirreza Abdolrashidi Lakshmish Ramaswamy |
| author_facet | Amirreza Abdolrashidi Lakshmish Ramaswamy |
| author_sort | Amirreza Abdolrashidi |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-22T19:44:42Z |
| format | Article |
| id | doaj.art-292d7659a6f14084aba4ff1e1fcde59b |
| institution | Directory Open Access Journal |
| issn | 2312-8623 |
| language | English |
| last_indexed | 2024-12-22T19:44:42Z |
| publishDate | 2015-12-01 |
| publisher | European Alliance for Innovation (EAI) |
| record_format | Article |
| series | EAI Endorsed Transactions on Collaborative Computing |
| spelling | doaj.art-292d7659a6f14084aba4ff1e1fcde59b2022-12-21T18:14:43ZengEuropean Alliance for Innovation (EAI)EAI Endorsed Transactions on Collaborative Computing2312-86232015-12-011512010.4108/eai.17-12-2015.150810An Analytical Study of Computation and Communication Tradeoffs in Distributed GraphAmirreza Abdolrashidi0Lakshmish Ramaswamy1Department of Computer Science, The University of Georgia, Athens, Georgia, USA; ara@cs.uga.eduDepartment of Computer Science, The University of Georgia, Athens, Georgia, USADistributed 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.http://eudl.eu/doi/10.4108/eai.17-12-2015.150810Distributed Vertex-Centric Graph ProcessingPerformance ModelingParallel ProcessingGraph Partitioning. |
| spellingShingle | Amirreza Abdolrashidi Lakshmish Ramaswamy An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph EAI Endorsed Transactions on Collaborative Computing Distributed Vertex-Centric Graph Processing Performance Modeling Parallel Processing Graph Partitioning. |
| title | An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph |
| title_full | An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph |
| title_fullStr | An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph |
| title_full_unstemmed | An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph |
| title_short | An Analytical Study of Computation and Communication Tradeoffs in Distributed Graph |
| title_sort | analytical study of computation and communication tradeoffs in distributed graph |
| topic | Distributed Vertex-Centric Graph Processing Performance Modeling Parallel Processing Graph Partitioning. |
| url | http://eudl.eu/doi/10.4108/eai.17-12-2015.150810 |
| work_keys_str_mv | AT amirrezaabdolrashidi ananalyticalstudyofcomputationandcommunicationtradeoffsindistributedgraph AT lakshmishramaswamy ananalyticalstudyofcomputationandcommunicationtradeoffsindistributedgraph AT amirrezaabdolrashidi analyticalstudyofcomputationandcommunicationtradeoffsindistributedgraph AT lakshmishramaswamy analyticalstudyofcomputationandcommunicationtradeoffsindistributedgraph |