Parallel backtracking with answer memoing for independent and-parallelism
From MaRDI portal
Abstract: Goal-level Independent and-parallelism (IAP) is exploited by scheduling for simultaneous execution two or more goals which will not interfere with each other at run time. This can be done safely even if such goals can produce multiple answers. The most successful IAP implementations to date have used recomputation of answers and sequentially ordered backtracking. While in principle simplifying the implementation, recomputation can be very inefficient if the granularity of the parallel goals is large enough and they produce several answers, while sequentially ordered backtracking limits parallelism. And, despite the expected simplification, the implementation of the classic schemes has proved to involve complex engineering, with the consequent difficulty for system maintenance and extension, while still frequently running into the well-known trapped goal and garbage slot problems. This work presents an alternative parallel backtracking model for IAP and its implementation. The model features parallel out-of-order (i.e., non-chronological) backtracking and relies on answer memoization to reuse and combine answers. We show that this approach can bring significant performance advantages. Also, it can bring some simplification to the important engineering task involved in implementing the backtracking mechanism of previous approaches.
Recommendations
- scientific article; zbMATH DE number 1497835
- scientific article; zbMATH DE number 3967899
- Strict and nonstrict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions
- scientific article; zbMATH DE number 3965422
- A backtracking algorithm for the stream AND-parallel execution of logic programs
Cites work
- Automatic compile-time parallelization of logic programs for restricted, goal level, independent and parallelism
- Determinacy Analysis for Logic Programs Using Mode and Type Information
- Integrated program debugging, verification, and optimization using abstract interpretation (and the Ciao system preprocessor)
- Overview of DASWAM: Exploitation of dependent and-parallelism
- Strict and nonstrict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions
- Tabled evaluation with delaying for general logic programs
Cited in
(3)
This page was built for publication: Parallel backtracking with answer memoing for independent and-parallelism
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3087444)
