US4145733A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data processing apparatus for highly parallel execution of stored programs
Assignee: MISUNAS DAVID P
•
Filing: 1976-09-07
•
Granted: 1979-03-20
•
Expires: 1996-09-07
Abstract
Abstract A processor is described which achieves highly parallel execution of programs represented in data-flow form. The processor operates in a data-driven fashion; that is, an instruction of a program in the processor is enabled for execution upon the arrival of all required operands, and upon being executed, sends copies of the resulting value to all instructions which require it for their execution. The processor incorporates a form of deadlock prevention between the instructions of a data-flow program, allowing a value to be generated by an instruction and sent to the successor instructions in the computation only when those instructions are ready to receive the value. The incorporation of this mechanism prevents the possibility of conflict between successive stages of a pipelined computation and between successive iterations of an iterative computation.
Inventors
- 👤 David P. Misunas
- 👤 Jack B. Dennis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 18:16
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4494
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
440 words
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 index; (b) operation means for managing signals in the execution of arithmetic and logical operations on signals representing data values; (c) decision means for managing signals in the execution of comparison and testing operations on signals representing data values; (d) control identity means for managing signals in the execution of identity operations on signals representing control values; (e) first arbitration means operatively connected between said active memory means and said operation means and 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 said decision means, each of said signals representing first information packets consisting of signals representing an instruction of said record of active instructions together with data values required for its execution; (f) second arbitration means operatively connected between said active memory means and said control identity means for concurrently transmitting signals representing a plurality of second information packets from said active memory means to said control identity means, each of said signals representing second information packets consisting of signals representing control values necessary to insure correct operation of said digital data processor; (g) first 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 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; (h) second control means operatively connected between said control identity means and said active memory means for concurrently transmitting signals representing a plurality of fourth information packets from said control identity means to said active memory means, said signals representing fourth information packets consisting of signals representing control values necessary to insure correct operation of said digital data processor; and (i) distribution means operatively connected between said operation means and said active memory means for concurrently transmitting signals representing a plurality of fifth information packets from said operation means to said active memory means, said signals representing fifth information packets consisting of signals representing data values computed by said operation means and required for execution of said record of active instructions contained in said active memory means.
Claim 2
Dependent Claim
440 words
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 index; (b) operation means for managing signals in the execution of arithmetic and logical operations on signals representing data values; (c) decision means for managing signals in the execution of comparison and testing operations on signals representing data values; (d) control identity means for managing signals in the execution of identity operations on signals representing control values; (e) first arbitration means operatively connected between said active memory means and said operation means and 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 said decision means, each of said signals representing first information packets consisting of signals representing an instruction of said record of active instructions together with data values required for its execution; (f) second arbitration means operatively connected between said active memory means and said control identity means for concurrently transmitting signals representing a plurality of second information packets from said active memory means to said control identity means, each of said signals representing second information packets consisting of signals representing control values necessary to insure correct operation of said digital data processor; (g) first 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 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; (h) second control means operatively connected between said control identity means and said active memory means for concurrently transmitting signals representing a plurality of fourth information packets from said control identity means to said active memory means, said signals representing fourth information packets consisting of signals representing control values necessary to insure correct operation of said digital data processor; and (i) distribution means operatively connected between said operation means and said active memory means for concurrently transmitting signals representing a plurality of fifth information packets from said operation means to said active memory means, said signals representing fifth information packets consisting of signals representing data values computed by said operation means and required for execution of said record of active instructions contained in said active memory means.
Claim 3
Dependent Claim
34 words
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.
Claim 4
Dependent Claim
19 words
The digital data processor of claim 2 wherein said information records include a set of instructions and data items.
Claim 5
Dependent Claim
28 words
The digital data processor of claim 3 wherein each of said instructions includes control status means, control receipt means, and a set of functional specifications and destination indices.
Claim 6
Dependent Claim
49 words
The digital data processor of claim 4 wherein each of said functional specifications includes a set of operational specifications and decision specifications, each of said operational specifications designating a function performed by said operation means and each of said decision specifications designating a function performed by said decision means.
Claim 7
Dependent Claim
31 words
The digital data processor of claim 4 wherein said destination indices consist of unique cell indicia and routing specifications, said unique cell indicia each designating the unique index of a cell.
Claim 8
Dependent Claim
50 words
The digital data processor of claim 6 wherein each of said routing specifications specifies whether said unique cell indicia associated with the routing specification are to be included with said first information packets transmitted to said first arbitration means or said second information packets transmitted to said second arbitration means.
Claim 9
Dependent Claim
19 words
The digital data processor of claim 4 wherein said control status means consists of means for holding control indicia.
Claim 10
Dependent Claim
54 words
The digital data processor of claim 8 wherein each of said control indicia specifies the number of said fourth information packets which must be received from said second control means before said first information packets are transmitted to said first arbitration means and said second information packets are transmitted to said second arbitration means.
Claim 11
Dependent Claim
19 words
The digital data processor of claim 4 wherein said control receipt means consists of means for holding control records.
Claim 12
Dependent Claim
38 words
The digital data processor of claim 10 wherein each of said control records indicates the availability of cells to receive said fifth information packets from said distribution means and said third information packets from said first control means.
Claim 13
Dependent Claim
29 words
The digital data processor of claim 10 wherein each of said control records represents a recording of the arrival of said fourth information packets from said second control means.
Claim 14
Dependent Claim
23 words
The digital data processor of claim 3 wherein each of said data items consists of means for holding a plurality of data records.
Claim 15
Dependent Claim
38 words
The digital data processor of claim 13 wherein each of said data records consists of means for holding a set of data values or control values and indicia indicating the presence of said data values and control values.
Claim 16
Dependent Claim
28 words
The digital data processor of claim 14 wherein each of said data values is delivered to said cell in said fifth information packet received from said distribution means.
Claim 17
Dependent Claim
29 words
The digital data processor of claim 14 wherein each of said control values is delivered to said cell in said third information packet received from said first control means.
Claim 18
Dependent Claim
62 words
The digital data processor of claim 1 wherein said operation means performs arithmetic and logical operations on signals representing first information packets conveying data values received from said first arbitration means and transmits results achieved from the execution of an arithmetic or logical operation on the received signals representing data values as signals representing said fifth information packets to said distribution means.
Claim 19
Dependent Claim
56 words
The digital data processor of claim 17 wherein said first information packets are received by said operation means from said first arbitration means, said first information packets containing destination cell indices and all relevant operands, and said fifth information packets directed from said operation means to said distribution means include destination cell indices and result values.
Claim 20
Dependent Claim
62 words
The digital data processor of claim 1 wherein said decision means performs comparison and testing operations on signals representing second information packets conveying data values received from said second arbitration means and transmits results achieved from the execution of comparison or testing operations on the received signals representing data values as signals representing said third information packets to said first control means.
Claim 21
Dependent Claim
57 words
The digital data processor of claim 19 wherein said first information packets are received by said decision means from said first arbitration means, said first information packets containing destination cell indices and all relevant operands, and said third information packets directed from said decision means to said first control means include destination cell indices and control values.
Claim 22
Dependent Claim
56 words
The digital data processor of claim 1 wherein said control identity means performs identity operations on signals representing second information packets received from said second arbitration means and transmits results achieved from the execution of identity operation on the recieved signals representing control values as signals representing said fourth information packets to said second control means.
Claim 23
Dependent Claim
58 words
The digital data processor of claim 21 wherein said second information packets are received by said control identity means from said second arbitration means, said second information packets containing destination cell indices and control values, and said fourth information packets directed from said control identity means to said second control means include destination cell indices and control values.
Claim 24
Dependent Claim
332 words
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 index; (b) operation means for managing signals in the execution of arithmetic and logical operations on signals representing data values; (c) control identity means for managing signals in the execution of identity operations on signals representing control values; (d) first arbitration means operatively connected between said active memory means and said operation means for concurrently transmitting signals representing a plurality of first information packets from said active memory means to said operation means, each of said signals representing first information packets consisting of signals representing an instruction of said record of active instructions together with data values required for its execution; (e) second arbitration means operatively connected between said active memory means and said control identity means for concurrently transmitting signals representing a plurality of second information packets from said active memory means to said control identity means, each of said signals representing second information packets consisting of signals representing control values necessary to insure correct operation of said digital data processor; (f) second control means operatively connected between said control identity means and said active memory means for concurrently transmitting signals representing a plurality of fourth information packets from said control identity means to said active memory means, said signals representing fourth information packets consisting of signals representing control values necessary to insure correct operation of said digital processor; and (g) distribution means operatively connected between said operation means and said active memory means for concurrently transmitting signals representing a plurality of fifth information packets from said operation means to said active memory means, said signals representing fifth information packets consisting of signals representing data values computed by said operation means and required for execution of said record of active instructions contained in said active memory means.
Claim 25
Dependent Claim
332 words
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 index; (b) operation means for managing signals in the execution of arithmetic and logical operations on signals representing data values; (c) control identity means for managing signals in the execution of identity operations on signals representing control values; (d) first arbitration means operatively connected between said active memory means and said operation means for concurrently transmitting signals representing a plurality of first information packets from said active memory means to said operation means, each of said signals representing first information packets consisting of signals representing an instruction of said record of active instructions together with data values required for its execution; (e) second arbitration means operatively connected between said active memory means and said control identity means for concurrently transmitting signals representing a plurality of second information packets from said active memory means to said control identity means, each of said signals representing second information packets consisting of signals representing control values necessary to insure correct operation of said digital data processor; (f) second control means operatively connected between said control identity means and said active memory means for concurrently transmitting signals representing a plurality of fourth information packets from said control identity means to said active memory means, said signals representing fourth information packets consisting of signals representing control values necessary to insure correct operation of said digital processor; and (g) distribution means operatively connected between said operation means and said active memory means for concurrently transmitting signals representing a plurality of fifth information packets from said operation means to said active memory means, said signals representing fifth information packets consisting of signals representing data values computed by said operation means and required for execution of said record of active instructions contained in said active memory means.
References Cited (Backward Citations)
US3349375A
Cited
US3343135A
Cited
US3537074A
Cited
US3657736A
Cited
US3732548A
Cited
US3749845A
Cited
US3810100A
Cited
US3962706A
Cited
US4074232A
Cited
US4032899A
Cited
US4071706A
Cited
US4058672A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1982-03-19 | 1982-09-18 | 1983-03-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1986-03-19 | 1986-09-18 | 1987-03-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1990-03-19 | 1990-09-18 | 1991-03-20 | $7700.00 | Window Closed / Lapsed |