Data processing apparatus for highly parallel execution of stored programs

• US 4,153,932 A
• Filed: 08/19/1975
• Issued: 05/08/1979
• Est. Priority Date: 03/29/1974
• Status: Expired due to Term

• Current Assignee: Dataflow Computer Corporation, David P. Misunas
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Dennis, Jack B., Misunas, David P.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Rhoads, Jan E.
• Application Number:
  US05/605,932
• Time in Patent Office: 1,358 Days
• Field of Search: 445/1, 340/172.5, 179/15 AQ, 179/15 AT, 179/15 BA, 179/15 BV, 179/18 ES, 364/200 MS File, 364/900 MS File
• US Class Current: 712/27
• CPC Class Codes: G06F 9/4494 data driven

Abstract

A processor is described which achieves highly parallel execution of programs represented in data-flow form. The language implemented incorporates conditional and iteration mechanisms, and the processor incorporates practical data-flow processing of a Fortran-level data-flow language. The processor has a unique architecture which avoids the problems of processor switching and memory/processor interconnection that usually limit the degree of realizable concurrent processing. The architecture offers an unusual solution to the problem of structuring and managing a two-level memory system.

Claims

1. A digital data processor comprising:

(a) active memory means for holding at least a record of active instructions, said active memory means containing a plurality of cells, each cell holding one instruction of said record of active instructions and each cell having a unique cell index addressable by a destination address;

(b) instruction memory means for holding at least a record of a program, said instruction memory means holding all instructions comprising said record of a program and each instruction having a unique instruction index;

(c) operation means for managing signals in the execution of arithmetic and logical operations on signals representing data values including at least a destination address and a computed value.

(d) decision means for managing signals in the execution of comparison and testing operations on signals representing Boolean and control values;

(e) first arbitration means operatively connected between said active memory means and said operation means and operatively connected between said active memory means and said decision means for concurrently transmitting signals representing a plurality of first information packets from said active memory means to said operation means and for concurrently transmitting signals representing a plurality of second information packets from said active memory means to said decision means, each of said signals representing first information packets and each of said signals representing second information packets consisting of signals representing an instruction of said record of active instructions together with all critical data values required for its execution;

(f) control means operatively connected between said decision means and said active memory means for concurrently transmitting signals representing a plurality of third information packets from said decision means to said active memory means, each of said signals representing third information packets consisting of signals representing Boolean and control values computed by said decision means and required for the execution of said record of active instructions contained in said cells of said active memory means;

(g) first distribution means operatively connected between said operation means and said active memory means for concurrently transmitting signals representing a plurality of fourth information packets from said operation means to said active memory means, each of said signals representing fourth information packets consisting of signals representing data values computed by said operation means and required for execution of each of said active instructions contained in said active memory means at its corresponding destination address;

(h) memory command means operatively connected between said active memory means and said instruction memory means for concurrently transmitting signals representing a plurality of fifth information packets from said active memory means to said instruction memory means, each of said signals representing fifth information packets consisting of signals specifying storage, retrieval, and administrative operations to be performed by said instruction memory means;

(i) second arbitration means operatively connected between said active memory means and said instruction memory means for concurrently transmitting signals representing a plurality of sixth information packets from said active memory means to said instruction memory means said sixth packet representing instructions whose operations have been performed, each of said signals representing sixth information packets consisting of signals representing instructions of said record of a program to be temporarily stored in said instruction memory means; and

(j) second distribution means operatively connected between said instruction memory means and said active memory means for concurrently transmitting signals representing a plurality of seventh information packets from said instruction memory means to said active memory means, each of said signals representing seventh information packets consisting of signals representing instructions of said record of a program being conveyed to said active memory means to become instructions of said record of active instructions.

2. The digital data processor of claim 1 wherein said active memory means includes a plurality of cells, each of said cells having register means, said register means consisting of means for holding information records.

3. The digital data processor of claim 2 wherein said information records include a set of instructions and data items, each of said instructions including a set of functional specifications and destination indices, each of said functional specifications designating a path through said first arbitration means to one of said operation means or said decision means and each of said destination indices specifying a path through said control means or said first distribution means to one of said cells in said active memory means.

4. The digital data processor of claim 3 wherein each of said functional specifications includes a set of operational specifications and decision specifications, each of said operational specifications designating a path through said first arbitration means to one of said operation means and each of said decision specifications designating a path through said first arbitration means to one of said decision means.

5. The digital data processor of claim 1 wherein said operation means consists of computation means for the execution of aritmetic and logical operations on operand values received from said first arbitration means and first result means for transmitting data values realized by said computation means in conjunction with destination indices to said first distribution means.

6. The digital data processor of claim 5 wherein said signals representing first information packets are received by said operation means from said first arbitration means, and first information packets containing destination indices and all relevant operands, and said signals representing fourth information packets directed from said operation means to said first distribution means include a plurality of destination indices and result values.

