Fused modular multiply and add operation
View Patent ↗A computer-implemented method includes receiving performing a fused modular multiply and add operation to compute d=((a*b)+c) % p, wherein a, b, and c, are provided as a set of operands. A first multiply-and-accumulate unit computes a binary multiplication to compute a*b. A second multiply-and-accumulate unit computes a first intermediate result by updating a result of the binary multiplication using p. An accumulator of a third multiply-and-accumulate unit is initialized with c. The third multiply-and-accumulate unit computes a second intermediate result using the first intermediate result and c. An adder unit subtracts a portion of the second intermediate result from a portion of the result of the binary multiplication. The output of the adder is provided as a result of the fused modular multiply and add operation.
1. A computer-implemented method comprising:
receiving, by a processing unit, an instruction to perform a fused modular multiply and add operation to compute d=((a*b)+c) % p, wherein a, b, and c are provided as a set of operands;
computing, by a first multiply-and-accumulate unit, a binary multiplication to compute a*b;
computing, by a second multiply-and-accumulate unit, a first intermediate result by updating a result of the binary multiplication using p;
initializing an accumulator of a third multiply-and-accumulate unit with c;
computing, by the third multiply-and-accumulate unit, a second intermediate result using the first intermediate result and c;
subtracting, by an adder, a portion of the second intermediate result from a portion of the result of the binary multiplication; and
outputting, as a result of the fused modular multiply and add operation, an output of the adder.
2. The computer-implemented method of claim 1 , wherein the adder has a bit-width wider than a multiplier in the first multiply-and-accumulate unit.
3. The computer-implemented method of claim 2 , wherein the bit-width of the adder is one more than the bit-width of the first multiplier.
4. The computer-implemented method of claim 1 , wherein initializing the accumulator of the third multiply-and-accumulate unit with c comprises storing a value of c in lower order bits of the accumulator.
5. The computer-implemented method of claim 1 , wherein computing the first intermediate result comprises performing a second binary multiplication of the result of the binary multiplication of a*b with a precomputed constant.
6. The computer-implemented method of claim 5 , wherein computing the second intermediate result comprises multiplying higher order bits of the first intermediate result with modulus p, wherein a value of p is stored in the third multiply-and-accumulate unit prior to invoking the instruction.
7. The computer-implemented method of claim 1 , further comprising correcting the output of the adder to ensure that the output is between 0 and p.
8. A system comprising:
a set of registers; and
a set of multiply-and-accumulate units comprising three multiply-and-accumulate units, each comprising a multiplier and an accumulator, the set of multiply-and-accumulate units coupled with the set of registers, the set of multiply-and-accumulate units is configured to perform a method for performing a fused modular multiply and add operation to compute d=((a*b)+c) % p, wherein a, b, and c are provided in the set of registers, and wherein performing the fused modular multiply and add operation comprises:
computing, by a first multiply-and-accumulate unit, a binary multiplication to compute a*b;
computing, by a second multiply-and-accumulate unit, a first intermediate result by updating a result of the binary multiplication using p;
initializing an accumulator from a third multiply-and-accumulate unit with c;
computing, by the third multiply-and-accumulate unit, a second intermediate result using the first intermediate result and c;
subtracting, by an adder, a portion of the second intermediate result from a portion of the result of the binary multiplication; and
outputting, as a result of the fused modular multiply and add operation, an output of the adder.
9. The system of claim 8 , wherein the adder has a bit-width wider than a multiplier in the first multiply-and-accumulate unit.
10. The system of claim 9 , wherein the bit-width of the adder is one more than the bit-width of the first multiplier.
11. The system of claim 8 , wherein initializing the accumulator from the third multiply-and-accumulate unit with c comprises storing a value of c in lower order bits of the accumulator.
12. The system of claim 8 , wherein computing the first intermediate result comprises perform a second binary multiplication of the result of the binary multiplication of a*b with a precomputed constant.
13. The system of claim 12 , wherein computing the second intermediate result comprises multiplying higher order bits of the first intermediate result with modulus p, wherein value of p is stored in the third multiply-and-accumulate unit prior to invoking an instruction to perform the fused multiply and add operation.
14. The system of claim 8 , further comprising correcting the output of the adder to ensure that the output is between 0 and p.
15. A computer program product comprising a computer-readable memory that has computer-executable instructions stored thereupon, the computer-executable instructions when executed by a processor cause the processor to perform a method for performing a fused modular multiply and add operation to compute d=((a*b)+c) % p, wherein a, b, and c are provided as operands, and wherein performing the fused modular multiply and add operation comprises:
computing, by a first multiply-and-accumulate unit, a binary multiplication to compute a*b;
computing, by a second multiply-and-accumulate unit, a first intermediate result by updating a result of the binary multiplication using p;
initializing an accumulator from a third multiply-and-accumulate unit with c;
computing, by the third multiply-and-accumulate unit, a second intermediate result using the first intermediate result and c;
subtracting, by an adder, a portion of the second intermediate result from a portion of the result of the binary multiplication; and
outputting, as a result of the fused modular multiply and add operation, an output of the adder.
16. The computer program product of claim 15 , wherein the bit-width of the adder is one more than the bit-width of a multiplier in the first multiply-and-accumulate unit.
17. The computer program product of claim 15 , wherein initializing the accumulator from the third multiply-and-accumulate unit with c comprises storing a value of c in lower order bits of the accumulator.
18. The computer program product of claim 15 , wherein computing the first intermediate result comprises perform a second binary multiplication of the result of the binary multiplication of a*b with a precomputed constant.
19. The computer program product of claim 18 , wherein computing the second intermediate result comprises multiplying higher order bits of the first intermediate result with modulus p, wherein value of p is stored in the third multiply-and-accumulate unit prior to invoking an instruction to perform the fused multiply and add operation.
20. The computer program product of claim 15 , further comprising correcting the output of the adder to ensure that the output is between 0 and p.