Batched Evaluation of Full-Sharing Multithreaded Tabling
Miguel Areias and Ricardo Rocha
June 2015
Abstract
Tabling is a technique that overcomes some limitations of traditional
Prolog systems in dealing with redundant sub-computations and
recursion. When tabling is combined with multithreading, we have the
best of both worlds, since we can exploit the combination of higher
declarative semantics with higher procedural control. To support this
combination, the Yap Prolog system has, at engine level, multiple
designs that vary from a No-Sharing design, where each thread
allocates fully private tables, to a Full-Sharing (FS) design, where
threads share the complete table space. In this work, we propose an
extension to the table space data structures, which we named Private
Answer Chaining (PAC), as way to support batched scheduling evaluation
with the FS design. Batched scheduling is one of the most successful
tabling scheduling strategies, known to be useful when a tabled logic
program requires an eager propagation of answers and/or do not
requires the complete set of answers to be found. Experimental results
show that PAC is a good first approach, since with it the FS design
remains quite competitive.
Bibtex
@InProceedings{areias-slate15-post,
author = {M. Areias and R. Rocha},
title = {{Batched Evaluation of Full-Sharing Multithreaded Tabling}},
booktitle = {Post-Proceedings of the 4th Symposium on Languages, Applications and Technologies (SLATE 2015)},
pages = {113--124},
number = {563},
series = {CCIS},
publisher = {Springer},
editor = {J. L. Sierra-Rodríguez and J. Paulo Leal and A. Simões},
month = {June},
year = {2015},
address = {Madrid, Spain},
}
Download Paper
PDF file
Springer