Achieving Up To Zero Communication Delay In Bsp-Based Graph Processing Via Vertex Categorization

Keywords

Clustering algorithms; Computational modeling; Delays; Message systems; Partitioning algorithms; Roads; Synchronization

Abstract

The Bulk Synchronous Parallel (BSP) model, which divides a graphing algorithm into multiple supersteps, has become extremely popular in distributed graph processing systems. However, the high number of network messages exchanged in each superstep of the graph algorithm will create a long period of time. We refer to this as a communication delay. Furthermore, the BSP's global synchronization barrier does not allow computation in the next superstrep to be scheduled during this communication delay. This communication delay makes up a large percentage of the overall processing time of a superstep. While most recent research has focused on reducing number of network messages, but communication delay is still a deterministic factor for overall performance. In this paper, we add a runtime communication and computation scheduler into current graph BSP implementations. This scheduler will move some computation from the next superstep to the communication phase in the current superstep to mitigate the communication delay. Finally, we prototyped our system, Zebra, on Apache Hama, which is an open source clone of the classic Google Pregel. By running a set of graph algorithms on an in-house cluster, our evaluation shows that our system could completely eliminate the communication delay in the best case and can achieve average 2X speedup over Hama.

Publication Date

9-10-2015

Publication Title

Proceedings of the 2015 IEEE International Conference on Networking, Architecture and Storage, NAS 2015

Number of Pages

112-121

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/NAS.2015.7255213

Socpus ID

84960874661 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84960874661

This document is currently not available here.

Share

COinS