HigG : parallel processing of large-scale graphs

E. Krepska, T. Kielmann, W.J. Fokkink, H.E. Bal

    Research output: Contribution to journalArticleAcademic


    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.
    Original languageEnglish
    Pages (from-to)3-13
    Number of pages10
    JournalOperating Systems Review
    Issue number2
    Publication statusPublished - 2011


    Dive into the research topics of 'HigG : parallel processing of large-scale graphs'. Together they form a unique fingerprint.

    Cite this