7. The digital data processor of claim 1 wherein said decision means consists of testing means for the execution of comparison and testing operations on Boolean and control values contained in said second information packets received from said first arbitration means and second result means for transmitting values realized by said testing means in conjunction with destination indices to said control means.

8. The digital data processor of claim 7 wherein said signals representing second information packets are received by said decision means from said first arbitration means, said information packets containing destination indices and all revelant operands, and said signals representing third information packets directed from said decision means to said control means including a plurality of destination indices and result values.

9. The digital data processor of claim 1 wherein said first arbitration means concurrently transmits a plurality of signals representing first information packets from said active memory means to said operation means and a plurality of signals representing second information packets from said active memory means to said decision means, each of said first and second information packets containing a functional specification, a destination index, and all relevant operands, said functional specification designating a path through said arbitration means to said operation and decision means, said functional specification designating either an operation to be performed by said operation means on said relevant operands contained in said first information packet or by said decision means on said relevant operands contained in said second information packet, and said destination index designating a path through said first distribution means or said control means for a result value realized by the performance of the operation specified by said functional specification.

10. The digital data processor of claim 1 wherein said active memory means contains a plurality of cell blocks, each of said cell blocks being characterized by a plurality of cells, said cells constituting means for holding instructions and their relevant operands, said instructions being characterized by functional specifications and destination indices, said cell blocks constituting a cache for active instructions.

11. The digital data processor of claim 1 wherein a plurality of said signals representing third information packets are concurrently transmitted by said control means from said decision means and each of said packets contains a destination index and a control value, said destination index specifying a path through said control means to a destination cell in said active memory means and said control value representing a result computed by said decision means.

12. The digital data processor of claim 1 wherein a plurality of said signals representing fourth information packets are concurrently transmitted by said first distribution means from said operation means and each of said packets contains a destination index and a result value, said destination index specifying a path through said first distribution means to a destination cell in said active memory means and said result value representing a result computed by said operation means.

13. The digital data processor of claim 1 wherein said record of a program has instructions, each instruction being held in a location of said instruction memory having a unique address identifier, said instructions including functional specifications, destination indices and operand control pairs.

14. The digital data processor of claim 1 wherein a plurality of signals representing sixth information packets are concurrently transmitted by said second arbitration means and each contains a unique address identifier and an instruction containing a functional specification, destination indices and operand control pairs, wherein said unique address identifier designates the location of said instruction in said instruction memory means, specifying a path through said second arbitration means to said location in said instruction memory means.

15. The digital data processor of claim 1 wherein a plurality of said signals representing seventh information packets are concurrently transmitted by said second distribution means and each contains a unique address identifier and an instruction containing a functional specification, destination indices and operand control pairs, said unique address identifier designates the location of said instruction in said instruction memory means and specifies a path through said second distribution means to a destination cell in said active memory means, where said instruction contained in the seventh information packet upon receipt by said cell becomes a member of said record of active instructions.

16. The digital data processor of claim 1 wherein a plurality of said signals representing fifth information packets are concurrently transmitted by said memory command means and each contains a unique address identifier and a command for said instruction memory means, said unique address identifier designating the location in said instruction memory means affected by said command and said unique address identifier specifying a path through said memory command means to said location in said instruction memory means.

17.

18. A digital data processor comprising:

(a) active memory means for holding at least a record of active instructions, said active memory means containing a plurality of cells, each cell holding one instruction of said record of active instructions and each cell having a unique cell index addressable by a destination address;

(b) operation means for managing signals in the execution of arithmetic and logical operations on signals representing data values including at least a destination address and a computer value;

(c) decision means for managing signals in the execution of comparison and testing operations on signals representing Boolean and control values;

(d) arbitration means operatively connected between said active memory means and said operation means and operatively connected between said active memory means and said decision means for concurrently transmitting signals representing a plurality of first information packets from said active memory means to said operation means and for concurrently transmitting signals representing a plurality of second information packets from said active memory means to said decision means, each of said signals representing first information packets and each of said signals representing second information packets consisting of signals representing an instruction of said record of active instructions together with all critical data values required for its execution;

(e) control means operatively connected between said decision means and said active memory means for concurrently transmitting signals representing a plurality of third information packets from said decision means to said active memory means, each of said signals representing third information packets consisting of signals representing Boolean and control values computed by said decision means and required for the execution of said record of active instructions contained in said cells of said active memory means; and

(f) distribution means operatively connected between said operation means and said active memory means for concurrently transmitting signals representing a plurality of fourth information packets from said operation means to said active memory means, each of said signals representing fourth information packets consisting of signals representing data values computed by said operation means and required for execution of each of said active instructions in said active memory means at its corresponding destination address.