Parallel Execution of Temporal Logic Programs

Using Dataflow Computation

Kang Zhang Mehmet A. Orgun

Department of Computing, Macquarie University Sydney, NSW 2109, Australia

[ABSTRACT] The paper presents a data?driven execution model, CHEM, for a temporal logic programing language, Chronolog. An intermediate virtual machine is proposed, which is granulated at clause argument level to exploit argument parallelism through unification. Context?parallelism, inherent in temporal logic programs, is exploited through dynamic tagging approach typically used in dataflow computers. The model is process?based and supports AND?, OR?parallelism in the highly distributed dataflow environment. Implementation techniques used to support these forms of parallelism are described.

Keywords: Chronolog, temporal logic programs, parallelism, data?driven model, virtual machine.

1. INTRODUCTION

Temporal logic [Gol87] has been successfully used as a formalism in concurrent program specification and verification, modelling temporal databases and reasoning about time. More recently, several researchers have suggested that temporal logic can be directly used to extend the basis of logic programming. For instance, Tokio [AFM86] is a temporal logic language, based on interval logic; Templog [AM89] and Chronolog [Wad88, OW92] are based on linear?time temporal logics; and Temporal Prolog [Gab87] is based on linear and branching time temporal logics.

However, there is little work done on implementing temporal logic languages. Some of the early suggested implementations are based on translation into standard logic programs [Wad88] or by meta?interpretation [KAFT86]. These implementation techniques can form the basis of a quick prototype system, but such an implementation cannot exploit parallelism inherent in logic programs and the context?parallelism offered by tem-

poral logic programs. In temporal logic programming, computations at different moments in time, i.e. in different contexts, can be performed in parallel. Communication between computations at different moments in time is controlled by time?dependencies that result from the use of temporal operators. Context?parallelism is therefore an inherent property of temporal logic programming. It can be more effectively exploited by a dataflow implementation using tagging scheme as implemented in dynamic dataflow computers [GKW85]. This parallelism is in addition to AND/OR?parallelism existing in standard logic programs [Con87].

When alternative clauses in a procedure are evaluated simultaneously, OR?parallelism is achieved [Zha93]. OR?parallelism can also be exploited at a higher level in terms of the search tree, which represents the execution of the program. The unification of more than one clause head with a given goal is considered as separate branches of the search tree. Multiple such branches, each including the clause involved and its continuation, can be executed in parallel. AND?parallelism is exploited when more than one goal in a clause body are evaluated in parallel. Each goal in a body may include multiple OR branches.

Most parallel execution models of logic programs are control?flow based: there is a centralised control and the sequence of instructions is handled by a program counter. Since control?flow approach requires the execution sequence to be predefined, it is difficult to implement context?parallelism of temporal logic programs, which is dynamic in nature (it is in fact run?time generated). However, dataflow computation offers an ideal solution to the context?parallelism. The computations in a dataflow machine are data?driven, i.e. an operation is executed as soon as all of its input operands are available. The result of an operation is sent to one or more other operations as their operands. Such computations can be visualised as two?dimensional graphs which