TECHNICAL FIELD

[0001] Embodiments of the present invention relate to the field of matrix multiplication technologies, and more specifically, to a system and a method for matrix multiplication.

BACKGROUND

[0002] Dedicated matrix multiplication acceleration is widely used in high performance computing (HPC) and artificial intelligence (Al), but these two area have different requirements for size types - integer32 (int.32)/integer64 (int64) is mainly used for the HPC, while int8/intl6 is commonly used for the Al. For hardware manufacturers, this provides two strategic directions-creating special accelerators for the Al and HPC or minimizing development costs by creating accelerators suitable for the two areas. A common way to support different size types in the hardware is for each integer length (such as AMD® CDNA™ Matrix Core

Technology) to implement a separate multiply accumulator (MAC) unit. However, due to partially unused hardware and higher power consumption, this usually makes a final product less competitive compared with the matrix multiplication accelerator dedicated for a particular area.

SUMMARY

[0003] Embodiments of the present application provide a system and a method for matrix multiplication, which provide a reconfigurable multi-size matrix multiplication support.

[0004] According to a first aspect, provided is a system for matrix multiplication, including a forward conversion unit, a modular arithmetic unit and a reverse conversion unit, where the forward conversion unit is configured to: receive binary input values and a control signal, where the control signal is configured to indicate a size type of the input values; make a forward conversion on the input values according to the size type to obtain converted values of the input values, where a converted value of each input value is a set of residues of the input value in a residue number system (RNS); and output the converted values to the modular arithmetic unit; where the modular arithmetic unit is configured to: receive the converted values from the forward conversion unit; perform a modular arithmetic operation on the converted values according to a set of modulos of the RNS to obtain operation results; and output the operation results to the reverse conversion unit; where the reverse conversion unit is configured to: receive the operation results and the control signal; and make a reverse conversion on the operation results according to the control signal to obtain the binary output values, where the binary output values and the binary input values have the same size type.

[0005] As an example, the size type includes one of the following types: a 64-bit type, a

32-bit type or a 16-bit type.

[0006] In addition, as an example, the reverse conversion unit is configured to make a reverse conversion on the operation results according to the control signal and Chinese

Remainder Theorem (CRT) to obtain the binary output values. Optional, the CRT also can be replaced with extended CRT (EXCRT) or Mixed-Radix Conversion (MRC).

[0007] According to the system proposed by the present application, a residue number system (RNS) is configured to enable a multi- size support in matrix multiplication hardware acceleration. The forward conversion unit and the reverse conversion unit enables the multi- size support under a dedicated control signal. An extension for the forward conversion unit of the RNS allows to interpret a 64-bit input value differently depending on a control signal value, and perform modulo reduction operations for a single 64-bit value, or two 32-bit values or four

16-bit values. An extension for the reverse conversion unit of the RNS based on Chinese

Remainder Theorem (CRT) (merely an example) allows to reconstruct different size types of values using efficient hierarchical controlled accumulation. As a result, the proposed system for the matrix multiplication provides the multi-size support for the matrix multiplication without increasing hardware area and implements less power consumption.

[0008] In some implementation manners, the forward conversion unit includes M multiplexers which corresponds to M modulo reduction unit groups, where the system supports value processing of multiple size types, the multiple size types include a first size type and a second size type, and the first size type corresponds to a maximum size that supported by the system; in the case that the control signal indicates the first size type, M multiplexers obtain each of the binary input values as an input of the corresponding modulo reduction unit groups respectively; or in the case that the control signal indicates the second size type, the M multiplexers obtain part bits of each of the binary input values as an input of the corresponding modulo reduction unit groups respectively, M is an integer greater than or equal to 2.

[0009] In some implementation manners, each of the M modulo reduction unit groups comprises P modulo reduction units, P is an integer greater than or equal to 2.

[0010] As an example, M=4, P=4, that is, the forward conversion units includes four modulo reduction unit groups, and each of four modulo reduction unit groups corresponding to the four multiplexers includes four modulo reduction units respectively.

[0011] In addition, M-P is the number of modulos contained in a modulo set corresponding to the RNS of the proposed application.

[0012] In some implementation manners, where the forward conversion unit includes four multiplexers and four modulo reduction unit groups, the four multiplexers are in one-to-one correspondence with the four modulo reduction unit groups; each of the four modulo reduction unit groups includes four modulo reduction units, and the four modulo reduction unit groups comprise sixteen modulo reduction units in all, where the sixteen modulo reduction units are in one-to-one correspondence with sixteen modulos of the RNS; where the four multiplexers are specifically configured to: receive the control signal; determine the size type of the input values as a 64-bit type in case of a value of the control signal being equal to a first value; obtain the input values, and output each input value to each of the sixteen modulo reduction units; and where the sixteen modulo reduction units are specifically configured to: perform a reduction operation on each input value to obtain sixteen converted values based on their corresponding modulos respectively, where each of the sixteen modulo reduction units obtains one converted value of the sixteen converted values.

[0013] According to this embodiment, an extension for a RNS forward conversion unit allows to interpret each 64-bit input value as a single 64-bit value based on a control signal value, and the forward conversion unit performs a forward conversion on the input 64-bit value to obtain residues of the input 64-bit value.

[0014] It should be noted that, sixteen is used as an example in this embodiment as it is easy to be divided by four, and it actually can be any number other than sixteen of the total modulo used. Furthermore, there is no strict requirement for having the same number of modulo s between different groups, for example, there may be three, four, five or other number of modulos in a group. The requirements only relate to the multiplication value of the modulo which is supposed to be higher than a binary range covered.

