Efficient hardware instructions for single instruction multiple data processors: fast fixed-length value compression

Patent metadata

Field	Value
Publication number	US-11113054-B2
Application number	US-201615211418-A
Country	US
Kind code	B2
Filing date	Jul 15, 2016
Priority date	Sep 10, 2013
Publication date	Sep 7, 2021
Grant date	Sep 7, 2021

Abstract

Methods and apparatuses for determining set-membership using Single Instruction Multiple Data (“SIMD”) architecture are presented herein. Specifically, methods and apparatuses are discussed for compressing or packing, in parallel, multiple fixed-length values into a stream of multiple variable-length values using SIMD architecture.

First claim

What is claimed is:

1. One or more non-transitory, computer-readable media storing one or more instructions that, when executed by one or more processors, cause producing a vector of variable-length values from a vector of fixed-length values;
wherein a first register stores a plurality of fixed-length values from the vector of fixed-length values, wherein each fixed-length value in the vector of fixed-length values is a variable-length value that has been padded, as needed, to achieve a particular fixed length,
wherein a series of single instruction multiple data (SIMD) subregisters of a second register stores a plurality of length values from a vector of lengths, wherein each fixed-length value in the vector of fixed-length values corresponds to a length value in the vector of lengths, and wherein each length value in the vector of lengths indicates an unpadded length of a corresponding fixed-length value in the vector of fixed-length values;
wherein the one or more instructions, when executed by the one or more processors, cause:
storing, in a third register, the plurality of fixed-length values into the vector of variable-length values, wherein storing the vector of variable-length values in the third register is based on the vector of lengths, wherein each variable-length value in the vector of variable-length values is unpadded, and wherein a pointer specifies a memory address of the vector of variable length values stored in the third register;
determining, based on the vector of lengths, a particular key in an offset lookup table;
determining that a particular offset is indexed in the offset lookup table by the particular key;
updating the pointer based on the particular offset.

2. The one or more non-transitory, computer-readable media of claim 1 , wherein each length value in the vector of lengths indicates an unpadded length by indicating a minimum number of bytes needed to represent the fixed-length value to which said each length value corresponds.

3. The one or more non-transitory, computer-readable media of claim 1 , wherein a first length in the vector of lengths is different than a second length in the vector of lengths.

4. The one or more non-transitory, computer-readable media of claim 1 , wherein the one or more instructions, when executed by the one or more processors, cause:
generating a scatter-mask based on the vector of lengths;
storing, in a series of SIMD subregisters of a fourth register, the scatter-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the scatter-mask stored in the fourth register.

5. The one or more non-transitory, computer-readable media of claim 1 , wherein a scatter-mask lookup table stores a plurality of scatter-masks, wherein each scatter-mask in the scatter-mask lookup table is indexed by a unique key;
wherein the one or more instructions, when executed by the one or more processors, cause:
determining, based on the vector of lengths, a particular key in the scatter-mask lookup table;
determining that a particular scatter-mask is indexed by the particular key;
storing, in a series of SIMD subregisters of a fourth register, the particular scatter-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the particular scatter-mask stored in the fourth register.

6. The one or more non-transitory, computer-readable media of claim 1 , wherein the one or more instructions, when executed by the one or more processors, cause:
generating a shuffle-mask based on the vector of lengths;
storing, in a series of SIMD subregisters of a fourth register, the shuffle-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the shuffle-mask stored in the fourth register.

7. The one or more non-transitory, computer-readable media of claim 1 , wherein a shuffle-mask lookup table stores a plurality of shuffle-masks, wherein each shuffle-mask in the shuffle-mask lookup table is indexed by a unique key;
wherein the one or more instructions, when executed by the one or more processors cause:
determining, based on the vector of lengths, a particular key in the shuffle-mask lookup table;
determining that a particular shuffle-mask is indexed by the particular key;
storing, in a series of SIMD subregisters of a fourth register, the particular shuffle-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the particular shuffle-mask stored in the fourth register.

8. A method for producing a vector of variable-length values from a vector of fixed-length values;
wherein a first register stores a plurality of fixed-length values from the vector of fixed-length values, wherein each fixed-length value in the vector of fixed-length values is a variable-length value that has been padded, as needed, to achieve a particular fixed length,
wherein a series of single instruction multiple data (SIMD) subregisters of a second register stores a plurality of length values from a vector of lengths, wherein each fixed-length value in the vector of fixed-length values corresponds to a length value in the vector of lengths, and wherein each length value in the vector of lengths indicates an unpadded length of a corresponding fixed-length value in the vector of fixed-length values;
the method comprising:
storing, in a third register, the plurality of fixed-length values into the vector of variable-length values, wherein storing the vector of variable-length values in the third register is based on the vector of lengths, wherein each variable-length value in the vector of variable-length values is unpadded, and wherein a pointer specifies a memory address of the vector of variable length values stored in the third register;
determining, based on the vector of lengths, a particular key in an offset lookup table;
determining that a particular offset is indexed in the offset lookup table by the particular key;
updating the pointer based on the particular offset.

9. The method of claim 8 , wherein each length value in the vector of lengths indicates an unpadded length by indicating a minimum number of bytes needed to represent the fixed-length value to which said each length value corresponds.

10. The method of claim 8 , wherein a first length in the vector of lengths is different than a second length in the vector of lengths.

11. The method of claim 8 , the method further comprising:
generating a scatter-mask based on the vector of lengths;
storing, in a series of SIMD subregisters of a fourth register, the scatter-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the scatter-mask stored in the fourth register.

12. The method of claim 8 , wherein a scatter-mask lookup table stores a plurality of scatter-masks, wherein each scatter-mask in the scatter-mask lookup table is indexed by a unique key;
wherein the method further comprising:
determining, based on the vector of lengths, a particular key in the scatter-mask lookup table;
determining that a particular scatter-mask is indexed by the particular key;
storing, in a series of SIMD subregisters of a fourth register, the particular scatter-mask; and
storing, in the third register, the plurality of fixed-length values into the vector of variable-length values based on the particular scatter-mask stored in the fourth register.

13. The method of claim 8 , wherein the method further compr

Assignees

• Oracle Int Corp

Inventors

• Chavan Shasank K
• Watanaprakornkul Phumpong
• Chen Victor

Classifications

• G06F9/30038

  using a mask · CPC title

• G06F9/30018

  Bit or string instructions · CPC title

• G06F9/30036 Primary

  Instructions to perform operations on packed data, e.g. vector, tile or matrix operations · CPC title

• G06F15/8053

  Vector processors · CPC title

• G06F9/30032

  Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE · CPC title