ACD Atlas Computing Division Distributed Computing Systems

Jump To Main Content

Jump Over Banner

Home

ACDDCSProjects

Jump Over Left Menu

DCS Projects: Reading University

DR J D ROBERTS

PROGRAM TRANSFORMATIONS FOR TIGHTLY COUPLES DISTRIBUTED SYSTEMS

March 82 - Feb 85

Although detailed studies during 1982-83 have been confined to fairly simple examples, it is possible to see two distinct roles emerging for transformations of distributed programs.

The first is in the theoretical derivation of fundamental programs (library programs). This is exemplified by the systematic translation of a Lucid specification to a Dataflow diagram and thence to a collection of CSPs (communicating special processes). It is viewed primarily as a human reasoning activity.

The second is in the transformation of programs expressed in a neutral, configuration-independent and typically very highly distributed form into some other representation more suitable for given actual configurations. The main transformations here are the lumping together of specified groups of processes into single processes and also the multiplying of parallel channels into a single channel. This is viewed as an activity to be performed automatically under manual direction, and explicit algorithms have been identified for restricted cases.

One particular case which is highly restrictive, but nevertheless sufficiently applicable to be of a practical use. is the pipeline (ie. any system in which no data is recirculated and reviewed as a collection of CSPs which after an initialisation period enter a simple loop) [[1]. In this case groups of CSPs can be merged to produce similar CSPs without problems of deadlock nor any other complication; but if greater generality is allowed, the class does not appear to be closed under this type of transformation until schemata are considered of very great generality. The current theoretical work is for this reason directed towards identifying automatable transformations for these general situations, Petri nets being used as representations. It is expected that programs resulting from this process would be more suitable for automatic compilation than human comprehension.

As always, the investigators would be pleased to communicate with others regarding any potential applications especially in real-time data or signal processing.

References

1. J. D. Roberts and S. A. Williams. The Construction and Transformation of Collections of Communicating Sequential Processes that Represent Pipeline Configurations, Internal Report RCS 181. Nov. 1983.