Decomposability and its role in parallel logic-program evaluation

AbstractThis paper is concerned with the issue of parallel evaluation of logic programs. We define the concept of program decomposability, which means that the load of evaluation can be partitioned among a number of processors, without a need for communication among them. This in turn results in a very significant speedup of the evaluation process. Some programs are decomposable, whereas others are not. We completely syntactically characterize three classes of single-rule programs with respect to decomposability: nonrecursive, simple linear, and simple chain programs. We also establish two sufficient conditions for decomposability