Meta Logic Programming for Modelling Message?Passing

Parallel Programs

Kang Zhang
Department of Computing, Macquarie University
Sydney, NSW 2109, Australia
Email: [email protected]
Fax: +61?2?8059531

ABSTRACT

Several message?passing parallel programming languages have become available on various MIMD machines (e.g. Occam on the transputer and CMMD on the CM?5) in recent years. Yet run?time characteristics of this class of languages has not been widely studied, and the programming support is much needed for more productive and efficient program development. This paper provides an overview of a modelling tool for Occam2, implemented as two levels of meta interpreters. The general features of a message?passing programming paradigm is modelled through an extended Prolog with the notion of dynamically created, time?dependent, communication processes. The extended communication and process creation and termination mechanisms, and their interpretations are described. The second level interpreter interprets the primitive processes and constructions of the Occam2 language. Given a performance metrics of the target machine, e.g. a network of transputers, the interpreter can predict the program speed in a fashion of event?driven simulation. Communication?related errors, such as deadlock, can be detected with an extended version of the high level interpreter.

1. INTRODUCTION

Several message?passing parallel programming languages have become available on various MIMD machines, e.g. Occam on the transputer and CMMD on the CM?5, in recent years. Generally, parallel programming introduces an extra dimension of complexity over conventional sequential programming. This is particularly true with message?passing parallel programming. When designing a message?passing program, one must consider the allocation of multiple tasks to be run simultaneously and the coordination of these tasks through inter?task communication. The ideal parallelism is usually achieved through concurrent execution of multiple tasks by maximising the ratio of computations verses communication among the tasks. However, concurrency and task interaction introduce new problems into programs, such as the management of shared resources and the possibility of deadlocks (when several tasks mutually wait on each other to advance). Another problem is that when several tasks are running concurrently, it is not always possible to predict their relative speeds. Therefore, running the same program with the same data may not always give the same results. Such programs are said to be non?deterministic and are apparently very difficult to debug.

This paper introduces a tool which models message?passing parallel programs written in Occam2 [Inmos 88a], predicts the program performance, assists the program analysis, and detects communication deadlocks. Occam2 is a concurrent programming language, based on the concepts of CSP [Hoare 85] and designed to express parallel algorithms and their implementation on a network of processing components, typically transputers [Inmos 88b].

Tools for monitoring or modelling Occam2 programs have been developed in recent years. Among these, graphical approach for visualising Occam2 program structure and execution behaviour have been most widely used [Abdennadher 92, Marwaha 93, Roberts 89]. Program visualisation exploits the power of computer graphics to convey the static or run?time information and thus is particularly suitable for concurrent and parallel programs