Data compression and decompression using SIMD instructions

Patent metadata

Field	Value
Publication number	US-9274802-B2
Application number	US-201313747342-A
Country	US
Kind code	B2
Filing date	Jan 22, 2013
Priority date	Jan 22, 2013
Publication date	Mar 1, 2016
Grant date	Mar 1, 2016

Abstract

Compression and decompression of numerical data utilizing single instruction, multiple data (SIMD) instructions is described. The numerical data includes integer and floating-point samples. Compression supports three encoding modes: lossless, fixed-rate, and fixed-quality. SIMD instructions for compression operations may include attenuation, derivative calculations, bit packing to form compressed packets, header generation for the packets, and packed array output operations. SIMD instructions for decompression may include packed array input operations, header recovery, decoder control, bit unpacking, integration, and amplification. Compression and decompression may be implemented in a microprocessor, digital signal processor, field-programmable gate array, application-specific integrated circuit, system-on-chip, or graphics processor, using SIMD instructions. Compression and decompression of numerical data can reduce memory, networking, and storage bottlenecks. This abstract does not limit the scope of the invention as described in the claims.

First claim

The invention claimed is:

1. A computer system, comprising:
a data processor and memory accessible by the data processor, the memory storing computer programs executable by the data processor, including at least one application program and a set of functions to implement operations to perform compression of data samples from a data set, the at least one application program and the set of functions including single instruction multiple data (SIMD) instructions for at least a portion of the operations to be executed by the data processor, the data processor including a set of registers;
a first register of the register set to store a plurality of operands corresponding to an encoding group of data samples;
an exponent register of the register set, the data processor responsive to a SIMD instruction for operations to determine a maximum exponent value of the plurality of operands in the first register and to store the maximum exponent value in the exponent register;
interleaver logic to interleave bits of the operands in the first register to produce a plurality of nibbles to store in a second register of the register set, wherein the interleaver logic maps the bits to a given nibble based on a place value of the bits in respective operands;
a third register of the register set, the data processor responsive to a SIMD instruction for operations to select a subset of nibbles from the plurality of nibbles in the second register to store in the third register, wherein a number of nibbles for the subset is based on the maximum exponent value, wherein the subset of nibbles includes interleaved mantissa bits of the operands; and
logic to pack the interleaved mantissa bits of the subset of nibbles from the third register to a compressed data packet, wherein the packed interleaved mantissa bits represent compressed data for the encoding group of data samples.

2. The system of claim 1 , wherein the operations further include operations to encode the maximum exponent value to generate an exponent token for the encoding group and to pack the exponent token in the compressed data packet.

3. The system of claim 2 , further comprising a second exponent register of the register set to store a previous maximum exponent value, wherein the operations further include operations to calculate a difference between the maximum exponent value and the previous maximum exponent value to form an exponent difference and to encode the exponent difference to generate the exponent token.

4. The system of claim 3 , further comprising exponent difference registers to store the exponent difference and a previous exponent difference, wherein the operations further include operations to encode the exponent difference and the previous exponent difference to generate the exponent token.

5. The system of claim 1 , wherein the plurality of operands stored in the first register comprises a plurality of data samples for the encoding group from the data set.

6. The system of claim 1 , further comprising:
an input register of the register set to store a plurality of data samples from the data set for the encoding group; and
a first derivative register of the register set, the data processor responsive to a SIMD instruction for operations to calculate derivatives of the plurality of data samples from the input register and to store the plurality of first derivate samples in the first derivative register.

7. The system of claim 6 , wherein the operations include operations to select the input register or the first derivative register in accordance with a parameter, the selected register to provide the plurality of operands for the first register.

8. The system of claim 6 , wherein the first derivative register provides the plurality of operands for the first register.

9. The system of claim 6 , wherein the operations further include an operation to attenuate the plurality of data samples in accordance with an attenuation factor to produce a plurality of attenuated samples and to store the plurality of attenuated samples in the input register.

10. The system of claim 6 , further comprising:
a second derivative register of the register set, the data processor responsive to a SIMD instruction for operations to calculate derivatives of the plurality of first derivative samples from the first derivative register and to store the plurality of second derivate samples in the second derivative register.

11. The system of claim 10 , wherein the operations further include an operation to select the input register, the first derivative register or the second derivative register in accordance with a parameter, the selected register to provide the plurality of operands for the first register.

12. The system of claim 1 , wherein the operands in the first register have a floating-point data format, wherein the operations to select the subset of nibbles provide the number of consecutive nibbles beginning with a most significant nibble of the second register for the subset.

13. The system of claim 1 , wherein the operands in the first register have an integer data format, wherein the operations to select the subset of nibbles provide the number of consecutive nibbles beginning with a least significant nibble of the second register for the subset.

14. The system of claim 1 , wherein a number of operands in the first register is four.

15. The system of claim 14 , wherein the interleaver logic maps the bits having a particular place value in the four operands to a particular nibble in the plurality of nibbles.

16. A method for data compression using a data processor, the method comprising steps of:
storing a plurality of operands corresponding to an encoding group of data samples in a first register of a register set of the data processor;
determining a maximum exponent value of the plurality of operands in the first register;
interleaving bits of the operands in the first register to produce a plurality of nibbles to store in a second register of the register set, wherein the interleaving maps the bits to a given nibble based on a place value of the bits in respective operands;
selecting a subset of nibbles from the plurality of nibbles in the second register to store in a third register of the register set, wherein a number of nibbles for the subset is based on the maximum exponent value, wherein the subset of nibbles includes interleaved mantissa bits of the operands; and
packing the interleaved mantissa bits of the subset of nibbles from the third register to a compressed data packet, wherein the packed interleaved mantissa bits represent compressed data for the encoding group of data samples, wherein the data processor responds to at least one single instruction multiple data (SIMD) instruction to perform at least one of the steps.

17. The method of claim 16 , further comprising:
encoding the maximum exponent value to generate an exponent token for the encoding group; and
packing the exponent token in the compressed data packet.

18. The method of claim 17 , further comprising:
calculating a difference between the maximum exponent value and a previous maximum exponent value to form an exponent difference; and
encoding the exponent difference to generate the exponent token.

19. The method of claim 18 , further comprising:
encoding the exponent difference and a previous exponent difference to generate the exponent token.

20. The method of claim 16 , wherein the plurality of operands stored in the first register comprises a plurality of data samples for the encoding g

Assignees

• Altera Corp

Inventors

• Wegener Albert W

Classifications

• G06F7/38 Primary

  Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation · CPC title

• G06F9/3001

  Arithmetic instructions · CPC title

• H03M13/27

  using interleaving techniques · CPC title

• H03M7/6005

  Decoder aspects · CPC title

• H03M7/3059

  Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression · CPC title