The ROLOG User Manual - Version 1.0

Balkrishna Ramkumar Dept. of Computer Science

University of Illinois at Urbana-Champaign Urbana, Illinois 61801

October 15, 1989

THE ROLOG COPYRIGHT NOTICE

Authors: Balkrishna Ramkumar and Laxminant. V. Kalé (C) 1989 The Board of Trustees of the University of Illinois All Rights Reserved

Permission to use, copy, modify, and distribute this software and its documentation for educational, research, and non-profit purposes is hereby granted provided that the above copyright notice, the original authors names, and this permission notice appear in all such copies and supporting documentation; that no charge be made for such copies; and that the name of the University of Illinois not be used for advertising or publicity pertaining to distribution of the software without specific prior written permission. Any entity desiring permission to incorporate this software into commercial products should contact the Computing Research Laboratory, Department of Computer Science, University of Illinois, 1304 W. Springfield Avenue, Urbana, IL 61801. The University of Illinois makes no representations about the suitability of this software for any purpose. It is provided ”as is” without express or implied warranty.

Chapter 1

Introduction

This document is a user-manual for the ROLOG (programming with Reduce-Or LOGic) compiler for the parallel execution of logic programs. The compiler is an implementation of the Reduce-Or process model for the parallel execution of logic programs [3]. It is machine independent and is currently running on both shared and nonshared memory machines. More specifically, it is running on the Intel iPSC/2 hypercube, the Encore Multimax, the Sequent Symmetry (and Balance), and the Alliant FX/8.

Currently the ROLOG compiler accepts Prolog clauses as input in the form of a data dependency graphs. The dependencies are currently specified in the form of hand annotations. Chapter 4 discusses them in detail. The compiler has been designed to permit static analysis modules to be added in the future, whence these modules would be reponsible for automatically annotating the programs.

In this document, no details are given about the ROLOG abstract machine, the binding environment used to permit machine independence across both shared and nonshared machines, and its performance on the above mentioned machines. Details on these topics can be found in [9, 6, 8].

1.1 Limitations

This is a preliminary release of the compiler. We describe here, the limitations of the current version of the compiler and the proposed improvements in later versions.

The compiler runs only in an “all-solutions” mode, i.e. all possible solutions for a given query are computed. In this context, it is important to note that the binding environment developed for the compiler is not stack based. So there is no backtracking in our model and the “all-solutions” approach is a natural consequence. In later versions, we will buffer solutions at the root of the search space and supply them one at a time to the user as is done in C-Prolog or SB-Prolog.

Another limitation is that a read-eval loop has not yet been implemented for the compiler. Therefore, the code generator for Prolog programs and the byte code simulator are separate programs (written in C) which have to be invoked from the Shell. The read-eval loop will be made available in the next release.

The compiler accepts only pure Prolog as input. Cuts^{1}, asserts, retracts and other “side-effect” builtins are not accepted in the input Prolog programs. The only exception to this statement is the “write” predicate.

The compiler is a machine independent application on top of a run time support system called the Chare Kernel [4, 7]. The Chare Kernel is not part of this release, but is necessary to be able to run ROLOG. The source for the Chare Kernel is currently in the ck directory (see Chapter 2). The Chare Kernel will be released independently in the near future.

1.2 Reporting Bugs

As with any preliminary (?) release of software, the possibility of bugs cropping up always exists. Should you encounter any bugs, please send a concise bug report to ramkumar@cs.uiuc.edu. Any problems, doubts or queries may also be addressed to ramkumar@cs.uiuc.edu. Any suggestions for improvement are always welcome.

1Cut is permitted in sequential Prolog code, i.e. if the predicate definition in which a cut appears is declared to be sequential. See Chapter 3 for further details.

Installation

