Run-length encoding decompression

• US 10,534,606 B2
• Filed: 09/28/2015
• Issued: 01/14/2020
• Est. Priority Date: 12/08/2011
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Brooks, Jeffrey S., Golla, Robert, Danysh, Albert, Chavan, Shasank, Agrawal, Prateek, Ewoldt, Andrew, Weaver, David
• Primary Examiner(s): Li, Aimee
• Assistant Examiner(s): Cromer, Andrew J
• Application Number:
  US14/867,929
• Publication Number:
  US 20160019064A1
• Time in Patent Office: 1,569 Days
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 9/30003 Arrangements for executing specific machine instructions
• CPC Class Codes: G06F 9/30018 Bit or string instructions
• 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/30038 using a mask
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

Approaches are described to improve database performance by implementing a RLE decompression function at a low level within a general-purpose processor or an external block. Specifically, embodiments of a hardware implementation of an instruction for RLE decompression are disclosed. The described approaches improve performance by supporting the RLE decompression function within a processor and/or external block. Specifically, a RLE decompression hardware implementation is disclosed that produces a 64-bit RLE decompression result, with an example embodiment performing the task in two pipelined execution stages with a throughput of one per cycle. According to embodiments, hardware organization of narrow-width shifters operating in parallel, controlled by computed shift counts, is used to perform the decompression. Because of the decreased time required to perform RLE decompression according to embodiments, the performance of tasks that use embodiments described herein for decompression of run-length encoded data is made more efficient.

Claims

1. A method comprising:

receiving an instruction to decompress a run-length-encoded (RLE) value;

wherein the RLE value comprises a plurality of bits;

wherein each bit, of the RLE value, corresponds to a corresponding run length of a plurality of run lengths; and

in response to receiving the instruction to decompress the RLE value, performing a set of actions during both of a first pipelined execution stage and a second pipelined execution stage;

wherein the first pipelined execution stage comprises;

replicating each bit, of the RLE value, a number of times indicated by the corresponding run length that corresponds to the bit, to produce a respective decompressed sub-value of a plurality of decompressed sub-values that are based on the RLE value; and

wherein at least one plurality of bits, from the RLE value, are replicated in parallel;

concatenating the decompressed sub-values, of the plurality of decompressed sub-values, in parallel based on the order of the bits within the RLE value to which the decompressed sub-values correspond, to produce two or more decompressed intermediate values;

wherein the second pipelined execution stage comprises concatenating the two or more decompressed intermediate values to produce a decompressed value;

storing the decompressed value as a result for the instruction to decompress the RLE value;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein

all of the decompressed sub-values, of the plurality of decompressed sub-values, have the same number of bits, respectively;

the method further comprises;

shifting zero or more bits out of one or more decompressed sub-values, of the plurality of decompressed sub-values, to produce one or more adjusted intermediate sub-values;

wherein a number of bits shifted out of each of the one or more adjusted intermediate sub-values is based, at least in part, on the corresponding run length that corresponds to the bit, of the RLE value, that is represented in the decompressed sub-value.

3. The method of claim 2, wherein:

each of the plurality of run lengths is represented as a biased value;

the method further comprises;

calculating a plurality of shift counts, one for each particular bit of the RLE value, based on the corresponding run length, of the plurality of run lengths, that corresponds to the particular bit, and

wherein each shift count, of the plurality of shift counts, corresponds to the decompressed sub-value that also corresponds to the corresponding bit of the RLE value; and

wherein each of the plurality of shift counts respectively represents a number of bits to be shifted out of the corresponding decompressed sub-value, of the plurality of decompressed sub-values.

4. The method of claim 3, wherein calculating a particular shift count, of the plurality of shift counts, comprises inverting the corresponding run length on which the particular shift count is based.

5. The method of claim 3, wherein the biased values, of the plurality of run lengths, are each represented by three bits.

6. The method of claim 3, further comprising:

respectively concatenating at least two adjusted intermediate sub-values with two or more decompressed sub-values, of the plurality of decompressed sub-values, to produce two or more composite replicated sub-values;

