IP Library › Granted Patent US 12,670,370
Granted Patent B1
US 12,670,370 · App. 17/237,370 · Granted Jun 30, 2026

Systems and methods for activation sparse and kernel sparse general matrix multiplication in neural networks

Inventors: Alexander Matveev (Cambridge, MA); Nir Shavit (Cambridge, MA)
Assignee: Red Hat, Inc.
G06N3/063G06F7/523G06F7/78G06F9/445
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,670,370
App. No.
17/237,370
Filed
Apr 22, 2021
Granted
Jun 30, 2026
Kind
B1
Art Unit
2147
USPC
706/15
Abstract

A system and method for performing multiplication for a neural network, e.g. for data of one or more layers in a neural network, may include loading a portion of a compressed version of a sparse input matrix into a cache memory; uncompressing a subset of the data in the portion of the compressed version of the sparse input matrix; and multiplying a sparse kernel matrix by the subset of the data using a set of instructions which are themselves created based on the sparse kernel matrix.

Claims (28)

1 . A method of executing a layer of a neural network (NN), the method comprising:

loading, by a processor and from a memory external to the processor, a portion of a compressed version of an input matrix into a cache, the cache being local to the processor, wherein the input matrix comprises data output from a previous layer of the NN or input data to a first layer of the NN, wherein the previous layer is prior to the layer of the NN to be executed;

after loading the portion of the compressed version of the input matrix into the cache, generating, by the processor, an uncompressed portion of the input matrix by uncompressing the loaded portion of the compressed version of the input matrix, to avoid subsequently using instructions that perform multiplication on the compressed version of the input matrix when executing the layer of the NN, wherein the uncompressed portion is stored in the cache that is local to the processor;

after the uncompressed portion is stored in the cache, executing, by the processor, the layer of the NN by using the uncompressed portion of the input matrix stored in the cache, wherein the executing involves multiplying a kernel matrix by the uncompressed portion of the input matrix using a set of instructions, wherein the set of instructions were pre-generated prior to the execution of the layer of the NN based on the kernel matrix and relate to non-zero elements of the kernel matrix; and

outputting, by the processor, an output generated by the NN based at least in part on the execution of the layer of the NN.

2 . The method of claim 1 , wherein the compressed version of the input matrix is compressed using a compressed sparse column (CSC) format.

3 . The method of claim 1 , wherein the set of instructions do not include instructions relating to zero elements of the kernel matrix.

4 . The method of claim 1 , comprising repeating the loading, uncompressing and multiplying operations until all of the input matrix has been multiplied.

5 . A system for executing a layer of a neural network (NN), the system comprising:

a memory; and

a processor comprising a cache local to the processor, wherein the memory is external to the processor, and wherein the processor is configured to:

load, from the memory external to the processor, a portion of a compressed version of an input matrix into the cache local to the processor, wherein the input matrix comprises data output from a previous layer of the NN or input data to a first layer of the NN, wherein the previous layer is prior to the layer of the NN to be executed;

after loading the portion of the compressed version of the input matrix into the cache, generate an uncompressed portion of the input matrix by uncompressing the loaded portion of the compressed version of the input matrix, to avoid subsequently using instructions that perform multiplication on the compressed version of the input matrix when executing the layer of the NN, wherein the uncompressed portion is stored in the cache that is local to the processor;

after the uncompressed portion is stored in the cache, execute the layer of the NN by using the uncompressed portion of the input matrix stored in the cache, wherein the executing involves multiplying a kernel matrix by the uncompressed portion of the input matrix using a set of instructions, wherein the set of instructions were pre-generated prior to the execution of the layer of the NN based on the kernel matrix and relate to non-zero elements of the kernel matrix; and

outputting an output generated by the NN based at least in part on the execution of the layer of the NN.

6 . The system of claim 5 , wherein the compressed version of the input matrix is compressed using a compressed sparse column (CSC) format.

7 . The system of claim 5 , wherein the set of instructions do not include instructions relating to zero elements of the kernel matrix.

8 . The system of claim 5 , wherein the processor is configured to repeat the loading, uncompressing and multiplying operations until all of the input matrix has been multiplied.

9 . A method of executing a layer of a neural network (NN), the method comprising:

loading, by a processor and from a memory external to the processor, a compressed input matrix into a cache, the cache being local to the processor, wherein the compressed input matrix represents an output from a previous layer of the NN or input data to a first layer of the NN, wherein the previous layer is prior to the layer of the NN to be executed;

generating, by the processor, uncompressed data by uncompressing data of the compressed input matrix, to avoid subsequently using instructions that perform multiplication on the compressed input matrix when executing the layer of the NN, wherein the uncompressed data is stored in the cache that is local to the processor;

loading, by the processor, a set of instructions into an instruction cache, wherein the set of instructions relate to non-zero elements of a kernel matrix;

