Matrix multiplication in hardware using modular math
A first group of modulo result matrices corresponding to modulo of elements of a first matrix by each of a plurality of moduli is stored. A second group of modulo result matrices corresponding to modulo of elements of a second matrix by each of the plurality of moduli is stored. It is determined whether an element operation of a multiplication of the first matrix with the second matrix can be performed using a first hardware multiplication module rather than a second hardware multiplication module. In response to a determination that the element operation can be performed using the first hardware multiplication module, the element operation is performed using the first hardware multiplication module including by multiplying one or more corresponding elements from the first group of modulo result matrices with one or more corresponding elements from the second group of modulo result matrices.
1. A system, comprising:
a memory configured to:
store a first group of modulo result matrices corresponding to modulo of elements of a first matrix by each of a plurality of moduli; and
store a second group of modulo result matrices corresponding to modulo of elements of a second matrix by each of the plurality of moduli; and
an integrated circuit configured to:
determine whether an element operation of a multiplication of the first matrix with the second matrix using a first hardware multiplication module rather than a second hardware multiplication module is ensured to be accurate; and
in response to a determination that the element operation using the first hardware multiplication module is ensured to be accurate, perform the element operation using the first hardware multiplication module including by multiplying one or more corresponding elements from the first group of modulo result matrices with one or more corresponding elements from the second group of modulo result matrices.
2. The system of claim 1 , wherein the plurality of moduli includes numbers thirteen, fifteen, and sixteen.
3. The system of claim 1 , wherein the memory configured to store the first group of modulo result matrices and the second group of modulo result matrices is a random access memory.
4. The system of claim 1 , wherein the integrated circuit is configured to determine whether the element operation of the multiplication of the first matrix with the second matrix using the first hardware multiplication module is ensured to be accurate including by being configured to determine a first bit width associated with a result of the element operation and compare the first bit width with a second bit width associated with a product equal to the plurality of moduli multiplied with each other.
5. The system of claim 4 , wherein the integrated circuit is configured to determine the first bit width including by being configured to determine bit widths of elements of the first matrix and the second matrix and upper bounds associated with the bit widths of elements of the first matrix and the second matrix.
6. The system of claim 1 , wherein the integrated circuit is configured to determine whether the element operation of the multiplication of the first matrix with the second matrix using the first hardware multiplication module is ensured to be accurate including by being configured to determine whether Chinese remainder theorem associated conditions are met.
7. The system of claim 1 , wherein the element operation of the multiplication of the first matrix with the second matrix is a dot product operation.
8. The system of claim 1 , wherein the first hardware multiplication module includes a group of four-bit dot product multipliers.
9. The system of claim 1 , wherein the second hardware multiplication module is configured to handle larger bit-width numbers than the first hardware multiplication module.
10. The system of claim 1 , wherein the integrated circuit is configured to perform the element operation using the first hardware multiplication module further including by applying a reconstruction after multiplying the one or more corresponding elements from the first group of modulo result matrices with the one or more corresponding elements from the second group of modulo result matrices.
11. The system of claim 10 , wherein applying the reconstruction includes performing modulo operations to determine a group of remainders and multiplying each remainder from the group of remainders with a corresponding specified number from a group of specified numbers.
12. The system of claim 11 , wherein each specified number in the group of specified numbers is associated with a corresponding modulus from the plurality of moduli for which the specified number modulo the corresponding modulus equals one and the specified number modulo any other modulus from the plurality of moduli equals zero.
13. The system of claim 11 , wherein the first hardware multiplication module includes digital electronic circuits that are specifically adapted to perform multiplications associated with the group of specified numbers.
14. The system of claim 1 , wherein the integrated circuit is further configured to forward an output of either the first hardware multiplication module or the second hardware multiplication module by using a multiplexer.
15. The system of claim 1 , wherein the first matrix and the second matrix include unsigned integer elements.
16. The system of claim 1 , wherein the first matrix and the second matrix include eight-bit elements.
17. The system of claim 1 , wherein the determination that the element operation using the first hardware multiplication module is ensured to be accurate is based at least in part on an addition performed using an adder tree.
18. The system of claim 1 , wherein the first hardware multiplication module includes digital logic gate implementations that are specifically adapted to perform modulo operations associated with the plurality of moduli.
19. A method, comprising:
storing a first group of modulo result matrices corresponding to modulo of elements of a first matrix by each of a plurality of moduli;
storing a second group of modulo result matrices corresponding to modulo of elements of a second matrix by each of the plurality of moduli;
determining whether an element operation of a multiplication of the first matrix with the second matrix using a first hardware multiplication module rather than a second hardware multiplication module is ensured to be accurate; and
in response to a determination that the element operation using the first hardware multiplication module is ensured to be accurate, performing the element operation using the first hardware multiplication module including by multiplying one or more corresponding elements from the first group of modulo result matrices with one or more corresponding elements from the second group of modulo result matrices.
20. A computer program product, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:
storing a first group of modulo result matrices corresponding to modulo of elements of a first matrix by each of a plurality of moduli;
storing a second group of modulo result matrices corresponding to modulo of elements of a second matrix by each of the plurality of moduli;
determining whether an element operation of a multiplication of the first matrix with the second matrix using a first hardware multiplication module rather than a second hardware multiplication module is ensured to be accurate; and
in response to a determination that the element operation using the first hardware multiplication module is ensured to be accurate, performing the element operation using the first hardware multiplication module including by multiplying one or more corresponding elements from the first group of modulo result matrices with one or more corresponding elements from the second group of modulo result matrices.