A number of studies have been made on the parallelism embedded in the logic programming languages for the purpose of performance improvements in the execution of the logic programs. The difficulty of AND parallel execution is due to the shared variables between the subgoals. This problem can be resolved by the algorithm that controls which subgoal is solved first. The algorithm can be used either at compile-time or at run-time.
This thesis proposes an AND/OR process model which extracts more AND parallelism by checking the bindings of the shared variables using the self-checking criteria of binding sets during run-time.
The proposed model is applied to the tree-structured architecture, using the allocation algorithm which allocates the clauses to be unified with each subgoal of a clause to the child processors of the current processor which contains that clause.
본 논문에서는 논리언어를 병렬로 수행하는 모델에 관해서 논하였다. 병렬로 수행하는 방법에는 AND-parallelism과 OR-parallelism 을 이용하는 방법이 있다. OR-parallelism 은 쉽게 수행할 수 있지만 AND-parallelism 은 한 clause 내의 공유 변수로 인하여 쉽게 수행할 수 없다. 이 문제를 해결하기 위해서 run-time 에 사용할 수 있는 self-checking criteria 를 제시하였으며 이것을 이용해서 병렬수행모델을 구성하였다.
또한, 제안된 모델을 tree 구조의 다중처리기에 적용시켰으며 논리 프로그램의 각 clause 들을 다중처리기에 할당하기 위한 알고리즘을 제시하였다.
모든 처리기는 MIMD 형태로 동작하며 message 전달이 서로 이웃한 처리기 사이에서만 일어나므로 traffic 이 분산된다. 한 처리기는 자기 아래 처리기에서 보내오는 해만 가지고 있으면 되므로 기억 장소가 적게 들며 SIMD 로 동작하는 모델보다 더 많은 parallelism 을 수행할 수 있다.
