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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2019

Autores

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

Revista

Título: Concurrency Computation Practice and Experience

Vol. 31

ISSN: 1532-0626

Editora: Wiley-Blackwell

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 2 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 14