EFFICIENT HARDWARE INSTRUCTIONS FOR SINGLE INSTRUCTION MULTIPLE DATA PROCESSORS

• US 20140013078A1
• Filed: 09/10/2013
• Published: 01/09/2014
• Est. Priority Date: 12/08/2011
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ganesh, Amit, Chavan, Shasank K., Marwah, Vineet, Kamp, Jesse, Patthak, Anindya C., Gleeson, Michael J., Holloway, Allison L., Macnicol, Roger
• Granted Patent: US 9,342,314 B2
• Time in Patent Office: Days
• US Class Current: 712/22
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 9/30018 Bit or string instructions
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• 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/30109 having multiple operands in a single register
• CPC Class Codes: G06F 9/30112 comprising data of variable length
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3867 using instruction pipelines
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]

Abstract

A method and apparatus for efficiently processing data in various formats in a single instruction multiple data (“SIMD”) architecture is presented. Specifically, a method to unpack a fixed-width bit values in a bit stream to a fixed width byte stream in a SIMD architecture is presented. A method to unpack variable-length byte packed values in a byte stream in a SIMD architecture is presented. A method to decompress a run length encoded compressed bit-vector in a SIMD architecture is presented. A method to return the offset of each bit set to one in a bit-vector in a SIMD architecture is presented. A method to fetch bits from a bit-vector at specified offsets relative to a base in a SIMD architecture is presented. A method to compare values stored in two SIMD registers is presented.

Claims

1. A processor that stores, in a bit vector within the processor, results of a comparison between values in a first set of SIMD subregisters and values in a corresponding second set of SIMD subregisters:

wherein the first set of SIMD subregisters are contiguous in a first SIMD register;

wherein the second set of SIMD subregisters are contiguous in a second SIMD register;

wherein the processor is configured to respond to one or more instructions by;

setting a bit in the bit vector to “

1”

for each subregister, in the first set of SIMD subregisters, that stores a value that satisfies a comparative operator with respect to the value stored in a corresponding subregister, of the second set of SIMD subregisters.

2. The processor of claim 1, wherein the processor is further configured to respond to the one or more instructions by setting a bit in the bit vector to “

0”

for each subregister, in the first set of SIMD subregisters, that stores a value that does not satisfy the comparative operator with respect to the value stored in the corresponding subregister, of the second set of SIMD subregisters.

3. The processor of claim 1, wherein the processor is further configured to respond to the one or more instructions by, before setting any bits in the bit vector to “

1”

in response to the one or more instructions, clearing all bits in the bit vector.

4. The processor of claim 1, wherein the processor is further configured to respond to the one or more instructions by shifting the bit vector by a particular number of bits.

5. The processor of claim 1, wherein the comparative operator is an equals operator.

6. The processor of claim 1, wherein the bit vector is stored in a SIMD register.

7. The processor of claim 1, wherein the bit vector is stored in a SIMD subregister.

8. The processor of claim 1, wherein the bit vector is stored in cache memory located on a chip that includes in the processor.

9. The processor of claim 1, wherein the one or more instructions are a single instruction.

10. The processor of claim 9, wherein the single instruction is performed in one cycle.

11. A method comprising:

storing results of a comparison between values in a first set of SIMD subregisters to values in a second set of SIMD subregisters in a bit vector;

wherein the first set of SIMD subregisters are contiguous in a first SIMD register;

wherein the second set of SIMD subregisters are contiguous in a second SIMD register;

wherein storing results comprises;

setting a bit in the bit vector to “

1”

for each subregister with a value stored in the first set of SIMD subregisters that satisfies a comparative operator with the value in a corresponding subregister in the second set of SIMD subregisters.

12. The method of claim 11, further comprising setting a bit in the bit vector to “

0”

for each subregister with a value stored in the first set of SIMD subregisters that does not match the value in the corresponding subregister in the second set of SIMD subregisters.

13. The processor of claim 11, wherein prior to setting bits, clearing bits in the bit vector.

14. The processor of claim 11, further comprising shifting the bit vector by a particular number of bits.

15. The processor of claim 11, wherein the comparative operator is an equals operator.

16. The processor of claim 11, wherein the bit vector is stored in a SIMD register.

17. The processor of claim 11, wherein the bit vector is stored in a SIMD subregister.

18. The processor of claim 11, wherein the bit vector is stored in cache memory located on a chip that includes in a processor.

19. The processor of claim 11, wherein the method is performed in response to receiving a single instruction.

20. The processor of claim 19, wherein the single instruction is performed in one cycle on a processor.