Instruction support for performing montgomery multiplication
Techniques are disclosed relating to a processor including instruction support for performing a Montgomery multiplication. The processor may issue, for execution, programmer-selectable instruction from a defined instruction set architecture (ISA). The processor may include an instruction execution unit configured to receive instructions including a first instance of a Montgomery-multiply instruction defined within the ISA. The Montgomery-multiply instruction is executable by the processor to operate on at least operands A, B, and N residing in respective portions of a general-purpose register file of the processor, where at least one of operands A, B, N spans at least two registers of general-purpose register file. The instruction execution unit is configured to calculate P mod N in response to receiving the first instance of the Montgomery-multiply instruction, where P is the product of at least operand A, operand B, and R^−1.
1. A processor, comprising:
a control unit configured to issue instructions for execution, wherein the instructions are programmer-selectable from a defined instruction set architecture (ISA);
a general-purpose register file including a plurality of registers; and
an instruction execution unit configured to receive instructions issued by the control unit, wherein the received instructions include a first instance of a Montgomery-multiply instruction defined within the ISA, wherein the Montgomery-multiply instruction is executable by the processor to operate on at least operands A, B, and N residing in respective portions of the general-purpose register file, wherein at least one of operands A, B, N spans at least two of the plurality of registers, and wherein a size of the respective portions is indicated by a size parameter, and wherein the instruction execution unit is configured to calculate P mod N in response to receiving the first instance of the Montgomery-multiply instruction, wherein P is the product of at least operand A, operand B, and R^−1, wherein R is a value based on the size parameter.
2. The processor of claim 1 , wherein the first instance of the Montgomery-multiply instruction includes the size parameter.
3. The processor of claim 1 , wherein the Montgomery-multiply instruction is executable by the processor to operate on an additional operand N′, where N′ resides in one of the plurality of registers of the general-purpose register file.
4. The processor of claim 1 , wherein the processor is configured to retrieve operands A, B, and N from the respective portions of the general-purpose register file, wherein the respective portions are fixed by the processor.
5. The processor of claim 1 wherein the at least two registers include an architecturally-visible integer register and an architecturally-visible floating point register.
6. The processor of claim 1 , wherein the instruction execution unit includes a multiplier datapath configured to multiply operands having a maximum number of bits MAX, wherein either or both of operands A and B includes more than the maximum number of bits MAX, and wherein the instruction execution unit is configured to perform, in response to receiving the first instance of the Montgomery-multiply instruction, a plurality of multiplication operations between 1) portions of operand A and 2) portions of operand B, wherein the instruction execution unit is configured to perform the plurality of multiplication operations within the multiplier datapath to produce a plurality of products.
7. The processor of claim 6 , wherein the instruction execution unit is further configured to:
sum the plurality of products to produce an intermediary value; and
compare the intermediary value with operand N; and
in response to the intermediary value being greater than or equal to operand N, subtract operand N from the intermediary value to produce a result of the first instance of the Montgomery-multiply instruction.
8. The processor of claim 1 , wherein the received instructions include a first Montgomery-square instruction defined within the ISA, wherein the Montgomery-square instruction is executable by the processor to operate on operands D and E residing in respective portions of the general-purpose register file, wherein the Montgomery-square instruction is executable by the instruction execution unit to calculate Q mod E, and wherein Q is the product of at least operand D^2.
9. A method, comprising:
a control unit of a processor issuing instructions for execution;
an instruction execution unit of the processor receiving one or more of the issued instructions, including a first instance of a Montgomery-multiply instruction defined within an instruction set architecture (ISA) of the processor, wherein the Montgomery-multiply instruction is executable by the processor to operate on operands A, B. and N residing in respective portions of a general-purpose register file of the processor, wherein at least one of operands A, B, N spans at least two of registers of the general-purpose register file, and wherein a size of the respective portions is indicated by a size parameter; and
the instruction execution unit calculating P mod N to obtain a result of the first instance of the Montgomery-multiply instruction, wherein P is the product of at least operand A, operand B, and R^−1, wherein R is a value based on the size parameter.
10. The method of claim 9 , further comprising:
the instruction execution unit executing a plurality of instances of the Montgomery-multiply instruction to calculate (A^F) mod N, wherein F is an integer.
11. The method of claim 10 , wherein the method is usable to perform public-key encryption.
12. The method of claim 9 , wherein the received one or more instructions include a Montgomery-square instruction defined within the ISA of the processor, wherein the Montgomery-square is executable by the processor to operate on operands D and E residing in respective portions of the general-purpose register file, and wherein the method further comprises:
the instruction execution unit executing the first instance of the Montgomery-square instruction to calculate Q mod E, wherein Q is the product of at least D^2.
13. The method of claim 12 , wherein executing the first instance of the Montgomery-square instruction includes:
performing a plurality of multiplication operations between portions of operand D; and
doubling one or more products of the plurality of multiplication operations.
14. The method of claim 9 , wherein the issued instructions are selected from a plurality of threads, wherein he method further comprises:
in response to issuing the first instance of the Montgomery-multiply instruction for a given one of the plurality of threads, the control unit preventing additional instructions from issuing from the given thread until the first instance of the Montgomery-multiply instruction completes execution.
15. The method of claim 9 , wherein the issued instructions include an instance of a non-Montgomery-multiply instruction, and wherein the method further comprises:
in response to receiving the instance of the non-Montgomery-multiply instruction during execution of the first instance of the Montgomery-multiply instruction:
the instruction execution unit suspending execution of the first instance of the Montgomery-multiply instruction;
the instruction execution unit executing the instance of the non-Montgomery-multiply instruction; and
the instruction execution unit resuming execution of the first instance of the Montgomery-multiply instruction after completion of the instance of the non-Montgomery-multiply instruction.
16. The method of claim 9 , further comprising:
the instruction execution unit calculating P*R to obtain a result of the first instance of the Montgomery-multiply instruction.
17. A non-transitory computer-readable storage medium having program instructions stored thereon that are executable by a processor, wherein the program instructions include:
a first instance of a Montgomery-multiply instruction defined within an instruction set architecture (ISA) of the processor, wherein the Montgomery-multiply instruction is executable by the processor to operate on operands A, B, and N residing in respective portions of a general-purpose register file of the processor, wherein at least one of operands A, B, N spans at least two registers of the general-purpose register file, and wherein a size of the respective portions is indicated by a size parameter, wherein the first instance of the Montgomery-multiply instruction is executable by the processor to calculate P mod N in response to receiving the first instance of the Montgomery-multiply instruction, wherein P is the product of at least operand A, operand B, and R^−1, wherein R is a value based on the size parameter.
18. The computer-readable storage medium of claim 17 , wherein the first instance of the Montgomery-multiply instruction includes the size parameter, and wherein the Montgomery-multiply instruction is executable by the processor to store a result of calculating P mod N in a respective portion of the general-purpose register file.
19. The computer-readable storage medium of claim 17 , wherein processor includes a multiplier datapath configured to multiply operands having a maximum number of bits MAX, wherein either or both of operands A and B includes more than the maximum number of bits MAX, and wherein the Montgomery-multiply instruction is executable by the processor to perform a plurality of multiplication operations between 1) portions of A and 2) portions of B, wherein the plurality of multiplication operations are executable within the multiplier datapath to produce a plurality of products.
20. The computer-readable storage medium of claim 17 , wherein the program instructions include a first instance of a Montgomery-square instruction defined within the ISA, wherein the Montgomery-square instruction is executable by the processor to operate on operands F and G residing in respective portions of the general-purpose register file, and wherein the first instance of the Montgomery-square instruction is executable by the processor to calculate Q mod G, wherein Q is the product of at least F^2.