# US 11,113,601 B1 · Method and system for balanced-weight sparse convolution processing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,113,601 B1
- Document ID: US11113601B1
- Status: Granted
- Kind: B1
- Application number: 16/917,256
- Filed: 2020-06-30
- Granted: 2021-09-07
- Earliest claimed: 2020-06-30
- Assignees: Moffett Technologies Co., Limited
- Applicants: Moffett Technologies Co., Limited
- Inventors: Zhibin Xiao; Enxu Yan; Wei Wang; Yong Lu
- Web page: https://patentgrep.com/patent/US11113601B1

## CPC

- G06N 3/063: using electronic means
- G06N 3/08: Learning methods
- G06N 3/04: Architecture, e.g. interconnection topology
- G06N 3/045: Combinations of networks
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/0495: Quantised networks; Sparse networks; Compressed networks
- G06N 3/082: modifying the architecture, e.g. adding, deleting or silencing nodes or connections
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for balanced-weight sparse convolution processing. An exemplary method comprises: obtaining an input tensor and a plurality of filters; segmenting the input tensor into a plurality of sub-tensors according to a number of available processors; segmenting each of the plurality of filters into one or more sub-filters to obtain a plurality of the sub-filters; respectively assigning the plurality of sub-tensors and sub-filters to the available processors; for each of the available processors, iterating each of the index-value pairs and identifying, based on the index-value pair, a corresponding input value in the assigned sub-tensor to perform a multiply-and-accumulate (MAC) operation to generate a partial sum; reassigning the plurality of sub-filters to the available processors by rotating the plurality of sub-filters among the plurality of processors; and accumulating a plurality of the partial sums to obtain an output tensor.

## Claims

### Claim 1

A computer-implemented method, comprising:
obtaining an input tensor and a plurality of filters, wherein the input tensor and the plurality of filters have a same number of channels;
segmenting the input tensor into a plurality of sub-tensors according to a number of available processors;
pruning each of the plurality of filters so that every predetermined number of channels comprise a fixed number of non-zero weights;
segmenting each of the plurality of filters into a plurality of the sub-filters, wherein each of the plurality of the sub-filters comprises the same number of non-zero weights;
respectively assigning the plurality of sub-tensors and the plurality of sub-filters to the available processors, wherein each of the plurality of sub-filters is represented in a compact memory layout storing the non-zero weights of the sub-filter as index-value pairs, each of the index-value pairs comprising a channel-dimension index, a width-dimension index, and a corresponding non-zero weight;
for each of the available processors, iterating each of the index-value pairs in the compact memory layout of the assigned plurality of sub-filters, and identifying a corresponding input value in the assigned sub-tensor at a location identified by the channel-dimension index and the width-dimension index of the index-value pair to perform a multiply-and-accumulate (MAC) operation to generate a partial sum;
reassigning the plurality of sub-filters to the available processors by rotating the plurality of sub-filters among the plurality of processors; and
accumulating a plurality of the partial sums generated from each of the plurality of processors to obtain an output tensor.

### Claim 2 (depends on 1)

The method of claim 1, wherein each of the plurality of sub-tensors comprises the same number of channels as the input tensor.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
pruning each of the plurality of filters so that every a predetermined number of channels of the filter comprise the same number of non-zero values.

### Claim 4 (depends on 1)

The method of claim 1, wherein the identifying a corresponding input value in the assigned sub-tensor to perform a MAC operation to generate a partial sum comprises:
performing a multiplication operation based on the identified input value and the corresponding non-zero weight in the index-value pair to obtain a dot product; and
accumulating the dot product with a corresponding partial sum to obtained a new partial sum.

### Claim 5 (depends on 1)

The method of claim 1, wherein each of the plurality of filters comprises a channel-dimension, a height dimension, and a width dimension, and
the segmenting each of the plurality of filters into one or more sub-filters comprises:
dividing the channel-dimension into a plurality of channel groups; and
segmenting, according to the plurality of channel groups, the filter into a plurality of sub-filters with each corresponding to one of the plurality of channel groups.

