Simpler is Faster: Multi-Dimensional Lock-Free Arrays for Multithreaded Mode-Directed Tabling in Prolog
Miguel Areias and Ricardo Rocha
July 2017
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},
}
Download Paper
PDF file