Once you have copied the all the compiler related files on your target machine, you should see the following files: COPYING, INSTALL, manual.dvi, rolog.tar.Z and ck.tar.Z. The COPYING file lays out the copying licencing policies relating to the use of the ROLOG compiler. It has also been described on pages 1-3 of this document. The INSTALL file is a C-shell script file that installs the compiler files in your directory. It is also possible to set up the compiler to automatically assign priorities to subgoals with the objective of finding the first solution fast (For details of the priority assignment and other related details, please see the references.) by adding a “priority” parameter while running INSTALL (see below). “manual.dvi” is the tex object code for this document (surprise! surprise!). The remaining two files are compressed “tar” files that contain the ROLOG compiler and related source code. For convenience, we will assume that these files have been copied into a directory called ROLOG on the target machine.

2.1 Installation without Priorities

Currently, the following machines can serve as target machines for the ROLOG compiler if automatic priority assignments for finding the first solution first is not required: the Encore Multimax, the Sequent Balance and Symmetry, the Alliant FX/8, the Intel iPSC/2 hypercube, and any unix based uniprocessor machine (like the Sun, for example). To install the compiler, with ROLOG as the current working directory, provide execute permission on INSTALL and type

     INSTALL <machine_name>

Currently, machine name can be one of max, sequent, alliant, ipsc2, unix, sun^{1}.

1Due to size of one of the files involved, on the sun it is necessary to use the -J option to compile it. Hence “sun”

is being distinguished from unix

2.2 Installation for Prioritized Execution

The following machines can serve as target machines for the ROLOG compiler: the Encore Multimax, the Sequent Balance and Symmetry, the Alliant FX/8, and any unix based uniprocessor machine. Prioritized execution of Prolog is not currently supported on non-shared memory machines such as the Intel iPSC/2 Hypercube. We expect to support these in a later version of the compiler. To install the compiler for prioritized execution, with ROLOG as the current working directory, provide execute permission on INSTALL and type

     INSTALL <machine_name> <priority>

Currently, machine name can be one of max, sequent, alliant, unix, sun for prioritized execution. Three kinds of prioritized execution are available and the system will prompt you to select one of them. The three priority options provide prioritized execution with increasing sophistication and therefore, overhead. For a detail explanation see [5]. The priority options are explained below:

1. The priority with Distance Bits provides the basic prioritized execution of programs with least overhead.

2. The priority with Static Instance Bits provides priorities to clauses and literals within a clause up to a certain level after which all clauses and literals are executed with the same priority.

3. The priority with Dynamic Instance Bits provides the most sophisticated prioritized execution with dynamically assigning distinct priorities to clauses and the literals within a clause.

Once the INSTALL file has been run, it will uncompress the “tar.Z” files mentioned earlier, extract the ROLOG compiler source files from them and “make” the necessary object files. Once the “INSTALLation” is complete, you should find three object files in the ROLOG directory on your target machine: gen, sim and disasm. You may choose to move them to a publicly accessible location (e.g. /usr/local/bin) and/or provide suitable alias commands in your .cshrc file. (Alternatively, you may prefer to modify the PATH variable in your .cshrc file to include the directory containing these files.)

The gen executable file is the ROLOG code generator. It takes as input (annotated) Prolog programs and generates abstract machine code. The disasm file disassembles this file and displays

ROLOG  ck rolog compiler  rolog progs gen dis common max alliant sequent ipsc2 unix

Figure 2.1: The directory structure in which the source code for the compiler has been organized.

the abstract machine instructions generated. sim is the abstract machine simulator which interprets the code generated by gen. Details on the use of the ROLOG compiler can be found in Chapter 5.

