作者：
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 considered. The AND/OR process model uses the nested loop model for it,...
详细信息
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 considered. The AND/OR process model uses the nested loop model for it, which incurs much inefficiencies because it does not consider the relationship between literals. The improvement based on this point is made from static analysis of the data dependency graph which represents the relationship between literals in a clause. It is shown that our improved method for generating tuples is better than the AND/OR process model. Adoption of the improved method makes multiple failure situation handled more efficiently. We also show 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. Our 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.
暂无评论