[0015] In some implementation manners, where the forward conversion unit includes four multiplexers and four modulo reduction unit groups, the four multiplexers are in one-to-one correspondence with the four modulo reduction unit groups; each of the four modulo reduction unit groups includes the four modulo reduction units, and the four modulo reduction unit groups comprise the sixteen modulo reduction units in all, where the sixteen modulo reduction units are in one-to-one correspondence with sixteen modulos of the RNS; where the four multiplexers are specifically configured to: receive the control signal; determine the size type of the input values as a 32-bit type in case of a value of the control signal being equal to a second value; where a first multiplexer and a third multiplexer of the four multiplexers obtain low 32 bits of each input value respectively, the first multiplexer outputs the low 32 bits to a corresponding first modulo reduction unit group, and the third multiplexer outputs the low 32 bits to a corresponding third modulo reduction unit group; where a second multiplexer and a fourth multiplexer of the four multiplexer obtain high

32 bits of each input value respectively, the second multiplexer outputs the high 32 bits to a corresponding second modulo reduction unit group, and the fourth multiplexer outputs the high

32 bits to a corresponding fourth modulo reduction unit group; and where the four modulo reduction units are specifically configured as follows: the first modulo reduction unit group and the third modulo reduction unit group perform a modulo reduction operation on the low 32 bits to obtain four converted values, respectively, based on four modulos corresponding to the four modulo reduction units contained in each of the first modulo reduction unit group and the third modulo reduction unit group, respectively; and the second modulo reduction unit group and the fourth modulo reduction unit group perform a modulo reduction operation on the high 32 bits to obtain four converted values, respectively, based on four modulos corresponding to the four modulo reduction units contained in each of the second modulo reduction unit group and the fourth modulo reduction unit group, respectively.

[0016] According to this embodiment, the extension for the RNS forward conversion unit allows to interpret each 64-bit input value as two 32-bit values based on the control signal value, and the forward conversion unit performs the forward conversion on the two 32-bit values, respectively, to obtain the residues of the two 32-bit values.

[0017] In some implementation manners, where the forward conversion unit includes four multiplexers and four modulo reduction unit groups, the four multiplexers are in one-to-one correspondence with the four modulo reduction unit groups; each of the four modulo reduction unit groups includes the four modulo reduction units, and the four modulo reduction unit groups comprise the sixteen modulo reduction units in all, where the sixteen modulo reduction units are in one-to-one correspondence with sixteen modulos of the RNS; where each of the four multiplexers is specifically configured to: receive the control signal; determine the size type of the input values as a 16-bit type in case of a value of the control signal being equal to a third value; obtain one of four segments constituting each input value, and output the obtained segment to a corresponding modulo reduction unit group, respectively; and where each of the modulo reduction unit groups is specifically configured to: perform a modulo reduction operation on the corresponding segment, respectively, based on four modulos corresponding to the four modulo reduction units contained in each of the four modulo reduction unit groups, to obtain four converted values, respectively.

[0018] According to this embodiment, the extension for the RNS forward conversion unit allows to interpret each 64-bit input value as four 16-bit values based on the control signal value, and the forward conversion unit performs the forward conversion on the four 16-bit values respectively, to obtain the residues of the four 16-bit values.

[0019] In some implementation manners, where the modular arithmetic unit includes sixteen multiply accumulator (MAC) units, the sixteen MAC units are in one-to-one correspondence with the sixteen modulos, and the sixteen MAC units are in one-to-one correspondence with the sixteen modulo reduction units; where each of the sixteen MAC units is specifically configured to: receive converted values from a corresponding modulo reduction unit, and perform modulo multiplication and a modulo accumulation operation on each converted value based on a corresponding modulo to obtain a corresponding operation result; and where when performing the modulo multiplication and the modulo accumulation operation, the sixteen MAC units form different groups in the following way: the sixteen MAC units form one group in case of the size type of the input values being

64-bit type, where the group is configured to perform the modulo multiplication and the modulo accumulation operation on the sixteen converted values from the sixteen modulo reduction units, and output sixteen operation results corresponding to the sixteen converted values; or the sixteen MAC units form two groups in case of the size type of the input values being

32-bit type, where each of the two groups includes eight MAC units, one of the two groups is configured to perform the modulo multiplication and the modulo accumulation operation on eight converted values and output eight operation results corresponding to the eight converted values, and the eight converted values comprise the four converted values from the first modulo reduction unit and the third modulo reduction unit, respectively; where the other of the two groups is configured to perform the modulo multiplication and the modulo accumulation operation on the other eight converted values and output eight operation results corresponding to the other eight converted values, and the other eight converted values comprise the four converted values from the second modulo reduction unit and the fourth modulo reduction unit, respectively; or the sixteen MAC units form four groups in case of the size type of the input values being

16-bit type, where each of the four groups includes four MAC units, the four groups are in one- to-one correspondence with the four modulo reduction unit groups, and each of the four groups is configured to perform the modulo multiplication and the modulo accumulation operation on the four converted values from the four modulo reduction units contained in the corresponding modulo reduction group and output four operation results corresponding to the four converted values, respectively.

[0020] In some implementation manners, where the reverse conversion unit supports reverse conversion of multiple size types, and the multiple size types further include a third size type, and the third size type corresponds to the minimum size supported by the system; the reverse conversion unit includes a first multiplexer set containing M P multiplexers and a second multiplexer set containing V multiplexers, the M P multiplexers are in one-to-one correspondence with M P operation results from the modular arithmetic unit respectively, and the V multiplexers are used for outputting the binary output values; in the case that the value of the control signal indicates the first size type, each of the V multiplexers obtains a segment of a modulo reduction result which is related to all of the M P operation results as an output respectively, and V segments corresponding to the V multiplexers reconstruct an binary output value corresponding to the first size type; or, in the case that the value of the control signal indicates the third size type, each of the V multiplexers obtains an modulo reduction result which is related to P operation results of the

M P operation results as an output, and the modulo reduction result obtained by each of the multiplexers reconstruct an binary output value corresponding to the third size type; or, in the case that the value of the control signal indicates the second size type, each of the V multiplexers obtains a modulo reduction result which is related to L operation results of the

M P operation results as an output, and the modulo reduction result obtained by each of the V multiplexers is a segment of an binary output corresponding to the second size type, L is an integral multiple of P.

[0021] As an example, M=4, P=4, and V=4, and the first multiplexer set includes 16 multiplexers, and the second multiplexer set includes 4 multiplexer.

