US 9,300,320 B2 · System and method for dictionary-based cache-line level code compression for on-chip memories using gradual bit removal

Abstract

A multi-pass compression iteratively removes combinations of bits from locations in each word of a cache line of an uncompressed data stream. For each combination of removed bits, the remaining bits in the word values of the cache line are analyzed to generate a compression score. A highest compression score triggers the building of a dictionary from the remaining bits in the word values of the cache line. After a dictionary is built, the method may continue iteratively to create subsequent dictionaries from the words that remain uncompressed in the cache line. To decompress a word, a first bit section of the compressed word is used to identify a dictionary that is then queried for bits indexed in a second bit section of the compressed word. The uncompressed word is reconstructed by interleaving the queried bits with the removed combination of bits from a third bit section of the word.

Claims30

Dependent claims

A method for cache-line level compression and decompression (“CLADE”) of a data stream in a system on a chip (“SoC”) in a portable computing device (“PCD”), the method comprising:

iteratively removing combinations of bits from locations in each word of a cache line of an uncompressed data stream;
for each combination of removed bits, analyzing remaining bits in the word values of the cache line using an objective function, wherein the objective function generates a compression score that quantifies the value of a dictionary built from the remaining bits in the word values of the cache line;
and
based on a highest compression score, generating a first dictionary from the remaining bits in the word values after removal of the combination of bits associated with the highest compression score.

1 more element

A system for cache-line level compression and decompression (“CLADE”) of a data stream in a system on a chip (“SoC”) in a portable computing device (“PCD”), the system comprising:

a CLADE module operable for:
iteratively removing combinations of bits from locations in each word of a cache line of an uncompressed data stream;
for each combination of removed bits, analyzing remaining bits in the word values of the cache line using an objective function, wherein the objective function generates a compression score that quantifies the value of a dictionary built from the remaining bits in the word values of the cache line;
and
based on a highest compression score, generating a first dictionary from the remaining bits in the word values after removal of the combination of bits associated with the highest compression score.

2 more elements

A computer program product comprising a computer usable medium having a computer readable program code embodied therein, said computer readable program code adapted to be executed to implement a method for cache-line level compression and decompression (“CLADE”) of a data stream in a system on a chip (“SoC”) in a portable computing device (“PCD”), said method comprising:

iteratively removing combinations of bits from locations in each word of a cache line of an uncompressed data stream;
for each combination of removed bits, analyzing remaining bits in the word values of the cache line using an objective function, wherein the objective function generates a compression score that quantifies the value of a dictionary built from the remaining bits in the word values of the cache line;
and
based on a highest compression score, generating a first dictionary from the remaining bits in the word values after removal of the combination of bits associated with the highest compression score.

1 more element

Dependencies are inferred from the claim text.

System and method for dictionary-based cache-line level code compression for on-chip memories using gradual bit removal

Life of this patent

System and method for dictionary-based cache-line level code compression for on-chip memories using gradual bit removal

Life of this patent

Abstract

Claims30