Parallel Backtracking with Answer Memoing for Independent And-Parallelism

Details Parallel Backtracking with Answer Memoing for Independent And-Parallelism Parallel Backtracking with Answer Memoing for Independent And-Parallelism

2011-07-24

arxiv.org/abs/1107.4724v1

Theory and Practice of Logic Programming (2011) volume 11, issue 4-5, pages 555-574

Computer Science

Programming Languages

19 pages, 15 figures, uses tlp style

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Parallel Backtracking with Answer Memoing for Independent And-Parallelism does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Parallel Backtracking with Answer Memoing for Independent And-Parallelism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel Backtracking with Answer Memoing for Independent And-Parallelism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-76436