Annotation of Logic Programs for Independent AND-Parallelism by Partial Evaluation
This addresses the challenge of efficiently parallelizing logic programs for improved performance in computational logic systems, though it appears incremental as it builds on existing partial evaluation methods.
The paper tackles the problem of automatic AND-parallelization in logic programs by introducing a novel technique based on partial evaluation, which generates annotations for independent parallelism and transforms source programs to expose more parallelism opportunities, resulting in the first parallelizing partial evaluator approach.
Traditional approaches to automatic AND-parallelization of logic programs rely on some static analysis to identify independent goals that can be safely and efficiently run in parallel in any possible execution. In this paper, we present a novel technique for generating annotations for independent AND-parallelism that is based on partial evaluation. Basically, we augment a simple partial evaluation procedure with (run-time) groundness and variable sharing information so that parallel conjunctions are added to the residual clauses when the conditions for independence are met. In contrast to previous approaches, our partial evaluator is able to transform the source program in order to expose more opportunities for parallelism. To the best of our knowledge, we present the first approach to a parallelizing partial evaluator.