Palgol is a high-level domain-specific language for Pregel, and it currently compiles to Pregel+. Main features of this language include:
- 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
- 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
- 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 requires the following environments:
- a c++ compiler (C++11 compatible)
The following steps build the compiler:
$ cd $(top) $ cmake . $ make
The compiler is a single executable
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):
- Open: Tool -> Developer -> New Syntax
- Copy the syntax file
$(top)/sublime/Palgol.sublime-syntaxand 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
A bunch of Palgol sample programs are included in this repository. They can be found in the folder:
- PageRank (pagerank.pal)
- Single-Source Shortest Path (sssp.pal)
- Shiloach-Vishkin Practical Pregel Algorithm (sv.pal, sv_improved.pal)
- Strongly Connected Components (scc.pal, scc2.pal)
- Randomized Bipartite Matching (bm.pal)
- Randomized Graph Coloring (gc.pal)
- Minimum Spanning Forest (msf.pal)
- Triangle Counting (tc.pal)
- Attribute Broadcasting (bcast.pal)
- 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 arxiv.org, 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