A method of generating n-tuples for a clause with n-variables as its argument under the and/or process model (Conery, 1983) of logic programs is investigated. The and/or process model employs the nested loop model, w...
详细信息
A method of generating n-tuples for a clause with n-variables as its argument under the and/or process model (Conery, 1983) of logic programs is investigated. The and/or process model employs the nested loop model, which incurs numerous inefficiencies because it does not take into consideration the relationship between literals. An improved method for generating tuples for the backward execution is developed using the static analysis of the data dependency graph. This method removes the inefficiency and redundancy of the nested loop model. Adoption of the improved method allows multiple failure situations to be handled more efficiently. It is also shown that several backtrack literals can be found for multiple failures by analyzing the sources of failures when the improved method is used for generating tuples. The proposed method is illustrated by several examples.
An efficient backward execution method for AND-parallelism in logic programs is proposed. It is devised through a close examination of some relation over literals, which can be represented by paths in the data depende...
详细信息
An efficient backward execution method for AND-parallelism in logic programs is proposed. It is devised through a close examination of some relation over literals, which can be represented by paths in the data dependency graphs. The scheme is more efficient than other works in the sense that it performs less unfruitful resetting (and consequently, canceling) operations. Its rationale is also intuitively clear and natural. Furthermore, the relevant analyses needed for the proposal are largely achieved at compile time, which alludes to actual efficiency.
This paper presents a parallel execution model for exploiting AND-parallelism in Horn Clause logic programs. The model is based upon the generator-consumer approach, and can be implemented efficiently with small run-t...
详细信息
This paper presents a parallel execution model for exploiting AND-parallelism in Horn Clause logic programs. The model is based upon the generator-consumer approach, and can be implemented efficiently with small run-time overhead. Other related models that have been proposed to minimize the run-time overhead are unable to exploit the full parallelism inherent in the generator-consumer approach. Furthermore, our model performs backtracking more intelligently than these models. We also present two implementation schemes to realize our model: one has a coordinator to control the activities of processes solving different literals in the same clause; and the other achieves synchronization by letting processes pass messages to each other in a distributed fashion. Trade-offs between these two schemes are then discussed.
Recently Conery proposed a backward execution algorithm for AND-parallel execution of logic programs, and Ng and Leung extended it. They adopt the same data structure called mark(s) set to store information about fail...
详细信息
Recently Conery proposed a backward execution algorithm for AND-parallel execution of logic programs, and Ng and Leung extended it. They adopt the same data structure called mark(s) set to store information about failure history during AND-parallel evaluation of clauses. Both of the two algorithms essentially have the same rationale with minor differences and have been considered correct, largely due to their intuitive persuasiveness. We closely re-examine those algorithms and find out that they are incorrect. Their incorrectness comes from oversimplification of failure situations. Our analyses focused on the mark(s)-set-based backtrack literal selection are presented. We also propose another backtrack literal selection method based on the mark(s) set, and prove its correctness.
暂无评论