Efficient hardware instructions for single instruction multiple data processors

• US 9,342,314 B2
• Filed: 09/10/2013
• Issued: 05/17/2016
• 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
• Primary Examiner(s): ABAD, FARLEY J
• Application Number:
  US14/023,265
• Publication Number:
  US 20140013078A1
• Time in Patent Office: 980 Days
• US Class Current: 1/1
• 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 configured to:

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

load each run-length value, in a vector of run-length values, into a corresponding subregister of a series of subregisters in a SIMD register that resides in the processor;

respond to one or more instructions by decompressing bits in the bit vector into a second register in the processor;

wherein bits in the bit vector are contiguous;

wherein run-length values within the vector of run-length values are contiguous;

wherein decompressing bits in the bit vector includes;

for one or more run-length values in the vector of run-length values in the series of subregisters, copying the corresponding bit in the bit vector in the first register into the second register according to the run-length value, such that copies of the corresponding bit are contiguously stored in the second register as indicated by the run-length value.

2. The processor of claim 1, wherein:

the first register is not wide enough to hold all decompressed bits in the bit vector; and

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

storing bits in the first register in memory, upon detecting that the SIMD register is full; and

continuing to copy bits from the bit vector in the second register into the first register.

3. The processor of claim 1, wherein the processor is further configured to respond to the one or more instructions by setting to zero all bits in the first register other than bits storing decompressed values.

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. A processor:

wherein each run-length value in a vector of run-length values represents how many bits each bit in a bit vector should be decompressed to, respectively;

wherein bits in the bit vector are contiguously stored in memory;

wherein values within the vector of run-length values are contiguously stored in memory;

wherein results are stored in memory;

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

copy a set of bits in the bit vector from memory into a first register; and

copy a particular number of run-length values from the vector of run-length values from memory into a series of subregisters in a SIMD register, wherein each run-length value is copied into a different subregister in the series of subregisters;

wherein each bit in the set of bits has a corresponding run-length value in a subregister in the series of subregisters;

decompress each bit, such that copies of each bit are contiguously-stored in a second register as is indicated by the corresponding run-length value in the subregister of the series of subregisters.

7. The processor of claim 6, wherein results are stored contiguously in memory.

8. The processor of claim 6, wherein memory is cache memory located on a chip that includes in the processor.

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

10. The processor of claim 9, wherein a same number of bits are decompressed each time the single instruction is received.

11. A method comprising:

loading a bit vector into a first register;

loading each run-length value, in a vector of run-length values, into a corresponding subregister of a series of subregisters in a SIMD register;

responding to one or more instructions by decompressing bits in the bit vector into a second register;

wherein bits in the bit vector are contiguous;

wherein run-length values within the vector of run-length values are contiguous;

wherein decompressing bits in the bit vector includes;

for one or more run-length values in the vector of run-length values in the series of subregisters, copying the corresponding bit in the bit vector in the first register into the second register according to the run-length value, such that copies of the corresponding bit are contiguously stored in the second register as indicated by the run-length value.

12. The method of claim 11, wherein:

the first register is not wide enough to hold all decompressed bits in the bit vector; and

the method further comprising responding to the one or more instructions by;

storing bits in the first register in memory, upon detecting that the SIMD register is full; and

continuing to copy bits from the bit vector in the second register into the first register.

13. The method of claim 11 further comprising responding to the one or more instructions by setting to zero all bits in the first register other than bits storing decompressed values.

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

15. The method of claim 14, wherein the single instruction is performed in one cycle by a processor.

16. A method:

wherein each run-length value in a vector of run-length values represents how many bits each bit in a bit vector should be decompressed to, respectively;

wherein bits in the bit vector are contiguously stored in memory;

wherein values within the vector of run-length values are contiguously stored in memory;

wherein results are stored in memory;

wherein the method comprises, in response to one or more instructions;

copying a set of bits in the bit vector from memory into a first register; and

copying a particular number of run-length values from the vector of run-length values from memory into a series of subregisters in a SIMD register, wherein each run-length value is copied into a different subregister in the series of subregisters;

wherein each bit in the set of bits has a corresponding run-length value in a subregister in the series of subregisters;

decompressing each bit, such that copies of each bit are contiguously-stored in a second register as is indicated by the corresponding run-length value in the subregister of the series of subregisters.

17. The method of claim 16, wherein results are stored contiguously in memory.

18. The method of claim 16, wherein memory is cache memory located on a chip that includes in a processor executing the method steps.

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

20. The method of claim 19, wherein a same number of bits are decompressed each time the single instruction is received.