Tagged token data processing system with operand matching in activation frames

In a data processing system, a method, performed by the system, of matching operands of a single instruction, comprising the steps of:

• a) locating a first available operand of the instruction, checking a memory location for presence of another available operand and storing the first available operand of the instruction in the memory location where another operand is not present;
• b) altering a state of the memory location to reflect that an operand of the instruction is stored at the memory location;
• c) locating a second available operand of the instruction;
• d) checking the memory location for presence of the first available operand of the instruction;
• and
• e) reading the first available operand from the memory location and sending the operands to a processing means to execute the instruction.

A method of processing tokens in a data processing system having a pipeline of processing units, comprising the steps, performed by the pipeline, of:

• a) receiving a token from a token buffer into the pipeline;
• b) by means of a first stage of the pipeline, fetching an instruction from memory of the data processing system to operate on the token;
• c) in a second stage of the pipeline, performing operand matching on the token as indicated by the fetched instruction;
• d) in a third stage of the pipeline, performing an ALU operation specified by the fetched instruction;
• and
• e) in a fourth stage of the pipeline, forming a new token or tokens from results of the ALU operation and the fetched instruction.

A method of handling exceptions in a pipelined data processing system comprising the steps, performed by the system, of:

• a) storing activities in a register as they enter a pipeline;
• b) flagging an activity when an exception occurs;
• c) halting processing of the activity;
• d) freezing the value of the activity in the register so that its value may not be changed or replaced;
• e) replacing the activity with a noninterruptable exception activity that remedies the exception;
• f) processing the exception activity;
• g) continuing the processing of the activity.

A data processing system comprising

• a) a memory for storing instructions and for storing activation frames that are working areas in which operands are matched;
• b) a buffer for storing tokens that represent operands as the tokens wait to be processed;
• c) a processing pipeline in communication with the memory and the buffer for processing tokens stored in the buffer, comprising
• an instruction fetch stage for fetching instructions to manipulate the tokens in the pipeline;
• an operand matching stage for matching the operands responsive to the fetched instruction;
• an operation stage for performing operations specified by the fetched instruction;
• and
• a token formation stage for forming new tokens carrying results of the operations specified by the fetched instruction.

A tagged token data flow machine comprising:

• a processor pipeline which processes tokens and produces new tokens,
• a buffer for storing tokens to be processed in the processor pipeline,
• a plurality of registers for recording activities associated with the tokens in each stage of the pipeline such that, if an exception occurs, an activity that caused the exception is available, ad
• an exception handler for resolving exceptions that occur in the pipeline by examining the plurality of registers to find an activity for each exception that occurs.

A tagged token data flow machine comprising:

• a plurality of memory locations each having a value field and a state field and
• a programmed processor for responding to tokens to store data values in the memory locations and operate on the data values, the programmed processor comprising:
• means for reading a state field of a memory location;
• and
• means for processing a sticky matching rule by writing a value of a token into a value field of a memory location if a state field of the location indicates that another value is not present and by changing the state field of the location, the state field being changed to indicate that a replaceable value is present if the value of the token is not a constant and to indicate that a retained constant is present if the value of the token is a constant.

In a data flow processing system a method, performed by the system, comprising:

• providing tokens, each token comprising a frame pointer, an instruction pointer and a value, the instruction pointer pointing to an instruction which processes the values of tokens with identical frame pointers and identical instruction pointers;
• responsive to a token, addressing a storage location in memory identified by the instruction pointer within an activation frame identified by the frame pointer;
• and
• determining whether a value is stored in the addressed storage location, and
• if a value is stored, performing the operation determined by the instruction pointer on the stored value and the value of the token to create a new token, and
• if the value is not stored, storing the value of the token in the storage location.

In a data processing system comprising at least one data processor and memory, the memory having instructions and data stored therein, a method, performed by the system, comprising:

• generating tokens, each token identifying a frame pointer, which points to an activation frame of memory locations on which a block of instructions operates, and an instruction pointer;
• responsive to an instruction pointer of a token, determining whether an operand is stored in the activation frame to which the frame pointer points;
• and
• initiating an operation determined by the instruction pointer on the operands once all operands for the operation relative to the activation frame are available.