[0022] In some implementation manners, where the first multiplexer set includes sixteen multiplexers, and the sixteen multiplexers are in one-to-one correspondence with the sixteen

MAC units, where the sixteen multiplexers are four multiplexer groups, and each of the four multiplexer groups includes the four multiplexers; where the sixteen multiplexers contained in the first multiplexer set are respectively configured to receive the control signal, and return a constant value from three pre-computed constant values according to the control signal, respectively; where the reverse conversion unit further includes a multiplier set, the multiplier set includes sixteen multipliers, the sixteen multipliers are in one-to-one correspondence with the sixteen multiplexers contained in the first multiplexer set, and the sixteen multipliers are in one- to-one correspondence with the sixteen MAC units; where each of the sixteen multipliers is configured to perform a multiplication operation on an output of a corresponding multiplier of the sixteen multipliers and an output of a corresponding MAC unit of the sixteen MAC units, and output a corresponding operation result; where the reverse conversion unit further includes three adder sets, a first adder set of the three adder sets includes four adders, where the four adders are in one-to-one correspondence with the four multiplexer groups, and an input of each adder of the four adders includes outputs of four multipliers corresponding to the four multiplexers in the corresponding multiplexer group; a second adder set of the three adder sets includes two adders, where a first adder of the two adders is configured to receive an output of the first adder and an output of the second adder contained in the first adder set, and a second adder of the two adders is configured to receive an output of the third adder and an output of the fourth adder contained in the first adder set; a third adder set of the three adder sets includes one adder, where the adder is configured to receive outputs of the two adders contained in the second adder set; where the second multiplexer set includes the four multiplexers, and an input of each multiplexer contained in the four multiplexers is obtained by performing the modulo reduction operation on outputs of the four adders contained in the first adder set, an input of each multiplexer contained in the four multiplexers is obtained by performing the modulo reduction operation on the outputs of the two adders contained in the second adder set, or an input of each multiplexer contained in the four multiplexers is obtained by performing the modulo reduction operation on an output of the adder contained in the third adder set; and where the four multiplexers contained in the second multiplexer set are configured to receive the control signal and determine a corresponding output value according to the control signal.

[0023] In some implementation manners, where the pre-computed three constant values of a i-th multiplexer of the sixteen multiplexers contained in the first multiplexer set comprise: where and i is a positive integer; where the i-th multiplexer is specifically configured to: output in case of the value of the control signal being equal to the first value; output in case of the value of the control signal being equal to the second value; and output in case of the value of the control signal being equal to the third value.

[0024] In some implementation manners, a set of the sixteen modulos of the RNS is where the sixteen modulos meet the following criteria:

[0025] In some implementation manners, where the four modulo reduction unit groups are in one-to-one correspondence with four modulo groups consisting of the sixteen modulos, and the four modulo groups are: and where

[0026] It should be noted that, values of the sixteen modulo s are taken merely as an example, and the criteria the sixteen modulo must meet has been listed as above.

[0027] In some implementation manners, where the four multiplexers contained in the second multiplexer set are specifically configured as follows: in case of the value of the control signal being equal to the first value, an output of each of the four multiplexers is an operation result by performing a modulo reduction operation s%M ⁶⁴ on the output of the adder contained in the third adder set, where s is the output of the adder contained in the third adder set, and outputs of the four multiplexers are four segments of the operation result, respectively, where the four segments are

[0028] In some implementation manners, where the four multiplexers contained in the second multiplexer set are specifically configured as follows: in case of the value of the control signal being equal to the second value, outputs of a first multiplexer and a second multiplexer of the four multiplexers are operation results by performing a modulo reduction operation on an output of the first adder contained in the second adder set, where t ₁ is the output of the first adder contained in the second adder set, and the outputs of the first multiplexer and the second multiplexer are two segments of the operation results, respectively, where the two segments are and outputs of a third multiplexer and a forth multiplexer of the four multiplexers are operation results by performing a modulo reduction operation on an output of the second adder contained in the second adder set, where t ₂ is the output of the second adder contained in the second adder set, and the outputs of the third multiplexer and the fourth multiplexer are two segments of the operation results, where the two segments are

[0029] In some implementation manners, where the four multiplexers comprised in the second multiplexer set are specifically configured to: in case of the value of the control signal equals to the third value, an output of the j-th multiplexer of the four multiplexer is an operation result by performing a modulo reduction operation on an output of the j-th adder comprised in the first adder set, where p _j is the output of the j-th adder, and j is an integer, and outputs of the four multiplexer are respectively

[0030] According to a second aspect, provided is a method for matrix multiplication, including: receiving binary input values and a control signal, where the control signal is configured to indicate a size type of element values of two matrices to be performed matrix multiplication; obtaining the element values according to the input values and the control signal; making a forward conversion on the element values to obtain converted values of the element values, where a converted value of each element value is a set of residues of the element value in a residue number system (RNS); performing a modular arithmetic operation on the converted values according to a set of modulos of the RNS to obtain operation results, where the modular arithmetic operation includes the matrix multiplication; and making a reverse conversion on the operation results according to the control signal to obtain binary output values, where the output values and the input values have the same size type, and an output matrix will consist of the output values.

[0031] In some implementation manners, where the obtaining the element values according to the input values and the control signal further includes: obtaining the element values by determining each input value as a single 64-bit element value in case of a value of the control signal being equal to a first value; obtaining the element values by splitting each input value into two 32-bit element values in case of the value of the control signal being equal to a second value; or obtaining the element values by splitting each input value into four 16-bit element values in case of the value of the control signal being equal to a third value.

[0032] In some implementation manners, where a set of sixteen modules of the RNS is and the sixteen modulos meet the following criteria:

[0033] According to a third aspect, a computing device is provided. The computing device has a function of implementing the method in the second aspect and any possible implementation manners of the second aspect. The function may be implemented by using a hardware. The hardware or the software includes one or more units corresponding to the foregoing function. Optional, the computing device is a chip or chip system.

