Compressing device and method using parameters of quadtree method

Patent metadata

Field	Value
Publication number	US-11569843-B2
Application number	US-202117183471-A
Country	US
Kind code	B2
Filing date	Feb 24, 2021
Priority date	May 7, 2020
Publication date	Jan 31, 2023
Grant date	Jan 31, 2023

Abstract

A device configured to compress a tensor including a plurality of cells includes: a quadtree generator configured to generate a quadtree searching for a non-zero cell included in the tensor and extract at least one parameter value from the quadtree; a mode selector configured to determine a compression mode based on the at least one parameter; and a bitstream generator configured to generate a bitstream by compressing the tensor based on the compression mode.

First claim

What is claimed is:

1. A device configured to compress a tensor comprising a plurality of cells, the device comprising:
a quadtree generator configured to generate a quadtree searching for a non-zero cell comprised in the tensor and extract at least one parameter from the quadtree;
a mode selector configured to determine a compression mode based on the at least one parameter; and
a bitstream generator configured to generate a bitstream by compressing the tensor based on the compression mode.

2. The device of claim 1 , wherein the at least one parameter comprises:
a first parameter generated as a result of the quadtree and corresponding to a total number of bits in which location information about the non-zero cell is represented;
a second parameter corresponding to a number of bits from a least significant bit to a bit of a non-zero largest digit, in response to a cell having a largest value among non-zero cells being expressed in binary; and
a third parameter corresponding to a number of zero cells among the plurality of cells.

3. The device of claim 2 , wherein the mode selector is further configured to select a first compression mode, in which the tensor is compressed in a quadtree method, as the compression mode, in response to a value of the first parameter being less than or equal to a number of cells included in the tensor.

4. The device of claim 2 , wherein the mode selector is further configured to select a second compression mode, in which the tensor is compressed in a zero bitmap method in which the non-zero cell is regarded as 1 and a zero cell is regarded as ′0, as the compression mode, in response to a value of the first parameter exceeding a number of cells included in the tensor and a product value of a value of the second parameter and a value of the third parameter exceeding the number of cells.

5. The device of claim 2 , wherein the mode selector is further configured to select a third compression mode, in which the tensor is compressed in a fixed length method in which the tensor is compressed based on a bit width of a cell of a largest value among the plurality of cells, as the compression mode, in response to a value of the first parameter exceeding a number of cells included in the tensor and a product value of a value of the second parameter and a value of the third parameter being less than or equal to the number of cells.

6. The device of claim 1 , wherein the tensor comprises 4 M cells, where M is a natural number.

7. The device of claim 1 , wherein the tensor comprises at least one of a feature map and a weight.

8. The device of claim 1 , wherein the bitstream generator is further configured to output the bitstream to at least one storage area of a plurality of storage areas corresponding to the compression mode.

9. A neural network processor comprising:
an arithmetic circuit configured to generate a tensor comprising a plurality of cells by performing a computation on input data by using a neural network; and
a neural tensor compressor configured to output a bitstream by compressing the tensor,
wherein the neural tensor compressor is further configured to generate a quadtree corresponding a repetitive spatial division method to search for a non-zero cell comprised in the tensor, extract at least one parameter from the quadtree, and determine a compression mode of the bitstream based on the at least one parameter.

10. The neural network processor of claim 9 , wherein the at least one parameter comprises:
a first parameter generated as a result of the quadtree and corresponding to a total number of bits in which location information about the non-zero cell is represented;
a second parameter corresponding to a total number of bits from a least significant bit to a bit of a non-zero largest digit, in response to a cell having a largest value among non-zero cells being expressed in binary; and
a third parameter corresponding to a number of zero cells among the plurality of cells.

11. The neural network processor of claim 10 , wherein the neural tensor compressor is further configured to, when a value of the first parameter is less than or equal to a number of cells included in the tensor, compress the tensor by applying a quadtree method.

12. The neural network processor of claim 10 , wherein the neural tensor compressor is further configured to, when a value of the first parameter is greater than a number of cells included in the tensor and when a product value of a value of the second parameter and a value of the third parameter is greater than the number of cells, compress a bitstream by applying a zero bitmap method in which the non-zero cell is regarded as 1, and a zero cell is regarded as 0.

13. The neural network processor of claim 10 , wherein, when a value of the first parameter is greater than a number of cells included in the tensor and when a product value of a value of the second parameter and a value of the third parameter is less than or equal to the number of cells, the bitstream is compressed by applying a fixed length method in which the tensor is compressed based on a bit width of a cell having a largest value among the plurality of cells.

14. The neural network processor of claim 9 , wherein the tensor comprises 4 M cells, where M is a natural number.

15. The neural network processor of claim 9 , wherein the bitstream is output to one storage area of a plurality of storage areas provided corresponding to the compression mode.

16. A method comprising:
receiving a tensor as a result of repeated arithmetic computations performed on a feature map and a weight;
extracting at least one parameter, as a result of repeated spatial division of the tensor to compress a zero cell among a plurality of cells comprised in the tensor;
determining a compression mode based on the at least one parameter; and
outputting a bitstream based on the compression mode.

17. The method of claim 16 , wherein the extracting of the at least one parameter comprises:
extracting a first parameter generated as a result of a quadtree and corresponding to a total number of bits in which location information about a non-zero cell is represented;
extracting a second parameter corresponding to a total number of bits from a least significant bit to a bit of a non-zero largest digit in response to a cell having a largest value among non-zero cells being expressed in binary; and
extracting a third parameter corresponding to a number of zero cells among the plurality of cells.

18. The method of claim 17 , wherein the determining of the compression mode comprises:
comparing a value of the first parameter to a number of cells included in the tensor; and
comparing a product value of a value of the second parameter and a value of the third parameter with the number of cells, in response to the value of the first parameter being greater than the number of cells.

19. The method of claim 18 , further comprising:
compressing the tensor in a quadtree method in response to the value of the first parameter being less than or equal to the number of cells.

20. The method of claim 18 , further comprising:
when the product value of the value of the second parameter and the value of the third parameter is greater than the number of cells, compressing the tensor in a zero bitmap method in which the non-zero cell is regarded as 1, and a zero cell is regarded as 0; and
when the product value of the value of the second parameter and the value of the third parameter is less than or equal to the number of cells,

Assignees

• Samsung Electronics Co Ltd

Inventors

• Jun Sungho
• Park Junseok
• Suh Sangmin
• Lee Heonsoo
• Jang Hyukjae
• Jeong Kyungah

Classifications

• H03M7/405 Primary

  Tree adaptation · CPC title

• G06N3/02

  Neural networks · CPC title

• H03M7/3066 Primary

  by means of a mask or a bit-map · CPC title

• G06N3/0464

  Convolutional networks [CNN, ConvNet] · CPC title

• G06N3/0495

  Quantised networks; Sparse networks; Compressed networks · CPC title