ACD Atlas Computing Division Distributed Computing Systems

Jump To Main Content

Jump Over Banner

Home

ACDDCSProjects

Jump Over Left Menu

DCS Projects: University of Bath

PROF J P FITCH and DR P J WILLIS

FEASIBILITY STUDY OF A MULTIPROCESSOR ARCHITECTURE

Feb 82 - Jan 83

Background and Nature of Research

This project arose from a need to evaluate tree-represented pictures rapidly. It was soon realised that the architecture which developed was amenable to a wider class of problems exhibiting parallelism and this has come to dominate the research.

Broadly the multiprocessor system is organised as a binary tree except that the network is closed by interconnecting what would be the leaves and the root. For certain numbers of processors, this is possible in a completely regular fashion so that the network looks the same from any node. Each node interfaces to exactly three neighbouring nodes and each node consists of a single processor. The closing of the tree is done so cycles on the structure are as large as possible to ensure that a given processor can spawn sub-tasks with a low probability that these tasks will return to the initiating processor. The nature of the interconnection scheme is described in detail in [1].

Research Goals

The SERC grant awarded to the project was for a one year feasibility study. Modest simulation studies have been performed, followed by the direct implementation of the six processor machine. Further experimentation has centred on programming the actual hardware. thus forcing the investigators to adopt realistic solutions to problems such as message passing. task division and so forth.

For the same reason the investigators wished to use a relatively powerful processor at each node, so that potentially interesting results would not be masked by. for example. the addressing limitations of 8 bit micros. Accordingly, the investigators set out to build a six node machine based on 1/4Mbyte Motorola 68000 computers.

Achievements

A six processor net, with interrupt-driven parallel corrections. has been constructed. A dual floppy disk has been added to permit stand-alone working. Disk storage is currently being supplied by an interface to a separate machine.

On the software side, a Tripos operating system implementation is running satisfactorily to give a development environment, and a version of Cambridge LISP developed in Bath for the M68000 is running. A simple task spawning mechanism has been demonstrated.

Work in Hand

Work is progressing along two lines. Currently, most activity centres around a conversion environment with explicitly indicated parallelism, but there is also a long term interest in automatic concurrency analysis within Lisp.

The somewhat ad-hoc disk access and the need to use one of the processors as the development machine are current practical difficulties.

Dr Jed Marti has been a SERC Visiting Fellow for the latter six months of 1982. His intimate knowledge of LISP-like environments and grasp of hardware limitations has made his contribution to the project substantial and the investigators wish to highlight the value of such Fellowships. Dr Marti's LISP concurrency analyser is expected to be used soon as a basis of a concurrent compiler [2].

References

1. A.Bowyer, P.J.Willis and J.R.Woodwark, A Multi-Processor Architecture for Solving Spatial Problems, Computer Journal, 24, 1981.

2. J.Marti, Compilation Techniques for a Control-Flow Concurrent LISP System, LISP Conference, Stanford University, 1980.

3. J.D.Marti and J.P.Fitch, The Bath Concurrent Lisp Machine, Proc. Eurocal'83 (to be published in Springer Lecture Notes series).