Method and apparatus for elimination of prolog and epilog instructions in a vector processor using data validity tags and sink counters

• US 7,415,601 B2
• Filed: 08/29/2003
• Issued: 08/19/2008
• Est. Priority Date: 06/28/2002
• Status: Expired due to Fees

• Current Assignee: Motorola Mobility LLC (Lenovo Group Ltd.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Essick, Raymond B. IV, Moat, Kent D., May, Philip E., Norris, James M., Lucas, Brian G.
• Primary Examiner(s): DOLLINGER, TONIA LYNN MEONSKE
• Application Number:
  US10/652,135
• Publication Number:
  US 20040128473A1
• Time in Patent Office: 1,817 Days
• Field of Search: 712/233, 712216-218, 712/226, 711/152
• US Class Current: 712/233
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30105 Register structure
• CPC Class Codes: G06F 9/325 for loops, e.g. loop detection or loop counter
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/38585 with result invalidation, e.g. nullification
• CPC Class Codes: G06F 9/3889 controlled by multiple instructions, e.g. MIMD, decoupled access or execute

Abstract

A method and apparatus for the elimination of prolog and epilog instructions in a vector processor. To eliminate the prolog, a functional unit of the vector processor has at least one input for receiving an input data value tagged with a data validity tag and an output for outputting an intermediate result tagged with a data validity tag. The data validity tags indicate the validity of the data. Before a loop is executed, the data validity tags are set to indicate that the associated data values are invalid. During execution of the loop body a functional unit checks the validity of input data. If all of the input data values are valid the functional operation is performed, the corresponding data validity tag set to indicate that the result is valid. If any of the input data values is invalid, the data validity tag of the result is set to indicate that the result is invalid. To eliminate the epilog, an iteration counter is associated with each sink unit of the vector processor. When a specified number of data values have been produced by a particular sink, no more data values are produced by that sink. The instructions for the pipelined loop body may be repeated, without alteration, to eliminate prolog and epilog instructions.

Claims

1. A method for executing, on a processor, a pipelined program loop having a loop body but no separately coded prolog instructions for priming the pipeline, the processor comprising a plurality of functional units coupled through an interconnection switch and controlled by a controller, each functional unit of the plurality of functional units having at least one input for receiving an input data value and an associated input data validity tag, the method comprising:

executing the loop body for a plurality of iterations without executing any separately programmed prolog instruction for priming the pipeline; and

at each iteration of the plurality of iterations;

determining if the input data values of a functional unit of the plurality of functional units are valid by checking the associated input data validity tags,

executing the iteration whether or not the input data values are valid, and

setting an output data validity tag to indicate that a resulting output data from the functional unit is invalid if any of the input data values to the functional unit is invalid.

2. A method in accordance with claim 1, wherein a functional unit of the plurality of functional units includes a result register for storing an intermediate result and an associated output data validity tag, the method further comprising:

at each iteration of the plurality of iterations;

if all of the input data values are valid, performing a functional operation on the input data values, storing the result of the functional operation in the result register and setting the associated output data validity tag to indicate that the intermediate result is valid.

3. A method in accordance with claim 2, further comprising initializing an output data validity tag in the result register of each of the plurality of functional units to indicate that the associated intermediate result is invalid.

4. A method in accordance with claim 3, further comprising:

storing output data values only if the associated output data validity tag indicates that the data is valid.

5. A method in accordance with claim 3, wherein the processor further comprises at least one data source unit, each with an associated source iteration counter, the method further comprising:

initializing each source iteration counter; and

at each iteration of the specified number of iterations for which a data value is to be read by a data source unit;

determining from the source iteration counter associated with the data source unit if all data values have been retrieved from memory;

if not all data values have been retrieved from memory, adjusting the source iteration counter, retrieving a data value from a data memory and setting the associated data validity tag to indicate that the result is valid; and

if all data values have been retrieved from memory, setting the output data validity tag to indicate that the result is invalid.

6. A method in accordance with claim 5, further comprising each data source unit signaling the controller when the associated source iteration counter indicates that all data values have been retrieved from memory.

7. A method in accordance with claim 3, wherein the pipelined program loop has no separately coded epilog instructions for draining the pipeline and the processor further comprises at least one data sink, each data sink being associated with a sink iteration counter and operable to receive an output data value and an associated output data validity tag from the interconnection switch, the method further comprising:

initializing the sink iteration counter of each data sink; and

at each iteration of the specified number of iterations;

determining the validity of the output data from the associated output data validity tag;

if the output data is valid;

determining from the sink iteration counter if all data values have been committed to memory;

adjusting the sink iteration counter associated with the data sink unit if not all data values have been committed to memory;

committing the output data value to memory if not all data values have been committed to memory; and

signaling the controller if all data values have been committed to memory, and

if the output data is invalid;

leaving the sink iteration counter unchanged.

8. A method for executing, on a processor, a pipelined program loop having a loop body but no separately coded epilog instructions for draining the pipeline comprising a plurality of functional units and at least one data sink coupled through an interconnection switch and controlled by a controller, each data sink being associated with a sink iteration counter, the method comprising:

initializing each sink iteration counter;

executing the loop body for a specified number of iterations without executing any separately programmed epilog instruction for draining the pipeline; and

at each iteration of the specified number of iterations for which a data value is to be sunk by a data sink unit;

determining if the sink iteration counter of the data sink unit indicates that all data values have been committed to memory, and

executing the iteration without committing the data value to memory if the sink iteration counter indicates that all data values have been committed to memory.

9. A method in accordance with claim 8, further comprising committing the data value to memory if not all data values have been committed to memory.

10. A method in accordance with claim 8, further comprising adjusting the sink iteration counter associated with the data sink unit if not all data values have been committed to memory.

11. A method as in claim 8, further comprising each data sink unit signaling the controller when the associated sink iteration counter indicates that all data values have been committed to memory.

12. A method as in claim 11, further comprising terminating the execution of the pipelined program loop after all data sink units have signaled to the controller that all their data values have been committed to memory.

13. A method for reducing the number of instructions in a program for controlling a computational pipeline of a processor, the method comprising:

implementing instructions for priming the pipeline as one or more iterations of the loop body;

associating each data value in the pipeline with a data validity tag;

initializing data validity tags to indicate that associated data values are invalid; and

during execution of the loop body;

setting data validity tags to indicate that an associated data value is valid if it is the result of an operation on all valid data; and

setting data validity tags to indicate that an associated data value is invalid if it is the result of an operation on any invalid data.

14. A method in accordance with claim 13, further comprising implementing control words for draining the pipeline as one or more iterations of the loop body.

15. A method in accordance with claim 13, further comprising:

during execution of the loop body;

setting data validity tags to indicate that an associated data value is invalid if an associated source counter has expired.

16. A method in accordance with claim 13, further comprising:

during execution of the loop body;

sinking a data value to a data sink unless an associated data validity tag indicates that the data value is invalid.

17. A method in accordance with claim 13, further comprising:

during execution of the loop body;

sinking a data value to a data sink unless an associated sink counter has expired.