[0034] According to a forth aspect, a chip is provided. The chip includes a plurality of circuits, where the plurality of circuits are configured to have functions of units included in a system according to the first aspect and any possible implementation manners of the first aspect.

DESCRIPTION OF DRAWINGS

[0035] One or more embodiments are exemplarily described by corresponding accompanying drawings, and these exemplary illustrations and accompanying drawings constitute no limitation on the embodiments. Elements with the same reference numerals in the accompanying drawings are illustrated as similar elements, and the drawings are not limiting to scale, in which:

[0036] FIG. 1 is a schematic block diagram of a system for multi-size support matrix multiplication according to the present application.

[0037] FIG. 2 is an example of a RNS basic process.

[0038] FIG. 3 is a schematic structural diagram of a forward conversion unit according to the present application.

[0039] FIG.4 is an example of forward conversion unit of the present application.

[0040] FIG. 5 is a schematic structural diagram of a modular arithmetic unit according to the present application.

[0041] FIG. 6 is a schematic structural diagram of a reverse conversion according to the present application.

[0042] FIG. 7 is a schematic diagram of a method for matrix multiplication according to the present application.

DESCRIPTION OF EMBODIMENTS

[0043] In order to understand features and technical contents of embodiments of the present disclosure in detail, implementations of the embodiments of the present disclosure will be described in detail below with reference to the accompanying drawings, and the attached drawings are only for reference and illustration purposes, and are not intended to limit the embodiments of the present disclosure. In the following technical descriptions, for ease of explanation, numerous details are set forth to provide a thorough understanding of the disclosed embodiments. One or more embodiments, however, may be practiced without these details. In other cases, well-known structures and apparatuses may be shown simplified in order to simplify the drawings.

[0044] 1. Residue Number System (RNS)

[0045] A RNS is defined by a set of k modules called moduli. The k modulos are generally supposed to be pairwise coprime, j. Let M be a product of all then an integer x in a range of [0,M — 1] is represented in the RNS by a set of its residues under Euclidean division by the moduli; that is, [0046] One of the greatest RNS feature is that addition and multiplication between pairs of corresponding remainders are independent and can be performed in parallel. In the present application, it is proposed to use the RNS to enable a hardware-efficient reconfigurable support for matrix multiplication with the integrated support for different integer types, including int64, int32 and inti 6.

[0047] A common solution to support various integer types is to add dedicated multiply accumulator (MAC) units for each size. An advantage of the solution is that it can perform calculations of various integer types and sizes in parallel. When only large (e.g., HPC) or small size (e.g., Al) integer calculations are required, hardware efficiency cannot be improved by equipping a dedicated MAC for each size. A similar idea that supports multi-size computing is to use smaller multiplication to create larger one. Many ways can be used to build a D X D multiplier by multipliers. Implementation of 64-bit multiplication via 4 x32-bit multiplications increases 17-20% of additional hardware and consumes 23-25% of power compared with dedicated 64-bit multiplication. The typical implementation of a dedicated 64- bit multiplier is 3.2-3.9 times larger than the area of a 32-bit multiplier, and in order to implement a 64-bit multiplier, an additional 128-bit accumulator is required. A reconfigurable multi-size feature by splitting D x D multiplier into multipliers requires a final value to be fully reconstructed as result of a multiplication operation, which has a significant additional cost in the hardware.

[0048] In view of this, a system for matrix multiplication is proposed, and the proposed system provides a multi-size matrix integer multiplication support without increasing hardware area and implements better power consumption compared with regular 64-bit integer matrix multiplication.

[0049] The present application proposes to use a residue independent computation feature of the RNS in order to provide the multi-size support for the matrix multiplication. A main idea of the proposed solution by the present application is to split 64-bit multiplication into 16 modular multiplications, which has a set of advantages. The proposed solution is supposed to be used in a system for matrix multiplication hardware by switching all multiplication and accumulation operations to the RNS. While switching to the RNS requires additional forward conversion and reverse conversion costs, in the case of the matrix multiplication, it is ignored because the number of conversion operations is one order of magnitude less than the number of multiplication and addition.

[0050] The following describes the proposed solution of the present application.

[0051] FIG.1 is a schematic block diagram of a system for multi-size support matrix multiplication according to the present application. As shown in FIG.l, a system (100) includes a forward conversion unit (110), a modular arithmetic unit (120) and a reverse conversion unit

(130). The forward conversion unit (110) is configured to receive binary values of input matrices A, B, and perform a forward conversion on the binary values to obtain converted values, that is, perform a binary number system (BNS) to a RNS conversion. Additionally, the forward conversion unit (110) interprets an input value differently depending on an input control signal of the system (100). In this application, a 64-bit input value is interpreted by the forward conversion unit (110) as a single 64-bit value, two 32-bit values or four 16-bit values according to a value of the control signal (expressed by a control signal value in the following embodiments). For example, if the control signal value is equal to 0, the 64-bit input value is interpreted to a single 64-bit value, or if the control signal value is equal to 1, the 64-bit input value is interpreted to two 32-bit values, or if the control signal value is equal to 2, the 64-bit input value is interpreted to four 16-bit values. The forward conversion unit (110) outputs the converted values to the modular arithmetic unit (120). The modular arithmetic unit (120) performs a modular arithmetic operation on the converted values to obtain an operation result based on the control signal. For the matrix multiplication, the modular arithmetic operation includes modular multiplication and modular accumulation. The modular arithmetic unit (120) outputs the operation result to the reverse conversion unit (130). The reverse conversion unit

(130) is configured to perform a reverse conversion on the operation result according to the control signal value and Chinese Remainder Theorem (CRT) to reconstruct binary output values of an output matrix C. Specifically, the reverse conversion is a conversion from the RNS to the

BNS. In the proposed solution, all of the multiplication and accumulation operations are performed in the RNS.

