Multi-dimensional lock-free arrays for multithreaded mode-directed tabling in Prolog

• Type: Article in International Scientific Journal
• Date: 2019

Authors

Miguel Areias (Author) FCUP; Ricardo Rocha (Author) FCUP

Journal

Title: Concurrency Computation Practice and Experience

Vol. 31

ISSN: 1532-0626

Publisher: Wiley-Blackwell

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 2 Citations

Other information

Authenticus ID: P-00N-S7K

DOI: 10.1002/cpe.4491

Abstract (EN): 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, thus being 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14