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

摘要

This work proposes a new design for the supporting data structures used to implement multithreadedtabling in Prolog systems. Tabling is an implementation technique that improves theexpressiveness of traditional Prolog systems in dealing with recursion and redundant computations.Mode-directed tabling is an extension to the tabling technique that supports the definitionof alternative criteria for specifying how answers are aggregated, thus being very suitable forproblems 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 programmingproblems by creating a new design that improves the representation of multi-dimensionalarrays in the context of multithreaded tabling. To do so, we introduce a new mode for indexingarguments in mode-directed tabled evaluations, named dim, where each dim argument featuresa uni-dimensional lock-free array. Experimental results using well-known dynamic programmingproblems on a 32-core machine show that the new design introduces less overheads and clearlyimproves the execution time for sequential and multithreaded tabled evaluations.