If the target machine is the Intel iPSC/2, instead of the sim object file, you will find three files: sim.host, sim.node and sim.in in the ROLOG directory. The sim.host file is the object file running on the iPSC/2 host processor, a copy of the sim.node file runs on each of the iPSC/2 nodes, and sim.in contains parameter values for the (relatively complex) load balancing on the iPSC/2. It is sufficient to know that this file must be present in the current working directory when “sim.host” is run. For details on executing Prolog programs on the Intel iPSC.2 see Chapter 5. Figure 2.1 describes the directory structure in which the compiler source code is organized. At the root is the ROLOG directory which contains two sub-directories called ck (for Chare-Kernel) and rolog compiler. In the ck directory is the run-time support environment on which the ROLOG compiler is written and provides a machine independent interface to the compiler. The other subdirectory, rolog compiler contains the source code for the compiler.

As indicated in Figure 2.1, the rolog compiler directory contains the following sub-directories: rolog progs, dis, gen, common, max, sequent, alliant, ipsc2 and unix. rolog progs contains sample Prolog programs written for the ROLOG compiler. gen contains the source code for the code generator. The source code for the disassembler of the generated code can be found in dis. The common directory contains all the source files for an abstract machine simulator to interpret the generated code. The other directories contain “makefiles” for the appropriate target machines. The unix directory supports a sequential version of the ROLOG compiler.

2.3 Problems

The user may encounter a couple of minor problems on a machine running System V Unix (for example, Intel iPSC/2). It is necessary to type

     csh INSTALL <machine_name>

to run the INSTALL script.

On the iPSC/2 hypercube, it is advisable to run the INSTALL script when there are no other users. The creation of the sim object file requires a very large amount of swap space, and it is very likely that the compilation will run out of memory if other users are running jobs on the iPSC/2 host at the same time.

Prolog: The Language

For reasons of expediency, we do not discuss the basic aspects of the Prolog language in this version of the document. Later versions of this document will remedy this omission. The basic syntax accepted by the ROLOG compiler is identical to that accepted by SB-Prolog (see [1]) or that discussed in books like The Art of Prolog by Leon Sterling and Ehud Shapiro [10].

We briefly list the builtins supported by the compiler. The behaviour of these builtins is as described in the SB-Prolog manual. The builtins currently supported are write, is, =:=, =

=, <, >, =<, >=, =, var, nonvar, atom, integer, functor, arg, =...

The builtins notably absent from this list (which have been postponed for the next version) are

not, setof, bagof, findall, P− >Q;R, read, and X^P. Other builtins not included in this

list will be added to the compiler on a demand driven basis.

Annotations for AND Parallelism

This description has been taken largely from Keith Hamburg’s M.S. thesis (see [2].)

4.1 Data Join Graphs

The body of a clause consists of a set of literals. It is not usually efficient to compute them all in parallel. Frequently, some partial ordering among the literals can be used to solve the query effectively. The Data Join Graph (DJG) encodes the parallelism of a clause by specifying which literals execute sequentially and which to execute in parallel. Each arc in the graph represents a literal of the clause. Each node denotes a joining point for the data produced by literals (arcs) incident on the node. Literals (arcs) emanating from a node can be evaluated only after the node is triggered. A DJG for the principal clause of the recursive quicksort program is given in Figure 4.1. Here, the two quicksort subgoals can be executed in parallel, but append cannot be triggered until the solutions for the quicksort subgoals have been computed.

The Prolog language has been extended to allow two separate ways of specifying a DJG.

4.1.1 Parenthetical Graph Notation

A restricted class of Data Join Graphs may be represented in what we call parenthetical notation. The parenthetical operators used in the body are “,” which is the sequential operator (as in sequential Prolog), and is read “followed by”, and //, which is the parallel operator and is read “in parallel with”. Parentheses are allowed for grouping. The principal clause for quicksort written in parenthetical notation is:

quick_sort([X| Rest],Sorted) :-

quick_sort([ ], [ ]).
quick_sort([X| Rest],Sorted) :-
         partition(Rest, X, Smaller, Bigger),
         quicksort(Smaller, Sorted1), quicksort(Bigger, Sorted2),
         append(Sorted1, [X| Sorted2], Sorted).

0  2  3  1 partition(...)  quicksort(...) quicksort(...)  append(...)

