A methodology for detecting shared variable dependencies in logic programs

AND-parallel execution of logic programs turns out to be an intricate matter whenever clause literals are linked by shared variables. Shared variable dependencies call for special precautions to prevent processes from computing inconsistent bindings while working on clause literals simultaneously. Therefore, most systems restrict AND-parallelism to its producer/consumer style by allowing only independent literals to run in parallel. These literals then act as producers of variable bindings which will be consumed by dependent literals in subsequent steps. However, to implement producer/consumer parallelism efficiently, appropriate methods must be available for detecting dependencies caused by shared variables. Concerning such dependencies this paper presents a methodology which may serve as a basis for efficient dependency checking by performing compile and run-time analysis of program clauses