Machine Independent and and or Parallel Execution of Logic Programs: Part I—The Binding Environment

We describe a binding environment for the and and or parallel execution of logic programs that is suitable for both shared and nonshared memory multiprocessors. The binding environment was designed with a view of rendering a compiler using this binding environment machine independent. The binding environment is similar to closed environments proposed by Conery. However, unlike Conery’s scheme, it supports or and independent and parallelism on both types of machines. The term representation, the algorithms for unificaiton and the join algorithms for parallel and branches are presented in this paper. We also detail the differences between our scheme and Conery’s scheme. A compiler based on this binding environment has been implemented on a platform for machine independent parallel programming called the Chare Kernel. In Part II of this paper, we describe the implementation of the compiler as a machine independent program and provide performance data on five parallel machines: the Encore Multimax, the Sequent Symmetry, the Intel i860 hypercube, and the NCUBE 2 hypercube. The compiler runs unchanged on all these parallel machines, thereby demonstrating machine independent parallel programming for a large real application. The benchmark programs also demonstrate the versatility of the compiler in exploiting different forms of parallelism in logic programs.