In this thesis, the Goal Process model which is a new parallel execution model of Prolog programs and X-WAM multiprocessor System(X-WAMS) are proposed.
The Goal Process Model supports restricted AND parallelism with both intelligent back-tracking and eager OR. Compared to the other models for AND parallel execution of Prolog programs, the Goal Process Model can enhance the performance of nondeterministic programs with a lot of backtrackings due to both the eager OR and the intelligent backtracking.
As an intermediate code for the Goal Process Model, extended conditional graph expression which is an extension of the conditional graph expression of DeGroot is also suggested. The extended conditional graph expression contains the information for both the forward execution and the backward execution of a clause. It is generated automatically by a static flow analysis of a given program.
The X-WAMS is a multiprocessor system which can support both AND and OR parallelism. The control mechanism of the X-WAMS is based on the Goal Process Model. However, OR parallelism can also be exploited in the X-WAMS by the static split of a Prolog program. That is, after a given program is split into disjoint programs for OR parallel execution, they are distributed over all the processors in the X-WAMS. Then, a disjoint program is solved independently by a processor using the control mechanism of the Goal Process Model. Therefore, the static decision for OR parallel execution and the dynamic decision for AND parallel execution are made in the X-WAMS.
본 논문에서는 Prolog 프로그램을 위한 새로운 병렬 수행 모델과 이를 위한 가상적인 다중 처리기 시스템 X-WAMS을 제시하고 그 성능을 평가한다. 새로운 병렬 수행 모델인 Goal Process Model은 제한된 AND 병렬성과 효율적인 backtracking 기능을 지원하는 병렬 수행 모델 이며 Conery의 AND/OR Process Model 에 기초하고 있다. 이에대해 X-WAMS은 Goal Process Model을 위한 확장된 (eXtended) WAM이며 동시에 정적인 프로그램 분할 방식을 이용하여 AND 와 OR 병렬성을 동시에 추구할 수 있는 다중처리기 시스템 이다.
X-WAMS에서 주어진 프로그램은 OR 병렬성을 이용하여 여러개의 프로그램으로 나누어진후, 각각의 프로그램은 AND 병렬성을 이용할 수 있도록 확장된 CGE로 자동 변환 되며, 최종적으로 각각의 CGE는 X-WAMS 코드로 컴파일 된다. 컴파일된 code는 각 X-WAMS의 처리기에 분산된 후 각 코드를 수행하는 goal process들에 의해 독립적으로 처리된다. 즉 OR 병렬 처리는 정적인 프로그램 분할에의해 생성된 독립된 goal process들에 의해 이루어지며 AND 병렬 처리는 X-WAMS내에 생기는 idle한 처리기들을 이용하여 각각의 goal process들이 새로운 goal process들을 만들어냄으로써 동적으로 이루어 진다. 따라서 X-WAMS는 AND와 OR 병렬성이 동시에 나타나는 비결정적 (non-deterministic) 프로그램과 AND 병렬성이 주로 나타나는 결정적 (deterministic) 프로그램을 효과적으로 병렬 수행할 수 있는 가상적인 다중처리기 시스템 이다.
