Table space designs for implicit and explicit concurrent tabled evaluation
From MaRDI portal
Abstract: One of the main advantages of Prolog is its potential for the implicit exploitation of parallelism and, as a high-level language, Prolog is also often used as a means to explicitly control concurrent tasks. Tabling is a powerful implementation technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant sub-computations. Given these advantages, the question that arises is if tabling has also the potential for the exploitation of concurrency/parallelism. On one hand, tabling still exploits a search space as traditional Prolog but, on the other hand, the concurrent model of tabling is necessarily far more complex since it also introduces concurrency on the access to the tables. In this paper, we summarize Yap's main contributions to concurrent tabled evaluation and we describe the design and implementation challenges of several alternative table space designs for implicit and explicit concurrent tabled evaluation which represent different trade-offs between concurrency and memory usage. We also motivate for the advantages of using fixed-size and lock-free data structures, elaborate on the key role that the engine's memory allocator plays on such environments, and discuss how Yap's mode-directed tabling support can be extended to concurrent evaluation. Finally, we present our future perspectives towards an efficient and novel concurrent framework which integrates both implicit and explicit concurrent tabled evaluation in a single Prolog engine. Under consideration in Theory and Practice of Logic Programming (TPLP).
Recommendations
- Euro-Par 2004 Parallel Processing
- Towards multi-threaded local tabling using a common table space
- Description, implementation, and evaluation of a generic design for tabled CLP
- scientific article; zbMATH DE number 2085268
- Tabled evaluation with delaying for general logic programs
- Tableaux for constructive concurrent dynamic logic
- ExpTime tableaux with global caching for hybrid PDL
Cites work
- Efficient access mechanisms for tabled logic programs
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 1033192 (Why is no real title available?)
- scientific article; zbMATH DE number 839542 (Why is no real title available?)
- Lock-free parallel dynamic programming
- NB{\texttt{malloc}}: Allocating memory in a lock-free manner
- On applying or-parallelism and tabling to logic programs
- On combining linear-based strategies for tabled evaluation of logic programs
- Parallel functional programming in Eden
- Parallel ILP for distributed-memory architectures
- Tabled evaluation with delaying for general logic programs
- Tabling as a library with delimited control
- The language features and architecture of B-Prolog
- The YAP prolog system
- Towards multi-threaded local tabling using a common table space
- XSB: extending Prolog with tabled logic programming
Cited in
(4)
This page was built for publication: Table space designs for implicit and explicit concurrent tabled evaluation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4559837)