calculating a respective composite shift count, for each of the two or more composite replicated sub-values, based on the shift count for the respective decompressed sub-value included in the composite replicated sub-value;

shifting zero or more bits, from each of the two or more composite replicated sub-values, based on the shift count calculated for the respective composite replicated sub-value;

wherein said calculating the composite shift count is performed in parallel with said shifting the zero or more bits out of the two or more composite replicated sub-values.

7. The method of claim 6, wherein concatenating the decompressed sub-values to produce the two or more decompressed intermediate values comprises:

concatenating the two or more composite replicated sub-values together to produce the two or more decompressed intermediate values.

8. The method of claim 2, wherein shifting zero or more bits out of one or more decompressed sub-values comprises shifting, in parallel, zero or more bits out of two or more decompressed sub-values of the plurality of decompressed sub-values.

9. The method of claim 1, wherein the set of actions is performed using hardware that is implemented in one of:

a block that is external to one or more processors of the one or more computing devices;

or

one or more processors of the one or more computing devices.

10. The method of claim 1, wherein, in the decompressed value, the bits of the decompressed sub-values, of the plurality of decompressed sub-values, are concatenated without any intervening unused bits between the bits of the decompressed sub-values.

11. The method of claim 1, further comprising:

receiving an instruction to determine a length of the decompressed value;

in response to receiving the instruction to determine the length of the decompressed value;

calculating a plurality of shift counts, one for each particular bit of the RLE value, based on the corresponding run length, of the plurality of run lengths, that corresponds to the particular bit,

adding together the plurality of shift counts to produce a total shift count value, and

performing a 2'"'"'s complement on the total shift count value to produce a determined length value; and

returning, as a result for the instruction to determine the length of the decompressed value, the determined length value.

12. The method of claim 11, wherein:

the instruction to decompress the RLE value is a first instruction to decompress a first RLE value;

the decompressed value is a first decompressed value that is represented with a 64 bit-representation;

the determined length value indicates a length of less than 64 bits;

the 64 bit-representation includes one or more unused bits; and

the method further comprises;

receiving a second instruction to decompress a second RLE value;

in response to receiving the second instruction, performing the set of actions, based on information for the second RLE value, to produce a second decompressed value;

receiving one or more instructions to concatenate the first decompressed value and the second decompressed value based, at least in part, on the determined length value; and

in response to receiving the one or more instructions to concatenate the first decompressed value and the second decompressed value based, at least in part, on the determined length value, generating a concatenated value that includes both the first decompressed value and the second decompressed value without intervening unused bits.

13. The method of claim 1, wherein each of the first pipelined execution stage and the second pipelined execution stage has a throughput of one cycle.

14. One or more non-transitory computer-readable media storing one or more sequences of instructions, which, when executed by one or more processors, cause:

receiving an instruction to decompress a run-length-encoded (RLE) value;

wherein the RLE value comprises a plurality of bits;

wherein each bit, of the RLE value, corresponds to a corresponding run length of a plurality of run lengths; and

in response to receiving the instruction to decompress the RLE value, performing a set of actions during both of a first pipelined execution stage and a second pipelined execution stage;

wherein the first pipelined execution stage comprises;

replicating each bit, of the RLE value, a number of times indicated by the corresponding run length that corresponds to the bit, to produce a respective decompressed sub-value of a plurality of decompressed sub-values that are based on the RLE value; and

wherein at least one plurality of bits, from the RLE value, are replicated in parallel;

concatenating the decompressed sub-values, of the plurality of decompressed sub-values, in parallel based on the order of the bits within the RLE value to which the decompressed sub-values correspond, to produce two or more decompressed intermediate values;

wherein the second pipelined execution stage comprises concatenating the two or more decompressed intermediate values to produce a decompressed value;

storing the decompressed value as a result for the instruction to decompress the RLE value.

15. The one or more non-transitory computer-readable media of claim 14, wherein:

all of the decompressed sub-values, of the plurality of decompressed sub-values, have the same number of bits, respectively;

the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, cause;

shifting zero or more bits out of one or more decompressed sub-values, of the plurality of decompressed sub-values, to produce one or more adjusted intermediate sub-values;

