SamsungGranted patentChips & hardwareInterest 4/10

Samsung patents method to shrink sparse data for lower power

Patent drawing
Patent drawing from the official filing.

Samsung has been granted a patent for a way to compress data that contains many empty spaces, known as sparse matrices. The method uses a repeating process to shorten sequences of zeros, which reduces the amount of data the hardware has to move. This reduction in data movement helps lower the power consumption of the device.

Why it mattersThis technique could help make computer chips more energy efficient by reducing the work they have to do when processing large datasets with lots of empty values.

In the filing’s own words

A sparse matrix is compressed using recursive application of word replacement based on a bijective process. The bijective process generally shrinks sequences of zeros. The shrinkage generally continues at a geometric rate with additional recursions, up to a limit. The bijective process reaches a global minimum for an output sequence. After the global minimum is reached, the length of the output expands at a linear rate. Due to the bijective process, decompression is able to proceed in a lossless manner to exactly recover the input sparse matrix. Clusters of non-zero bits in the sparse matrix may be in a single line or distributed across neighboring lines. Clusters in a single line are addressed by a design parameter corresponding to a distance between binary-1s in the data. Clusters distributed across neighboring lines are flattened using a pre-processing stage.

What exactly they claim (claim 1)

1. A method of compressing an initial input sequence comprising a plurality of words to obtain a compressed output sequence using a plurality of recursion stages, the method comprising: inputting a first word into a first recursion stage of the plurality of recursion stages, wherein the plurality of words comprises the first word; replacing, in the first recursion stage, the first word to obtain a second word and outputting the second word to a second recursion stage of the plurality of recursion stages; and repeating the inputting, the replacing and the outputting until a final word of the initial input sequence has been replaced by the first recursion stage, wherein the plurality of words comprises the final word, wherein successive recursion stages continue to perform the inputting, the replacing and the outputting until no further second words are provided to the successive recursion stages (?) from an upstream recursion stage, wherein an output sequence at an output of a final recursion stage of the plurality of recursion stages is the compressed output sequence, and wherein hardware power consumption is reduced by reducing bit-toggles.

Facts

Company
Samsung (SAMSUNG ELECTRONICS CO., LTD.)
Official title
Sparse matrix compression using recursive word replacement maps
Patent number
US12801520B2
Application number
19185809
Filed
Apr 22, 2025
Granted
Nov 17, 2026
Inventors
2
Claims
20

Classified under

G06F 12/0223 Physics & computing

More from Samsung in Chips & hardware

Summaries are simplified from the filing’s own abstract and first claim. A patent filing is not a product announcement.
Patent data and drawings: U.S. Patent and Trademark Office (USPTO). Nebula is not affiliated with or endorsed by the USPTO.