### Claim 6 (depends on 5)

The method of claim 5, wherein the segmenting the filter into a plurality of sub-filters according to the channel groups comprises:
segmenting the filter into a plurality of chunks according to the plurality of channel groups; and
segmenting each of the plurality of chunks along the height dimension to obtain the plurality of sub-filters, wherein each of plurality of sub-filters shares the width dimension with the filter.

### Claim 7 (depends on 5)

The method of claim 5, wherein a subset of the plurality of sub-tensors from a same horizontal plane of the input tensor are respectively assigned to a subset of the available processors, and
the assigning the plurality of sub-filters to the available processors comprises:
identifying a subset of the plurality of sub-filters that are from a same filter but correspond to different channel groups; and
respectively assigning the subset of the plurality of sub-filters to the subset of the available processors.

### Claim 8 (depends on 1)

The method of claim 1, wherein the rotating the plurality of sub-filters among the plurality of processors comprises:
reassigning the plurality of sub-filters to the available processors by rotating a sub-filter that was assigned to an i-th processor to an (i+1)-th processor.

### Claim 9 (depends on 1)

The method of claim 1, wherein the partial sum generated by performing the MAC operation is stored in an accumulation buffer of the processor that is accessible by neighboring processors.

### Claim 10 (depends on 1)

The method of claim 1, wherein the accumulating the plurality of the partial sums generated from each of the plurality of processors to obtain an output tensor comprises:
during a current convolution layer of a neural network, accumulating the plurality of the partial sums generated from each of the plurality of processors to obtain an activation sub-tensor;
in response to the current convolution layer not being a last convolution layer, storing the activation sub-tensor in the processor for a next convolution layer of the neural network; and
in response to the current convolution layer being the last convolution layer, aggregating a plurality of the activation sub-tensors from the available processors to obtain the output tensor.

### Claim 11 (depends on 1)

The method of claim 1, wherein the representing each of the plurality of sub-filters in a compact memory layout storing the non-zero weights of the sub-filter as index-value pairs comprises:
converting each of the index-value pairs into a same number of bits; and
aggregating a plurality of the same number of bits as a bit array to represent the sub-filter.

### Claim 12

A system for balanced-weight sparse convolution processing, comprising one or more processors and one or more non-transitory computer-readable memories coupled to the one or more processors and configured with instructions executable by the one or more processors to cause the system to perform operations comprising:
obtaining an input tensor and a plurality of filters, wherein the input tensor and the plurality of filters have a same number of channels;
segmenting the input tensor into a plurality of sub-tensors according to a number of available processors;
pruning each of the plurality of filters so that every predetermined number of channels comprise a fixed number of non-zero weights;
segmenting each of the plurality of filters into a plurality of the sub-filters, wherein each of the plurality of the sub-filters comprises the same number of non-zero weights;
respectively assigning the plurality of sub-tensors and the plurality of sub-filters to the available processors, wherein each of the plurality of sub-filters is represented in a compact memory layout storing the non-zero weights of the sub-filter as index-value pairs, each of the index-value pairs comprising a channel-dimension index, a width-dimension index, and a corresponding non-zero weight;
for each of the available processors, iterating each of the index-value pairs in the compact memory layout of the assigned plurality of sub-filters, and identifying a corresponding input value in the assigned sub-tensor at a location identified by the channel-dimension index and the width-dimension index of the index-value pair to perform a multiply-and-accumulate (MAC) operation to generate a partial sum;
reassigning the plurality of sub-filters to the available processors by rotating the plurality of sub-filters among the plurality of processors; and
accumulating a plurality of the partial sums generated from each of the plurality of processors to obtain an output tensor.

### Claim 13 (depends on 12)

The system of claim 12, wherein each of the plurality of sub-tensors comprises the same number of channels as the input tensor.

### Claim 14 (depends on 12)