wherein a number of bits shifted out of each of the one or more adjusted intermediate sub-values is based, at least in part, on the corresponding run length that corresponds to the bit, of the RLE value, that is represented in the decompressed sub-value.

16. The one or more non-transitory computer-readable media of claim 15, wherein:

each of the plurality of run lengths is represented as a biased value;

the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, cause;

calculating a plurality of shift counts, one for each particular bit of the RLE value, based on the corresponding run length, of the plurality of run lengths, that corresponds to the particular bit, and

wherein each shift count, of the plurality of shift counts, corresponds to the decompressed sub-value that also corresponds to the corresponding bit of the RLE value; and

wherein each of the plurality of shift counts respectively represents a number of bits to be shifted out of the corresponding decompressed sub-value, of the plurality of decompressed sub-values.

17. The one or more non-transitory computer-readable media of claim 16, wherein calculating a particular shift count, of the plurality of shift counts, comprises inverting the corresponding run length on which the particular shift count is based.

18. The one or more non-transitory computer-readable media of claim 15, wherein shifting zero or more bits out of one or more decompressed sub-values comprises shifting, in parallel, zero or more bits out of two or more decompressed sub-values of the plurality of decompressed sub-values.

19. The one or more non-transitory computer-readable media of claim 14, wherein the set of actions is performed using hardware that is implemented in one of:

one or more processors of the one or more computing devices;

or

a block that is external to one or more processors of the one or more computing devices.

20. The one or more non-transitory computer-readable media of claim 14, wherein the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, cause:

receiving an instruction to determine a length of the decompressed value;

in response to receiving the instruction to determine the length of the decompressed value;

calculating a plurality of shift counts, one for each particular bit of the RLE value, based on the corresponding run length, of the plurality of run lengths, that corresponds to the particular bit,

adding together the plurality of shift counts to produce a total shift count value, and

performing a 2'"'"'s complement on the total shift count value to produce a determined length value; and

returning, as a result for the instruction to determine the length of the decompressed value, the determined length value.

21. The one or more non-transitory computer-readable media of claim 20, wherein:

the instruction to decompress the RLE value is a first instruction to decompress a first RLE value;

the decompressed value is a first decompressed value that is represented with a 64 bit-representation;

the determined length value indicates a length of less than 64 bits;

the 64 bit-representation includes one or more unused bits; and

the one or more sequences of instructions further comprise instructions which, when executed by one or more processors, cause;

receiving a second instruction to decompress a second RLE value;

in response to receiving the second instruction, performing the set of actions, based on information for the second RLE value, to produce a second decompressed value;

receiving one or more instructions to concatenate the first decompressed value and the second decompressed value based, at least in part, on the determined length value; and

in response to receiving the one or more instructions to concatenate the first decompressed value and the second decompressed value based, at least in part, on the determined length value, generating a concatenated value that includes both the first decompressed value and the second decompressed value without intervening unused bits.

22. The one or more non-transitory computer-readable media of claim 14, wherein each of the first pipelined execution stage and the second pipelined execution stage has a throughput of one cycle.

23. A computing device comprising:

one or more processors;

one or more first hardware components configured to perform a first set of actions comprising a first pipelined execution stage for decompressing run-length encoded (RLE) values;

one or more second hardware components configured to perform a second set of actions comprising a second pipelined execution stage for decompressing RLE values; and

one or more computer-readable media configured to store decompressed values based on RLE values;

wherein the first set of actions comprises;

replicating each bit, of an RLE value that comprises a plurality of bits, a number of times indicated by a corresponding run length that corresponds to the bit, to produce a respective decompressed sub-value of a plurality of decompressed sub-values that are based on the RLE value, and

wherein at least one plurality of bits, from the RLE value, are replicated in parallel;

concatenating the decompressed sub-values, of the plurality of decompressed sub-values, in parallel based on the order of the bits within the RLE value to which the decompressed sub-values correspond, to produce two or more decompressed intermediate values;

wherein the second set of actions comprises;

concatenating the two or more decompressed intermediate values to produce a decompressed value; and

storing the decompressed value in the one or more computer-readable media.