Efficient handling of vector high-level language conditional constructs in a SIMD processor

• US 7,793,084 B1
• Filed: 05/20/2003
• Issued: 09/07/2010
• Est. Priority Date: 07/22/2002
• Status: Expired due to Fees

• Current Assignee: Cue Biotech Incorporated
• Original Assignee: Cue Biotech Incorporated
• Inventors: MIMAR, Tibet
• Primary Examiner(s): Chan, Eddie P
• Assistant Examiner(s): FAHERTY, COREY S
• Application Number:
  US10/441,336
• Time in Patent Office: 2,667 Days
• Field of Search: 712/2, 712/236
• US Class Current: 712/236
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX
• 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/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30094 Condition code generation, e.g. Carry, Zero flag
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]

Abstract

The present invention provides an efficient method to implement nested if-then-else conditional statements in a SIMD processor, which requires only one vector compare instruction for both if and else parts of the conditional construct. No stack and stack-handling instructions are needed for vector condition codes. Two condition code flag bits representing if and else parts of testing per element provide for nesting of multiple if-then-else. All SIMD instructions are conditional including the vector compare instruction, and this provides a method for aggregating multiple conditions in nested if-then-else statements. M full levels of if-then-else nesting requires (2^M−1) nodes or vector test instructions and 2^M+1 condition code flags per vector element. Also, capability to compare any element of first source vector register with any element of second source vector is provided.

Claims

1. An execution unit for use in a computer system for conditionally performing a vector operation defined in a computer instruction, the execution unit comprising:

first and second input vector registers for holding respective first and second source vector operands on which said vector operation defined in the instruction is to be carried out, wherein each of said first and second input vector registers holds a plurality of vector elements of a predetermined size, each vector element defining one of a plurality of vector element positions;

a vector condition flag register for storing a plurality of condition flags for each of said plurality of vector element positions, each element of said plurality of condition flags defining a true or false condition value;

means for loading said first and second input vector registers;

a plurality of operators associated respectively with said plurality of vector element positions for carrying out said vector operation on respective vector elements of said first source vector operand and said second source vector operand;

a vector compare unit for comparing said first and second source vector operands in accordance with a test field defined in the instruction, and generating a test condition flag for each of said plurality of vector element positions;

a vector condition code calculate logic that compounds said test condition flag with a prior generated condition flag of said vector condition flag register to generate a resultant condition flag for each of said plurality of vector element positions, said prior generated condition flag selected in accordance with a condition field defined in the instruction;

means to store said resultant condition flag into a destination condition flag of said vector condition flag register for each of said plurality of vector element positions, said destination condition flag selected in accordance with destination field defined in the instruction; and

means for storing the output of said vector operation to a destination vector register in accordance with said prior generated condition flag of each respective vector element of said vector condition flag register on a vector element-by-element basis.

2. The execution unit according to claim 1, wherein said vector condition code calculate logic generates a pair of condition code flags corresponding to IF and ELSE branches of a if-else comparison, and stores said pair of condition code flags into a destination flag pair of said vector condition flag register for each of said plurality of vector element positions.

3. The execution unit according to claim 1, wherein results of said vector operation is written to said destination vector register in accordance with a mask bit in addition to said prior generated condition flag for each of said plurality of vector element positions.

4. The execution unit according to claim 1, further including:

means for mapping said first source vector operands;

means for mapping said second source vector elements;

a control vector for controlling mapping of said first and second source vector operands;

said vector compare unit inputs are operably coupled to said mapped first source vector operands and said mapped second source vector operands; and

whereby said vector compare unit compares, for each of said plurality of vector element positions, respective elements of said mapped first source vector operands and said mapped second source vector operands, in accordance with said test field defined in the instruction.

5. The execution unit according to claim 4, wherein said mask bit is part of each element of said control vector register, and update of said destination condition flag is enabled when respective said mask bit is false.

6. The execution unit according to claim 4, wherein three instruction formats are supported in pairing elements of said first and second source vector operands:

respective said first and second source vector operands element-to-element format as default, said second source vector operand one-element broadcast format, and said first and second source vector operands any-element-to-any-element format requiring said control vector as third source vector operand.

7. The execution unit according to claim 1, wherein comparison tests defined by said test field include:

greater-than, greater-than-or-equal-to, less-than, less-than-or-equal-to, and equal.

