An adaptive mechanism and mixed strategies approach to parallel execution of logic programs
E. Rogers, Mohamad Ali Kodeih · 1988
Current methods of generating control decisions for execution of logic programs rely generally on information provided by (e.g., mode declarations, variable annotations and system predicates). These constructs can burden the programmer and make logic programs less elegant and more difficult to understand and maintain. This paper presents a new method for parallel execution of logic programs that will be queried intensively and emphasizes automatic generation of control decisions. Typically automatic determination of control decisions leads to inefficient execution. This is caused either by inaccurate decisions, if these decisions are made at compile time (that is, prior to execution), or by the large amount of bookkeeping, if these decisions are made at run time. In order to limit this inefficiency, this research presents a scheme which consists of the following. (1) Execution of a program involves the use of two strategies: Strategy One, which determines control decisions at run time and Strategy Two, which generates control decisions at compile time (without extra-logical constructs). (2) The program is partitioned into two components, with distinct strategies (One and Two) applied. Strategy One determines dependence/independence relations and execution order of the literals in a program at run time. It implements an adaptive mechanism which improves and re-uses information obtained about each literal in previous executions. This mechanism is shown to improve execution speed-up. In contrast to Strategy One, Strategy Two determines dependence/independence relations and execution order of literals in the program. It is demonstrated through examples that, when little or no information is available from the user, this method extracts more parallelism than other methods which infer types of bindings of variables statically. In order to apply both strategies to different portions of the program, a method which partitions the program into two disjoint sets is described. The method is based on studies of partitioned programs having regular structures. This parallel execution scheme is simulated and simulation results demonstrate that further speed-up is obtained when a mixed strategy is used.