[0052] FIG. 2 is an example of a RNS basic flow. As shown in FIG.2, in RNS, a value is converted into k residues by performing a modular arithmetic operation on the value based on a set of k modulos. After a forward conversion, binary arithmetic operations could be converted into arithmetic operations under the RNS. For a residue number system which has a set of modulos for input matrices A and B, binary values a _ij and b _ij representing matrix elements satisfying a dynamic range can be represented as respectively. During matrix multiplication, elements of matrix A are first multiplied to elements of matrix B: and when an operation result Z also satisfies the dynamic range, elements of resulting matrix Z can be represented as k residues: which then converted to binary value.

[0053] FIG. 3 is a schematic structural diagram of a forward conversion unit according to the present application. As shown in FIG.3, a forward conversion unit includes four multiplexers and four modulo reduction unit groups, where each modulo reduction unit group includes four modulo reduction units, so the four modulo reduction unit groups include sixteen modulo reduction units in all. As shown in FIG.3, the four multiplexers are MUX 1, MUX2,

MUX3 and MUX4, respectively, and the sixteen modulo reduction units are modulo reduction unit 1, modulo reduction unit 5, ..., and modulo reduction unit 16, respectively. The sixteen modulo reduction units are in one-to-one correspondence with sixteen modulos provided by the present application, and a set of the sixteen modulos are represented as

[0054] An input value A (64 bits) represents a single 64-bit value, or two 32-bit values or four 16-bit values depending on a control signal (as CTRL shown in FIG.3) value. Examples are given as follows:

[0055] (1) CTRL=0, the input value A represents a single 64-bit value, which is represented here as A[63:0];

[0056] (2) CTRL=1, the input value A represents two 32-bit values, which is represented here as {A[63:32], A[31:0]};

[0057] (3) CTRL=2, the input value A represents four 16-bit values, which is represented here as {A[63:48], A[47:32], A[31 : 16], A[15:0]}. [0058] It should be understood that, if the input value represents two 32-bit values, the two

32-bit values are low 32 bits and high 32 bits of the input value (64 bits), respectively, and if the input value represents four 16-bit values, the four 16-bit values are four segments of the input value (64 bits), respectively, and each of the four segments includes 16 bits. In addition,

A is an example of an input value, actually, there are a large of input values of two matrices that need to be performed matrix multiplication.

[0059] As shown in FIG.3, the forward conversion is based on four multiplexers, which provide the appropriate inputs for the sixteen modulo reduction units based on the CTRL signal value. Four groups of modulo reduction units make reduction for the 64-bit input value.

[0060] An example of the set of the sixteen modulos is given below.

[0061] Consider that the following set of pairwise co-prime modulos has the following features:

[0068]

[0069] Therefore, the entire set of modulos can be used for 64-bit multiplication. When

CTRL=0, all the sixteen modulo reduction units will get A. In this case, outputs of the four multiplexers, that is, A ₀ [63 :0], A ₁ [63:0], A ₂ [63:0] and A ₃ [63:0], are the same, that is, A.

[0070] Two subsets of the modulos can be used for 32-bit multiplication, that is, a first subset is represented as and a second subset is represented as When CTRL=1, the first subset is handled by the first and the third multiplexer, both of them will return low 32 bits of the input value A, and the second subset is handled by the second and the fourth multiplexer, both of them will return high 32 bits of the input value A. In this case, the first and the third group will get A[31 :0], and the second and the fourth group will get A[63:32],

[0071] Four subsets of the modulos can be used for 16-bit multiplication, that is,

{ m ₁ , m ₅ ,m ₉ , m ₁₃ }=[512, 487, 473, 151], { m ₃ , m ₇ , m ₁₁ ,m ₁₅ }=[509, 481, 431, 137],

{m ₂ , m ₆ ,m ₁₀ , m ₁₄ }=[511, 485, 467, 139], {m ₄ , m ₈ , m ₁₂ , m ₁₄ }=[489, 479, 167, 131], When

CTRL=2, each multiplexer will return corresponding 16 bits of the input value A, and each group of modulo reduction units will process a single 16-bit value. In this case, the first group will get A[15:0], the second group will get A[31 :16], the third group will get A[47:32], and the fourth group will get A[63:48].

[0072] In the above different cases, the modulo reduction units perform a modulo reduction operation on values received from the corresponding multiplexer to obtain converted values in the RNS corresponding to input values. It should be noted that the converted values actually are RNS residues of the input values.

[0073] For example, when CTRL=0, the input value is a single 64-bit value, and each modulo reduction unit gets the single 64-bit value, and then process the single 64-bit value based on corresponding modulo, respectively. A modulo reduction unit 1 performs the modulo reduction operation on the single 64-bit value based on a modulo corresponding to the modulo reduction unit 1, that is mi, and modulo reduction unit 5 performs the modulo reduction operation on the single 64-bit value based on a modulo corresponding to a modulo reduction unit 5, that is m ₅ , and so on. The sixteen modulo reduction units will return sixteen residues, that is {x ₁ , x ₂ ,x ₃ , ..., x ₁₆ } shown in FIG.3.

[0074] When CTRL=1, the input value is two 32-bit values, the modulo reduction units of the first and the third group will get low 32 bits of the input value, which is called a first 32-bit value, and modulo reduction units of the second and the fourth group will get high 32 bits of the input value, which is called a second 32-bit value. The modulo reduction units of the first and the third group process the first 32-bit value based on the corresponding modules, respectively. Specifically, each modulo reduction unit of the first and the third group performs a modulo reduction operation on the first 32-bit value based on corresponding modulo to obtain a corresponding residue. Each modulo reduction unit of the second and the fourth group performs the modulo reduction operation on the second 32-bit value based on the corresponding modulo to obtain the corresponding residue. As a result, the first 32-bit value is converted into a set of residues in the RNS by a set of the modules {m ₁ , m ₅ , m ₉ , m ₁₃ , m ₃ , m ₇ , m ₁₁ , m ₁₅ }, where the set of the residues is {xi, xs,X9, X13, X2, X6,xio, X14}, and the second 32-bit value is also converted into a set of residues in the RNS by the set of modulos

