Technical reports

General theory relating to the implementation of concurrent symbolic computation

James Thomas Woodchurch Clarke

August 1989, 113 pages

This technical report is based on a dissertation submitted January 1989 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Trinity College.

DOI: 10.48456/tr-174

Abstract

The central result of this work is the discovery of a new class of architectures, which I call D-RISC, sharing some characteristics of both dataflow and Von Neumann RISC computers, for concurrent computation. This rests on an original and simple theory which relates the demands of concurrent computation on hardware resources to the fundamental performance constraints of technology. I show that dataflow and Von Neumann architectures have different fundamental hardware constraints to performance, and that therefore and D-RISC architecture, which balances these two constraints, is likely to be optimum for concurrent computation.

The work forms four related sections:

A study of the nature of concurrent symbolic computation and the demands which it makes from any implementation. Two new results emerge from this. A model of computation which will be used extensively in subsequent sections, and a way of incorporating imperative updates in a functional language, similar but superior to non-deterministic merge, which captures locally sequential updates in a computation with minimum constraint on global concurrency.

The computational model is udes to contrast different policies for localising data near a CPU. A new type of cache is proposed which renames all of its cached addresses in order to reduce CPU word-length.

CPU design is examined and a new class of architectures for concurrent computation, called D-RISCs, are proposed.

The multiple-thread implementation problems encountered in the new architectures are examined. A new analysis of the relationship between scheduling and intermediate store use in a symbolic concurrent computation is presented.

Full text

PDF (8.7 MB)

BibTeX record

@TechReport{UCAM-CL-TR-174,
  author =	 {Clarke, James Thomas Woodchurch},
  title = 	 {{General theory relating to the implementation of
         	   concurrent symbolic computation}},
  year = 	 1989,
  month = 	 aug,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-174.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-174},
  number = 	 {UCAM-CL-TR-174}
}