Figure 4.1: The quicksort program and the Data Join Graph for its principal clause.

0  2  3  1 p(I,X)q(I,T)r(X,Y)  s(X,Z) t(Y,T,U)

Clause body: p(I,X), q(I,T), r(X,Y), s(X,Z), t(Y,T,U).

Figure 4.2: A DJG that cannot be expressed using parenthetical notation.

         partition(Rest, X, Smaller, Bigger),
         (quicksort(Smaller, Sorted1) // quicksort(Bigger, Sorted2)),
         append(Sorted1, [X| Sorted2], Sorted).

The parallel operator has higher precedence than the sequential operator, but parentheses make

the notation clearer.

4.1.2 Arbitrary Graph Notation

Parenthetical notation has the advantages that the syntax is easy to remember, and it is easy

to read. One notable disadvantage is that some graphs simply cannot be represented using this

notation. Figure 4.2 is an example of such a graph.

A more general (and more complex) notation , called arbitrary notation, has been created to

deal with such graphs. Arbitrary notation specifies, for every node number, which literals leave the

q(A,B)  q(A,B) r(A,C)  r(A,C) s(A,D)  s(A,D) null

Figure 4.3: The DJG with multiple AND parallel branches and an equivalent transformation for the clause p(A,B,C,D) :- (q(A,B) // r(A,C) // s(A,D)).

node and what node they go to. The arbitrary notation for the above graph is

     pred :- 0: p(I,X) ==> 2, q(I,T) ==> 3;
             2: r(X,Y) ==> 3, s(X,Z) ==> 1;
             3: t(Y,T,U) ==> 1.

The first and last nodes in the DJG must be numbered 0 and 1 respectively. (The graph is numbered automatically when using parenthetical notation.) Note that any graph may be specified using arbitrary notation, but it is cumbersome, so parenthetical notation is preferable for simple graphs.

4.1.3 Restrictions

Join nodes in a DJG are restricted to a maximum of two incoming arcs. This is not a restriction on the expressivity of parallelism in Prolog programs because it is always possible to transform graphs with more than two incoming arcs at join nodes to one with two arcs. This is shown in Figure 4.3.

Currently, these annotations have to be provided by hand. We have a framework for adding static analysis modules to automate this process: such modules would incorporate the results of their analysis by adding the above annotations to the source program automatically.

4.1.4 Compiler Directives

The compiler also permits the programmer to specify useful information about predicates and clauses via compiler directives. A compiler directive has the form:

             :- <directive>(<pred>/<arity>).

Currently four compiler directives are accepted. One directive is det, which specifies determinacy of a predicate. A predicate is deterministic if at most one solution can ever be returned from a call to the predicate. Another compiler directive is nofail, which says that no call to that predicate will ever fail. If det and nofail are used in conjunction for a predicate, the predicate is specified to always return one solution. Another compiler directive is mutex, which states that the clauses of the predicate are pairwise mutually exclusive. Lastly, the programmer can request that a particular predicate always be evaluated sequentially bye using the seqex directive.

Compiler directives may be placed anywhere in the program. More than one may be specified at a time. For example,

     :- det(p/2).
     :- det([p/2, q/3, r/3]).
     :- det(p/2), nofail([p/2, q/3]), seqex(p/2).

are all legal compiler directives. An error message will be generated if a predicate/arity pair is specified in a compiler directive for a predicate that does not exist in the program.

4.1.5 Example Programs

We give here two example programs to illustrate the use of the annotations. The first is the simple recursive fibonacci program which has a sequential component to it and makes use of the available compiler directives to optimise it’s evaluation. The programs are given below:

:- seqex(sfib/2), det(sfib/2), nofail(sfib/2).
:- mutex(fib/2),  det(fib/2),  nofail(fib/2).
sfib(0,0).
sfib(1,1).
sfib(M,N) :- M > 1, M1 is M-1, M2 is M-2, sfib(M1,N1), sfib(M2,N2), N is N1+N2.
fib(M,N) :- M > 15,  ((M1 is M-1, fib(M1,N1))  //  (M2 is M-2, fib(M2,N2))),
                                                                 N is N1+N2.
fib(M,N) :- M =< 15, ((M1 is M-1, sfib(M1,N1)) //  (M2 is M-2, sfib(M2,N2))),
                                                                 N is N1+N2.
?- fib(25,M).   /* what is the fibonacci of 25? */

2 4 1 3  5  6

Figure 4.4: A map colouring example.

This program computes the fibonacci of all values <= 15 sequentially. Thus, the seqex directive provides a simple, yet powerful, way to incorporate grainsize control in programs.

In Figure 4.5 we provide one possible formulation of the map colouring problem for a map with six regions in Figure 4.4. The solutions to the top level query will generate all possible solutions. This example illustrates the expressive power of the arbitrary graph annotations. We have applied the restriction on join nodes (incoming arcs limited to 2) to the DJG in Figure 4.5.

0  2  3 4 5 6  7 8 9  10 11 12  13  1 1,2  2,3 2,4 2,5 2,6  1,3 3,4 3,6 1,5 5,6 1,6

colour(R1,R2,R3,R4,R5,R6) :-
 0: next(R1,R2) ==> 2;
 2: next(R2,R3) ==> 3, next(R2,R4) ==> 4,
    next(R2,R5) ==> 5, next(R2,R6) ==> 6;
 3: null ==> 7, null ==> 8, next(R1,R3) ==> 10;
 4: null ==> 7;
 5: null ==> 9, next(R1,R5) ==> 11;
 6: null ==> 8, null ==> 9, next(R1,R6) ==> 12;
 7: next(R3,R4) ==> 10;
 8: next(R3,R6) ==> 11;
 9: next(R5,R6) ==> 12;
10: null ==> 13;
11: null ==> 13;
12: null ==> 1;
13: null ==> 1.
next(blue,red).
     :
?- colour(R1,R2,R3,R4,R5,R6).

Figure 4.5: A possible DJG for the map colouring problem and the annotated program to represent it. The unlabelled arcs in the DJG correspond to null arcs.

Compiling and Executing Prolog Programs

The read-eval loop for the compiler has not been implemented in this version. Consequently, Prolog programs cannot be run interactively with this version on ROLOG. It is necessary to do the compilation and execution of Prolog programs, much the same way as C programs are on Unix.

5.1 Compiling Prolog Programs

Once the installation is complete, in the ROLOG directory (see Chapter 2) you should find an object file called gen. The gen program takes as input annotated Prolog programs as described in Chapter 4. When invoked, it creates two files as output, one contains the abstract machine instructions representing the Prolog program and the other contains the pure code or the skeletal code, the symbol table, and other related program data structures^{1} associated with the input Prolog program. gen is invoked as follows:

    gen [ -o <outfname> ] <filename>

where < filename > is the input file containing the Prolog program and < outfname > is the name of an output file name. The output file name is optional. If it is specified, the two output files created by gen are < outfname > .bc and < outfname > .pure. The former contains the abstract machine instructions representing the input Prolog program, the latter the pure code in the Prolog program. If no < outfname > is specified, the files created are Bytecode and Bytecode.pure by default. It is a good practice to specify < outfname >; it is conventional to use the same name as < filename >.

1The compiler uses structure sharing.

Another object file that can be found under ROLOG after installation is disasm. If you wish to obtain a disassembly of a compiled Prolog program, you may do so by typing:

    disasm [ <filename> ]

The < filename > field here is the same as the < outfname > field in the gen instruction (i.e. one having two files with the .bc and .pure extensions, respectively). If it is not provided, < filename > defaults to Bytecode. The output from disasm is sent to standard output.

5.2 Executing Prolog Programs

The manner in which programs are executed on shared and nonshared memory machines differ slightly. We describe each of them below.

5.2.1 Shared Memory Machines

If ROLOG has been installed on a shared memory machine, the third object file that you will find in the ROLOG directory after installation is sim. This file is the abstract machine simulator that interprets the code generated by gen. It is invoked as follows:

    sim [-T size] [-S size] [-Tr size] [-Prt] <filename>  [+p procs] [+m mem]

where < filename > is the name of the output files after running gen on the input Prolog program (i.e. the one which has two the extensions .bc and .pure respectively). The “-” switches are used by the ROLOG compiler whereas the “+” switches are used by the Chare Kernel. The square brackets (“[ ]”) are used to denote that fields inside the brackets are optional. The “-” and “+” options may be placed anywhere after sim on the command line. We have placed them as above to distinguish them easily.

−T This switch allows you to specify the amount of “term-space” required in multiples of 1K words. (Term-space is the area of memory in which new terms are constructed.) If the switch is not used, the default size is 100K words.

−S allows you to specify the size of the sequential stack (i.e. when a predicate is being evaluated in sequential mode by using the seqex compiler directive.). The default size for the sequential stack is currently 20K words.

−T r allows you to specify the size of the sequential trail. The default size for the trail is 7.5K words.

−P rt will enable the printing of the execution time after each solution is found in the Prolog search space.

+p allows you to specify the number of processors that you would like to run the simulator on. If not specified, the default number of processors is 1.

+m allows you to specifies the amount of memory requested per processor in kilobytes. The default memory size if 1 megabyte per requested processor. (It is quite likely that this much memory will not be available for a large number of processors. For such cases, it is necessary to explicitly request a smaller amount of memory using the +m switch.)

5.2.2 Nonshared Memory Machines

The only nonshared memory machine that the simulator currently runs on is the Intel iPSC/2 hypercube. Once the installation is complete, you should see three files in the ROLOG directory: sim.host, sim.node and sim.in. The first is the “host” component of the simulator, i.e. one that runs on the iPSC/2 host. The second is the “node” component of the simulator. The third is an input file used implicitly by sim.host that specifies several load balancing and queue management parameters on each of the nodes. It suffices to note that this file must belong to the directory from which sim.host is invoked.

To run the simulator on the iPSC/2 hypercube, it is first necessary to acquire a cube of the required size. This is done by typing:

    getcube -t n

where n is the required number of nodes. (n must be a power of 2, otherwise the power of 2 ≥ n is allocated.) Once a cube of the required size is available, the simulator can be invoked by

    sim.host sim.node <filename>

where filename identifies the two .bc and .pure files created by gen. The sim.in file is implicitly assumed to be available. This separation of sim into sim.host and sim.node is required on the iPSC/2 because of the need to explicitly broadcast the “node” program on each of the iPSC/2 nodes. sim.host thus explicitly broadcasts sim.node to each of the nodes, then broadcasts < filename > .bc ,< filename > .pure and sim.in files explicitly to the sim.node programs running on each of the nodes.

5.3 Problems

The following problems have been observed when running the compiler on the parallel machines.

As mentioned briefly earlier, allocating very large amounts of memory per processor leads to unpredictable behaviour on certain parallel machines. For example, the Encore Multimax simply fails to allocate the required number of processors, and allocates fewer with suitable error messages. For example:

     sim foo +p 4 +m 8000   /* 4 processors, 8Mb per processor requested */
     ROLOG Version 1.0
     PE 0 active
     PE 2 active
     INIT: failed to start pe #1
     PE 3 active

The behaviour is similar on the Intel iPSC/2, where any node that fails to satisfy the memory request aborts with a suitable error message. The other machines refuse to execute the sim command if the memory requested was not available.

5.4 Limitations

An awkward feature of the version of the Chare Kernel in the ck directory (see Chapter 2) is that the maximum number of available processors (MaxP e) is defined as a constant in a file called host.h in the ck/< memtype >/machine − id > directory under ROLOG. < memtype > is either shared or nonshared depending on whether the target machine is a shared memory or a nonshared memory machine. < machine − id > is one of max, alliant, sequent, ipsc2, unix, sun. The MaxP e field may need to be changed if the configuration of your target machine is different from the current value of MaxP e.

CREDITS

This work was originally conceived by Laxmikant V. Kale. The Reduce-Or Process Model for the parallel execution of logic programs was developed as part of his Ph.D. thesis at SUNY Stonybrook (December 1985). The optimised join algorithm for the exploitation of AND parallelism in logic programs also appears in his thesis. A binding environment for the parallel execution of logic programs on shared and nonshared machines was then jointly developed by Balkrishna Ramkumar and Laxmikant V. Kale and forms part of the former’s Ph.D. thesis at the University of Illinois. The abstract machine for both the Reduce-Or process model and the join algorithm was developed by Balkrishna Ramkumar.

The implementation of the Reduce-Or process model, binding environment, the abstract machine simulator and the join algorithm for the compiler was done by Balkrishna Ramkumar. The initial parser for the code generator was written by David Sehr, and further expanded with annotations, and primitive analysis by Keith Hamburg and David Roch. Modifications and additional analysis for compiled implementation of the optimised join algorithm were done by Balkrishna Ramkumar. The code generator was written by Balkrishna Ramkumar with assistance initially from Kevin Nomura. Kevin Nomura was also responsible for the original disassembler, which has since been expanded on by Balkrishna Ramkumar.

The Chare Kernel, the run time support system used by ROLOG, was implemented on the Intel iPSC/2 by Wennie Wei Shu and forms part of her Ph.D. thesis at the University of Illinois. The initial implementation of the Chare Kernel on the shared memory machines was done by Laxmikant V. Kale and ported to the Alliant FX/8. Kevin Nomura extended it and ported it onto the other shared memory machines and implemented the shared memory management modules. Vikram Saletore implemented the queueing and prioritizing strategies for the Chare Kernel, and added priority strategies for obtaining a first solution faster to ROLOG.

Bibliography

[1] Debray S.K. The SB-Prolog System, Version 2.5 - A User Manual. Technical Report, Dept. of Computer Science, University of Arizona, Tucson AZ 85721, November 1988.

[2] Hamburg K.A. Graph Analysis, Determinacy Analysis, and Annotations for Parallel Execution of Logic Programs. Master’s thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign, August 1988.

[3] Kale L.V. Parallel Architectures for Problem Solving. PhD thesis, Dept. of Computer Science, SUNY, Stonybrook, December 1985.

[4] Kale L.V. The Design Philosophy of the Chare Kernel Parallel Programming System. in preparation.

[5] Kale L.V. and Saletore V. Obtaining First Solution Faster in Parallel Problem Solving. In North American Conference on Logic Programming, October 1989. to appear.

[6] Kale L.V., Ramkumar B. and Shu W. A Memory Organization Independent Binding Environment for AND and OR Parallel Execution of Logic Programs. In The 5th International Conference/Symposium on Logic Programming, pages 1223–1240, Seattle, August 1988.

[7] Ramkumar B. and Kale L.V. A Chare Kernel Implementation of a Parallel Prolog Compiler. submitted for publication.

[8] Ramkumar B. and Kale L.V. Compiled Execution of the REDUCE-OR Process Model on Multiprocessors. In North American Conference on Logic Programming, October 1989. to appear.

[9] Ramkumar B., Kale L.V. An Abstract Machine for the Reduce-OR Process Model for Parallel Prolog. In Proceedings of the Second Symposium on Knowledge Based Computer Systems, Bombay, India, December 1989. to appear.

[10] Sterling L. and Shapiro E. The Art of Prolog. The MIT Press, 1986.