Speculative computations in or-parallel tabled logic programs

• Type: Article in International Scientific Journal
• Date: 2004

Authors

Rocha, R (Author) FCUP; Silva, F (Author) FCUP; Costa, VS (Author) FCUP

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-000-D5N

DOI: 10.1007/978-3-540-27775-0_18

Abstract (EN): Pruning operators, such as cut, are important to develop efficient logic programs as they allow programmers to reduce the search space and thus discard unnecessary computations. For parallel systems, the presence of pruning operators introduces the problem of speculative computations. A computation is named speculative if it can be pruned during parallel evaluation, therefore resulting in wasted effort when compared to sequential execution. In this work we discuss the problems behind the management of speculative computations in or-parallel tabled logic programs. In parallel tabling, not only the answers found for the query goal may not be valid, but also answers found for tabled predicates may be invalidated. The problem here is even more serious because to achieve an efficient implementation it is required to have the set of valid tabled answers released as soon as possible. To deal with this, we propose a strategy to deliver tabled answers as soon as it is found that they are safe from being pruned, and present its implementation in the OPTYap parallel tabling system.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15