Search unit to accelerate variable length compression/decompression

Patent metadata

Field	Value
Publication number	US-9154157-B2
Application number	US-201213629467-A
Country	US
Kind code	B2
Filing date	Sep 27, 2012
Priority date	Sep 27, 2012
Publication date	Oct 6, 2015
Grant date	Oct 6, 2015

Abstract

Systems and methods to accelerate compression and decompression with a search unit implemented in the processor core. According to an embodiment, a search unit may be implemented to perform compression or decompression on an input stream of data. The search unit may use a look-up table to identify appropriate compression or decompression symbols. The look-up table may be populated with a table derived using the variable length coding symbols of a sequence of vertices to be compressed or extracted from a received data stream to be decompressed. A comparator and a finite state machine may be implemented in the search unit to facilitate traversal of the look-up table.

First claim

What is claimed is:

1. A method for performing efficient operations to compress or decompress data, the method comprising:
receiving, at a processor core, data comprising a table to be searched;
sorting, at the processor core, the table data by a search column;
populating, in a search unit within the processor core, a look-up table with the sorted table data;
receiving, at the search unit, data for processing, wherein the data for processing comprises a plurality of symbols;
for each symbol in the data for processing:
searching, with the search unit, the look-up table for a match to the symbol;
identifying, with the search unit, a matching row of the look-up table;
adding, at the processor core, a portion of the matching row to a data stream for output;
transmitting, from the search unit, the output data stream to a receiver, wherein the output data represents a transformation of the data for processing into compression values or decompression values corresponding to the data for processing.

2. The method of claim 1 , wherein each row of the look-up table includes a compressed delta symbol, a delta symbol, and a length.

3. The method of claim 2 , wherein the plurality of symbols comprise a plurality of deltas for compression.

4. The method of claim 3 , wherein the search column is a column of the table comprising delta values.

5. The method of claim 3 , wherein the portion of the matching row comprises a compressed delta of the associated symbol.

6. The method of claim 2 , further comprising: calculating, at the processor core, delta values for each element in the received table data.

7. The method of claim 1 , wherein the table data is generated using variable length coding for a sequence of vertices.

8. The method of claim 7 , wherein the data for processing comprises the sequence of vertices.

9. The method of claim 7 , wherein the table data comprises a Huffman table.

10. The method of claim 1 , wherein the data for processing is to be compressed.

11. The method of claim 1 , wherein the data for processing is to be decompressed.

12. The method of claim 11 , wherein the plurality of symbols comprise a plurality of compressed deltas.

13. The method of claim 12 , wherein the search column is a column of the table comprising compressed deltas.

14. The method of claim 12 , wherein the portion of the matching row comprises a decompressed delta value of the associated symbol.

15. The method of claim 1 , further comprising: for each portion of a matching row added to the output data stream, calculating, at the processor core, an original symbol of the delta value.

16. A search unit implemented in a processor core, the search unit to perform efficient operations to compress or decompress data, the search unit comprising:
a memory unit configured to store a look-up table;
a comparator; and
a finite state machine (FSM) configured to control a binary search of the look-up table;
wherein the search unit is configured to:
receive table data;
populate the look-up table with the received table data;
receive data for processing, wherein the data for processing comprises a plurality of symbols and for each symbol in the plurality of symbols:
search the look-up table for a match to the symbol,
identify, with the comparator, a matching row of the look-up table,
upon identification of the matching row, update the FSM and return the matching row;

generate an output data stream for transmission to a receiver, wherein the output data represents a transformation of the data for processing into compression values or decompression values corresponding to the data for processing.

17. The search unit of claim 16 , wherein the data for processing is to be compressed.

18. The search unit of claim 17 , wherein the plurality of symbols comprise a plurality of deltas for compression.

19. The search unit of claim 16 , wherein the data for processing is to be decompressed.

20. The search unit of claim 19 , wherein the plurality of symbols comprise a plurality of compressed deltas.

Assignees

• Intel Corp

Inventors

• Satish Nadathur Rajagopalan
• Kim Changkyu
• Chhugani Jatin

Classifications

• H03M7/30 Primary

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title