MACHINE-INDEPENDENT AND AND OR PARALLEL EXECUTION OF LOGIC PROGRAMS .1. THE BINDING ENVIRONMENT

We describe a binding environment for the AND and OR parallel executio n of logic programs that is suitable for both shared and nonshared mem ory multiprocessors. The binding environment was designed with a view of rendering a compiler using this binding environment machine indepen dent. The binding environment is similar to closed environments propos ed by Conery. However, unlike Conery's scheme, it supports OR and inde pendent AND parallelism on both types of machines. The term representa tion, the algorithms for unificaiton and the join algorithms for paral lel AND branches are presented in this paper. We also detail the diffe rences between our scheme and Conery's scheme. A compiler based on thi s binding environment has been implemented on a platform for machine i ndependent parallel programming called the Chare Kernel. In Part II of this paper, we describe the implementation of the compiler as a machi ne independent program and provide performance data on five parallel m achines: the Encore Multimax, the Sequent Symmetry, the Intel i860 hyp ercube, and the NCUBE 2 hypercube. The compiler runs unchanged on all these parallel machines, thereby demonstrating machine independent par allel programming for a large real application. The benchmark programs also demonstrate the versatility of the compiler in exploiting differ ent forms of parallelism in logic programs.