UNIVERSITY OF MANCHESTER

Department of Computer Science

Data-Flow Research Project

Research Reports : Abstracts

September 1997

The Data-Flow Research Group at Manchester investigated data-driven computer architecture between 1976 and 1995. An initial research grant from the then Science Research Council (SRC) of Great Britain funded the construction of a prototype hardware system which became operational in October 1981. Subsequent grants from the renamed Science and Engineering Research Council (SERC) led to the production of a compiler and code generator for the high-level, single-assignment language SISAL (in 1983), and the hardware was enhanced by the addition of a specialised Structure Store to hold complex data structures (in 1985). Initial performance evaluation of the system was supported by Digital Equipment Corporation under its External Research Programme. An investigation of the performance of the hardware and software in small-scale and large-scale applications was funded by the UK Alvey Programme in advanced information technology, leading to a full evaluation report (in 1989). Specific research on dataflow computing reached a natural conclusion as the project team moved on to undertake general comparisons of the many different approaches to parallel computing, and evolved into the Centre for Novel Computing (CNC) in the early 1990s.

This document contains summary information about the Group members, abstracts of the literature produced by the Group, and also includes details of development and simulation software which were produced during the project. For many years, evolving versions of this document were distributed to interested parties in paper form. This version is intended to be the final one, for installation on the World Wide Web as an historical record of the Manchester Data-Flow Project.

The literature falls into six categories:


Project Personnel

The following is intended to be a complete list, in alphabetical order, of all people who were ever involved in the project. If anyone has been missed out, or you know the whereabouts of anyone listed without a current contact address, please e-mail details to: jgurd@cs.man.ac.uk
name in projectfromtorole current e-mail (where known)
Val Aspin19821982 student.
Dr Pedro Barahona1983 1987 student.
Karim Benkherouf1980 1981 student.
Prof Wim Bohm19841990RA/lecturerbohm@cs.colostate.edu
Dr Dave Bowen 1978 1981 student.
Dave Bradshaw 1978 1978 student.
Ruth Brimley19801980student.
Dr Vicky Bush19791990student/RA/lecturer vicky.bush@csm.uwe.ac.uk
Dr Arthur Catto19781981student.
Naranker Dulay19811982student.
Mick Edwards19821983student.
Dr John Foley19821989RA.
Dr John Glauert19771983student/RA jrwg@sys.uea.ac.uk
Prof John Gurd 19761995lecturerjgurd@cs.man.ac.uk
Dr Zahran Halim19821986student.
Ian Horrocks19831983 RAihorrocks@cs.man.ac.uk
Dr Yasuhiro Inagami19871988visitor.
Rob Jarratt19831984student.
Pete Jinks19771978studentpjinks@cs.man.ac.uk
Jamal Kamani19841984student.
Dr Katsura Kawakami19831985studentawakami@mrit.mei.co.jp
Bob King19861987RA.
Dr Chris Kirkham19781990lecturerkirkham@cs.man.ac.uk
Geoff Lane19771980studentgeoff.lane@mcc.ac.uk
Dr Jose Oliveira19811984student.
Adrian Parker19831986RA/lecturer.
Dave Pearson19811981 student.
Geoff Richmond 19811982student.
Dr Carlos Ruggiero19841987student.
Dr John Sargeant19811986student/RA jsargeant@cs.man.ac.uk
Dr Brian Saunders19821985RA/lecturer.
Dr Jos=E9 da Silva19781982student.
Dr Dave Snelling19921995RA/lecturersnelling@fecit.co.uk
Gary Tan1986 1986 student.
Heidi Tang19861987student.
Dr Yong-Meng Teo 1986 1990 student.
Dr Arthur Veen 1985 1985 RA.
Prof Ian Watson 1976 1983 lecturer watson@cs.man.ac.uk
Pete Whitelock 1978 1981 student.
Dr Martin York 1988 1992 student.
John Zurawski 1977 1977 student.

Postal Addresses

For Internal Reports, software distribution or direct enquiries to project staff:

Department of Computer Science

University of Manchester

Oxford Road

Manchester, M13 9PL

UK

For Theses and Dissertations:

The Librarian

The John Rylands University Library

University of Manchester

Oxford Road

Manchester, M13 9PL

UK

Enquiries for Theses and Dissertations should ask:


Published Papers

1 title: A Multilayered Dataflow Computer Architecture

authors: J.R. Gurd, I. Watson

volume: IEEE Conference Proceedings, Catalog no. 77CH1253-4C Proceedings International Conference on Parallel Processing

date: August 1977, p94 (one page only)

abstract: A short paper summarising some of the work described in the Internal Report, number R1, of the same title.


2 title: A Prototype Dataflow Computer with Token Labelling

authors: I. Watson, J.R. Gurd

volume: AFIPS Proceedings, vol.48

Proceedings National Computing Conference

date: June 1979, pp. 623-628

abstract: An implementation-orienteddescription of the Manchester prototype dataflow computer. A brief discussion of the token labelling scheme is followed by a high-level description of the system architecture. Outlines of the construction of various modules in the machine are given, and a short analysis of performance is presented. The problems of programming the system are summarised.


3 title: Data Driven System for High Speed Parallel Computing (1 & 2)

authors: J.R. Gurd, I. Watson

volume: Computer Design, vol.9 nos.6 & 7

date: June & July 1980, pp. 91-100 & 97-106

abstract: This two-part feature article introduces and describes the Manchester prototype data driven computer. Part 1 explores the motivations for studying data driven machines, and develops a computational model based on dataflow graphs. Part 2 describes the engineering detail of a system which implements the model.


4 title: Nondeterministic Dataflow Graphs

authors: A.J. Catto, J.R. Gurd

