Browse Prior Art Database

A Virtual Processor for Parallel Logic Programs

IP.com Disclosure Number: IPCOM000128598D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 13 page(s) / 48K

Publishing Venue

Software Patent Institute

Related People

John S. Conery: AUTHOR [+4]

Abstract

The Warren Abstract Machine is the state of the art in implemen-tation technology for Prolog. Its success is based on an instruction set that supports unification, clause selection, and the management of variable binding environments. Prolog is a sequential programming language, and many of the operations of the WAM rely on the standard, depth-first execution order of Prolog programs. This paper introduces OM, a virtual processor for parallel logic programs. The processor is being designed so that a collection of OM processors will be suitable for a large scale, non-shared memory multiprocessor. Some of the features of the WAM, such as instructions for unification, are present in OM, but other aspects, such as control instructions and the management of binding environments, have been redesigned to support programs of an abstract parallel execution model. Submitted to ASPLOS-II DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE UNIVERSITY OF OREGON 4 i *Supported by a Tektronix Fellowship

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Virtual Processor for Parallel Logic Programs

John S. Conery David M. Meyer*

CIS-TR-87-01 February 4, 1987

Abstract

The Warren Abstract Machine is the state of the art in implemen-tation technology for Prolog. Its success is based on an instruction set that supports unification, clause selection, and the management of variable binding environments. Prolog is a sequential programming language, and many of the operations of the WAM rely on the standard, depth-first execution order of Prolog programs. This paper introduces OM, a virtual processor for parallel logic programs. The processor is being designed so that a collection of OM processors will be suitable for a large scale, non-shared memory multiprocessor. Some of the features of the WAM, such as instructions for unification, are present in OM, but other aspects, such as control instructions and the management of binding environments, have been redesigned to support programs of an abstract parallel execution model.

Submitted to ASPLOS-II DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE UNIVERSITY OF OREGON

4 i *Supported by a Tektronix Fellowship

I Introduction

The idea of a virtual machine is an accepted and useful technique for imple-menting programming languages. There are many benefits, including porta-bility to different host machines, ease of implementation, and flexibility for experimenting with different implementation techniques. Virtual machines have been designed for a number of languages, from the S- machines of the Burroughs B1700, to the Pascal P-machine, to virtual machines for more modern languages such as Smalltalk, Scheme, and Prolog. Another advan-tage, one that is especially true for languages such as Prolog that require complex interpreters, is that compilation to a virtual instruction set enables a much faster execution. A compiler can perform at compile time many of the operations that would be executed at runtime. The Warren Abstract Machine, or WAM, is an elegant design that enables compile-time opti-mizations of control decisions and memory allocation, leading to significant speed-up in the execution of Prolog programs [191. Research in parallel execution of logic programming languages is now entering an interesting new phase, with many research groups studying im-plementation techniques. There are a number of competing abstract models for parallel execution of logic: committed choice AND-parallel models, such as Parlog [4], GHC [181, and Concurrent Prolog [17]; pure OR-parallel mod-els [31; and hybrid models that support both AND and OR parallelism, such as the AND/OR Process Model [7,51. For each of these models, there are active research projects studying implementation techniques, and in most cases the work is centered on defining a virtual machine for programs -of the abstract model. This paper introduces a virtual processor architecture for programs of the AND/OR Process Model. The...