PROVIDING EFFICIENT MULTIPLICATION OF SPARSE MATRICES IN MATRIX-PROCESSOR-BASED DEVICES

• US 20190065150A1
• Filed: 08/30/2018
• Published: 02/28/2019
• Est. Priority Date: 08/31/2017
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Heddes, Mattheus Cornelis Antonius Adrianus, Dreyer, Robert, Verrilli, Colin Beaton, Vaidhyanathan, Natarajan, Bhattacharya, Koustav
• Granted Patent: US 10,725,740 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 15/8015 One dimensional arrays, e.g. rings, linear arrays, buses
• CPC Class Codes: G06F 15/8053 Vector processors
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/063 using electronic means
• CPC Class Codes: G06N 3/082 modifying the architecture, e.g. adding, deleting or silencing nodes or connections

Abstract

Providing efficient multiplication of sparse matrices in matrix-processor-based devices is disclosed herein. In one aspect, a matrix processor of a matrix-processor-based device includes a plurality of sequencers coupled to a plurality of multiply/accumulate (MAC) units for performing multiplication and accumulation operations. Each sequencer determines whether a product of an element of a first input matrix to be multiplied with an element of a second input matrix has a value of zero (e.g., by determining whether the element of the first input matrix has a value of zero, or by determining whether either the element of the first input matrix or that of the second input matrix has a value of zero). If the product of the elements of the first input matrix and the second input matrix does not have a value of zero, the sequencer provides the elements to a MAC unit to perform a multiplication and accumulation operation.

Claims

1. A matrix-processor-based device comprising a matrix processor, wherein:

the matrix processor comprises a plurality of sequencers communicatively coupled to one or more multiply/accumulate (MAC) units of a plurality of MAC units; and

the matrix processor is configured to;

receive a first input matrix and a second input matrix;

select, by each sequencer of the plurality of sequencers, an element of the first input matrix and an element of the second input matrix to be multiplied;

determine, by the sequencer, whether a product of the element of the first input matrix and the element of the second input matrix will equal zero (0); and

responsive to determining that the product of the element of the first input matrix and the element of the second input matrix will not equal zero (0);

provide, by the sequencer, the element of the first input matrix and the element of the second input matrix to a corresponding MAC unit of the plurality of MAC units; and

perform, by the corresponding MAC unit, a multiplication and accumulation operation using the element of the first input matrix and the element of the second input matrix.

2. The matrix-processor-based device of claim 1, wherein the matrix processor is further configured to, responsive to determining that the product of the element of the first input matrix and the element of the second input matrix will equal zero (0), withhold, by the sequencer, the element of the first input matrix and the element of the second input matrix from the corresponding MAC unit.

3. The matrix-processor-based device of claim 1, wherein the plurality of MAC units comprises a number of MAC units equal to a number of elements in an output matrix resulting from multiplying the first input matrix and the second input matrix.

4. The matrix-processor-based device of claim 3, wherein:

the plurality of sequencers comprises a number of sequencers equal to a number of rows in the output matrix; and

the matrix processor is configured to determine whether the product of the element of the first input matrix and the element of the second input matrix will equal zero (0) by being configured to determine, by the sequencer of the plurality of sequencers, whether the element of the first input matrix has a value of zero (0).

5. The matrix-processor-based device of claim 3, wherein:

the plurality of sequencers comprises a number of sequencers equal to a number of elements in the output matrix; and

the matrix processor is configured to determine whether the product of the element of the first input matrix and the element of the second input matrix will equal zero (0) by being configured to determine, by the sequencer of the plurality of sequencers, whether either of the element of the first input matrix and the element of the second input matrix has a value of zero (0).

6. The matrix-processor-based device of claim 1, wherein:

the plurality of MAC units comprises a number of MAC units equal to a number of rows in an output matrix resulting from multiplying the first input matrix and the second input matrix;

the plurality of sequencers comprises a number of sequencers equal to the number of rows in the output matrix.

7. The matrix-processor-based device of claim 1, wherein:

the plurality of MAC units comprises a number of MAC units equal to twice a number of elements in the first output matrix;

