GAP logo

GBSP

Scott Beamer, David Patterson, Krste Asanović

Specialized hardware is not helpful if it is not programmable. Leveraging the Asp framework from the SEJITS project, we built a simple graph domain-specific language (DSL) around the bulk-synchronous parallel model (similar to Pregel). Our DSL implements the vertex-centric programming model and we call it the Graph Bulk-Synchronous Parallel (GBSP) system [1].

Our implementation's single-threaded performance is comparable to the performance of the standard Boost Graph Library (BGL). Our graph DSL within Python is able to compete with native C++ due to the SEJITS approach. Better yet, since GBSP implements the BSP model, it was trivial to parallelize it. BGL is not parallelized and thus can not take advantage of additional cores.

References

  1. "Portable Parallel Performance from Sequential, Productive, Embedded Domain-Specific Languages", Shoaib Kamil, Derrick Coetzee, Scott Beamer, Henry Cook, Ekaterina Gonina, Jonathan Harper, Jeffrey Morlan, and Armando Fox, Symposium on Principles and Practice of Parallel Programming (PPoPP), New Orleans, Louisiana, February 2012. ACM
  2. "Understanding and Improving Graph Algorithm Performance", Scott Beamer. Ph.D. Thesis, University of California Berkeley, September 2016. PDF TR
    SPEC Kaivalya Dixit Distinguished Dissertation Award

GAP Project Home