8. The execution unit according to claim 1, wherein comparison tests defined by said test field include a delta test.

9. The execution unit according to claim 1, wherein one of said plurality of condition flags of said vector condition flag register is hardwired to always-true, and one of said plurality of condition flags of said vector condition flag register is hardwired to always-false for each of said plurality of vector element positions.

10. A method for a vector comparison of a first source vector and a second source vector, and providing a conditional vector operation, each vector comprising at least first and second vector elements, the method comprising:

storing said first source vector;

storing said second source vector;

comparing elements of said stored first source vector and said stored second source vector for a selected comparison test and calculating a test condition flag for each vector element position;

accessing stored condition values derived from the results of executing a prior instruction sequence and selecting a condition flag from a plurality of condition flags for each vector element position;

calculating a resultant condition flag by compounding said calculated test condition flag with said selected condition flag;

storing said resultant condition flag for said vector comparison into a selected destination condition flag of said plurality of condition flags; and

storing results of said conditional vector operation for arithmetic and logical vector operations to a destination vector in accordance to said selected condition flag value for each vector element position, said destination vector being the same size as said stored first source vector and said stored second source vector.

11. The method of claim 10, wherein calculating said resultant condition flag for both said calculated condition true and false cases of said vector comparison by compounding said calculated test condition flag with said selected condition flag, and inverse of said calculated test condition flag with said selected condition flag, respectively, and storing into two condition flags of said plurality of condition flags.

12. The method of claim 10, wherein output of said conditional vector operation is written to said destination vector in accordance with a mask bit and said selected condition flag.

13. The method of claim 10, further comprising:

storing a control vector;

selecting, in accordance with each vector element of said stored control vector, a respective one of the vector elements of said stored first source vector;

selecting, in accordance with each vector element of said stored control vector, a respective one of the vector elements of said stored second source vector;

means for performing said conditional vector operation or said vector comparison on said selected stored first source vector and said selected stored second source vector.

14. The method of claim 13, further comprising:

storing said mask bits as part of said stored control vector;

storing said resultant condition flag in accordance with said mask bit for each respective vector element position.

15. The method of claim 10, wherein said selected comparison tests include:

greater-than, greater-than-or-equal-to, less-than, less-than-or-equal-to, equal.

16. The method of claim 10, wherein said selected comparison tests include a delta test.

17. The method of claim 10, wherein one of the condition flags of said plurality of condition flags for each vector element position is always true, and one of the condition flags of said plurality of condition flags for each vector element position is always false.

18. An apparatus for a comparison test of first and second source vectors, and for performing nested vector conditional operations, the apparatus comprising:

a vector register file including a plurality of vector registers with a plurality of read data ports and at least one write data port, wherein said plurality of vector registers are accessed in parallel and substantially at the same time;

a condition flag vector for storing a plurality of condition flags for each respective vector element;

means for loading said plurality of vector registers of said vector register file with at least said first and second source vectors;

means for performing said comparison test and compounding results of said comparison test with a selected condition flag of said condition flag vector;

means for storing output of said vector comparison test into a destination condition flag of said condition flag vector for each vector element position;

a vector operation unit including plurality of computing elements coupled to said plurality of read data ports of said vector register file for performing arithmetic or logical operations on the vector elements in parallel; and

an enable logic coupled to write port of said vector register file for providing means for storing the output of said vector operation unit in a destination vector register in said vector register file on a vector element-by-element basis in accordance with said selected condition flag of said condition flag vector.

19. The apparatus of claim 18, wherein said comparison test calculates both IF and ELSE condition flag pair corresponding to if-else conditional construct and stores said condition flag pair into two said destination condition flags in said condition flag vector.

20. The apparatus of claim 18, wherein said enable logic operates in accordance with a mask bit for each vector element position in addition to said selected condition flag.

21. The apparatus of claim 18, further comprising:

at least one control vector register;

means for mapping first and second source vectors in accordance with said at least one control vector register values, and providing said mapped first source vector and said mapped second source vector as alternative inputs to said comparison test and said vector operation unit.

22. The apparatus of claim 18, wherein one of said plurality of condition flags is hard wired to always true for each respective element position.

23. The apparatus of claim 18, wherein list of possible said comparison tests include:

greater-than, greater-than-or-equal-to, less-than, less-than-or-equal-to, equal.

24. The apparatus of claim 18, wherein list of possible said comparison tests include a delta test.