Method and apparatus for nested instruction looping using implicit predicates

• US 7,945,768 B2
• Filed: 06/05/2008
• Issued: 05/17/2011
• Est. Priority Date: 06/05/2008
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola Mobility, Inc. (Lenovo Group Ltd.)
• Inventors: Essick, Raymond B. IV, Moat, Kent D., Schuette, Michael A.
• Primary Examiner(s): PETRANEK, JACOB ANDREW
• Application Number:
  US12/133,885
• Publication Number:
  US 20090307472A1
• Time in Patent Office: 1,076 Days
• Field of Search: 712/241
• US Class Current: 712/241
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/325 for loops, e.g. loop detection or loop counter

Abstract

A method and apparatus for executing a nested program loop on a vector processor, the loop comprising outer-pre, inner and outer-post portions. An input stream unit of the vector processor provides a data value to a data path and sets an associated data validity tag to ‘valid’ once per outer loop iteration, as indicated by an inner counter of the input stream unit. The tag is set to ‘invalid’ in other iterations. Functional units of the vector processor operate on data values in the data path, each functional unit producing a valid result if the data validity tags associated with inputs data values are set to ‘valid’. An output stream unit of the vector processor sinks a data value from the data path once per outer loop iteration if an associated data validity tag indicates that the data value is valid.

Claims

1. A vector processor for executing a nested program loop having an inner loop and an outer loop, the vector processor comprising:

a first input stream unit comprising a fetch unit, a logic circuit and a first inner counter, the first input stream unit being configured to fetch a data value once per outer loop iteration of the nested program loop, as indicated by the first inner counter and being further configured to output, to a data path, the data value and a data validity tag associated with the data value, the data validity tag indicating that the data value is valid, and the first input stream unit being configured to set the data validity tag associated with the data value to indicate that the data value is invalid at other iterations of the inner loop;

a plurality of functional units, each functional unit being configured to operate on input data values in the data path and produce, as output, a data value and an associated data validity tag, wherein the data validity tag is set to indicate that the output data value is valid if all of the inputs are valid; and

a first output stream unit configured to receive a data value and an associated data validity tag from the data path, the first output stream unit comprising a store unit, a logic circuit and a second inner counter,

wherein, once per outer loop iteration of the nested program loop, as indicated by the second inner counter, the first output stream unit sinks a data value if it is valid, as indicated by the associated data validity tag, and

wherein, at other inner loop iterations, or if the data validity tag indicates that the data value is invalid, the first output stream unit does not sink the data value;

wherein the data path comprises an interconnect switch configured to couple between the plurality of functional units, the first input stream unit and the first output stream unit.

2. A vector processor in accordance with claim 1, further comprising a data latch configured to store a data value in a memory and to output the stored data value to the data path, wherein the stored data value is replaced by an input data value only if the input data value is valid.

3. A vector processor in accordance with claim 2, wherein the data latch further comprises a counter that is set when a data value is stored in the memory and is updated when a data value is output and wherein the data latch is configured to output a data validity tag to indicate that the output data value is invalid if the counter has expired.

4. A vector processor in accordance with claim 2, wherein the data latch is configured to pass a data value from an outer portion of the nested program loop to an inner portion of the nested program loop.

5. A vector processor in accordance with claim 1, wherein the first input stream unit and the first output stream unit are configured to execute instructions in an outer portion of the nested program loop.

6. A vector processor in accordance with claim 1, wherein the first input stream unit further comprises an outer counter configured to count outer iterations of the nested program loop and wherein the output data validity tag is set to indicate that the output data value is invalid if the outer counter has expired.

7. A vector processor in accordance with claim 1, wherein the first output stream unit further comprises an outer counter that counts outer iterations of the nested program loop and wherein the first output stream unit is configured such that a data value is not sunk if the outer counter has expired.

8. A vector processor in accordance with claim 1, wherein the first input stream unit is configured to provide output data values to a plurality of data paths of an unrolled loop, and is further configured such that on a last iteration of the unrolled loop, the first input stream unit provides M outputs data values, where M is a number of inner iterations remaining as determined from the first inner counter.

9. A vector processor in accordance with claim 1, further comprising a second input stream unit configured to load a data value once per iteration of the inner loop and to output, to a data path, the data value and a data validity tag associated with the data value, the data validity tag indicating that the data value is valid.

10. A method of executing a nested program loop on a vector processor, the nested loop comprising an outer-pre portion, an inner portion and an outer-post portion, the method comprising:

providing a data value to a data path and setting an associated data validity tag to ‘

valid’

once per outer loop iteration, as indicated by an inner counter;

setting the associated data validity tag to ‘

invalid’

if the inner counter does not indicate a start of an inner loop;

performing functional operations on data values in the data path, each functional operation producing a valid result if the data validity tags associated with inputs data values are set to ‘

valid’

; and

sinking a data value from the data path once per outer loop iteration, as indicated by an inner counter, if an associated data validity tag indicates that the data value is valid.

11. A method in accordance with claim 10, wherein the nested program loop is executed on K parallel data paths, where K is greater than one, the method further comprising:

loading data values to L data paths of the K parallel data paths, where L is the minimum of K and the number of inner iterations remaining, as indicated by the inner counter.

12. A method in accordance with claim 11, further comprising, at each inner iteration of the nested loop:

tagging the data values loaded to the L data paths as valid;

tagging data values loaded to the other K-L data paths as invalid if K is greater than L; and

executing the K parallel data paths.

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

storing a data value from an outer portion of the nested program loop in a data latch if a data validity tag associated with the data value indicates that the data value is valid;

setting the data validity tag associated with the stored data value to indicate that the stored data value is valid; and

providing the stored data value and the associated data validity tag to the inner portion of the nested program loop.

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

setting the data validity tag associated with the stored data value to indicate that the stored data value is invalid when the inner counter indicates that the inner portion of the nested program loop is completed.

15. A method for providing a stream of data values to a data path of a vector processor configured to execute a nested program loop, the method comprising:

at each inner iteration of the nested loop;

updating an inner counter;

if the inner counter has a specified value;

retrieving a data value from a data source;

providing the data value to the data path; and

setting a data validity tag associated with the data value to indicate that the data value is valid;

otherwise, if the inner loop counter does not have the specified value;

setting the data validity tag associated with the data value to indicate that the data value is invalid; and

providing the data value and the associated data validity tag to the data path.

16. A method in accordance with claim 15, wherein the vector processor has K parallel data paths, where K is greater than one, the method further comprising:

at each inner iteration of the nested loop;

retrieving L data values from the data source, where L is the minimum of K and the number of inner iterations remaining, as indicated by the inner counter; and

providing the L data values to L data paths of the K parallel data paths.

17. A method in accordance with claim 16, further comprising, at each inner iteration of the nested loop:

tagging the data values provided to the L data paths as valid;

tagging data values loaded to the other K-L data paths as invalid if K is greater than L; and

executing the K parallel data paths.

18. A method in accordance with claim 15, wherein the data path includes a data latch, the method further comprising:

at each inner iteration of the nested loop;

providing an input data value and an associated data validity tag to the data latch;

the data latch updating a stored data value with the input data value if the data validity tag of the input data value indicates that the input data value is valid; and

the data latch providing the stored data value to the data path.