MACHINE-INDEPENDENT AND AND OR PARALLEL EXECUTION OF LOGIC PROGRAMS .2. COMPILED EXECUTION

In Part I of this paper, we presented a binding environment for the AN D and OR parallel execution of logic programs. This environment was in strumental in rendering a compiler for the AND and OR parallel executi on of logic programs machine independent. In this paper, we describe a compiler based on the Reduce-OR process model (ROPM) for the parallel execution of Prolog programs, and provide performance of the compiler on five parallel machines: the Encore Multimax, the Sequent Symmetry, the NCUBE 2, the Intel i860 hypercube and a network of Sun workstatio ns. The compiler is part of a machine independent parallel Prolog deve lopment system built on top of a run time environment for parallel pro gramming called the Chare kernel, and runs unchanged on these multipro cessors. In keeping with the objectives behind the ROPM, the compiler supports both OR and independent AND parallelism in Prolog programs an d is suitable for execution on both shared and nonshared memory machin es. We discuss the performance of the Prolog compiler in some detail a nd describe how grain size can be used to deliver performance that is within 10% of the underlying sequential Prolog compiler on one process or, and scale linearly with increasing number of processors on problem s exhibiting sufficient parallelism. The loose coupling between parall el and sequential components makes it possible to use the best availab le sequential compiler as the sequential component of our compiler.