Palgol is a high-level domain-specific language for Pregel, and it currently compiles to Pregel+. Main features of this language include:

  1. Vertex-centric programming paradigm with flexible remote reads and writes
    • Programmers basically specify how each vertex modifies its own state or mutates remote vertices's states (via local or remote writes)
    • A message-passing-based Pregel implementation is then automatically derived
  2. Highly structured way of programming + inherent support for iteration
    • A sophisticated program is constructed from atomic Palgol programs (called Palgol steps)
    • The sequence operation naturally concatenates two Palgol programs
    • The iteration operation iteratively executes a Palgol program until some condition is satisfied
  3. Efficient compiler-generated code
    • Around 2.53% speedup to 6.42% slowdown compared to well-optimized human written code in ordinary cases, and 30% slowdown for a few graph algorithms that benefit from voting to halt mechanism of Pregel.
    • Tested on real-world graphs using popular graph applications (PageRank, SSSP, SCC, S-V, LR, MSF)


The Compiler

The compiler requires the following environments:

  1. cmake
  2. a c++ compiler (C++11 compatible)

The following steps build the compiler:

$ cd $(top)
$ cmake .
$ make

The compiler is a single executable ./palgol

Syntax Highlighting

Vim users can enable syntax highlighting of Palgol programs (.pal files) through the following steps:

$ cp $(top)/vim/syntax/palgol.vim ~/.vim/syntax/
$ cp $(top)/vim/ftdetect/palgol.vim ~/.vim/ftdetect/

Sublime Text users can follow the following steps (work for Sublime Text 3):

  1. Open: Tool -> Developer -> New Syntax
  2. Copy the syntax file $(top)/sublime/Palgol.sublime-syntax and paste it to the opening window. Save it as Palgol.sublime-syntax in a speciefied folder, then enjoy the syntax highlighting.

Compiling and Executing Sample Applications

The Applications

A bunch of Palgol sample programs are included in this repository. They can be found in the folder: $(top)/examples/

  1. PageRank (pagerank.pal)
  2. Single-Source Shortest Path (sssp.pal)
  3. Shiloach-Vishkin Practical Pregel Algorithm (sv.pal, sv_improved.pal)
  4. Strongly Connected Components (scc.pal, scc2.pal)
  5. Randomized Bipartite Matching (bm.pal)
  6. Randomized Graph Coloring (gc.pal)
  7. Minimum Spanning Forest (msf.pal)
  8. Triangle Counting (tc.pal)
  9. Attribute Broadcasting (bcast.pal)
  10. List Ranking Algorithm (ranking.pal)

Compiling Palgol Programs

The follow command compiles a Palgol program to Pregel+ code (in C++).

$ ./palgol [-o <output>] <input>

By default, the output file is run.cpp, but the filename can be specified by the -o flag. The output source code should be compiled with two additional files:

$ ls template/
auxiliary.hpp   external.hpp

"external.hpp" is not necessary unless you use external functions in Palgol. You can read examples/msf.pal to see how to use external function in Palgol.

Please follow the Pregel+ documentation for compiling and running the code. Note that the compiler-generated code uses several features of C++11, so you need to add the option -std=c++11 in Pregel+'s Makefile.

Play with Palgol

Currently, we have published a technical report on, which introduces the core part of Palgol and the techniques for compilation (or code transformation). The syntax of current Palgol (which is slightly different from what we introduced in the technical report) can be found here, and a tutorial containing abundant examples and detailed explanation of the semantics can be found here.


Yongzhe Zhang (Ph.D. student)
The Graduate University of Advanced Studies (SOKENDAI), Japan
National Institute of Informatics