Data flow machine for data driven computing

• US 5,465,368 A
• Filed: 07/24/1990
• Issued: 11/07/1995
• Est. Priority Date: 07/22/1988
• Status: Expired due to Fees

• Current Assignee: United States Department of Energy (Government of the United States of America)
• Original Assignee: United States Department of Energy (Government of the United States of America)
• Inventors: Grafe, Victor G., Davidson, George S.
• Primary Examiner(s): Shin, Christopher B.
• Application Number:
  US07/559,523
• Time in Patent Office: 1,932 Days
• Field of Search: 364/200, 364/900
• US Class Current: 712/27
• CPC Class Codes: G06F 9/4494 data driven

Abstract

A data flow computer which 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 but 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.

Claims

1. A data flow machine, comprising at least two processor elements capable of receiving an input data token and operatively interconnected to receive and transmit data tokens between them, each of said processor elements comprising:

(a) two processors operatively connected, each of said processors further comprising

control logic,

data paths operatively connecting at least one execution unit,

an input means connected to receive said input data token to a data flow memory in a one-to-one operative connection with said processor and deliver said input data token to said data flow memory, said input means of each of said processors further comprises a first input FIFO register, a second input FIFO register, and a third input FIFO register, said first input FIFO register operatively connected to receive an input data token from the data flow memory in the one-to-one operative connection with that processor, said second input FIFO register operatively connected to receive an input data token from the other processor of the same processor element, and said third input FIFO register operatively connected to receive an input data token from another processor element,

a flag checking and updating means,

a transmitting means and

an output means to output said data token, said output means connected to said execution unit and comprising a first output FIFO register, a second output FIFO register, and a third output FIFO register,

(b) said data flow memory having a plurality of storage locations, each storage location having an address and a plurality of storage areas further comprising;

a parameter storage area for storing at least one parameter indicator,

an operation storage area for storing an operation indicator of an operation to be performed on at least one of said parameter indicators,

a flag storage area having a state representative of the presence of parameter indicators required by said operation, and

an output target address storage area which provides an output target address to which said output data token is directed;

wherein said input means directs an input data token having a target address and a first parameter indicator to one of said storage locations identified by said target address, and in response thereto said flag checking and updating means checks the state of the flag in the flag storage area in the identified storage location to determine if other parameter indicators required by the operation in the identified storage location are present and further updates the state of the flag in the flag storage area in the identified storage location to indicate that said first parameter indicator is present, and in response thereto said transmitting means transmits said operation indicator and those parameter indicators that are present in said identified storage location to said execution unit wherein said operation is performed and a valid output data token is generated only if all parameter indicators required by the operation are present in the identified storage location, said first output FIFO register is operatively connected to transmit an output data token to the data flow memory in the one-to-one operative connection with that processor, said second output FIFO register is operatively connected to transmit an output data token to the other processor of the same processor element, and said third output FIFO register is operatively connected to transmit an output data token to another processor element.

2. A data flow machine comprised of at least two processing elements interconnected to receive input data tokens and transmit output data tokens between them, and each of said processing elements further comprises two processors wherein each of said processors comprises control logic and data paths operatively connecting at least one execution unit, an input means, a flag checking and updating means, a transmitting means, an output means, and wherein there is a data flow memory in a one-to-one relationship with each of said processors;

said input means of each of said processors further comprises a first input FIFO register, a second input FIFO register, and a third input FIFO register, said first input FIFO register operatively connected to receive an input data token from the dam flow memory in the one-to-one operative connection with that processor, said second input FIFO register operatively connected to receive an input data token from the other processor of the same processing element, and said third input FIFO register operatively connected to receive an input data token from another processing element; and

said output means of each of said processors further comprises a first output FIFO register, a second output FIFO register, and a third output FIFO register, said first output FIFO register operatively connected to transmit an output data token to the data flow memory in the one-to-one operative connection with that processor, said second output FIFO register operatively connected to transmit an output data token to the other processor of the same processing element, and said third output FIFO register operatively connected to transmit an output data token to another processing element;

