×

Optimizing declarative parallel distributed graph processing by using constraint solvers. (English) Zbl 06900731

Gallagher, John P. (ed.) et al., Functional and logic programming. 14th international symposium, FLOPS 2018, Nagoya, Japan, May 9–11, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10818, 166-181 (2018).
Summary: Vertex-centric graph processing is a promising approach for facilitating development of parallel distributed graph processing programs. Each vertex is regarded as a tiny thread and graph processing is described as cooperation among vertices. This approach resolves many issues in parallel distributed processing such as synchronization and load balancing. However, it is still difficult to develop efficient programs requiring careful problem-specific tuning. We present a method for automatically optimizing vertex-centric graph processing programs. The key is the use of constraint solvers to analyze the subtle properties of the programs. We focus on a functional vertex-centric graph processing language, Fregel, and show that quantifier elimination and SMT (satisfiability modulo theories) are useful for optimizing Fregel programs. A preliminary experiment indicated that a modern SMT solver can perform optimization within a realistic time frame and that our method can significantly improve the performance of naively written declarative vertex-centric graph processing programs.
For the entire collection see [Zbl 1386.68007].

MSC:

68N17 Logic programming
68N18 Functional programming and lambda calculus
PDF BibTeX XML Cite
Full Text: DOI