HipG: Parallel Processing of Large-Scale Graphs
Abstract:
Distributed processing of real-world graphs is challenging due to their size and the inherent irregular structure of graph computations. We present HipG, a distributed framework that facilitates programming parallel graph algorithms by composing the parallel application automatically from the user-defined pieces of sequential work on graph nodes. To make the user code high-level, the framework provides a unified interface to executing methods on local and non-local graph nodes and an abstraction of exclusive execution. The graph computations are managed by logical objects called synchronizers, which we used, for example, to implement distributed divide-and-conquer decomposition into strongly connected components. The code written in HipG is independent of a particular graph representation, to the point that the graph can be created on-the-fly, i.e. by the algorithm that computes on this graph, which we used to implement a distributed model checker. HipG programs are in general short and elegant; they achieve good portability, memory utilization, and performance.
Graphs are stored in SVC-II distributed graph format described in Compressed and Distributed File Formats for Labeled Transition Systems by Stefan Blom, Izak van Langevelde, and Bert Lissera. (Electronic Notes in Theoretical Computer Science Volume 89, Issue 1, September 2003, Pages 68-83 PDMC 2003, Parallel and Distributed Model Checking (Satellite Workshop of CAV ’03)) [The abstract is so vague as to be useless. I tried to find an “open” copy of the paper but failed. Can you point to one?]
Implementation: www.cs.vu.nl/~ekr/HipG
From the implementation webpage:
HipG is a library for high-level parallel processing of large-scale graphs. HipG is implemented in Java and is designed for distributed-memory machine. Besides basic distributed graph algorithms it handles divide-and-conquer graph algorithms and algorithms that execute on graphs created on-the-fly. It is designed for clusters of machines, but can also be tested on desktops – all you need is a recent Java runtime environment. HipG is work in progress! (as of Apr’11)