
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 8509514 (dept), Fax: +61 2 8509551
Email: fcliu, mehmet, [email protected]
Abstract
Chronolog(Z) is a logic programming language based on a lineartime 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 streamoriented 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 contextparallelism in Chronolog programs, we propose the concept of parallel contextprocesses. 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 processbased and supports AND, ORparallelism in the highly distributed dataflow environment.
Topic: Parallel processing, computation models, logic programming.
Key Words: Temporal logic programming, operational semantics, contextparallelism,
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 timedependent and dynamic properties of certain problems in the realworld 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 metainterpretation [4], cannot exploit parallelism inherent in logic programs and contextparallelism which is offered by temporal logic programs.