{m ₂ ,m ₆ , m ₁₀ , m ₁₄ , m ₄ , m ₈ , m ₁₂ , m ₁₆ }, where the set of the residues is {x ₂ , x ₆ ,x ₁₀ , x ₁₄ , x ₄ , x ₈ , x ₁₂ , x ₁₆ }.

[0075] When CTRL=2, the input value is four 16-bit values. Each group of modulo reduction units will get a corresponding single 16-bit value, and then process the single 16-bit value. Specifically, the first group performs the modulo reduction operation by a set of modulo, that is to obtain a set of residues, that is and the second group performs the modulo reduction operation by a set of modulo, that is to obtain a set of residues, that is, and so on.

[0076] In addition, in FIG.3, “32’b0” or “48’b0” is from Verilog notation, “32’b0” means

“32 bits with 0”, and “48'b0” means “48 bits with 0”. The first multiplexer is taken as an example, {32 ’b0, A[31 :0]} means the 64-bit input value is performed only for the least significant 32 bits, that is, the low 32 bits of the 64-bit input value, and the most significant 32 bits of the 64-bit input value are regarded as zero by the first multiplexer (as shown in MUX1).

Another example is as follows, {48’b0, A[15:0]} means the 64-bit input value is performed only for the least significant 16 bits, and the most significant 48 bits of the 64-bit input value are regarded as zero by the first multiplexer. “32’b0” or “48’b0” corresponding to the other multiplexers has the similar meaning, which can be understood by those skilled in the art according to above examples, and is not explained here one by one.

[0077] Independent of an operation mode (a CTRL signal), a delay of the forward conversion will remain unchanged. This is mainly because all the modulo reduction units work with 64-bit input values independently on CTRL signal value. When only 16 bits are supposed to be converted, the most significant bits are just filled by 0.

[0078] It should be understand that, the architecture shown in FIG. 3 is only an example of the forward conversion unit, and the architecture is applied in the case that the system supports

64-bit size type, 32-bit size type and 16-bit size type. As another example, based on the set of the 16 modulos listed above of the present application, if only 64-bit size type and 32-bit size type are supported, the architecture of the forward conversion unit may be as shown in FIG. 4. [0079] FIG.4 is an example of forward conversion unit of the present application. It can be found in FIG.4 that the forward conversion unit includes two multiplexers, that is, MUX 1 and

MUX 2. Control signals indicate 64-bit size type or 32-bit size type. In the case that the control signal indicates a 64-bit size type, both the MUX 1 and MUX 2 get the input value A, and input value A will be inputted into modulo reduction unit groups corresponding to MUX 1 and MUX

2 respectively. In this case, A0=A1. In the case that the control signal indicates a 32-bit size type, the input value A will be interpreted as two 32-bit values, and MUX 1 gets the high 32 bits of the input value, and the MUX 2 gets the lower 32 bits of the input value. The high 32 bits of the input value will be inputted into the modulo reduction unit group corresponding to the MUX 1, and low 32 bits of the input value will be inputted into the modulo reduction unit group corresponding to the MUX 2. It can be seen that, in this example, MUX 1 and MUX 2 are in correspondence with two modulo reduction unit groups as shown in FIG.4, where each modulo reduction unit group includes 8 modulo reduction units. The 16 modulo reduction units are in one to one correspondence with 16 modulos of the RNS proposed by the present application.

[0080] Other structures of the system proposed by the present application will be described below by taking the architecture shown in FIG. 3 as an example of the forward conversion unit.

[0081] FIG.5 is a schematic structural diagram of a modular arithmetic unit according to the present application. As shown in FIG.5, a modular arithmetic unit includes sixteen multiply accumulator (MAC) units, and the sixteen MAC units are in one-to-one correspondence with sixteen modulos, i.e., provide by the present application. Each MAC unit includes a modulo adder and a modulo multiplier. Since a modulo operation can be executed independently, no additional multi-size support is required in the MAC unit except a dedicated mode (in other words, a dedicated signal) for 8-bit addition and multiplication, which should bypass reduction. The sixteen MAC units are implicitly grouped based on a control signal processing a single 64-bit value, or two 32-bit values or four 16-bit values.

[0082] It should be understood that, each modulo multiplier makes a calculation of = and each modulo adder makes a calculation of where and i is an integer. Here, x _i is a i-th residue of a residue set of an element value of a matrix A, and y _i is a i-th residue of an element value of a matrix B.

[0083] The sixteen MAC units are implicitly grouped based on the control signal value, processing the single 64-bit value, or two 32-bit values or four 16-bit values. For example, if

CTRL=0, the sixteen MAC units form a group, and process the single 64-bit value, and if

CTRL=1, the sixteen MAC units form two groups, one of the two groups includes eight MAC units corresponding to 8 modulos, that is, and the other group includes eight MAC units corresponding to the other 8 modulos, that is,

[0084] FIG. 6 is a schematic structural diagram of a reverse conversion according to the present application. As shown in FIG.6, such structure represents a reconstruction mechanism of a single 64-bit value, or two 32-bit values or four 16-bit binary values from RNS using the according to a control signal. Inputs for a reverse conversion unit are arithmetic operation results z _i , which are first multiplied by a pre-computed constant and the constant is different for each modulo and CTRL signal value. The CRT for reverse conversion is merely taken as an example. The diagram of FIG.6 shows how to enable multi-size support using CRT. However, the present application probably may not be limited to the CRT method for reverse conversion since other methods, such as extended CRT (EXCRT) or Mixed-Radix Conversion (MRC), can also be used to enable multi- size support.

[0085] Specifically, as shown in FIG.6, the reverse conversion unit includes a first multiplexer set and a second multiplexer set. The first multiplexer set includes sixteen multiplexers, where the sixteen multiplexers are in one-to-one correspondence with sixteen

MAC units, and the sixteen multiplexers are divided into four groups, and each group includes four multiplexers. The sixteen multiplexers are configured to receive a control signal, and return a pre-computed constant value from three pre-computed constant values.

