Efficient hardware instructions for processing bit vectors for single instruction multiple data processors

• US 9,697,174 B2
• Filed: 09/10/2013
• Issued: 07/04/2017
• Est. Priority Date: 12/08/2011
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Patthak, Anindya C., Gleeson, Michael J., Holloway, Allison L., Ganesh, Amit, Chavan, Shasank K., Marwah, Vineet, Kamp, Jesse, Macnicol, Roger
• Primary Examiner(s): Giroux, George
• Application Number:
  US14/023,249
• Publication Number:
  US 20140013077A1
• Time in Patent Office: 1,393 Days
• Field of Search: None
• CPC Class Codes: G06F 15/8007 single instruction multiple data [SIMD] multiprocessors
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations

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 is configured to, in response to one or more instructions:

load a bit vector into a first register that resides in the processor;

starting at a location in the first register, search the bit vector in the first register for a first set of bits that are set to one;

for each bit in the first set of bits, store a corresponding index value, of one or more of index values, in a SIMD register in the processor;

wherein the SIMD register includes a series of subregisters;

wherein, within the SIMD register, each corresponding index value is stored in a separate subregister of the series of subregisters;

wherein, within the SIMD register, each index value represents a position, within the bit vector, of a corresponding bit that is set to one; and

wherein bits in the bit vector are contiguous.

2. The processor of claim 1, wherein:

the SIMD register is not wide enough to hold all of the one or more index values; and

the processor is further configured to, in response to the one or more instructions;

detect that the SIMD register is full, and in response;

store each index in the SIMD register in memory;

store an address in a third register to point to a byte in memory at which to resume searching the bit vector; and

store an offset in a fourth register to indicate a bit in the byte at which to resume searching the bit vector.

3. The processor of claim 2, the processor continues to store index values in the SIMD register in response to receiving at least one subsequent instruction.

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

5. The processor of claim 4, wherein the single instruction is performed in one cycle.

6. The processor of claim 1, wherein searching the bit vector comprises searching the bit vector until an index is stored in each subregister in the SIMD register.

7. The processor of claim 1, wherein the processor is configured to:

store a value in a third register that resides in the processor, wherein the value is zero; and

increment the value stored in the third register for each index stored in the SIMD register.

8. The processor of claim 1, wherein the one or more instructions designate how many bytes to use for each subregister of the series of subregisters.

9. A processor that, within the processor, gathers one or more bits from a bit vector into a series of subregisters in a SIMD register:

wherein bits in the bit vector are contiguous;

wherein each index value in a vector of index values represents a position of a corresponding bit in the bit vector;

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

loading each bit, indexed by the vector of index values, into a separate subregister of the series of subregisters.

10. The processor of claim 9, wherein the processor is further configured to respond to the one or more instructions by sign-extending each bit loaded in each subregister, respectively.

11. The processor of claim 9, wherein the processor is further configured to respond to the one or more instructions by applying a mask to each subregister each bit was loaded into.

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

13. The processor of claim 12, wherein the single instruction is performed in one cycle.

14. A method comprising, in response to one or more instructions:

loading a bit vector into a first register;

starting at a location in the first registers, search the bit vector in the first register for a first set of bits that are set to one;

for each bit in the first set of bits, storing a corresponding index value, of one or more index values, in a SIMD register;

wherein the SIMD register includes a series of subregisters;

wherein, within the SIMD register, each corresponding index value is stored in a separate subregister of the series of subregisters;

wherein, within the SIMD register, each index value represents a position, within the bit vector, of a corresponding bit that is set to one;

wherein bits in the bit vector are contiguous.

15. The method of claim 14, wherein the SIMD register is not wide enough to hold all of the one or more index values;

and the method further comprises;

detecting that the SIMD register is full and in response;

storing each index in the SIMD register in memory;

storing an address in a third register to point to a byte in memory at which to resume searching the bit vector; and

storing an offset in a fourth register to indicate a bit in the byte at which to resume searching the bit vector.

16. The method of claim 15, continuing to store index values in the SIMD register in response to receiving at least one subsequent instruction.

17. The method of claim 14, wherein the one or more instructions are a single instruction.

18. The method of claim 17, wherein the method is performed by a processor in one cycle.

19. The method of claim 14, wherein searching the bit vector comprises searching the bit vector until an index is stored in each subregister in the SIMD register.

20. The method of claim 14 further comprising:

storing a value in a third register, wherein the value is zero; and

incrementing the value stored in the third register for each index stored in the SIMD register.

21. The method of claim 14, wherein the one or more instructions designate how many bytes to use for each subregister of the series of subregisters.

22. A method for a processor gathering one or more bits from a bit vector into a series of subregisters in a SIMD register comprising:

loading each bit, indexed by a vector of index values, into a separate subregister of the series of subregisters;

wherein bits in the bit vector are contiguous;

wherein each index value in the vector of index values represents a position of a corresponding bit in the bit vector.

23. The method of claim 22, wherein the processor is further configured to respond by sign-extending each bit loaded in each subregister, respectively.

24. The method of claim 22, wherein the processor is further configured to respond by applying a mask to each subregister each bit was loaded into.

25. The method of claim 22, wherein the processor is configured to perform the steps in response to receiving a single instruction.

26. The method of claim 25, wherein the single instruction is performed in one cycle.