Towards Multi-Threaded Local Tabling Using a Common Table Space
Miguel Areias and Ricardo Rocha
September 2012
Abstract
Multi-threading is currently supported by several well-known Prolog
systems providing a highly portable solution for applications that can
benefit from concurrency. When multi-threading is combined with
tabling, we can exploit the power of higher procedural control and
declarative semantics. However, despite the availability of both
threads and tabling in some Prolog systems, the implementation of
these two features implies complex ties to each other and to the
underlying engine. Until now, XSB was the only Prolog system combining
multi-threading with tabling. In XSB, tables may be either private or
shared between threads. While thread-private tables are easier to
implement, shared tables have all the associated issues of locking,
synchronization and potential deadlocks. In this paper, we propose an
alternative view to XSB's approach. In our proposal, each thread views
its tables as private but, at the engine level, we use a common table
space where tables are shared among all threads. We present three
designs for our common table space approach: No-Sharing (NS) (similar
to XSB's private tables), Subgoal-Sharing (SS) and Full-Sharing
(FS). The primary goal of this work was to reduce the memory usage for
the table space but, our experimental results, using the YapTab
tabling system with a local evaluation strategy, show that we can also
achieve significant reductions on running time.
Bibtex
@Article{areias-iclp12,
author = {M. Areias and R. Rocha},
title = {{Towards Multi-Threaded Local Tabling Using a Common Table Space}},
journal = {Journal of Theory and Practice of Logic Programming,
28th International Conference on Logic Programming (ICLP 2012), Special Issue},
pages = {427--443},
volume = {12},
number = {4 \& 5},
month = {September},
year = {2012},
}
Download Paper
PDF file
Cambridge University Press
Computing Research Repository (CoRR)