Data-Structuring Operations in Concurrent Computations.
Abstract
This thesis proposes operational specifications for a Structure Memory (SM). A specialized hardware component of a general-purpose computing system, the SM would directly execute operations on dynamically structured data stored in it. The computing system is assumed capable of exploiting program concurrency at the machine-instruction level. Concurrency among a set of program instructions which all examine or modify the same structure must be carefully controlled, if the program is to be determinate. The first of two major contributions of the thesis is a combination hardware/software discipline which affords maximal concurrency consistent with determinacy. Its key feature is that the SM will not return a given pointer until certain previously-returned pointers to the same structure are no longer available as operands. The second major contribution is the entry-execution model of concurrent computation. Reversing the emphasis of most previous work, this model concentrates on the operations performed by instructions, while abstracting away details of how operands are passed among them and how their execution order is determined. The essence of structure operators, that the result of an execution of one may depend on the input to previous executions of that and other operators, is given a natural expression in the new model. A proof of sufficient conditions for determinacy is made more generally applicable through use of the entry-execution model as its medium.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1979
- Accession Number
- ADA083233
Entities
People
- David Lee Isaman
Organizations
- Massachusetts Institute of Technology