A Parallel Execution Model for Chronolog

Chuchang Liu Mehmet A. Orgun Kang Zhang

Department of Computing, Macquarie University
Sydney, NSW 2109, Australia
Tel: +61 2 850-9514 (dept), Fax: +61 2 850-9551
E-mail: fcliu, mehmet, [email protected]

Abstract

Chronolog(Z) is a logic programming language based on a linear-time temporal logic with unbounded past and future. By adding "choice predicates" to Chronolog(Z), it is possible to obtain exactly one answer to a given goal when we want to model dataflow style of stream-oriented computations. This paper, based on the framework we propose for exploiting parallelism in Chronolog, discusses and enhances the parallel execution model CHEM so that it is suitable for Chronolog(Z) programs with choice predicates. Dealing with the inherent context-parallelism in Chronolog programs, we propose the concept of parallel context-processes. We also introduce an intermediate virtual machine (CVM), which is granulated to exploit the argument parallelism through temporal unification. The details of the CVM instruction set are given in this paper. The use of a warehouse facility as an associate memory to store the results of previous computations is an important feature of this model. This paper discusses the structure of the warehouse, its r^ole and use in parallel execution of Chronolog programs. An algorithm to manage the warehouse is given. The model is process-based and supports AND-, OR-parallelism in the highly distributed dataflow environment.

Topic: Parallel processing, computation models, logic programming.
Key Words: Temporal logic programming, operational semantics, context-parallelism, warehouse, dataflow computation.

1 Introduction

Temporal logic has been widely used as a formalism for program specification and verification, modelling temporal databases and reasoning about time [6, 7, 13]. In temporal logic, the meanings of formulas depend on an implicit time parameter and elements from different moments in time can be combined through the use of temporal operators. Therefore, temporal logic can model time-dependent and dynamic properties of certain problems in the real-world in a natural way. Recently, several researchers have suggested that temporal logic can be used as a programming language; see [9] for a comprehensive survey. However, there have been a few attempts at implementing temporal logic languages. Some of the early suggested implementations, which are based on translation into standard logic programs [14] or by meta-interpretation [4], cannot exploit parallelism inherent in logic programs and context-parallelism which is offered by temporal logic programs.