作者：
KIM, DHCHOE, KMProgramming Languages Laboratory
Department of Computer Science Korea Advanced Institute of Science and Technology 371-1 Kusong-Dong Yusang-Gu Taejon 305-701 South Korea
An efficient backward execution algorithm in the AND/OR Process Model for parallel evaluation of logic programs is proposed. The efficiency of the algorithm is achieved by means of information acquired during executio...
详细信息
An efficient backward execution algorithm in the AND/OR Process Model for parallel evaluation of logic programs is proposed. The efficiency of the algorithm is achieved by means of information acquired during execution of clauses. The algorithm is considered to be efficient in the sense that it issues fewer number of cancel messages and avoids unnecessary resetting operations. Furthermore, it performs independent redoing and resetting more concurrently than other related works.
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 backwardexecution 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.
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.
暂无评论