1. Yongzhe Zhang
  2. Palgol

Overview

HTTPS SSH

Introduction

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)

Installation

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 for vim

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

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

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 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.

Contact

Yongzhe Zhang (Ph.D. student)
The Graduate University of Advanced Studies (SOKENDAI), Japan
National Institute of Informatics
Email: zyz915@nii.ac.jp