the plurality of sequencers comprises a number of sequencers equal twice number of rows in the first input matrix.

8. The matrix-processor-based device of claim 1 integrated into an integrated circuit (IC).

9. The matrix-processor-based device of claim 1 integrated into a device selected from the group consisting of:

a set top box;

an entertainment unit;

a navigation device;

a communications device;

a fixed location data unit;

a mobile location data unit;

a global positioning system (GPS) device;

a mobile phone;

a cellular phone;

a smart phone;

a session initiation protocol (SIP) phone;

a tablet;

a phablet;

a server;

a computer;

a portable computer;

a mobile computing device;

a wearable computing device;

a desktop computer;

a personal digital assistant (PDA);

a monitor;

a computer monitor;

a television;

a tuner;

a radio;

a satellite radio;

a music player;

a digital music player;

a portable music player;

a digital video player;

a video player;

a digital video disc (DVD) player;

a portable digital video player;

an automobile;

a vehicle component;

avionics systems;

a drone; and

a multicopter.

10. A matrix-processor-based device, comprising:

a means for receiving a first input matrix and a second input matrix;

a means for selecting an element of the first input matrix and an element of the second input matrix to be multiplied;

a means for determining whether a product of the element of the first input matrix and the element of the second input matrix will equal zero (0); and

a means for performing a multiplication and accumulation operation using the element of the first input matrix and the element of the second input matrix, responsive to determining that the product of the element of the first input matrix and the element of the second input matrix will not equal zero (0).

11. The matrix-processor-based device of claim 10, further comprising, a means for withholding the element of the first input matrix and the element of the second input matrix, responsive to determining that the product of the element of the first input matrix and the element of the second input matrix will equal zero (0).

12. The matrix-processor-based device of claim 10, wherein the means for determining whether the product of the element of the first input matrix and the element of the second input matrix will equal zero (0) comprises a means for determining whether the element of the first input matrix has a value of zero (0).

13. The matrix-processor-based device of claim 10, wherein the means for determining whether the product of the element of the first input matrix and the element of the second input matrix will equal zero (0) comprises a means for determining whether either of the element of the first input matrix and the element of the second input matrix has a value of zero (0).

14. A method for performing efficient multiplication of sparse matrices, comprising:

receiving, by a matrix processor of a matrix-processor-based device, a first input matrix and a second input matrix;

selecting, by each sequencer of a plurality of sequencers of the matrix processor, an element of the first input matrix and an element of the second input matrix to be multiplied;

determining, by the sequencer, whether a product of the element of the first input matrix and the element of the second input matrix will equal zero (0); and

responsive to determining that the product of the element of the first input matrix and the element of the second input matrix will not equal zero (0);

providing, by the sequencer, the element of the first input matrix and the element of the second input matrix to a corresponding multiply/accumulate (MAC) unit of a plurality of MAC units of the matrix processor; and

performing, by the corresponding MAC unit, a multiplication and accumulation operation using the element of the first input matrix and the element of the second input matrix.

15. The method of claim 14, further comprising, responsive to determining that the product of the element of the first input matrix and the element of the second input matrix will equal zero (0), withholding, by the sequencer, the element of the first input matrix and the element of the second input matrix from the corresponding MAC unit.

16. The method of claim 14, wherein the plurality of MAC units comprises a number of MAC units equal to a number of elements in an output matrix resulting from multiplying the first input matrix and the second input matrix.

17. The method of claim 16, wherein:

the plurality of sequencers comprises a number of sequencers equal to a number of rows in the output matrix; and

determining whether the product of the element of the first input matrix and the element of the second input matrix will equal zero (0) comprises determining, by the sequencer of the plurality of sequencers, whether the element of the first input matrix has a value of zero (0).

18. The method of claim 16, wherein:

the plurality of sequencers comprises a number of sequencers equal to a number of elements in the output matrix; and

determining whether the product of the element of the first input matrix and the element of the second input matrix will equal zero (0) comprises determining, by the sequencer of the plurality of sequencers, whether either of the element of the first input matrix and the element of the second input matrix has a value of zero (0).