As researches in designing "smarter" computers proceed, the need for parallel execution of programs becomes apparent and essential. Also, multiprocessor environments spread swiftly in these days, as the cost for hardware has been declining. Nowadays, logic programming paradigm stands in the spotlight of numerous researchers, especially owing to massive potential parallelism inherent in logic programs. This parallelism can be classified into various types; AND, OR, stream, and search parallelism, among which AND and OR parallelism are the most notable ones.
From the motives described above, interests in AND/OR-parallel evaluation of logic programs have been rapidly growing. Thus, many models have been proposed for AND/OR-parallel execution of logic programs, among which the AND/OR Process Model proposed by Conery became dominant since it naturally reflected computational structures of logic programs.
AND-parallel execution in the AND/OR Process Model consists of two phases; forward and backward execution. The forward execution is conceptually simple, whereas the backward execution must solve two rather complex problems; backtrack literal selection and reset problems. A lot of algorithms have been suggested to execute the backward execution efficiently: to reduce the amount of work undone and redone by redoing a backtrack literal and resetting some other literals, intelligent backtracking and selective resetting algorithms have appeared.
Nevertheless, they have still been in controversy from the viewpoint of completeness, intelligence (i.e., doing less amount of unnecessary work somewhat without regard to overhead to achieve this task), and efficiency. This is caused by the "absence of really formalized and unified framework for AND parallelism," we think, and so the debate is quite likely to be baseless.
Therefore, we re-examine the problems of backward execution (backtrack literal selection and resetting) and try to devise a unified (or generalized) and formalized framework for AND-parallel evaluation of logic programs, the AND Process Configuration, in the dissertation. This framework is represented as a directed graph decorated with some attributes. The underlying graph grows dynamically as AND-parallel execution proceeds, and shows affection history among literals. On the other hand, some of the attributes represent failure situation.
The framework can be used to (1) uniformly solve the problems in backward execution, (2) elegantly explain the philosophy behind intelligent backtracking and selective resetting, (3) analyze the correctness and efficiency of other existing backward execution algorithms, and (4) develop a new algorithm to exhibit more intelligent behavior than other ones. We show that other existing studies in AND-parallel execution can be explained as instances of this framework. Furthermore, we propose three (rather realistic) backward execution algorithms based upon the proposed framework, which perform literal-level and/or solution-level selective resetting, including their correctness proof. The proposed algorithms enable us to perform backtracking and resetting more intelligently than other related works.
본 논문에서는 논리 프로그램의 AND-병렬 수행을 위한 통합된 틀로서 AND 프로세스 컨피규레이션(약해서 APC)이라고 불리우는 형식화된 객체를 제안하였다.
병렬 수행의 필요성과 논리 프로그램내에 내재하는 자연스런 병렬성이 결합하여 최근 약 십년간 논리 프로그램의 병렬 수행에 관해서 대단히 많은 연구가 있었다. 특히 AND-병렬성과 관련된 몇가지 문제를 해결하는데 연구가 집중되는 경향이었다.
그러나 많은 연구에도 불구하고 AND-병렬성과 연관된 문제를 위해 제안된 여러 해법들은 완전성과 효율성 측면에서 여전히 논쟁의 대상이 되고 있다. 본 논문에서는 이러한 현상이 AND-병렬 수행의 제문제들과 그것을 해결할 수 있는 요소들을 제대로 표현해 줄 수 있는 통합된 틀의 부재에 연유한다고 보았다.
제안된 틀, 즉 APC는 크게 두가지의 구성 요소로 이루어진다. 첫째는 AND 영향 그래프(약해서 AAG)로서 이것은 리트럴들간에 주고받았던 영향을 기록하는 동적으로 성장하는 그래프이다. 두번째는 몇가지 속성들로서 이것들은 AND-병렬 수행시 리트럴들의 상태와 과거의 실패가 일어났던 상황을 기록하는 역할을 한다.
본 논문에서는 (1) 제안된 틀을 사용함으로써 AND-병렬 수행과 관련된 제반 문제들을 통합적인 시각에서 효율적으로 처리할 수 있음을 보였고, (2) 기존의 여러가지 AND-병렬 수행 방법들이 제안된 틀의 단순화된 형태들임을 보였으며, (3) 제안된 틀을 도구로 사용하여 기존의 방법들을 분석한 결과, 지금까지 옳다고 알려진 어떤 방법들이 틀린것임을 밝혔고, (4) 제안된 틀을 바탕으로 하여, 기존의 방법들보다 효율적이라고 생각되는 새로운 방법을 개발했다.
