(The) AND process configuration

Abstract

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 form...