On Scaling Dynamic Programming Problems with a Multithreaded Tabling System
Miguel Areias and Ricardo Rocha
October 2014
Abstract
Tabling is a recognized and powerful implementation technique that
improves the declarativeness and expressiveness of traditional Prolog
systems in dealing with recursion and redundant computations. In a
nutshell, tabling consists of storing intermediate answers for
subgoals so that they can be reused when a variant subgoal
appears. The tabling technique can thus be viewed as a natural tool to
implement dynamic programming problems, where a general recursive
strategy divides a problem in simple sub-problems that, often, are 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, 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. To the best of our knowledge, no previous
work showed to be able to scale the execution of multithreaded dynamic
programming problems. 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
taking advantage of the multithreaded tabling engine of the Yap Prolog
system.
Bibtex
@InProceedings{areias-seps14,
author = {M. Areias and R. Rocha},
title = {{On Scaling Dynamic Programming Problems with a Multithreaded Tabling System}},
booktitle = {1st Workshop on Software Engineering for Parallel Systems (SEPS 2014)},
pages = {103--114},
editor = {A. Jannesari and W. F. Tichy and F. Wolf},
month = {October},
year = {2014},
address = {Portland, Oregon, USA},
}
Download Paper
PDF file
RWTH Aachen University