Simpler is Faster: Multi-Dimensional Lock-Free Arrays for Multithreaded Mode-Directed Tabling in Prolog
Abstract
This work proposes a new design for the supporting data structures used to implement multithreaded tabling in Prolog systems. Tabling is a implementation technique that improves the expressiveness of traditional Prolog systems in dealing with recursion and redundant computations. Mode-directed tabling is an extension to the tabling technique that supports the definition of alternative criteria for specifying how answers are aggregated, being thus very suitable for problems where the goal is to dynamically calculate optimal or selective answers. In this work, we leverage the intrinsic potential that mode-directed tabling has to express dynamic programming problems, by creating a new design that improves the representation of multi-dimensional arrays in the context of multithreaded tabling. To do so, we introduce a new mode for indexing arguments in mode-directed tabled evaluations, named dim, where each dim argument features a uni-dimensional lock-free array. Experimental results using well-known dynamic programming problems on a 32-core machine show that the new design introduces less overheads and clearly improves the execution time for sequential and multithreaded tabled evaluations.
Bibtex
@InProceedings{areias-hlpp17,
author = {M. Areias and R. Rocha},
title = {{Simpler is Faster: Multi-Dimensional Lock-Free Arrays for Multithreaded Mode-Directed Tabling in Prolog}},
booktitle = {Proceedings of the 10th International Symposium on High-level Parallel Programming and
Applications (HLPP 2017)},
pages = {25--42},
editor = {J. Daniel García},
month = {July},
year = {2017},
address = {Valladolid, Spain},
}