each said data flow memory having a plurality of storage locations, each storage location having an address and a plurality of storage areas further comprising;

a parameter storage area having a first parameter indicator storage area for storing a first parameter indicator, and a second parameter indicator storage area for storing a second parameter indicator, and

an operation storage area for storing an operation indicator of an operation to be performed on one of said parameter indicators, and

a flag storage area further comprising a first flag storage area and a second flag storage area for storing a first flag and a second flag, respectively, each of said flags having a state representative of the presence of said first parameter indicator and a second data parameter indicator in said first and second parameter indicator storage areas, respectively;

a sticky tag storage area further comprising a first sticky tag and a second sticky tag, said first and second sticky tag having a state to indicate that said first parameter indicator and said second data parameter indicator is always present in said first and second parameter indicator storage areas, respectively;

an output target address storage area which provides an output target address to which an output data token is directed;

wherein said input means directs a first input data token having an input target address and a parameter indicator to one of said storage locations identified by said input target address, and in response thereto said flag checking and updating means checks the state of each flag and sticky tag in the identified storage location to determine if other parameter indicators required by the operation in the identified storage location are present and further updates the state of the flags in the flag storage area in the identified storage location to indicate the parameter indicator of said first input data token is now present in the identified storage location, and in response thereto said transmitting means transmits said operation indicator and those parameter indicators that are present in said identified storage location to said execution unit wherein said operation is performed and a valid output data token is generated only if all parameter indicators required by the operation are present in the identified storage location, and if all parameter indicators required by the operation are not present in the identified storage location, then said input means directs a second input data token having said target address and a second parameter indicator to said identified storage location, and said flag checking and updating means checks said flags and said sticky tags to determine that said parameter indicator of said first input data token and said second parameter indicator is now present in said identified storage location and said transmitting means transmits said operation indicator and said parameter indicator of said first input data token and second parameter indicator to said execution unit which performs said operation upon said parameter indicators and generates an output data token.

3. A method of performing data flow processing in a data flow machine, said data flow machine comprising at least one processor element, each of which processor element further comprises a processor having control logic and data paths operatively connecting at least one execution unit an input means, a flag checking and updating means, and a transmitting means, and a data flow memory in a one-to one relationship with said processor, comprising:

(a) inputting a first input token having an input address and a first parameter indicator to a storage location identified by the input address of the first input token in a data flow memory, said data flow memory having a plurality of addressable storage locations, each storage location having a plurality of memory words associated with two parameters;

(b) storing the first parameter indicator in a first parameter memory word of the storage location in the data flow memory;

(c) checking and updating a first parameter flag word in the storage location of the data flow memory to indicate that the first parameter indicator is available;

(d) inputting a second input token having the same input address as the first token and a second parameter indicator to said identified storage location in the data flow memory;

(e) storing the second parameter indicator in a second parameter memory word of the identified storage location in the data flow memory;

(f) triggering a second parameter flag word in the storage location of the data flow memory to indicate that the second parameter indicator is available;

(g) transmitting the first and second parameter indicators, an instruction stored in an opcode memory word of the storage location, and a successor target address stored in a target address memory word of the storage location to an execution unit of a processor;

(h) executing an operation indicated by the instruction using parameters indicated by the first and second parameter indicators in the execution unit of the processor;

(i) generating an output token comprised of a target address and a resultant parameter indicator which embodies a result of said operation;

(j) transmitting the output token to the target address along a data path in the processor;

(k) resetting the first and second parameter flag word in the storage location to indicate that the first and second parameters are no longer available in said storage location of said data flow memory.

4. The method of performing data flow processing, as in claim 3, further comprising:

presetting at least one sticky tag memory word in the said identified storage location in the data flow memory indicating that at least one parameter indicator is always available;

storing in one of said parameter memory words an address in a data flow memory where a value of said parameter indicator is located;

retrieving the value of said parameter indicator from the data flow memory as indicated by the address stored in said parameter memory word, and

when all parameter indicators required by said operation are available, process the data as in steps g-k of claim 3.