Automatic Compile-Time Parallelization of Prolog Programs for Dependent And-Parallelism
Enrico Pontelli, Gopal Gupta, Francesco Pulvirenti, Alfredo Ferro · The MIT Press eBooks · 1997
The problem of automatically detecting dependent and-parallelism in Prolog programs has not been studied so far. In this paper we discuss major issues involved in using static analysis to detect dependent and-parallelism in Prolog programs. We present a static analysis technique based on abstract interpretation that detects (fruitful) dependent and-parallelism. Our method makes use of several types of information about the program---sharing and freeness, granularity of subgoals, and binding-times of program variables---computed using abstract interpretation. The information collected from different sources is used to produce a suitable annotation of the original program. This annotation identifies: (i) the most fruitful sources of parallelism; and, (ii) the dependencies that must be respected during execution. A prototype compiler that incorporates these ideas has been implemented and tested on the ACE and-or parallel Prolog system. The (very encouraging) results obtained are reported h...