[0086] The reverse conversion unit further includes a multiplier set, and the multiplier set includes sixteen multipliers, where the sixteen multipliers are in one-to-one correspondence with the sixteen multiplexers, and the sixteen multipliers are in one-to-one correspondence with the sixteen MAC units. Each multiplier of the sixteen multipliers contained in the multiplier set is configured to perform a multiplication operation on an output of the corresponding multiplexers and an output of the corresponding MAC unit.

[0087] The reverse conversion unit further includes three adder sets. A first adder set of the three adder sets includes four adders, where the four adders are in one-to-one correspondence with the four multiplexer groups, and an input of each adder of the four adders includes outputs of four multipliers corresponding to the four multiplexer groups.

[0088] A second adder set of the three adder sets includes two adders, where a first adder of the two adders is configured to receive an output of a first adder and an output of a second adder contained in the first adder set, and a second adder of the two adders is configured to receive an output of a third adder and an output of a fourth adder contained in the first adder set.

[0089] A third adder set of the three adder sets includes an adder, where the adder is configured to receive outputs of the two adders contained in the second adder set.

[0090] The second multiplexer set includes four multiplexers, where an input of each multiplexer is an operation result by performing a modulo reduction operation on outputs of the four adders contained in the first adder set, or outputs of the two adders contained in the second adder set, or an output of the adder contained in the third adder set.

[0091] The four multiplexers included in the second multiplexer set are configured to receive the control signal, and determine a corresponding output value according to the control signal value.

[0092] As shown in FIG.6, each multiplexer contained in the first multiplexer set will return a corresponding constant value, then each is multiplied by a constant, resulting in products being accumulated in groups by four modulos. A result of accumulation moves towards in the following directions:

(1) If CTRL=2 (represents 16-bit values), reduction by a corresponding constant value is applied on the result of the accumulation, and this leads to a final 32-bit value;

(2) If CTRL=1 (represents 32-bit values), it is accumulated with the neighboring group sum of products and then reduced by a corresponding constant value and this leads to a final 64-bit value;

(3) All the group sum of products are accumulated and then reduced by value this leads to a final 128-bit value.

[0093] The final set of multiplexers (that is, the second multiplexer set) forms correct output values according to a CTRL signal value, that is, the single 128-bit value, or two 64-bit values or four 32-bit output values.

[0094] It can be seen from FIG.6 that the three pre-computed constant values of the i-th multiplexer of the first multiplexer set are and z is a positive integer. The i-th multiplexer is specifically configured to output if the control signal value is equal to a first value, or output if the control signal value equals to the first value, or output if the control signal value is equal to the third value. As stated above, the three pre-computed constant values of the i-th multiplexer of the sixteen multiplexers are actually, the three pre-computed constant values of the i-th multiplexer are respectively, where for j is equal to 1 for and j is equal to 2 for for j is equal to 1 for j is equals to 2 for j is equal to 3 for and j is equal to 4 for That is, the subscript of the three pre-computed constant values relates to the corresponding group of modulo. For example, for 64-bit input type, there should be no subscript at all, that is, is actually For 32-bit input type, the subscript can be 1 or 2, that is, is actually and a value of the subscript depends on the group of modulo to which the m _i , belongs. It has been known that, there are two groups of modulo for 32-bit input type, since belongs to a first group of modulo, for M and belongs to a second group of modulo, for For 16-bit input type, the subscript can be 1, 2, 3 or 4, that is, is actually and the value of the subscript depends on the group of modulo to which the m _i belongs. There are four groups of modulo for 16-bit input type, are in one-to-one correspondence with the four groups, hence, for for and for

[0095] The four multiplexers contained in the second multiplexer set are specifically configured as follows:

[0096] if the control signal value is equal to the first value, an output of each of the four multiplexers is an operation result on an output of the adder contained in the third adder set by performing a modulo reduction operation, that is, where s is the output of the adder contained in the third adders set, here means “M for 64-bit input type”, the outputs of the four multiplexers are four segments of the modulo reduction operation result

(“modulo reduction result” for short somewhere), and the four segments are respectively;

[0097] if the control signal value is equal to the second value, outputs of a first multiplexer and a second multiplexer of the four multiplexers are operation results by performing the modulo reduction operation, that is on an output of a first adder contained in the second adder set, where is the output of the first adder contained in the second adder set, here means “ M for 32-bit input type”, the subscript (1) of relates to a first modulo group for 32-bit input type, and the outputs of the first multiplexer and the second multiplexer of the four multiplexers are two segments of the modulo reduction operation results, and the two segments are respectively. Outputs of a third multiplexer and a fourth multiplexer are operation results by performing the modulo reduction operation, that is, on an output of a second adder contained in the second adder set, where t ₂ is the output of the second adder contained in the second adder set, means “M for 32-bit input type”, and the subscript (2) of relates to a second modulo group for 32-bit input type. The outputs of the third multiplexer and the fourth multiplexer of the four multiplexers are two segments of the modulo reduction operation results, and the two segments are respectively;

[0098] if the control signal value is equal to the third value, an output of a j-th multiplexer of the four multiplexers is a modulo reduction operation result by performing the modulo reduction operation, that is, on an output of the j -th adder contained in the first adder set, where p _j is the output of the j-th adder, and j is an integer, here means “M for 16-bit input type”, and the subscript (j) of relates to a first, second, third or fourth modulo group for 16-bit input type. The outputs of the four multiplexers are respectively.

[0099] Alternatively, an output matrix will have 2x larger size type for the elements, which can be configured to properly handle overflows or implement fixed-point data types.

[00100] This application has the following advantages:

(1) The same set of t modular multipliers and adders can be configured to enable a single

64-bit, two 32-bit, four 16-bit and sixteen 8-bit MAC units by grouping modulos properly.

(2) Hardware area and power consumption of sixteen 8-bit/9-bit modular multipliers (need to fully cover [ 0, 2 ¹²⁸ - 1 ] binary range) is less than area and power consumption of a single 64- bit multiplier due to complex carry propagation logic for 64-bit adders and multipliers.

