An important objective in logic programming research is to improve the performance of logic programming systems. A promising approach, in this respect, is to introduce parallelism into the program evaluation mechanism. Many of these models have, however, been based on the conventional approach of organizing concurrent components of computations as independent communicating processes. Some of them have the data-driven computation organizations. In this thesis, we investigate the application of the data-driven organization to the evaluation of logic programs.
Several kinds of parallelism can be found in logic programs. It is natural to associate the logic programming with a dataflow architecture to cope with the high parallelism.
Since input/output relationships of arguments are not fixed in the logic programs, for the conventional dataflow models to exploit AND-parallelism, they require a run-time support to control the dynamic token flow which induces severe overhead, or the join operation whose cost is not cheap.
Until now, there has been no evidence that the dataflow model has been successfully employed to exploit the AND-parallelism for pure logic programs. In this thesis, we propose D-Model, which is a mode driven dataflow model for AND/OR-parallelism of logic programs. In this model dataflow graphs supporting AND/OR-parallelism for logic programs can be produced through a graph generation procedure based on the mode which can be predicted at compile-time. Although the dataflow graph in the model does not provide an optimal AND-parallelism, there is no run-time overhead such as dynamic arcs between the literal nodes and no join operation between the literals. D-Model adopts the dataflow call-by-value mechanism and reduces the amount of multiset. The OR-parallelism is also supported.
The mode can be generated at compile-time through a refined static data dependency analysis, which is a variation of the static data dependency analysis proposed by Chang, et. al.
The argument-parallelism is also extensively studied in this thesis. There are three important factors which affect the construction of a dataflow graph for literal unification. They are the mode, handling of the share-variables in the head arguments and the way arguments are unified, i.e., parallel or sequential execution. In this paper, six kinds of head literal unification graphs are suggested based on the these factors, and they are compared by a simulation in view of the argument-parallelism, efficiency, and space requirement. From the simulation based on the approximate values of the parameters, it was shown that the mode and the lazy execution of share node in the head literal are very important for the overall efficiency and the argument-parallelism. It was also found that the sequential graph has the disadvantages in all the aspects.
논리 프로그램은 내재한 병렬성이 많으며, 이러한 병렬성을 이용하여 논리 프로그램을 병렬 처리하기 위한 여러가지 기법들에 대해 많은 연구가 진행되고 있다. 이러한 연구들 중에서 병렬성이 많은 데이타 플로우 컴퓨터를 이용하여 논리 언어의 병렬성을 처리하려는 시도는 자연스러운 방법이라고 할 수 있다. 그러나 논리 프로그램의 인수는 양방향성의 입출력 특성을 가지는데 비하여 데이타 플로우 그래프에서는 한쪽 방향으로 입출력이 고정되어야 하기 때문에 논리 프로그램을 데이타 플로우 그래프로 효과적으로 변환하는 문제는 먼저 해결해야 한다. 특히 논리 프로그램의 AND 병렬성을 구현하기 위해서 관리가 어려운 동적 아크(dynamic arc)나 값비싼 join 연산자를 사용하기 쉽다.
본 논문에서는 논리 프로그램의 AND 병렬성을 데이타 플로우 모델로 효과적으로 구현하는 D-Model을 제시한다.
D-Model은 컴파일 때 인수의 모드를 예상하여 값비싼 동적 아크나 join 연산자가 없는 데이타 플로우 그래프를 생성하여 수행할 수 있게 한다. D-Model은 그래프 생성법, 토큰(token)의 구성 및 수행 메카니즘의 정의 즉 각 노드들의 기능에 대한 정의들로 이루어진다. 생성된 데이타 플로우 그래프는 AND 병렬성에서 문제가되는 공유 변수의 수를 줄일 수 있도록 데이타 플로우 call-by-value 기법을 사용하며, 같은 값이 여러번 생성되는 것을 방지할 수 있는 기능도 포함한다. 모드의 생성은 Chang의 방법을 개선한 refined static data dependency analysis를 사용한다. 또한 논리 프로그램의 인수 병렬성(argument parallelism)에 대한 연구 결과로 모드를 사용하는 방법과 공유 변수의 lazy evaluation이 효과적임을 알 수 있었다.
