# US 12,182,621 B2 · System and method for using sparsity to accelerate deep learning networks

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

- Number: US 12,182,621 B2
- Document ID: US12182621B2
- Status: Granted
- Kind: B2
- Application number: 18/005,725
- Filed: 2021-07-16
- Published: 2023-08-31
- Granted: 2024-12-31
- Earliest claimed: 2020-07-21
- Assignees: The Governing Council of the University of Toronto
- Applicants: The Governing Council of the University of Toronto
- Inventors: Mostafa Mahmoud; Andreas Moshovos
- Web page: https://patentgrep.com/patent/US12182621B2

## CPC

- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06F 9/3001: {Arithmetic instructions}
- G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations}
- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06N 3/045: Combinations of networks
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/0495: Quantised networks; Sparse networks; Compressed networks
- G06N 3/063: using electronic means
- G06N 3/082: modifying the architecture, e.g. adding, deleting or silencing nodes or connections
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

A system and method for using sparsity to accelerate deep learning networks. The method includes: communicating a bit vector to a scheduler identifying which values in an input tensor are non-zero; for each lane of the input tensor, determining which values are to be communicated for multiply-accumulate (MAC) operations, the determination including directing performance of one of: communicating the current value in the lane; communicating the next value in the same lane where such value is non-zero; communicating a value from a step ahead in time where such value is non-zero; and communicating a value from a neighboring lane where such value is non-zero; and outputting the values of the MAC operations.

## Claims

### Claim 1

A method for using sparsity to accelerate deep learning networks for a processing element, the method comprising:
receiving and storing input tensors respectively from a plurality of input streams for subsequent multiply-accumulate (MAC) operations;
communicating, to a scheduler, bit vectors corresponding to the input tensors identifying which values in the input tensors are non-zero, and determining, based on the bit vectors, locations of non-zero values;
for each MAC operation, selecting, for each corresponding lane of the input tensors, one of the values of the input tensor to form a non-zero value pair and be communicated for the MAC operation, the selection of the non-zero values comprising one of:
the current value in the lane;
the next value in the same lane where such value is non-zero;
a value from a step ahead in time where such value is non-zero; and
a value from a neighboring lane where such value is non-zero;
communicating the selected values for the MAC operations; and
outputting the values of the MAC operations.

### Claim 2 (depends on 1)

The method of claim 1, wherein the processing element is tiled together with a plurality of other processing elements, and receiving and storing the input tensors from the plurality of input streams comprises processing elements along a same row of the input streams share input and processing elements along a same column of the input streams share input.

### Claim 3 (depends on 2)

The method of claim 2, wherein each processing unit of the plurality of processing units uses a separate scheduler.

### Claim 4 (depends on 1)

The method of claim 1, wherein each processing unit along the same row uses a common scheduler.

### Claim 5 (depends on 1)

The method of claim 1, wherein the lanes are treated as arranged in a ring where a last of the lanes is neighbouring a first of the lanes.

### Claim 6 (depends on 1)

The method of claim 1, wherein communicating the value from the neighboring lane comprises communicating a value from a neighboring lane from a step ahead in time where such value is non-zero.

### Claim 7 (depends on 1)

The method of claim 1, wherein receiving and storing the input tensors from the plurality of input streams comprises storing each of the input streams in a respective staging buffer.

### Claim 8 (depends on 7)

The method of claim 7, wherein the staging buffer comprises a current step of the input stream and one or more steps ahead in time.

### Claim 9 (depends on 1)

The method of claim 1, wherein the scheduler uses a hierarchical priority scheme.

### Claim 10 (depends on 9)

The method of claim 9, wherein the hierarchical priority scheme comprises a dense schedule, followed by a plurality of steps increasingly ahead in time, and followed by a plurality of steps of neighbouring lanes increasingly ahead in time.

### Claim 11

A system for using sparsity to accelerate deep learning networks, the system comprising one or more processing units in communication with data memory for executing processing elements (PEs), each processing element receiving a plurality of input streams and comprising:
staging buffers for receiving and storing input tensors respectively from the plurality of input streams for subsequent multiply-accumulate (MAC) operations;
a scheduler to receive a bit vector from each staging buffer to identify which values in a respective one of the input tensors are non-zero and to determine, based on the bit vectors, locations of non-zero values;
wherein, for each MAC operation, the scheduler selects, for each corresponding lane of the input tensors, one of the values of the input tensor to form a non-zero value pair and be communicated to a MAC a unit, the selection of the non-zero values comprising one of:
the current value in the lane;
the next value in the same lane where such value is non-zero;
a value from a step ahead in time where such value is non-zero; and
a value from a neighboring lane where such value is non-zero; and
performing and outputting the values of the MAC operations by the MAC unit using the selected values.

### Claim 12 (depends on 11)

The system of claim 11, wherein the processing elements are collectively arranged in a tiled arrangement where processing elements along a same row of the input streams share input and processing elements along a same column of the input streams share input.

### Claim 13 (depends on 12)

The system of claim 12, wherein each processing unit uses a separate scheduler.

### Claim 14 (depends on 11)

The system of claim 11, wherein each processing unit along the same row uses a common scheduler.

### Claim 15 (depends on 11)

The system of claim 11, wherein the lanes are treated as arranged in a ring where a last of the lanes is neighbouring a first of the lanes.

### Claim 16 (depends on 11)

The system of claim 11, wherein communicating the value from the neighboring lane comprises communicating a value from a neighboring lane from a step ahead in time where such value is non-zero.

### Claim 17 (depends on 11)

The system of claim 11, wherein the staging buffer comprises a current step of the input stream and one or more steps ahead in time.

### Claim 18 (depends on 11)

The system of claim 11, wherein the scheduler uses a hierarchical priority scheme.

### Claim 19 (depends on 18)

The system of claim 18, wherein the hierarchical priority scheme comprises a dense schedule, followed by a plurality of steps increasingly ahead in time, and followed by a plurality of steps of neighbouring lanes increasingly ahead in time.

### Claim 20 (depends on 11)

The system of claim 11, wherein the scheduler receives two bit vectors from each of the staging buffers associated with values in each lane, the two bit vectors are bit-wise OR-ed to generate an output bit vector indicating where there is at least one zero, the scheduler, using the values in the output bit vector, selects a movement per lane so that as many of the non-zero values as possible are processed in a single step.