We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Parallel backtracking with answer memoing for independent and-parallelism.
- Authors
DE GUZMÁN, PABLO CHICO; CASAS, AMADEO; CARRO, MANUEL; HERMENEGILDO, MANUEL V.
- Abstract
Goal-level Independent and-parallelism (IAP) is exploited by scheduling for simultaneous execution of 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., nonchronological) 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.
- Subjects
PARALLEL algorithms; LOGIC programming; PERFORMANCE evaluation; MAINTENANCE; COMPUTER science; COMPUTER programming
- Publication
Theory & Practice of Logic Programming, 2011, Vol 11, Issue 4/5, p555
- ISSN
1471-0684
- Publication type
Article
- DOI
10.1017/S1471068411000172