On Scaling Dynamic Programming Problems with a Multithreaded Tabling Prolog System
Miguel Areias and Ricardo Rocha
June 2016
Abstract
Tabling is a powerful implementation technique that improves the
declarativeness and expressiveness of traditional Prolog systems in
dealing with recursion and redundant computations. It can be viewed as
a natural tool to implement dynamic programming problems, where a
general recursive strategy divides a problem in simple sub-problems
that are often the same. 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. However, at the engine level, such combination for dynamic
programming problems is very difficult to exploit in order to achieve
execution scalability as we increase the number of running threads. In
this work, we focus on two well-known dynamic programming problems,
the Knapsack and the Longest Common Subsequence problems, and we
discuss how we were able to scale their execution by using the
multithreaded tabling engine of the Yap Prolog system. To the best of
our knowledge, this is the first work showing a Prolog system to be
able to scale the execution of multithreaded dynamic programming
problems. Our experiments also show that our system can achieve
comparable or even better speedup results than other parallel
implementations of the same problems.
Bibtex
@Article{areias-jss16,
author = {M. Areias and R. Rocha},
title = {{On Scaling Dynamic Programming Problems with a Multithreaded Tabling Prolog System}},
journal = {Journal of Systems and Software},
pages = {417--426},
volume = {125},
year = {2017},
note = {(First online: June 2016)},
}
Download Paper
PDF file
ScienceDirect