US 5,675,757 A · Direct match data flow memory for data driven computing

Abstract

A data flow computer and method of computing is disclosed which utilizes a data driven processor node architecture. The apparatus in a preferred embodiment includes a plurality of First-In-First-Out (FIFO) registers, a plurality of related data flow memories, and a processor. The processor makes the necessary calculations and includes a control unit to generate signals to enable the appropriate FIFO register receiving the result. In a particular embodiment, there are three FIFO registers per node: an input FIFO register to receive input information form an outside source and provide it to the data flow memories; an output FIFO register to provide output information from the processor to an outside recipient; and an internal FIFO register to provide information from the processor back to the data flow memories. The data flow memories are comprised of four commonly addressed memories. A parameter memory holds the A and B parameters used in the calculations; an opcode memory holds the instruction; a target memory holds the output address; and a tag memory contains status bits for each parameter. One status bit indicates whether the corresponding parameter is in the parameter memory and one status bit to indicate whether the stored information in the corresponding data parameter is to be reused. The tag memory outputs a "fire" signal (signal R VALID) when all of the necessary information has been stored in the data flow memories, and thus when the instruction is ready to be fired to the processor.

Claims41

Dependent claims

A direct match data flow memory for use with a processor that provides control logic and data paths, said memory comprising:

a plurality of storage locations, each storage location associated with a unique physical address, and each storage location comprised of at least three memory words of variable width, as follows:
(a) a first parameter memory word for storing a first parameter indicator of a first data parameter received as input data;
(b) an opcode memory word for storing an operation to be performed on said first parameter;
(c) a first flag memory word associated with said first parameter memory word, said first flag memory word having a state representative of the presence of said parameter in said first parameter memory word, and said operation to be performed when said first parameter is present, and
(d) a first recycle indicator memory word indicating that said first parameter is always available.

2 more elements

A processor element capable of receiving an input token and generating an output successor token, said processor element comprising:

(a) a processor which provides control logic, data paths, and arithmetic operations;
(b) a direct match data flow memory in a one-to-one relationship with said processor, said direct match data flow memory having a plurality of storage locations, each storage location associated with a unique physical address, whereupon said processor directs an input token having a target address and a parameter indicator to an appropriately addressed storage location in said direct match data flow memory along one of said data paths, each storage location of said direct match data flow memory having a plurality of memory words of variable width, comprising:
(i) at least one parameter memory word for storing said parameter indicator;
(ii) an opcode memory word for storing an operation indicator;
(iii) a flag memory word associated with said parameter memory word, and (iv) a first recycle indicator word associated with said parameter memory word indicating a state transition of said flag memory word, said flag memory word having a state representative of the presence of said parameter indicator in said parameter memory word, and depending upon the state of said flag memory word, said processor performs said operation indicated by said opcode memory word on said parameter indicator if said parameter is available and said processor generates an output successor token having a target address and an output parameter indicator to be output along one of said data paths, said output functioning as an input token in another direct match data flow cycle.

2 more elements

A direct match data flow machine, comprised of:

at least one processor element capable of receiving an input token, said processor element comprising:
(a) a processor which provides control logic, data paths, and arithmetic operations;
(b) a direct match data flow memory, in a one-to-one relationship with said processor, said direct match data flow memory having a plurality of storage locations, each storage location associated with a unique physical address, whereupon said processor directs an input token having a target address and a parameter indicator to an appropriately addressed storage location in said direct match data flow memory along one of said data paths, each storage location of said direct match data flow memory having a plurality of memory words of variable width, comprising:
(i) at least one parameter memory word for storing said parameter indicator;
(ii) an opcode memory word for storing an operation indicator;
(iii) a flag memory word associated with said parameter memory word, and (iv) a first recycle indicator word associated with said parameter memory word indicating a state transition of said flag memory word, said flag memory word having a state representative of the presence of said parameter indicator in said parameter memory word, and depending upon the state of said flag memory word, said processor performs said operation indicated by said opcode memory word on said parameter indicator if said parameter is available and said processor generates an output successor token having a target address and an output parameter indicator to be output along one of said data paths, said output successor token capable of being an input token for said processor element.

3 more elements

A direct match data flow machine, comprising:

at least one processor element capable of receiving an input token, said processor element comprising:
(a) a processor which provides control logic, data paths, and arithmetic operations;
(b) a direct match data flow memory, in a one-to-one relationship with said processor, said direct match data flow memory having a plurality of storage locations, each storage location associated with a unique physical address, whereupon said processor directs an input token having a target address and a parameter indicator of a parameter to an appropriately addressed storage location in said direct match data flow memory along one of said data paths, each storage location of said direct match data flow memory having a plurality of memory words of variable width, comprising:
(i) a first parameter memory word for storing said first parameter indicator;
(ii) a first flag memory word associated with said first parameter memory word, said first flag memory word having a state representative of the presence of said first parameter indicator in said first parameter memory word;
(iii) first recycle indicator memory word indicating that said first parameter is always available;
(iv) a second parameter memory word for storing a second parameter indicator;
(v) a second flag memory word associated with said second parameter memory word, said second flag memory word having a state representative of the presence of said second parameter indicator in said second parameter memory word;
(vi) a second recycle indicator memory word for storing an operation indicator of an operation to be performed upon said first and second parameters when said first and second flag memory words, respectively, indicate that said first and second parameters are available;
and (viii) a target memory word for storing a target address to which a successor output token from said processor is directed;
and when said state of said first and second flag memory words indicates that said first and second parameters are available, said first and second parameters, said opcode memory word, and said target address flow from said direct match data flow memory to said processor, and said processor performs said operation indicated by said opcode memory word on said parameters and said processor generates an output successor token having a target address and an output parameter indicator to be output along one of said data paths, said output successor token capable of being an input token for said processor element.

8 more elements

Dependencies are inferred from the claim text.

Direct match data flow memory for data driven computing

Life of this patent

Direct match data flow memory for data driven computing

Life of this patent

Abstract

Claims41