A Framework for Exploiting Parallelism in Chronology

Chuchang Liu Mehmet A. Orgun Kang Zhang

Department of Computing, Macquarie University, NSW 2109, Australia

Tel: +61 2 850-9514 (dept), Fax: +61 2 850-9551

E-mail: fcliu, mehmet, [email protected]

Abstract

Chronolog is an extension of logic programming based on temporal logic. The paper presents a framework which can be used to exploit multiple levels of parallelism found in Chronolog programs, context parallelism, AND- and OR-parallelism. Based on an analysis of these modes of parallelism in Chronolog programs, a parallel execution mechanism of the language is discussed and a formal execution model is given. The inherent context-parallelism in Chronolog programs occurs when more than one childcomputation are active at a time, and it is exploited through dynamic tagging approach typically used in dataflow computers. At the level of clause arguments, we introduce an intermediate virtual machine (CVM), which is granulated to exploit the argument parallelism through temporal unification. We also give the details of the CVM instruction set. The model is process-based and supports AND-, OR-parallelism in the highly distributed dataflow environment.

1 Introduction

Temporal logic has been widely used as a formalism for program specification and verification, modelling temporal databases and reasoning about time. It has also been suggested that temporal logic can be used as a programming language [1, 2, 4, 9]. A comprehensive survey of temporal (and modal) extensions of logic programmingcan be found in [8]. 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 [11] or by meta-interpretation [7], cannot exploit parallelism inherent in logic programs

yTo appear in the Proceedings of the First IEEE International Conference on Algorithms and Architectures for Parallel Processing, 19{21 April 1995, Brisbane, Australia.

and the context-parallelism which is offered by temporal logic programs.

We outline a parallel execution model for temporal logic programming language Chronolog [9, 10], called CHEM (CHronolog Execution Model). The model, which was originally outlined in [13], is based on dataflow computation. The data-driven execution model supports argument parallelism through parallel processing of multiple procedure arguments. A new variable binding scheme is used to allow OR-parallelism to be exploited in the distributed dataflow environment. The support of Restricted AND-parallelism can also be incorporated in CHEM by taking advantage of dataflow graph annotation. Context-parallelism can be exploited when a goal is evaluated by executing multiple copies of the goal at different moments in time. This form of parallelism is implemented cost-effectively by using a warehouse to store previous computations for reuse. The use of the warehouse is very similar to a technique known as memoization". The dynamic tagging scheme used in the conventional tagged token dataflow machines is naturally suited to the warehouse implementation. It is, therefore, found that dataflow computation lends the CHEM model a flexible capability for support of parallelism at various levels.

In this paper, a detailed description of the CHEM model is presented. A parallel context-process solves a goal by creating a child-computation to solve each context-sub-goal. At the level of clause arguments, we propose an intermediate virtual machine called Chronolog virtual machine (CVM) which is granulated to exploit the argument parallelism through temporal unification, and, in particular, we give a detailed description of the CVM instruction set. In CHEM, a Chronolog program is formally compiled into a CVM object program which is a set of dataflow graphs. Each graph is responsible for a clause execution, and all nodes whose operands are available can be executed in parallel.