Technology has a profound influence on computer science. In the past, technology has always been a constraint and has required computer designers to organize computers around what was feasible rather than what was desired. Whenever new technology arrived (e.g., transistors in place of tubes) the line of feasibility simply moved. However, microelectronics has brought far more severe changes and the line of feasibility has not only moved drastically, even moving beyond what computer scientists were prepared for, but is now requiring us to reconsider the basic conceptual precepts upon which (almost) all computers have rested. That is, computer scientists have been confined totally to the so-called von Neumann class of computers and their three basic attributes: low-level machine language, centralized sequential control, and linear memory organization. Machines based upon these characteristics have worked fairly well in the past (the last 30 years), but recent developments in LSI technology have changed these attributes themselves into inappropriate constraints. For example, LSI favors distributed and asynchronous computer operation — a principle incompatible with von Neumann machines. Also, since basic components are far more complex, and thorough testing is economically unfeasable, achieving reliability must be a primary design consideration.

Petri-nets are used as a model of processes, and a property of a net called proper termination is defined and discussed. Proper termination is argued to be a useful property which a construct called a "module" should possess. This property assures reentrancy and freedom from deadlock in the net, and a theorem is given concerning the substitution or interchange of modules in a larger environment.

This report describes the meaning of various data flow operators in terms of relationships between the history of input lines and the history of output lines associated with an operator. Data flow programs are formed by interconnecting data flow operators, and by specifying the program input lines. The history of each line in a program is determined by the history of the input lines of the program. The semantics of a program are defined by a set of fixpoint equations determined by the data flow operators and their interconnections. The least fixpoint solution of such a system of equations is considered, and it is shown that all the operators and all programs under the Unraveling Interpreter are more defined than under the usual Queued Interpreter. However, if only physically meaningful (i.e. proper) inputs are considered then it is shown that both interpreters will arrive at the same least fixpoint solution. Since the Unraveling Interpreter is more defined than the Queued Interpreter, the dynamics of token generation under the Unraveling Interpreter, in general, exhibit more asynchrony than under the Queued Interpreter, even if the inputs to the program are restricted to be physically meangingful.

With the advent of LSI technology large numbers of inexpensive processors have become available, yet our ability to realize the full potential of this technology has fallen short. A primary reason for this failure has been due to an inability to move beyond the sequential control structure of conventional programming languages. The notion of a sequential and/or centralized control for a machine composed of large numbers of processing elements severely restricts the design and complexity of possible computer architectures. We claim that data flow languages (i.e., languages in which the execution of statements is constrained only by the availability of the required operants) provide an alternative base machine language more suited to a technology (such as LSI) which favors distributed processing.

The objective of the proposed research is to formulate and evaluate (by simulation) a machine whose design is based on a new technique of interpreting existing data flow languages. The most significant and distinguishing aspect of this new scheme of interpretation is that it permits a literal exchange of processing elements for computation time, in a very general and mechanical way. An architecture based on the new interpreter will allow a computation to unfold and spread dynamically over a space of processing elements. The machine also has the capability of partitioning itself into disjoining domains of activity, each domain corresponding to the execution of a distinct process.

When the proposed research is carried out, we will have shown that processing elements (space) can be exchanged for time, and that this makes possible a computer organization capable of effectively utilizing large number of processors.

The primary objective of the proposed research is to define and evaluate an architecture for a computer system comprising large numbers of small processors, thereby taking new advantage of LSI technology. Our premise, however, is that such a machine cannot be successful if based upon the usual von Neumann concepts of sequential control and the memory cell. Instead, we adopt the principles of dataflow as a more appropriate semantic base, since dataflow places no constraints on the order of execution other than the arrival of data. Such a basis appears very well suited to a technology disposed towards distributed processing.

We have developed so far both a high-level dataflow programming language and a base machine language into which programs are compiled for execution. We also have devised an interpreter for the base language capable of more highly asynchronous operation than other dataflow systems. It is the emulation of this interpreter that is the goal of the machine proposed here.

We feel that success in this work would be significant since such machines might not only speed the execution of programs, but may also allow the development and application of significant reliability and fail-soft techniques.

A second objective of the proposed work is to collect the experiences of others in using the particular high-level dataflow language we have devised, to improve it, and to determine how well people are able to program in dataflow.

The execution of a program may be viewed as the processing of a statement in a programming language by an underlying interpreter. This report discusses briefly the advantages of a data flow language over conventional programming methods, and then presents a new interpreter for a data flow language. Using as a base the data flow language of Dennis ["First Version of a Data Flow Procedure Language" Computation Structures Group Memo 93, Project MAC, MIT, Nov. 1973], the new interpreter magnifies the apparent asynchrony and speed of data flow, and it does so by (quite literally) exchanging blocks of processors for slices of time. The report gives details of the operation of this new interpreter, and identifies the consequences of the new interpreter on machine architecture and design.