In this thesis, a parallel token machine for the AND/OR parallelism of a logic programming language is proposed. This machine is composed of limited number of processors, a token pool, a waiting pool, and a common memory. The token pool contains the tokens in the running state and the waiting pool contains the tokens in the waiting state. The common memory stores a program, binding environments, and management information. A token in the token pool or the waiting pool represents the state of a process. As well as an OR parallelism, the parallel token machine exploits an AND parallelism found in a deterministic clause such as divide and conquer algorithms. Therefore, the parallel token machine increases the parallelism as compared with the OR-parallel token machine. A computational model to achieve AND/OR parallelism is presented, and to support that computational model, the machine instruction of the abstract machine and the interpretation cycle of a processor are newly defined.
본 論文에서 論理言語에 내재하는 parallelism을 수행하는 병렬수행 Token Machine을 제안하였다. 論理言語에 내재하는 parallelism에는 크게 보아 AND parallelism과 OR parallelism을 들 수 있는데, OR parallelism의 수행은 큰 문제가 없으나 AND parallelism인 경우 한 clause내의 literal사이에 종속관계(dependency)가 존재할 때 수행에 문제가 있다. 이 문제를 해결하기 위해 모우드 선언을 통해 구할 수 있는 literal ordering을 이용하여 AND parallelism을 수행하는 AND /OR 병렬수행모델을 제시하였다.
그리고 이 수행모델을 위한 공유 메모리(common memory)를 갖는 병렬 프로세서의 모델을 제시하고, 각 프로세서의 기계어(machine instruction)와 해석 싸이클(interpretation cycle)을 새로이 정의하였다.