[00101] There is no any dedicated multi-size support needed in the modular multipliers except dedicated handling of 8-bit multiplication, which can simply disable modular reduction in the present application. The logic of other size types is fully handled by RNS to BNS/ BNS to RNS converters. A separate control signal is added to the converters to maintain all possible input/output types that a matrix multiplier can handle. Depending on the control signal value, an input 64-bit value can be interpreted as l x64-bit value, or 2x32-bit values, or 4x 16-bit values or 16x8-bit values. [00102] A RNS forward conversion is implemented in a way to find a residue for 64-bit value for each modulo, this logic can be fully configured for different size types to deal with 64-bit input values, and it needs to simply expand the smaller size. The latency of forward conversion for all the integer size types will remain the same. A proper grouping of modulos is defined architecturally and fixed in the hardware. For 8-bit input type, forward conversion is simply bypassed.

[00103] Reverse conversion is based on hierarchical accumulation of intermediate values, where 64-bit size type requires the accumulation across all the layers, while 32-bit size type avoids the last level of the accumulation, 16-bit size type avoids the last two levels of the accumulation, and 8-bit size type bypass the reverse conversion.

[00104] Forward conversion and reverse conversion take more area and higher power consumption than modulo multipliers, however, they are only needed to convert all the values of input matrices and convert values of output matrix back. For a nXn matrix, the number of forward converters needed is 2x n ² , and the number of reverse converters needed is n ² , while assuming that the matrix is multiplied in one cycle, a total number of the modular arithmetic units is n ³ , which allows all costs of forward / reverse conversion to be hidden under the benefits of small modular multipliers. If a matrix multiplication hardware accelerator operates with a single row and a single column in one cycle, a ratio between converters and the modular arithmetic units will remain the same, that is, 2x n forward converters, n reverse converters, and the total number of the modular arithmetic units is n ² .

[00105] RNS multipliers (for the whole modulo set converting [0, 2 ¹²⁸ -1] range) can be implemented by occupying 40% less in area than a single 64-bit multiplier and consuming 50% less power. Assuming hardware area is occupied by 64 x 64 multiplier and its power consumption is 1, then we can build the following table with the costs of RNS based matrix multiplication (all the numbers below are results of actual experiments using the best known algorithms for forward/reverse conversion and modulo reduction).

Table 1 Therefore, a RNS matrix multiplication area is 2 x 0.7n ² +0.6n ³ +1.6n ² versus n When n=8, the RNS matrix multiplication area is 0.975 of 64x64 matrix multiplication area. When n=16, the RNS matrix multiplication area is 0.79 of 64x64 matrix multiplication area.

RNS matrix multiplication power consumption is versus When n=8, the RNS matrix multiplication power consumption is 0.775 of 64x64 matrix multiplication power consumption. When n=16, the RNS matrix multiplication power consumption is 0.64 of 64x64 matrix multiplication power consumption. It should be noted that these numbers can differ depending on actual technique process.

[00106] Accordingly, this application also provides a method for matrix multiplication.

[00107] FIG.7 shows a schematic diagram of a method for matrix multiplication according to the present application. The method can be performed by a system for matrix multiplication proposed by the present application. A method (600) specifically includes the following steps:

[00108] Step 610: receiving binary input values and a control signal, where the control signal is configured to indicate a size type of the element values of two matrices performing matrix multiplication.

[00109] As an example, the size type includes one of the following types: a 64-bit type, a

32-bit type or a 16-bit type.

[00110] Step 620: obtaining the element values according to the input values and the control signal, for example, obtaining the element values by determining each input value as a single

64-bit element value in case of a control signal value is equal to a first value, or obtaining the element values by splitting each input value into two 32-bit element values in case of a control signal value is equal to a second value, or obtaining the element values by splitting each input value into four 16-bit element values in case of a control signal value is equal to a third value.

[00111] Step 630: making a forward conversion on the element values to obtain converted values of the element values, where a converted value of each element value is a set of residues of the element value in a residue number system (RNS).

[00112] Step 640: performing a modular arithmetic operation on the converted values to obtain operation results, where the modular arithmetic operation includes matrix multiplication. [00113] Step 650: making a reverse conversion on the operation results according to the control signal to obtain binary output values, where the output values and the input values have the same size type, and an output matrix will consist of the output values.

[00114] As an example, the system makes the reverse conversion on the operation results by using the Chinese remainder theorem (CRT), EXCRT or MRC according to the control signal to obtain binary output values.

[00115] All related contents of steps in a method embodiment have been described in detail in the foregoing system embodiment, and in order to avoid repetition, details are not repeated here.

[00116] The present application also provides a chip or chip system including a plurality of circuits, and the plurality of circuits are configured to have functions of units included in a system for matrix multiplication as provided in the present application.

[00117] In the several embodiments provided in this application, it should be understood that the disclosed system and method may be implemented in other manners. For example, the described apparatus embodiment is merely an example. For example, the unit division is merely logical function division and may be other division in actual implementation. For example, a plurality of units or components may be combined or integrated into another system, or some features may be ignored or not performed. In addition, the displayed or discussed mutual couplings or direct couplings or communication connections may be implemented through some interfaces. The indirect couplings or communication connections between the apparatuses or units may be implemented in electronic, mechanical, or other forms.

[00118] The units described as separate parts may be or may not be physically separate, and parts displayed as units may be or may not be physical units, may be located in one position, or may be distributed on a plurality of network units. Some or all of the units may be selected based on actual requirements to achieve the objectives of the solutions of the embodiments.

[00119] In addition, functional units in the embodiments of this application may be integrated into one processing unit, or each of the units may exist alone physically, or two or more units are integrated into one unit.

[00120] The foregoing descriptions are merely specific implementations of this application, but are not intended to limit the protection scope of this application. Any variation or replacement readily figured out by a person skilled in the art within the technical scope disclosed in this application shall fall within the protection scope of this application. Therefore, the protection scope of this application shall be subject to the protection scope of the claims.