Downloads & Free Reading Options - Results

This progress report summarizes work performed under AFOSR-88-0152 on parallel logic programming, problem solving, and deductive databases. A parallel problem solving system, PRISM (Parallel Inference System), that was implemented on McMOB was ported to the BBN Butterfly machine. Two versions of PRISM were developed and are operational on the Butterfly: a message passing ring structure system and a shared-memory system. Experimental testing of PRISM on McMOB continued, while experiments were also conducted on the Butterfly systems. Three enhancements were made and completed during the grant period. These are: a capability to handle negated queries and a capability to assert and retract statements. In addition to the above, work continued in the area of informative answers to queries in deductive data bases. A thesis was completed on the subject. An interpreter was developed and is running, that can take restricted natural language as input and can respond with a cooperative natural language output. In the area of parallel software development, the following were accomplished. Theoretical work on slicing/splicing was completed. Tools were provided for software development using artificial intelligence techniques. AI software for massively parallel architectures was started.

This final report presents a summary of research accomplished to investigate parallel problem solving. Under the current grant a parallel problem solving system, PRISM (Parallel Inference System), that was implemented on the VAX/11-780, the PYRAMID and SUN machines, was ported successfully to McMOB and then to the BBN Butterfly parallel architecture. The McMOB architecture is essentially the ZMOB architecture with 16 Motorola 68000 processors, upgrading the Z80A microprocessors, interconnected in a ring structure. Experimental testing of PRISM on McMOB was undertaken in the current year. In addition, several enhancements were made to PRISM to permit experimental analyses to be made, and to incorporate additional features to take full advantage of parallelism in a problem solving environment. The tracing and statistical gathering packages were extended. An ability to display AND-parallelism was added to the trace program which displays the execution of a program on the parallel machines. In addition to the above, work continued in the area of informative answers to be presented to a user. Heuristic techniques were developed to determine which information to display. Keywords: Splicing compilers, Debugging software, Artificial intelligence.

45 p. 28 cm

Xerox PARC (Palo Alto Research Center) Parallel Logic Programming Ehud Shapiro Nov 25, 1986 Reel 2 of 2

The initial version of PRISM uses a simulation of the ZMOB hardware, and has been fully tested and debugged. In addition, several enhancements were made to PRISM to permit experimental analyses to be made, and to incorporate additional features to take full advantage of parallelism in a problem solving environment. Tracing and a statistical gathering package were added to permit experimental analysis. An AND-parallelism capability was added to achieve a second version of the PRISM system, and other features were added to the system to more fully exploit parallelism. Preliminary application and evaluation studies were performed. In the area of systems hardware and software, the ZMOB processor is now fully functional and in everyday use with 128 processors. Work is continuing on an experimental upgrade of some of ZMOB's processors to 68000s. Basic system software for multiprocessing on ZMOB is becoming more robust and performance studies now pinpoint areas for improvement. Studies of parallel software debugging continue to prove the value of multiple program views, and in particular the dicing approach was verified in a controlled experiment. We have also constructed an interactive visual slicer. Studies of the automatic parallelization of programs continues. We can now slice/splice arbitrarily structured programs and have techniques that significantly reduce information overhead between the slices and the splicer. (Author)

The objective of this effort was to investigate methods for distributing a knowledge base over multiple processors using the logic programming paradigm. A three-fold approach was employed and is discussed in this report. The first phase involved the testing of the Parallel Knowledge- based Execution System (PKES). Secondly, memory allocation techniques were investigated and evaluated. Lastly, a study of the implementation of data-typing in a logic programming paradigm is discussed. (CP)

Xerox PARC  (Palo Alto Research Center) Parallel Logic Programming Ehud Shapiro Nov 25, 1986 Reel 1 of 2

The purpose of this letter is to discuss our research into parallel systems software and hardware, and parallel problem solving. Under the current grant, a detailed design and partial implementation of a parallel problem solving system, PRISM (parallel inference system), based on logic was achieved. The PRISM requires that the ZMOB parallel processor be available for use. In addition, systems software and hardware have been developed. It is estimated that ZMOB will become available for use during the Fall of 1983. Hence, a full test and debugging of PRISM cannot be achieved under the current grant. At the end of the current grant we expect to have accomplished, as a minimum, all of the objectives proposed. That is, in the area of parallel problem solving, the initial PRISM has been fully designed; individual programs have been implemented and tested in a non-parallel environment; and investigations have been made into extensions to the initial design.

Under the current grant parallel hardware and systems software implemented on ZMOB in the previous year underwent extensive testing. A parallel problem solving system, PRISM (Parallel Inference System) implemented on the VAX/11-780 in the previous year was implemented on the PYRAMID and SUN machines. The initial version of PRISM uses a simulation of the ZMOB hardware, and has been fully tested and debugged. Experimental testing of PRISM on the simulated system was undertaken in the current year. In addition, several enhancements were made to PRISM to permit experimental analyses to be made, and to incorporate additional features to take full advantage of parallelism in a problem solving environment. The tracing and statistical gathering packages were extended. An AND-parallelism capability was added to achieve a second version of the PRISM system, and other features were added to the system to more fully exploit parallelism. A constraint solving machine was integrated with PRISM. In addition to the above, a general method to permit informative answers to be presented to a user has been developed. Theoretical results were obtained for circumscription and a method for computing in protected circumscription, using Horn clauses was developed. In the area of systems hardware and software, the ZMOB processor is now fully functional and in everyday use with 128 processors.

The initial version of PRISM uses a simulation of the ZMOB hardware, and has been fully tested and debugged. In addition, several enhancements were made to PRISM to permit experimental analyses to be made, and to incorporate additional features to take full advantage of parallelism in a problem solving environment. Tracing and a statistical gathering package were added to permit experimental analysis. An AND-parallelism capability was added to achieve a second version of the PRISM system, and other features were added to the system to more fully exploit parallelism. Preliminary application and evaluation studies were performed.

The initial version of PRISM uses a simulation of the ZMOB hardware, and has been fully tested and debugged. In addition, several enhancements were made to PRISM to permit experimental analyses to be made, and to incorporate additional features to take full advantage of parallelism in a problem solving environment. Tracing and a statistical gathering package were added to permit experimental analysis. An AND-parallelism capability was added to achieve a second version of the PRISM system, and other features were added to the system to more fully exploit parallelism. Preliminary application and evaluation studies were performed.

The Sync Model, a parallel execution method for logic programming, is preposed. The Sync Model is a multiple-solution data-driven model that realizes AND parallelism and OR-parallelism in a logic program assuming a message-passing multiprocessor system. AND parallelism is implemented by constructing a dynamic data flow graph of the literals in the clause body with an ordering algorithm. OR parallelism is achieved by adding special Synchronization signals to the stream of partial solutions and synchronizing the multiple streams with a merge algorithm. The ordering algorithm and the merge algorithm are described. The merge algorithm is proved to be correct and therefore, the Sync Model is proved complete, i.e., the execution of a logic program under the Sync Model generates all the solutions.

The Sync Model, a parallel execution method for logic programming, is preposed. The Sync Model is a multiple-solution data-driven model that realizes AND parallelism and OR-parallelism in a logic program assuming a message-passing multiprocessor system. AND parallelism is implemented by constructing a dynamic data flow graph of the literals in the clause body with an ordering algorithm. OR parallelism is achieved by adding special Synchronization signals to the stream of partial solutions and synchronizing the multiple streams with a merge algorithm. The ordering algorithm and the merge algorithm are described. The merge algorithm is proved to be correct and therefore, the Sync Model is proved complete, i.e., the execution of a logic program under the Sync Model generates all the solutions.