Multi-Dimensional Lock-Free Arrays for Multithreaded Mode-Directed Tabling in Prolog

Miguel Areias and Ricardo Rocha

2018

---

Abstract

This work proposes a new design for the supporting data structures used to implement multithreaded tabling in Prolog systems. Tabling is an 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

@Article{areias-ccpe18,
  author =    {M. Areias and R. Rocha},
  title =     {{Multi-Dimensional Lock-Free Arrays for Multithreaded Mode-Directed Tabling in Prolog}},
  journal =   {Concurrency and Computation: Practice and Experience,
               Special Issue: High‐level parallel programming in a heterogeneous world},
  pages =     {1--14},
  volume =    {31},
  number =    {5},
  month =     {March},
  year =      {2018},
}

Download Paper

PDF file
Wiley