The system of claim 12, wherein each of the plurality of filters comprises a channel dimension, a height dimension, and a width dimension, and
the segmenting each of the plurality of filters into one or more sub-filters comprises:
dividing the channel dimension into a plurality of channel groups; and
segmenting, according to the plurality of channel groups, the filter into a plurality of sub-filters with each corresponding to one of the plurality of channel groups.

### Claim 15 (depends on 12)

The system of claim 12, wherein the identifying a corresponding input value in the assigned sub-tensor to perform a MAC operation to generate a partial sum comprises:
performing a multiplication operation based on the identified input value and the corresponding non-zero weight in the index-value pair to obtain a dot product; and
accumulating the dot product with a corresponding partial sum to obtained a new partial sum.

### Claim 16 (depends on 12)

The system of claim 12, wherein the rotating the plurality of sub-filters among the plurality of processors comprises:
reassigning the plurality of sub-filters to the available processors by rotating a sub-filter that was assigned to an i-th processor to an (i+1)-th processor.

### Claim 17 (depends on 12)

The system of claim 12, wherein the accumulating the plurality of the partial sums generated from each of the plurality of processors to obtain an output tensor comprises:
during a current convolution layer of a neural network, accumulating the plurality of the partial sums generated from each of the plurality of processors to obtain an activation sub-tensor;
in response to the current convolution layer not being a last convolution layer, storing the activation sub-tensor in the processor for a next convolution layer of the neural network; and
in response to the current convolution layer being the last convolution layer, aggregating a plurality of the activation sub-tensors from the available processors to obtain the output tensor.

### Claim 18

A non-transitory computer-readable storage medium for balanced-weight sparse convolution processing, configured with instructions executable by one or more processors to cause the one or more processors to perform operations comprising:
obtaining an input tensor and a plurality of filters, wherein the input tensor and the plurality of filters have a same number of channels;
segmenting the input tensor into a plurality of sub-tensors according to a number of available processors;
pruning each of the plurality of filters so that every predetermined number of channels comprise a fixed number of non-zero weights;
segmenting each of the plurality of filters into a plurality of the sub-filters, wherein each of the plurality of the sub-filters comprises the same number of non-zero weights;
respectively assigning the plurality of sub-tensors and the plurality of sub-filters to the available processors, wherein each of the plurality of sub-filters is represented in a compact memory layout storing the non-zero weights of the sub-filter as index-value pairs, each of the index-value pairs comprising a channel-dimension index, a width-dimension index, and a corresponding non-zero weight;
for each of the available processors, iterating each of the index-value pairs in the compact memory layout of the assigned plurality of sub-filters, and identifying a corresponding input value in the assigned sub-tensor at a location identified by the channel-dimension index and the width-dimension index of the index-value pair to perform a multiply-and-accumulate (MAC) operation to generate a partial sum;
reassigning the plurality of sub-filters to the available processors by rotating the plurality of sub-filters among the plurality of processors; and
accumulating a plurality of the partial sums generated from each of the plurality of processors to obtain an output tensor.

### Claim 19 (depends on 18)

The storage medium of claim 18, wherein the identifying a corresponding input value in the assigned sub-tensor to perform a MAC operation to generate a partial sum comprises:
performing a multiplication operation based on the identified input value and the corresponding non-zero weight in the index-value pair to obtain a dot product; and
accumulating the dot product with a corresponding partial sum to obtained a new partial sum.

### Claim 20 (depends on 18)

The storage medium of claim 18, wherein the accumulating the plurality of the partial sums generated from each of the plurality of processors to obtain an output tensor comprises:
during a current convolution layer of a neural network, accumulating the plurality of the partial sums generated from each of the plurality of processors to obtain an activation sub-tensor;
in response to the current convolution layer not being a last convolution layer, storing the activation sub-tensor in the processor for a next convolution layer of the neural network; and
in response to the current convolution layer being the last convolution layer, aggregating a plurality of the activation sub-tensors from the available processors to obtain the output tensor.