after generating the uncompressed data and loading the set of instructions into the instruction cache, executing, by the processor, the layer of the NN, wherein the executing involves multiplying the kernel matrix by the uncompressed data using the set of instructions; and

outputting, by the processor, an output generated by the NN based at least in part on the execution of the layer of the NN.

10 . The method of claim 9 , wherein the compressed input matrix is compressed using a compressed sparse column (CSC) format.

11 . The method of claim 9 , wherein the set of instructions do not include instructions relating to zero elements of the kernel matrix.

12 . The method of claim 9 , comprising repeating the uncompressing and multiplying operations until all subblocks of the input matrix have been multiplied.

13 . The method of claim 9 , wherein the uncompressing and multiplying operations are performed over a series of iterations, the method comprising, prior to the first iteration, uncompressing a buffer of compressed input matrix data.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jul 30, 2025
From: NEURALMAGIC, INC.
To: RED HAT, INC.
Reel/Frame 072278/0309 →
Continuity (1)
Provisional Application 63013703 · Apr 22, 2020
References Cited (128)
US 5577166A · Mizuno · 1996 [cited by applicant]
US 7747070B2 · Puri · 2010 [cited by applicant]
US 9558156B1 · Bekas et al. · 2017 [cited by applicant]
US 9811775B2 · Krizhevsky et al. · 2017 [cited by applicant]
US 9818059B1 · Woo et al. · 2017 [cited by applicant]
US 10157045B2 · Venkataramani et al. · 2018 [cited by applicant]
US 10223333B2 · Chetlur et al. · 2019 [cited by applicant]
US 10572568B2 · Narayanamoorthy et al. · 2020 [cited by applicant]
US 10685082B2 · Bekas et al. · 2020 [cited by applicant]
US 10719323B2 · Baum et al. · 2020 [cited by applicant]
US 10832139B2 · Yan et al. · 2020 [cited by applicant]
US 10970619B1 · Xiao et al. · 2021 [cited by applicant]
US 11113601B1 · Xiao et al. · 2021 [cited by applicant]
US 11216732B2 · Zlateski et al. · 2022 [cited by applicant]
US 20100076915A1 · Xu et al. · 2010 [cited by applicant]
US 20110119467A1 · Cadambi et al. · 2011 [cited by applicant]
US 20110296146A1 · Anand et al. · 2011 [cited by applicant]
US 20120311299A1 · Blumrich et al. · 2012 [cited by applicant]
US 20130138589A1 · Yu et al. · 2013 [cited by applicant]
US 20150127327A1 · Bacchiani et al. · 2015 [cited by applicant]
US 20160224465A1 · Morad et al. · 2016 [cited by applicant]
US 20160239706A1 · Dijkman et al. · 2016 [cited by applicant]
US 20160328643A1 · Liu et al. · 2016 [cited by applicant]
US 20160350645A1 · Brothers et al. · 2016 [cited by applicant]
US 20160358070A1 · Brothers et al. · 2016 [cited by applicant]
US 20160379109A1 · Chung et al. · 2016 [cited by applicant]
US 20170032487A1 · Ashari et al. · 2017 [cited by applicant]
US 20170103313A1 · Ross et al. · 2017 [cited by applicant]
US 20170103317A1 · Young · 2017 [cited by applicant]
US 20170132496A1 · Shoaib et al. · 2017 [cited by applicant]
US 20170169567A1 · Chefd'Hotel et al. · 2017 [cited by applicant]
US 20170193136A1 · Prasad et al. · 2017 [cited by applicant]
US 20170193361A1 · Chilimbi et al. · 2017 [cited by applicant]
US 20170200094A1 · Bruestle et al. · 2017 [cited by applicant]
US 20170220524A1 · Herrero Abellanas et al. · 2017 [cited by applicant]
US 20170316311A1 · Pilly et al. · 2017 [cited by applicant]
US 20170316312A1 · Goyal et al. · 2017 [cited by applicant]
US 20170372202A1 · Ginsburg et al. · 2017 [cited by applicant]
US 20180046900A1 · Dally et al. · 2018 [cited by applicant]
US 20180096226A1 · Aliabadi et al. · 2018 [cited by applicant]
US 20180173571A1 · Huang et al. · 2018 [cited by applicant]
US 20180253402A1 · Redfern et al. · 2018 [cited by applicant]
US 20180315159A1 · Ould-Ahmed-Vall et al. · 2018 [cited by applicant]
US 20180322390A1 · Das et al. · 2018 [cited by applicant]
US 20180336468A1 · Kadav et al. · 2018 [cited by applicant]
US 20190042250A1 · Anders et al. · 2019 [cited by applicant]
US 20190042542A1 · Narayanamoorthy et al. · 2019 [cited by applicant]
US 20190056916A1 · Varma et al. · 2019 [cited by applicant]
US 20190138902A1 · Matveev et al. · 2019 [cited by applicant]
US 20190156206A1 · Graham et al. · 2019 [cited by applicant]
US 20190156214A1 · Matveev et al. · 2019 [cited by applicant]
US 20190156215A1 · Matveev et al. · 2019 [cited by applicant]
US 20190179818A1 · Lee · 2019 [cited by applicant]
US 20190205759A1 · Zhang · 2019 [cited by applicant]
US 20190212982A1 · Yoda et al. · 2019 [cited by applicant]
US 20190303743A1 · Venkataramani et al. · 2019 [cited by applicant]
US 20190354894A1 · Lazovich et al. · 2019 [cited by applicant]
US 20190370071A1 · Matveev et al. · 2019 [cited by applicant]
US 20190370644A1 · Kenney et al. · 2019 [cited by applicant]
US 20200034710A1 · Sidhu et al. · 2020 [cited by applicant]
US 20200089534A1 · Chen et al. · 2020 [cited by applicant]
US 20200090024A1 · Chen et al. · 2020 [cited by applicant]
US 20200097826A1 · Du et al. · 2020 [cited by applicant]
US 20200104717A1 · Alistarh · 2020 [cited by applicant]
US 20200117999A1 · Yoon et al. · 2020 [cited by applicant]
US 20200160181A1 · Zlateski et al. · 2020 [cited by applicant]
US 20200160182A1 · Matveev et al. · 2020 [cited by applicant]
US 20200190808A1 · Joydeep · 2020 [cited by examiner]
US 20200193274A1 · Darvish Rouhani et al. · 2020 [cited by applicant]
US 20200218978A1 · Kopinsky · 2020 [cited by applicant]
US 20200320400A1 · David · 2020 [cited by applicant]
US 20200342301A1 · Miao et al. · 2020 [cited by applicant]
US 20210027197A1 · Foerster et al. · 2021 [cited by applicant]
US 20210049463A1 · Ruff · 2021 [cited by applicant]
US 20210174190A1 · Janssen et al. · 2021 [cited by applicant]
US 20230316058A1 · Nurvitadhi · 2023 [cited by examiner]
CN 107145939A · 2017 [cited by examiner]
CN 107832839 · 2018 [cited by applicant]
CN 109993297A · 2019 [cited by examiner]
CN 111353591B · 2024 [cited by examiner]
CN 111382835B · 2024 [cited by examiner]
CN 111382848B · 2024 [cited by examiner]
EP 3037980 · 2016 [cited by applicant]
EP 3779681B1 · 2024 [cited by examiner]
TW 1786255B · 2022 [cited by examiner]
WO WO2017049496 · 2017 [cited by applicant]
WO WO2018053835 · 2018 [cited by applicant]
WO WO2019090325A1 · 2019 [cited by applicant]
WO WO2020046859A1 · 2020 [cited by examiner]
WO WO2020047823A1 · 2020 [cited by applicant]
WO WO2020072274A1 · 2020 [cited by applicant]
WO WO2020190772A1 · 2020 [cited by examiner]
WO WO2020190808A1 · 2020 [cited by examiner]
Deshpande, A beginner's guide to understanding convolutional neural networks, Jul. 20, 2016. [cited by applicant]
Alwani et al., “Fused-layer CNN accelerators.” 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2016, pp. 1-12. [cited by applicant]
Du et al., “Width Provably Matters in Optimization for Deep Linear Neural Networks”, May 27, 2019, arXiv:1901.08572v3. [cited by applicant]
Gale et al., “The State of Sparsity in Deep Neural Networks”, Feb. 25, 2019, arXiv:1902.09574v1. [cited by applicant]
Han et al., “Learning both Weights and Connections for Efficient Neural Networks”, 2015, Advances in Neural Information Processing Systems, vol. 28. [cited by applicant]
Hinton et al., “Distilling the Knowledge in a Neural Network”, Mar. 9, 2015. [cited by applicant]
Lavin et al., “Fast Algorithms for Convolutional Neural Networks”, Nov. 10, 2015. [cited by applicant]
Lecun et al., “Optimal brain damage”, Advances in neural information processing systems, 1990, pp. 598-605. [cited by applicant]
Mishra et al., “Apprentice: Using Knowledge Distillation Techniques to Improve Low-Precision Network Accuracy”, Nov. 15, 2017. [cited by applicant]
Rusu et al., “Progressive Neural Networks”, Sep. 7, 2016. [cited by applicant]
Budden et al., “Deep tensor convolution on multicores”, In Proceedings of the 34th International Conference on Machine Learning, 2017, vol. 70, pp. 615-624. [cited by applicant]
Chen, Xuhao, “Escoin: Efficient Sparse Convolutional Neural Network Inference on GPUs.” From Jul. 2017 “Conference '17”, Apr. 3, 2019 (Apr. 3, 2019) Retrieved on Jan. 17, 2020 (Jan. 17, 2020)from <https://arxiv.orq/pdf/… [cited by applicant]
Georganas et al., “Anatomy Of High-Performance Deep Learning Convolutions On SIMD Architectures.” In: SC18: International Conference for High Performance Computing, Networking, Storage and Analysis. Aug. 20, 2018 (Aug. … [cited by applicant]
Kaya et al., “Scalable sparse tensor decompositions in distributed memory systems”, SC'15: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE, 2015. (Year:… [cited by applicant]
Kim et al., “Designing Vector-Friendly Compact BLAS and LAPACK Kernels”, SC17, Nov. 12-17, 2017, Denver, CO, USA. [cited by applicant]
Lascorz et al., “Bit-Tactical: Exploiting Ineffectual Computations in Convolutional Neural Networks: Which, Why, and How”, Mar. 9, 2018. [cited by applicant]
Liu et al., “Sparse convolutional neural networks.” In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Jun. 12, 2015 (Jun. 12, 2015) Retrieved on Jan. 17, 2020. [cited by applicant]
Papyan et al., “Convolutional neural networks analyzed via convolutional sparse coding.” In: The Journal of Machine Learning Research. Jul. 17, 2017 (Jul. 17, 2017) Retrieved on Feb. 20, 2020. [cited by applicant]
Scardapane et al. “Group sparse regularization for deep neural networks.”, In: Neurocomputing. Jul. 2, 2016 (Jul. 2, 2016) Retrieved on Nov. 16, 2019 (Nov. 16, 2019). [cited by applicant]
Smith et al., “SPLATT: Efficient and parallel sparse tensor-matrix multiplication”, 2015 IEEE International Parallel and Distributed Processing Symposium, IEEE, 2015, (Year: 2015). [cited by applicant]
Wozniak et al., “GiMMiK-Generating bespoke matrix multiplication kernels for accelerators: Application to high-order Computational Fluid Dynamics”, Computer Physics Communications, vol. 202, 2016, pp. 12-22. [cited by applicant]
Zhangxiaowen Gong et al. “Sparse Train: Leveraging Dynamic Sparsity in Training DNNs on General-Purpose SIMD Processors”; 2019. [cited by applicant]
Yu, Dong, Li Deng, and Frank Seide. “The deep tensor neural network with applications to large vocabulary speech recognition”. IEEE Transactions on Audio Speech, and Language Processing 21.2 (2012): 388-396. (Year: 2012… [cited by applicant]
Kurtz, Mark, et al. “Inducing and Exploiting Activation Sparsity for Fast Neural Network Inference.” Proceedings of the International Conference on Machine Learning. 2020. [cited by applicant]
Robert Lim; “Methods for Accelerating Machine Learning in High Performance Computing”; University of Oregon—AREA—Jan. 2019. [cited by applicant]
Zhizhou Li et al.; “A CPU-based Algorithm for Traffic Optimization Based on Sparse Convolutional Neural Networks”; 2017 IEEE 30th Canadian Conference on Electrical and Computer (CCECE). [cited by applicant]
Baoyuan Liu et al.; “Sparse Convolutional Neural Networks”; CVPR 2015—Computer Vision Foundation—IEEE. [cited by applicant]
Hesham Mostafa et al.; “Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization”; Proceedings of the 36 th International Conference on Machine Learning, Long Beach, Califo… [cited by applicant]
Israt Nisa et al.; “Sampled Dense Matrix Multiplication for High-Performance Machine Learning”; 2018 IEEE 25th International Conference on High Performance Computing (Hi PC). [cited by applicant]
Yang, Huanrui, Wei Wen, and Hai Li. “Deephoyer: Learning sparser neural network with differentiable scale-invariant sparsity measures.” arXiv preprint arXiv:1908.09979 (2019). [cited by applicant]
Yuster, Raphael, and Uri Zwick. “Fast sparse matrix multiplication.” ACM Transactions On Algorithms (TALG) 1.1 (2005): 2-13. [cited by applicant]
Paixao, Crysttian A., and Flávio Codeço Coelho. Matrix compression methods. No. e1049. PeerJ PrePrints, 2015. [cited by applicant]
Park, Jongsoo, et al. “Faster cnns with direct sparse convolutions and guided pruning.” arXiv preprint arXiv:1608.01409 (2016). [cited by applicant]
https://www.kinematicsoup.com/news/2016/9/6/data-compression-bit-packing-101, published Sep. 6, 2016. [cited by applicant]
Williams, Samuel, Andrew Waterman, and David Patterson. “Roofline: an insightful visual performance model for multicore architectures.” [cited by applicant]