volume: Proceedings 8th IFIP World Computer Congress (IFIP'80)

publisher: North Holland Publishing Company

date: October 1980, pp. 251-256

abstract: Machine-level operations used for executing purely deterministic dataflow graphs are described. Extensions providing a basis for nondeterministic computation are proposed. Implementation models for a variety of low- and high-level language constructs are developed. In particular, the paper demonstrates the feasibility of using Hoare's Communicating Processes as a high-level, nondeterministic language for a data driven computer.


5 title: Nondeterministic Dataflow Programming

authors: A.J. Catto, J.R. Gurd, C.C. Kirkham

volume: Proceedings 6th ACM European Regional Conference (ICS'81)

publisher: Westbury House (IPC Science and Technology Press)

date: April 1981, pp. 435-444

abstract: Describes research into application of dataflow techniques in nondeterministic situations. The work has progressed concurrently with the design and construction of the Manchester prototype dataflow computer, and has influenced the machine architecture. The feasibility of using high-level nondeterministic programming languages to implement general applications on this system is demonstrated. This is achieved with the help of a range of matching functions, which are a unique feature of the Manchester system.


6 title: Generation of Dataflow Graphical Object Code for the Lapse Programming Language

authors: J.R. Gurd, J.R.W. Glauert, C.C. Kirkham

volume: Lecture Notes in Computer Science, vol.111 Proceedings Conference on Analysing Problem Classes and Programming for Parallel Computers (CONPAR'81)

publisher: Springer-Verlag

date: June 1981, pp. 155-168

abstract: Considers some aspects of code generation from the single-assignment language Lapse for the Manchester prototype dataflow computer. The syntax of Lapse, which resembles Pascal, is introduced, and code generation templates are presented. Some possible optimisations of flowgraph code are discussed, particularly in the implementation of arrays.


7 title: Design of a Processing Subsystem for the Manchester Dataflow Computer

authors: J.G.D. da Silva, J.V. Woods

volume: Proceedings of the IEE, vol.128E no.5

date: September 1981, pp. 218-224

abstract: Describes the main features of the processing unit for the Manchester prototype dataflow machine. The subsystem is implemented as a parallel array of processing elements with a modular input/|output interface. Faster execution rates can be achieved by the addition of more processing elements so that high speed is unnecessary in individual elements. Consequently, a conventional bit-slice architecture is sufficient for their construction. The nature of the ordercode is considered, and average instruction times are assessed.


8 title: Resource Management in Dataflow

authors: A.J. Catto, J.R. Gurd

volume: Proceedings ACM Conference on Functional Programming Languages and Computer Architecture

date: October 1981, pp. 77-84

abstract: Describes in detail an implementation of nondeterministic resource managers for the language Id on the Manchester prototype dataflow computer. For the non-specialist reader, the Manchester labelled dataflow schema and the resource management constructs of Id are outlined before details of the implementation are given.


9 title: A Practical Dataflow Computer

authors: I. Watson, J.R. Gurd

volume: IEEE Computer, vol.15 no.2

date: February 1982, pp. 51-57

abstract: A description of the Manchester machine in the IEEE Computer special issue on dataflow computing. The basic structure of the system is outlined, and the functions of the constituent modules are described. Particular attention is paid to the unusual "matching" functions used for pairing together data tokens at the input to computational nodes.


10 title: High Level Languages for Dataflow Computers

author: J.R.W. Glauert

volume: Pergamon-Infotech State of the Art Report series 10 no.2

Programming Technology

date: March 1982, pp. 173-193

abstract: A study of the programming language features that are commonly found in language designs for dataflow computing. The discussion is preceded by an outline of the essential characteristics of dataflow computers. Next, the cases for different styles of programming language are presented. Finally, the major contenders for implementation (the Single-Assignment Languages) are described and compared in some detail.


11 title: Developments in Dataflow Architecture

author: J.R. Gurd

volume: Proceedings SPL International Conference on the Fifth Generation

date: July 1982

abstract: An introduction to dataflow techniques and architectures, sketching the tradeoffs between various implementation methods in software and hardware. Includes a general comparison of four projects which are building, or have built, dataflow hardware.


12 title: Dataflow Architectures

author: J.R. Gurd

volume: Pergamon-Infotech State of the Art Report series 10 no.6

Supercomputer Technology

date: November 1982, pp. 247-268

abstract: General survey of dataflow computers, including philosophy of design, and hardware and software implementation techniques. Examples of practical dataflow systems are described, and a comparison of their merits and disadvantages is made.


13 title: A Pseudo-Associative Matching Store with Hardware Hashin= g

authors: J.G.D. da Silva, I. Watson

volume: Proceedings of the IEE, vol.130E no.1

date: January 1983, pp. 19-24

abstract: Describes the pseudo-associative Manchester prototype matching store. This uses hardware hashing and is implemented with conventional random-access memory. Because search operations in this store do not need to be performed in strict sequence, the main parallel hash table can operate concurrently with a separate overflow mechanism. Overflow searches need not halt progress of the main hash table searches. The resulting pseudo-associative store has an average access time close to the cycle time of the constituent random-access memory.


14 title: Preliminary Evaluation of a Prototype Dataflow Computer

authors: J.R. Gurd, I. Watson

volume: Proceedings 9th IFIP World Computer Congress (IFIP'83)

publisher: North Holland Publishing Company

date: September 1983, pp. 545-551

abstract: The hardware structure of the Manchester prototype dataflow computer is a pipelined ring which exhibits variable processing rate, by adjusting the number of active homogenous function units, up to a limit determined by the pipeline beat period. The system exhibits near-linear speedup with respect to the number of function units for a wide variety of programs, provided they have sufficient inherent parallelism to occupy all function units and pipeline stages. In the long-term, use of multiple-rings offers the potential for incremental expansion of available computing power.


15 title: The Dataflow Approach

authors: J.R. Gurd, I. Watson, C.C. Kirkham, J.R.W. Glauert

volume: Distributed Computing

editors: F.B. Chambers, D.A. Duce, G.P. Jones

publisher: Academic Press

date: September 1984, pp. 1-53

abstract: Four chapters of tutorial material on dataflow systems. Chapter 1 introduces fundamental principles. Chapter 2 considers the requirements for executing dataflow code and exploiting the exposed software parallelism. Three different experimental dataflow systems are studied. Performance of these systems is discussed. Chapter 3 describes the lowest-level languages which are used to specify graph programs for the Manchester machine. Textual representation of object code and a macro-assembly language are described. Chapter 4 introduces SISAL, a high-level language for dataflow programming, which is illustrated by a number of examples of language constructs and some complete programs. SISAL is a single-assignment language language with Pascal-like syntax which is being used for evaluation of a variety of multi-processors.


16 title: The Manchester Dataflow Project

authors: J.R. Gurd, I. Watson, C.C. Kirkham

volume: Distributed Computing Systems Programme

editor: D.A. Duce

publisher: Peter Peregrinus (IEE)

date: September 1984, pp. 270-289

abstract: Describes the history of the Manchester prototype dataflow computer. The hardware and software system designs are outlined, and the technical problems which have been encountered are described. Methods for resolving these problems are also addressed.


17 title: Evolution of a Dataflow Architecture

authors: J.R.W. Glauert, J.R. Gurd, C.C. Kirkham

volume: Concurrent Languages in Distributed Systems: Hardware Supported Implementation

editors: G.L. Reijns, E.L. Dagless

publisher: North Holland Publishing Company

date: January 1985, pp. 1-18

abstract: The evolution of the Manchester Dataflow Computer and its associated high-level and low-level programming languages is presented. The tagged-token dataflow model of computation is adopted and suitable hardware architectures are described. Language implementations are considered, ranging from conventional (Pascal-like), through single-assignment (dataflow), to functional (declarative) and nondeterministic. Selected implementation features are discussed in detail.


18 title: The Manchester Prototype Dataflow Computer

authors: J.R. Gurd, C.C. Kirkham, I. Watson

volume: Communications of the ACM, vol.28 no.1

date: January 1985, pp. 34-52

abstract: A comprehensive overview of the work of the Manchester dataflow research project. Commences with a description of the tagged-token model of dataflow computation, based on an example program (written in the high-level language SISAL) whose translation into dataflow object code is illustrated. Continues with a description of the Manchester system hardware, including details of store capacities and speeds. Contains information about benchmark programs and their performance on the system simulator and the hardware. Discusses future requirements for the system architecture.


19 title: Hardware and Software Enhancement of the Manchester Dataflow Machine

authors: A.P.W. B=F6hm, J.R. Gurd, J. Sargeant

volume: Proceedings IEEE Spring Computer Conference

date: February 1985, pp. 420-423

abstract: The Manchester dataflow project has been primarily hardware-oriented, with the main goal of building a prototype tagged-token dataflow machine. As this prototype nears completion, software requirements, and in particular the needs of the SISAL language, play an increasingly important role in the further development and enhancement of the machine. This paper surveys recent developments and future directions for performance improvement, including more efficient data storage and control activation.


20 title: Parallel Dataflow Programming

authors: J. Sargeant, J.R. Gurd

volume: IEEE Software, vol.2 no.4

date: July 1985, pp. 68-70

abstract: A short presentation of the research directions within the Dataflow Project at the University of Manchester. Emphasis is placed on the importance of dataflow language features for expessing parallelism, and the need to generate highly efficient object code for the target machine. Issues of immediate concern are identified, including stored data structures, system performance, control of parallelism, error handling, and programming efficiency.


21 title: The Manchester Dataflow Machine

author: J.R. Gurd

volume: Computer Physics Communications, vol.37 no.1

date: July 1985, pp. 49-62 (also in Future Generations Computer Systems, vol.1 no.4 June 1985, pp. 201-212)

abstract: A general survey of the Manchester prototype system hardware and software, including a brief analysis of system performance and an outline of current developments in architecture and programming techniques. Commences with a discussion of tagged-token dataflow, and low-level programming for the Manchester system. Contains some details of the hardware implementation, and characteristics of higher-level programming languages.


22 title: Transforming Recursive Programs for Execution on Parallel Machines

authors: V.J. Bush, J.R. Gurd

volume: Lecture Notes in Computer Science, vol.201 Proceedings IFIP Conference on Functional Programming Languages and Computer Architecture

publisher: Springer-Verlag

date: September 1985, pp. 350-367

abstract: Studies the application of a set of high-level recursive function transformations for automatic parallel program improvement. The tra nsformations are a generalisation of previously published results. The paper defines conditions under which it is possible to convert a linear recursive schema (with sequential run-time characteristics) into a bilinear, or double-recursive, schema (which has expanding concurrent run-time characteristics). A set of transform applications that permit different modes of evaluation of list operators in a variety of parallel environments is identified.


23 title: Simulated Performance of the Manchester Multi-ring Dataflow Machine

authors: P.M.C.C. Barahona, J.R. Gurd

volume: PARALLEL COMPUTING 85

editors: M. Feilmeier, G. Joubert, U. Schendel

publisher: North Holland Publishing Company

date: June 1986, pp. 419-424

abstract: Reports on a preliminary performance evaluation of a multiprocessor dataflow machine based on the single processor already in operation at Manchester. A method of allocating instructions to the processors is presented, and a switching network to interconnect the processors is described. The influence of allocation and network on the overall performance is examined. Simulation of the machine shows that programs are executed efficiently when their parallelism matches the parallelism of the machine hardware.


24 title: Efficient Dataflow Code Generation for SISAL

authors: A.P.W. B=F6hm, J. Sargeant

volume: PARALLEL COMPUTING 85

editors: M. Feilmeier, G. Joubert, U. Schendel

publisher: North Holland Publishing Company

date: June 1986, pp. 339-344

abstract: The efficiency of dataflow code generated from a high level language can be improved by both conventional and dataflow-specific optimisations. Such techniques are used in implementing the functional language SISAL on the Manchester Dataflow Machine.


25 title: Stored Data Structures on the Manchester Dataflow Machin= e authors: J. Sargeant, C.C. Kirkham volume: Computer Architecture News, vol.14 no.2 Proceedings 13th ACM International Symposium on Computer Architecture date: June 1986, pp. 235-242 abstract: Experience with the Manchester Dataflow Machine has highlighted the importance of efficient handling of stored data structures in a practical parallel machine. It has proved necessary to add a special-purpose structure store to the machine, and this paper describes the role of this structure store and the software which uses it. Some key issues in data structure handling for parallel machines are discussed.


26 title: A Scalable Dataflow Structure Store

authors: K. Kawakami, J.R. Gurd

volume: Computer Architecture News, vol.14 no.2 Proceedings 13th ACM International Symposium on Computer Architecture

date: June 1986, pp. 243-250

abstract: A design for a highly parallel data structure store for the prototype Manchester Dataflow Computer is presented. All storage functions can be performed concurrently, and the store is scalable in that an incremental increase in performance for any function can be achieved by adding appropriate hardware modules into the system. A relative balance in performance between the different functions can therefore be achieved. In a hardware version, logical and physical function units are independent, thus increasing configuration flexibility. The performance of a simple configuration is discussed.


27 title: Dataflow: Achievements and Prospects

authors: J.R. Gurd, C.C. Kirkham

volume: Proceedings 10th IFIP World Computer Congress (IFIP'86)

publisher: North Holland Publishing Company

date: September 1986, pp. 61-68

abstract: Dataflow is a method for concurrent execution of programs that exploits fine-grain data dependencies between instructions. Programs are expressed as directed graphs of instructions that are activated solely by the availability of their input data. Dataflow techniques have been under serious investigation for nearly two decades, and the first significantly sized prototype dataflow computers are now being evaluated. This paper reviews the progress of=20dataflow research to date, presents important achievements, and discusses the future prospects both for research and for more commercial development.


28 title: Processor Allocation in a Multi-ring Dataflow Machine

authors: P.M.C.C. Barahona, J.R. Gurd

volume: Journal of Parallel and Distributed Computing, vol.3 no.3

date: September 1986, pp. 305-327

abstract: Describes a method for allocating dataflow instructions to the processing elements of a multi-ring version of the Manchester prototype dataflow machine, and examines the influence of this method on the selection of a switching network for interconnecting the elements. Results obtained from simulation of the machine are presented, and it is shown that programs are executed efficiently when their parallelism matches the parallelism of the machine hardware.


29 title: The Manchester Dataflow Computing System

authors: J.R. Gurd, C.C. Kirkham, A.P.W. B=F6hm

volume: Experimental Parallel Computing Architectures

editor: J.J. Dongarra

publisher: North Holland Publishing Company

date: June 1987, pp. 177-219

abstract: Introduces the three basic components of the Manchester Dataflow System (the fine-grain message-passing tagged-token dataflow model of computation, the multi-ring hardware structure of the Manchester Dataflow Machine and the high-level single-assignment programming language SISAL) and illustrates how these have been integrated to form an efficient dataflow computing system. Includes a description of the structure store implementation.


30 title: SISAL: an Experimental Applicative Language for Scientific Computing

authors: J.R. Gurd, C.C. Kirkham, A.J. Parker

volume: Problem Solving Environments for Scientific Computing

editors: B. Ford, F. Chatelin

publisher: North Holland Publishing Company

date: July 1987, pp. 353-362

abstract: Describes some of the features of SISAL, a single-assignment language, and shows how such a language may be useful in allowing the parallelism available in a program to be exploited without requiring any special effort by its author. Furthermore, this is achieved without the need for compicated analysis by special-purpose pre-compiler programs. SISAL programmers can, however, still make use of loops and arrays, features of conventional programming languages that are natural for so many applications but which are absent from other applicative programming languages.


31 title: Fine-grain Parallel Computing: The Dataflow Approach

authors: J.R. Gurd, P.M.C.C. Barahona, A.P.W. B=F6hm, C.C. Kirkham, A.J. Parker, J. Sargeant, I. Watson

volume: Lecture Notes in Computer Science, vol.272 Future Parallel Computers

editors: P.C. Treleaven, M. Vanneschi

publisher: Springer-Verlag

date: September 1987, pp. 82-152

abstract: Gives a comprehensive overview of the fine-grain dataflow approach to parallel computing. Dataflow models of computation are introduced in detail. A range of dataflow machines are described, including a full description of the Manchester Dataflow Machine. Languages suitable for generating dataflow object-code are discussed, and the general-purpose single-assignment language SISAL is presented. SISAL to Manchester machine-code code-generation techniques are studied, and the overall language-compiler-hardware system performance is evaluated.


32 title: Control of Parallelism in the Manchester Dataflow Machin= e

author: C.A. Ruggiero, J. Sargeant

volume: Lecture Notes in Computer Science, vol.274

Functional Programming Languages and Computer Architecture

editor: G. Kahn

publisher: Springer-Verlag

date: September 1987, pp. 1-15

abstract: Considers schemes for controlling the amount of active program parallelism in a fine-grain parallel machine. Reviews inadequate software mechanisms of control, which rely on planting extra code to control execution order. Various attempts to design a hardware "throttle" for the Manchester Dataflow Machine are described. A coarse-grain, process-based throttle is presented, together with some performance results.


33 title: Dataflow Architectures and Implicit Parallel Programming

author: J.R. Gurd

volume: Multiprocessing in Meteorological Models

editors: G.R. Hoffman, D.F. Snelling

publisher: Springer-Verlag

date: December 1987, pp. 255-282

abstract: Presents the case for implicit parallel programming, where the programmer is not obliged to know the configuration of hardware on which a program will run. The implicit single-assignment language SISAL is presented. The tagged-token model of dataflow computation is introduced and several experimental parallel dataflow computers are described. The performance of a compiler generating dataflow machine-code from SISAL is presented.


34 title: Performance Issues in Dataflow Machines

authors: J.R. Gurd, A.P.W. B=F6hm, Y.M. Teo

volume: Future Generations Computer Systems, vol.3 no.4

date: December 1987, pp. 285-297

abstract: Explores issues affecting the performance of dataflow computers at the machine and language levels. Workload in a dataflow machine is in the form of fine-grain data packets which trigger instruction-level activity in the various components of the hardware architecture. Workload is identified by a compiler for a high-level, single-assignment language, and is distributed across the hardware components dynamically at run-time. The amount of work at any instant can be controlled by a parallelism "throttle". The paper specifically studies the performance of the prototype Manchester Dataflow Machine.


35 title: Implicit Parallel Processing: SISAL on the Manchester Dataflow Computer

authors: J.R. Gurd, A.P.W. B=F6hm

volume: Parallel Systems and Computation

editors: G. Paul, G.S. Almasi

publisher: North Holland Publishing Company

date: March 1988, pp. 179-204

abstract: Describes the implicit programming language SISAL together with its implementation on the Manchester Dataflow Machine. SISAL provides a means of programming parallel machines, without explicit specification of parallelism, using the notion of single-assignment. The Manchester Dataflow Machine implements a tagged-token dataflow model of computation using a multi-ring hardware structure. Techniques for code generation are discussed and some performance results are presented.


36 title: Tools for Performance Evaluation of Parallel Machines

authors: A.P.W. B=F6hm, J.R. Gurd

volume: Lecture Notes in Computer Science, vol.297 Proceedings 1st ACM International Conference on Supercomputing (ICS'87)

editor: C. Polychronopoulos

publisher: Springer-Verlag

date: June 1988, pp. 212-228

abstract: Describes graphical tools for observing the run-time behaviour of SISAL programs executing on a (simulated) multi-ring Manchester Dataflow Machine. The SISAL and IF1 languages are outlined, and the essentials of compile-time and run-time process structuring are described. Examples of run-time process trees are given. The simulated multi-ring dataflow machine is presented, and examples of machine-level behaviour are given.


37 title: Efficient Dataflow Code Generation for SISAL

authors: A.P.W. B=F6hm, J. Sargeant

volume: IEEE Transactions on Computers, vol.C-38 no.1

date: January 1989, pp. 4-14

abstract: Discusses techniques for achieving efficient performance from SISAL programs on the Manchester dataflow machine. Describes both language and machine briefly as an introduction. Then outlines dataflow code generation schemes, concentrating on data structures, function calling and for constructs. Evaluates performance in terms of S1 (executed instructions) and Sinf (critical path length) parameters for sample programs. Finally discusses methods of code improvement for instruction-set designer, compiler-writer and programmer, assessing the performance improvement available.


38 title: Monitoring Parallel Programs on Message-Passing Multiprocessors

authors: A.P.W. B=F6hm, J.R. Gurd, M.C. Kallstrom

volume: Aspects of Computation on Asynchronous Parallel Processors

editor: M. Wright

publisher: North Holland Publishing Company

date: March 1989, pp.139-157

abstract: Introduces two parallel message-passing system architectures, presents examples of graphical monitoring tools and gives illustrations of the practical application of these tools on the two systems. The paper also introduces an interesting experiment in which a simulator for the Manchester Dataflow Computer is being implemented in occam and executed on the transputer based ParSiFal T-Rack.


39 title: The Specification of a New Manchester Dataflow Machine

authors: Y. Inagami, J.F. Foley

volume: Proceedings 3rd ACM International Conference on Supercomputing (ICS'89)

publisher: ACM Press

date: June 1989, pp. 371-380

abstract: Describes the structure and operation of an advanced prototype computer based on the prototype Manchester Dataflow Computer instruction-set. Implementation in VLSI ECL logic is envisaged, and details of the proposed system construction are presented.


40 title: Monitoring Experimental Parallel Machines

authors: A.P.W. B=F6hm, J.R. Gurd, M.C. Kallstrom

volume: Instrumentation for Future Parallel Computing Systems

editors: M. Simmons, R. Koskela, I. Bucher

publisher: ACM Press

date: July 1989, pp.121-141

abstract: Introduces parallel program "animation" plus "tracing" and "condensing" monitoring tools for parallel computers. Illustrates the application of these techniques in the implementation of distributed simulators for a multi-ring dataflow machine on the ParSiFal T-Rack.


41 title: The Effect of Iterative Instructions in Dataflow Compute= rs

authors: A.P.W. B=F6hm, J.R. Gurd, Y.M. Teo

volume: Proceedings International Conference on Parallel Processing (ICPP'89)

publisher: Pennsylvania State University Press

date: August 1989, pp. I201-I208

abstract: Investigates the nature and extent of the benefits and adverse effects of iterative instructions in dataflow computers. An iterative instruction produces a sequence of outputs when presented with a single set of inputs. Such instructions reduce execution times, but exhibit coarse-grain characteristics which affect the normal, fine-grain operation of a dataflow machine.


42 title: Dataflow Architectures

author: J.R. Gurd

volume: Computer Science and Systems Engineering, vol.4 no.4

date: October 1989, pp. 241-251

abstract: A survey of recent dataflow research projects. Introduces dataflow notation and the tagged-token computational model. Discusses the principles of dataflow machine design and presents a number of state-of-the-art experimental systems. Discusses the issues involved in selecting a dataflow programming language and introduces the single-assignment approach.


43 title: Resource Management in a Multi-Ring Dataflow Machine

authors: A.P.W. B=F6hm, Y.M. Teo

volume: CONPAR 88

editors: C.R. Jesshope, K.D. Reinartz

publisher: Cambridge University Press

date: December 1989, pp. 566-577

abstract: Addresses the distribution of data structures and the control of program parallelism using a simulation model of the proposed Heterogeneous Multi-ring Manchester Dataflow Machine. The machine consists of several processing element rings, structure store rings and one global allocator ring. A scheme for distributed storage management is introduced. A dynamic hardware throttle is introduced. A scheme that controls the execution of macro dataflow instructions is proposed for integration into the throttle mechanism. Simulation results reveal that these enhancements reduce storage requirements significantly without loss of execution speed.


44 title: Iterative Instructions in the Manchester Dataflow Comput= er

authors: A.P.W. B=F6hm, J.R. Gurd

volume: IEEE Transactions on Parallel and Distributed Systems, vol.1 no.= 2

date: April 1990, pp. 129-139

abstract: Investigates the nature and extent of performance benefits and adverse effects of the iterative instructions used in the implementation of SISAL on the prototype Manchester Dataflow Computer.


45 title: Resource Management and Iterative Instructions

authors: Y.-M. Teo, A.P.W. B=F6hm

volume: Advanced Topics in Data-Flow Computing

editors: J.-L. Gaudiot, L. Bic

publisher: Prentice-Hall

date: 1991, pp. 481-499

abstract: Investigates the benefits and adverse effects of iterative instructions in the fine grain Manchester Data-Flow Machine. Two new resource management schemes for controlling iterative instruction execution are proposed and evaluated using simulation. Apart from reducing memory usage, these schemes have the important effect of reducing the occurence of pipeline bubbles caused by lengthy iterative instructions.


46 title: Manchester Data-Flow: A Progress Report

authors: J.R. Gurd, D.F. Snelling

volume: Proceedings 6th ACM International Conference on Supercomputing (ICS'92)

publisher: ACM Press

date: July 1992, pp. 216-225

abstract: Looks afresh at the Manchester Data-Flow Machine (MDFM) architecture, in the light of new hardware and software technology and the new state-of-the-art in data-flow computing, and derives an updated architecture, NMDFM, for a MDFM-style multi-processor system. Variable parameters of the NMDFM are investigated in an attempt to find an "optimum" set for future studies.


47 title: A Comparative Study of Data-Flow Architectures

authors: D.F. Snelling, G.K. Egan

volume: Parallel Architectures and Compiling Techniques

editors: M. Cosnard, G.-R. Gao, G.M. Silberman

publisher: North Holland Publishing Company

date: 1994, pp. 347-350

abstract: A short version of the report, number R5, listed in the next section. Three different data-flow systems (MDFM, SDFA and CSIRAC II) are compared in terms of the number of tokens they create per benchmark task.


48 title: Workload Management in Massively Parallel Computers: Some Data-Flow Experiences

authors: D.F. Snelling, J.R. Gurd

volume: Advanced Topics in Data-Flow Computing and Multi-Threading

editors: G.-R. Gao, L. Bic, J.-L. Gaudiot

publisher: IEEE Computer Society Press

date: 1995, pp. 325-347

abstract: Reviews workload management in both data-flow and thread-based parallel computers and draws analogies between the two styles. Workload management in data-flow systems, in general, and in the MDFM, in particular, is surveyed. The effectiveness of several management tehniques is analysed, in terms of their ability to control the instantaneous amount of memory required versus the induced decrease in performance. This is attempted for both the shared memory style MDFM and a distributed memory style data-flow system known as the Stateless Data-Flow Architecture (SDFA).


49 title: Exploiting Locality in a Stateless Data-Flow Architectur= e

author: D.F. Snelling

volume: Proceedings LLNL/CSU Conference on High Performance Functional Computing

publisher: Lawrence Livermore National Laboratory

date: April 1995, pp. 193-207

abstract: Of the two approaches to managing latency in parallel computer systems, latency hiding and latency avoidance, data-flow systems have traditionally exploited latency hiding only. The Stateless Data-Flow Architecture (SDFA) does both. The paper outlines the nature of latency and its impact on data-flow architecture, introduces salient features of the SDFA, and presents pertinent simulation results.


50 title: Self-Regulation of Workload in the Manchester Data-Flow Computer

authors: J.R. Gurd, D.F. Snelling

volume: Proceedings 28th ACM/IEEE International Symposium on Microarchitecture (MICRO-28)

publisher: IEEE Computer Society Press

date: November 1995, pp. 135-145

abstract: Investigates how memory use, via control of the prevailing workload, has been achieved in the Manchester Data-Flow Computing System (NMDFM hardware design plus SISAL language software system). The design and performance of the Throttle Unit, the hardware device responsible for managing the workload in this system, are presented and analysed.


Internal Reports

R1 title: A Multilayered Dataflow Computer Architecture

authors: J.R. Gurd, I. Watson, J.R.W. Glauert

date: March 1980, 90 pp. (3rd issue)

abstract: Introduces the multilayered dataflow computer architecture which is based upon a high level language and an underlying graphical notation for representing computations. The language, Lapse, employs a single-assignment rule together with some more familiar parallel programming constructs. The graphical notation utilises the concept of labels for dataflow tokens which use computational subgraphs reentrantly. The architecture is based on a ring structure in which binary representations of tokens circulate. The ring structure may be pipelined to achieve a rate of node execution limited by the amount of parallel activity permitted in the program and by the technology used. An extensible version of the architecture contains many rings in a multilayered, parallel structure whose execution rate is bound solely by the parallelism of the programs running on it.


R2 title: Manchester Dataflow Machine: Preliminary Benchmark Test Evaluation

author: J.F. Foley

code: UMCS-87-11-2

date: November 1987, 95 pp.

abstract: The Manchester Dataflow Hardware is supported by a Software compiler for the SISAL language and a number of programs have been written to act as Benchmark tests for the hardware. The Benchmark set used contains a wide range of programs including numerical algorithms, sorting, graph colouring and nqueens algorithms plus others. All programs are compiled using a range of optimisations, including functions inlining and vectorisation. The resulting statistics, obtained both by simulations and hardware are presented.


R3 title: The Heterogeneous Multi-Ring Dataflow Machine Simulator

authors: A.P.W. B=F6hm, Y.M. Teo

code: UMCS-89-3-1

date: March 1989, 26 pp.

abstract: Increased complexity in parallel and multiprocessor system architectures has accentuated the need for tools that assist in understanding the behaviour and evaluating the performance of these systems. This report describes a simulation model of the proposed Heterogeneous Multi-ring Dataflow Machine (MDM), consisting of a number of processing element rings, structure store rings and one global allocator ring. The structure of the multi-ring dataflow machine simulator, MR, is presented. Distributed storage management is introduced. A proposed dynamic hardware throttle mechanism which matches program parallelism to machine parallelism is discussed. A scheme that controls the execution of macro dataflow instructions is proposed for integration into the throttle mechanism. This report serves as the defining document for MR, which is one of the tools used for programming and architectural experimentations in the proposed multi-ring Manchester Dataflow Machine.


R4 title: Manchester Dataflow Machine: Benchmark Test Evaluation Report

author: J.F. Foley

code: UMCS-89-11-1

date: November 1989, 177 pp.

abstract: The Manchester Dataflow Hardware is supported by a Software compiler for the SISAL language and a number of programs have been written to act as Benchmark tests for the hardware. The Benchmark set used contains a wide range of programs including numerical algorithms, sorting, graph colouring and nqueens algorithms plus others. All programs are compiled using a range of optimisations, including functions inlining and vectorisation. The resulting statistics, obtained both by simulations and hardware are presented. This final report includes new Benchmark codes and contains results illustrating the effectiveness of a prototype hardware implementation of the parallelism throttle.


R5 title: A Comparative Study of Data-Flow Architectures

authors: D.F. Snelling, G.K. Egan

code: UMCS-94-4-3

date: April 1994, 20 pp.

abstract: Three widely different data-flow systems (MDFM, SDFA and CSIRAC II) are compared using a relatively uniform metric which is representative of the actual amount of 'work' performed by these systems when executing a small collection of 'kernel' benchmarks. The creation of tokens, which is a feature common to all data-flow systems, serves as the basis for this metric of 'work'. By counting the creation of tokens in all parts of the candidate systems, an accurate measure of the work performed can be obtained. All three machines perform approximately the same amount of work when solving the benchmark problems, but two systems (SDFA and CSIRAC II) demonstrate successful exploitation of their memory hierarchy. This report is an entended version of published paper number 47.


Ph.D. Theses (24 month projects)

D1 title: Implementation of Data Structures in a Dataflow Computer

author: D.L. Bowen

date: May 1981, 166 pp.

abstract: Considers implementation of data structures in high-level programming languages for the Manchester prototype dataflow machine. Structures are implemented in two different ways. Firstly, every component of a structure is transferred along common data paths in the program graph. Secondly, structures are stored in system memory, and are represented by pointers which are transferred as scalars in the program graph. The first method is shown to have some advantages in terms of parallelism, and limited storage needs. The second method reduces the work performed, but also limits parallelism unless the system architecture is altered. The design and implementation of the high-level language Mad, which is used as a test-bed for these ideas, is described. The results of simulation of example program runs are given.


D2 title: Nondeterministic Programming in a Data Driven Environmen= t

author: A.J. Catto

date: June 1981, 188 pp.

abstract: Demonstrates the support of nondeterministic applications on the Manchester prototype dataflow computer by developing flowgraph implementation models for three different high-level nondeterministic programming languages. The languages studied are Brinch-Hansen's Distributed Processes (procedure-oriented), Hoare's Communicating Processes (message-oriented), and Arvind and Gostelow's Id (dataflow oriented). At the machine-level, specialised matching functions are used to achieve the required nondeterminism, and nodes necessary for construction of safe flowgraphs are proposed. A new notation is used to facilitate verification of the flowgraph programs.


D3 title: A Pseudo-Associative Matching Store for the Manchester Prototype Dataflow Computer

author: J.G.D. da Silva

date: February 1982, 183 pp.

abstract: Describes in detail the philosophy and the physical design of the Matching Unit within the Manchester Prototype Dataflow Machine. Matching is restricted to a maximum of two operands destined as input to an instruction, and is implemented using associative storage techniques. The use of true content-addressable memory is precluded because of its low density and high cost. Therefore a pseudo-associative store using hardware hashing techniques and implemented with conventional random-access memory is employed. The data driven execution scheme implies that search operations in the associative store do not have to be resolved in the same sequence as they are presented to the Matching Unit. Consequently a structure using a main hash table of fixed capacity operating in parallel with a separate overflow mechanism can be utilised. To improve speed, the main hash table has multiple banks of store accessed in parallel. Overflow searches proceed without halting further match operations in the main hash table.


D4 title: The Formal Semantics of Deterministic Dataflow Programs

author: J.N.F. Oliveira

date: February 1984, 349 pp.

abstract: Addresses the=20impact of dataflow computing on software technology and, in particular, studies the semantics of dataflow programs. The Manchester dataflow system design is used as an example for the study. Semantics for the Manchester machine are described at the usual graphical level using notation characteristic of dataflow programming. Properties of the Manchester system are studied from both theoretical and practical points of view. Based on this semantics, methods for constructive design and proof of programs written for the Manchester machine are proposed. A transformational approach to dataflow program development based on functional programming is presented as the basis for a more ambitious reasoning methodology.


D5 title: Efficient Stored Data Structures for Dataflow Computing

author: J. Sargeant

date: August 1985, 217 pp.

abstract: One of the major problems in dataflow computing has been the handling of data structures. The concept of stored data structures must be integrated at reasonable cost into the dataflow model of computation. The thesis describes how this can be achieved, particularly in the context of the Manchester prototype dataflow machine. Problems are tackled at several levels, including that of the underlying hardware. An extension to the prototype architecture, the Structure Store, is described. The code generated for the dataflow language SISAL is discussed in detail. Particular attention is paid to the issue of garbage collection. Optimisations which improve the quality of dataflow code are described. As a result of this work, it is now possible to generate from SISAL dataflow code which is efficient in terms of the total number of instructions executed, while retaining the ability to exploit large amounts of parallelism. Simulation results are presented to demonstrate this achievement.


D6 title: The Application of a Formal Development Method to a Parallel Machine Environment

author: K.D. Jones

date: January 1986, 158 pp.

abstract: A well-established formal development method (VDM) is applied to an environment involving parallelism at the machine level. Necessary extensions to both the Meta-language and the method are discussed. A formal semantic definition for the Manchester Dataflow Machine is presented in the denotational style, using the VDM Meta-language extended to include relational objects. The nondeterminate applicative programming language REAL is presented and formally defined. A compile function from REAL to the machine is specified, and a correctness argument (with respect to the semantic definitions) is presented. The relevance of a formal development method to this unconventional environment is discussed.


D7 title: A Hardware Simulator for a Multi-ring Dataflow Machine

author: J.F. Foley

date: May 1986, 222 pp.

abstract: The Manchester dataflow machine has demonstrated a near linear speedup in program execution when multiple processors are used, provided only that sufficient parallelism is available within the problem. However, the machine has a limited memory bandwidth and this places a ceiling on computation rates; the matching and node stores are particular bottlenecks. One solution is a multi-ring machine consisting of a number of dataflow machines (each with several processors) connected by a switching network and operating in parallel. In order to test such a system, a hardware simulator has been built. This thesis gives details of the machine and the results of initial tests.


D8 title: Specification and Control of Execution of Nondeterministic Dataflow Programs

author: P.M.C.C. Barahona

date: April 1987, 180 pp.

abstract: Proposes extensions to the Manchester Dataflow System so as to combine heuristics and parallelism for efficient execution of non-deterministic applications. Investigates the suitability of the extended system for support of logic programming. A nondeterministic set data type and a priority construct are added to the SISAL language to allow flexible control=20of program execution. The set type prevents spurious data dependences from being introduced in the logical component of the program specification. The priority construct allows problem-dependent heuristics to be specified separately. A heuristic is acted on by a process-based means of controlling execution, added to the normal data-driven control. Simulations have produced encouraging results which are presented and analysed in detail.


D9 title: Throttle Mechanisms for the Manchester Dataflow Machine

author: C.A. Ruggiero

date: July 1987, 209 pp.

abstract: Addresses the problems caused by excessive software parallelism saturating storage in the prototype Manchester dataflow machine. Different software and hardware methods for controlling parallelism and thereby reducing store utilisation are presented. Each method is assessed by means of simulation. A process-based method is selected as the most suitable for a multi-processor machine. Advantages and disadvantages of this method are discussed. The importance of defining the boundaries of a process, and subsequently detecting its creation and termination, is noted. Three methods for detecting process termination are analysed. An instruction reference counting scheme is described in detail and its performance evaluated by means of simulation.


D10 title: Recursion Transformations for Run-time Control of Parallel Computations

author: V.J. Bush

date: August 1987, 200 pp.

abstract: Considers the transformation of recursive algorithms between forms that fit different parallel machines. Develops appropriate transformations based on an algebraic reasoning system for a dataflow model of computation. The functional language FP is used as a high-level notation for dataflow graphs. An operational semantics for a dynamic dataflow model is described and related to an algebraic semantics for FP. A taxonomy of recursive forms of algorithms is presented, and the relationship between the syntactic form of an algorithm and its behaviour is described. Transformations between different recursive forms are studied. Transformations between sequential and parallel forms, for both run-time and compile-time use, are developed.


D11 title: Parallel Structure Storage in a Dataflow Machine

author: K. Kawakami

date: September 1988, 229 pp.

abstract: Considers parallelism in structure store operations. It is shown that both space allocation and garbage collection can be performed in parallel, in addition to the normal store access operations. All such functions are designed to be scalable (i.e. performance can be increased incrementally by simply adding hardware modules of the appropriate type) and relative performances can be balanced. Details of the implementation of a hardware structure store for the prototype Manchester Dataflow Computer are given and its performance is evaluated, leading to suggestions for future extensions of the system to allow exploitation of greater parallelism.


D12 title: Concurrency Control in the Multi-Ring Manchester Dataflow Mac= hine author: Y.M. Teo date: November 1989, 239 pp. abstract: Demonstrates how to control over-abundent program parallelism so as to fully exploit available machine parallelism. Using the Multi-Ring Manchester Dataflow Machine as an example, an architectural approach to program concurrency control at two levels is proposed. Inter-process parallelism is controlled by a process-based hardware throttle which imposes depth-first process execution. The throttle is a self-adaptive feedback control mechanism that matches program and machine parallelism by scheduling processes for execution depending on the machine activity level. Intra-process parallelism is restrained by controlling the execution of iterative instructions. Two approaches, the self-scheduling method and the process-tree method, are studied. Apart from reducing memory usage, controlling iterative instructions has the important effect of reducing the occurrence of pipeline holes caused by lengthy iterative instructions. The optimal multi-ring configuration that can be supported by a hardware throttle is established.


D13 title: The Design and Analysis of a Stateless Data-Flow Architecture

author: D.F. Snelling

date: July 1993, 203 pp.

abstract: A dynamic tagged-token data-flow architecture, SDFA (Stateless Data-Flow Architecture), is presented and evaluated. SDFA does not support an explicit form of memory (state) and is thus better able to exploit the fundamental advantages of the data-flow model (uniform load balance, latency hiding, and good performance for small problems, in a distributed memory architecture) than stateful systems. With the shared memory constraint removed, the SDFA system becomes truly scalable. The thesis sets out the case for the stateless model, develops an architecture based on this approach, presents a detailed simulation-based analysis of the system, and proposes further research.


M.Sc. Method 2 Dissertations (12 month projects)

M1 title: Implementation of Monitors in a Dataflow Computer

author: G.B. Lane

date: October 1978, 142 pp.

abstract: Discusses the implications of structuring software into processes which are implemented in an inherently data driven system. Various mechanisms are studied whereby processes may be created, destroyed, controlled, and allocated resources. The mechanisms are based on the Manchester prototype dataflow system.


M2 title: Implementation of an Input/Output System for a Dataflow Comput= er

author: A. Benkherouf

date: January 1982, 99 pp.

abstract: Examines schemes for input/|output on the Manchester Dataflow Machine. Includes a comparison of the approaches used in the Lapse and Mad languages and their compilers. Proposes an extension to Lapse to use random-access files and describes an implementation of this scheme.


M3 title: Implementation of Structured Lucid on a Dataflow Computer

author: J. Sargeant

date: October 1982, 161 pp.

abstract: A logical follow-up to the work of Bush, this describes a demand driven implementation of a language derived from the original Lucid. A feature of the implementation is the use of lazy evaluation. Details of code generation for the constructs of Structured Lucid are given. Simulation results from running various test programs are presented. Code optimisations are suggested and the problems of garbage collection are examined.


M4 title: A Dataflow Implementation of SASL

author: G. Richmond

date: October 1982, 132 pp.

abstract: Techniques for implementing functional languages on the Manchester dataflow machine are investigated further. The work described is complementary to that of Sargeant. SASL programs are translated into dataflow graphs which simulate demand driven execution. Lazy evaluation of shared subexpressions, and techniques for implementing list structures and functions (including 'Curried' functions and other higher order functions) are topics which are given particular attention. Possible improvements, including a concurrent garbage collection scheme, are outlined.


M5 title: A Dataflow Software Development Environment

author: R.M.A. Jarratt

date: October 1984, 178 pp.

abstract: Presents a first attempt at providing software development tools for the Manchester Dataflow Machine. The emphasis is on debugging tools. Software development tools are surveyed and unusual characteristics of the dataflow environment are discussed. A symbolic post-mortem dumping facility for the single-assignment language Mad is described. Ways of providing powerful debugging tools, such as interactive debuggers, are discussed.


M6 title: Performance Evaluation of a Multi-ring Dataflow Machine

author: P.M.C.C. Barahona

date: October 1984, 137 pp.

abstract: The prototype Manchester dataflow computer is a uniprocessor composed of several units pipelined together in a ring. This thesis is a preliminary attempt to assess the performance of a multi-ring dataflow machine built with several such processing elements. The switch unit required to interconnect the rings, and the allocation of the dataflow instructions to the processing elements are topics which are discussed in detail. Simulation has been used to predict performance, and improvements to the ring architecture are proposed.


M7 title: A Dataflow Programming Environment

author: H.W.H. Tang

date: October 1987, 154 pp.

abstract: Describes the problems of monitoring activity in parallel computer systems, and presents the architectures of three experimental parallel machines under investigation at the University of Manchester. Two monitoring tools that present monitoring data for the Manchester Dataflow Machine in the form of animated graphical displays are described. A program-level tool displays a dataflow program executing on a parallel machine, and a machine-level tool displays the state of that machine.


M8 title: Performance Evaluation of a Heterogeneous Multi-ring Dataflow Machine

author: Y.M. Teo

date: October 1987, 133 pp.

abstract: Describes a performance evaluation of the proposed heterogeneous multi-ring Manchester Dataflow Machine. This consists of multiple processing element rings, multiple structure store rings, and a global allocator ring. A bottleneck analysis identifies the instruction store as the most critical bottleneck in the processing element ring. Architectural changes that remove this bottleneck are proposed. A message-based scheme is proposed for implementing the dynamic, process-based hardware throttle. The scheme is shown to reduce memory requirements in the processing element rings by matching program parallelism with available machine parallelism at run-time.


M9 title: Aspects of Implementation for SISAL 2.0 on the Manchester Dataflow Machine

author: M.I. York

date: May 1992, 152 pp.

abstract: Describes the problems involved in implementing the novel features in SISAL 2.0 which extend the array handling abilities of SISAL and add higher order functions to the language. Introduces methods of implementation of both sets of features on the Manchester Data-Flow Machine. Extensions to the hardware architecture are considered for improving the execution efficiency of curried functions.


M.Sc. Method 1 Dissertations (6 month projects)

S1 title: A Dataflow System Simulator

author: P.J. Jinks

date: October 1977, 72 pp.

abstract: Describes the implementation of a general-purpose, asynchronous system simulator, tailored to simulate a prototype dataflow computer design at hardware module level.


S2 title: The Design of a Processor Array for a Dataflow Architecture

author: J. Zurawski

date: October 1977, 174 pp.

abstract: Investigates various approaches to producing a constant throughput processing unit for a data driven computer. A comparative study of the effectiveness of different combinations of small microprocessors, bit-sliced families and dedicated random logic designs reveals the optimum choice to be a system based on the AMD2901A bit-sliced ALU. A complete design for this system is developed, together with performance estimates.


S3 title: A Single-Assignment Language for Dataflow Computing

author: J.R.W. Glauert

date: January 1978, 218 pp.

abstract: Describes a single-assignment language designed for compilation into data driven machine code. Explains the compilation process and the behaviour of resultant object code. Whilst the language is relatively simple, it raises many fundamental issues of code generation and optimisation in circumstances such as iteration, function calling, and handling of arrays. The latter area calls for some measure of demand driven action, in addition to the normal data driven mode. This study has had a large influence on the design of the prototype system ordercode.


S4 title: Extensions to=20a Compiler for Lapse, a Single-Assignment= Language for Dataflow Computing

author: A.G. Bradshaw

date: October 1978, 114 pp.

abstract: Building on the work of Glauert, this dissertation describes modifications to the Lapse compiler which optimise part of the code generation phase and increase the range of recognised data types.


S5 title: A Processing Unit for the Manchester Dataflow Computer

author: J.G.D. da Silva

date: November 1978, 127 pp.

abstract: Following on from the work of Zurawski, this dissertation presents a complete design for a constant throughput processing unit for the prototype data driven system. The unit is designed around AMD2903 bit-sliced ALUs. Details of microcode for a sample ordercode are given. Particular attention is paid to floating point operations.


S6 title: A Conventional Language for Dataflow Computation

author: P.J. Whitelock

date: October 1978, 92 pp.

abstract: Describes the problems of implementing a compiler for a simple sequential programming language (PL0, a subset of Pascal) producing data driven object code. Loops, procedures, reassignment and input/|output are studied in detail. The harder problems of gotos and arrays are treated briefly.


S7 title: A Dataflow Implementation of Lucid

author: V.J. Bush

date: October 1979, 118 pp.

abstract: Discusses the issues governing data driven machine-level execution of programs written in the mathematically oriented language, Lucid. The language itself is introduced, and some of its advantages explained. Translation of programs into an intermediate, graphical form is described. Machine-level implementation of the intermediate graphs is demonstrated, and run-time results are presented.


S8 title: Techniques for Data Driven Implementation of Functional Langua= ges

author: R.M. Brimley

date: October 1980, 70 pp.

abstract: Demonstrates the implementation of three aspects of functional programming languages, using dataflow techniques. The language features studied are lazy evaluation, higher order functions, and partial parameterisation. The examples used are based on the ordercode of the Manchester prototype dataflow machine.


S9 title: Nondeterministic Programming on a Dataflow Computer

author: D.J. Pearson

date: February 1982, 137 pp.

abstract: Examines the feasibilty of using the Manchester prototype dataflow machine to implement parallel, breadth-first nondeterministic algorithms. The classic n-queens problem is used as a basis for the study. Consideration is given to a means of terminating programs when only the first solution is required. The concurrent activity of several independent processes poses some interesting problems which are investigated and shown to be solvable in the Manchester System.


S10 title: A Dataflow Code Generator and Optimiser

author: V.E. Aspin

date: October 1982, 110 pp.

abstract: Describes the design and implementation of a back-end processor for the Template Assembler, TASS. The Assembler produces machine-level assembly code from compiler output. The back-end is responsible for code generation and machine-level optimisation. Interfaces between the code generator and the high and low level assemblers are described. The implementation is described as a four-stage process, with optimisation as an optional fifth stage. Existing optimisations are examined and future improvements are suggested.


S11 title: Parallel Data Driven Logic Simulation

author: J.A. Kamani

date: October 1986, 155 pp.

abstract: Describes the design and implementation of low-level event-driven and time-driven logic simulation programs to run on the prototype Manchester dataflow machine. The programs are based on a distributed control technique which leads to highly parallel execution by avoiding centralised control. The traditional assumptions of two-value simulators are adopted as they are useful for checking logical and general timing behaviour of=20both combinational and sequential circuits. An evaluation of the relative merits of the two simulation methods is presented.


S12 title: Exploitation of Parallelism in Lee's Algorithm Tracking Routi= nes

author: G.S.H. Tan

date: November 1986, 136 pp.

abstract: Tracking (or routing) connections on printed circuit boards or integrated circuits is a time-consuming process required during physical layout of logic designs. The thesis describes two tracking routines, based on the standard Lee's algorithm, written in the single-assignment language SISAL. Simulation results are presented showing how small tracking tasks can be performed in parallel on the Manchester dataflow machine.


Dataflow Simulation and Development Software in Pascal

This software is available on magnetic tape from the Dataflow Project Group, at the address given earlier. Unless otherwise requested, the tape will be recorded in ASCII code, variable block, labelled format, at 1600 b.p.i. The programs come complete with manuals and a package of utility routines. A handling charge of =A350 is payable for the tape and the software. Please send payment or an official order with your letter of request.


program: DFUTIL

title: Utility Routines

manual: Software Distribution Manual


program: SIM

title: Dataflow System Simulator

manuals: Basic Programming Manual Simulator Users Guide


program: IF1

title: IF1 Translator

manuals: IF1 Reference Manual

IF1 Compilation System Users Guide


Manchester Prototype Dataflow System Manuals

These are available only with the software release package described abov= e.

title: Basic Programming Manual

author: C.C. Kirkham

date: September 1987, 40 pp. (6th issue)

abstract: Machine-level programmer's view of the prototype system and software emulation facilities. Describes all the features of the operational hardware. Gives details of the textual representation of machine-code programs and data, and defines the prototype instruction-set. Illustrated by a small number of example programs.


title: IF1 Compilation System Users Guide

authors: J. Sargeant, A.P.W. B=F6hm

date: October 1985, 13 pp. (2nd issue)

abstract: A description of the programs used to compile and run dataflow code from the IF1 level. This is now the preferred route for generating code, and the only route available for SISAL programs. Formats for data preparation are given.


title: Simulator Users Guide

author: J. Sargeant

date: January 1986, 7 pp. (2nd issue)

abstract: Description of the dataflow machine simulator program SIM and how to use it. Includes instructions for obtaining monitoring information and shows how to interpret the output data.

Back to Research home page
Back to CNC home page