Multiplier pipelining optimization with a postponed estimation correction

Patent metadata

Field	Value
Publication number	US-2016283195-A1
Application number	US-201514668349-A
Country	US
Kind code	A1
Filing date	Mar 25, 2015
Priority date	Mar 25, 2015
Publication date	Sep 29, 2016
Grant date	—

Abstract

One embodiment provides a system. The system includes a register to store an operand; a multiplier; and optimizer logic to initiate a first reduction stage to operate on the operand, initiate a second reduction stage prior to completion of the first reduction stage, and determine whether a carry propagation has occurred.

First claim

What is claimed is:

1 . A system comprising:
a register to store an operand; a multiplier; and optimizer logic to initiate a first reduction stage to operate on the operand, initiate a second reduction stage prior to completion of the first reduction stage, and determine whether a carry propagation has occurred.

2 . The system of claim 1 , wherein the optimizer logic is further to perform a postponed estimate correction of a result of the second reduction stage if the carry propagation has occurred.

3 . The system of claim 1 , wherein the optimizer logic is further to reorder provision of a plurality of elements of the operand to the multiplier, the reordering to reduce a likelihood that the carry propagation will occur.

4 . The system of claim 1 , wherein the multiplier is to perform a plurality of pipelined multiplications of a plurality of elements of the operand.

5 . The system of claim 1 , further comprising modular exponentiation (ME) logic and a parameter store, the ME logic to precompute a first constant m′ and a second constant μ and to store the first constant and second constant in the parameter store.

6 . The system of claim 1 , wherein the operand is related to modular exponentiation.

7 . The system of claim 1 , wherein the first reduction stage and the second reduction stage are related to a modified Barrett reduction.

8 . A method comprising:
initiating, by optimizer logic, a first reduction stage to operate on an operand; initiating, by the optimizer logic, a second reduction stage prior to completion of the first reduction stage; and determining, by the optimizer logic, whether a carry propagation has occurred.

9 . The method of claim 8 , further comprising:
performing, by the optimizer logic, a postponed estimate correction of a result of the second reduction stage if the carry propagation has occurred.

10 . The method of claim 8 , further comprising:
reordering, by the optimizer logic, provision of a plurality of elements of the operand to a multiplier, the reordering to reduce a likelihood that the carry propagation will occur.

11 . The method of claim 8 , further comprising:
performing, by a multiplier, a plurality of pipelined multiplications of a plurality of elements of the operand.

12 . The method of claim 8 , further comprising:
precomputing, by modular exponentiation (ME) logic, a first constant m′ and a second constant μ; and storing, by the ME logic, the first constant and second constant in a parameter store.

13 . The method of claim 8 , wherein the operand is related to modular exponentiation.

14 . The method of claim 8 , wherein the first reduction stage and the second reduction stage are related to a modified Barrett reduction.

15 . At least one computer readable storage device having stored thereon instructions that when executed by one or more processors result in the following operations comprising:
initiating a first reduction stage to operate on an operand; initiating a second reduction stage prior to completion of the first reduction stage; and determining whether a carry propagation has occurred.

16 . The at least one device of claim 15 , wherein the instructions that when executed by one or more processors results in the following additional operations comprising:
performing a postponed estimate correction of a result of the second reduction stage if the carry propagation has occurred.

17 . The at least one device of claim 15 , wherein the instructions that when executed by one or more processors results in the following additional operations comprising:
reordering provision of a plurality of elements of the operand to a multiplier, the reordering to reduce a likelihood that the carry propagation will occur.

18 . The at least one device of claim 15 , wherein the instructions that when executed by one or more processors results in the following additional operations comprising:
performing a plurality of pipelined multiplications of a plurality of elements of the operand.

19 . The at least one device of claim 15 , wherein the instructions that when executed by one or more processors results in the following additional operations comprising:
precomputing a first constant m′ and a second constant μ; and storing the first constant and second constant in a parameter store.

20 . The at least one device of claim 15 , wherein the operand is related to modular exponentiation.

21 . The at least one device of claim 15 , wherein the first reduction stage and the second reduction stage are related to a modified Barrett reduction.

Assignees

• Intel Corp

Inventors

• O'Dwyer T J
• Laurent Pierre

Classifications

• G06F7/523 Primary

  Multiplying only · CPC title

• G06F2207/38

  Indexing scheme relating to groups G06F7/38 - G06F7/575 · CPC title

• G06F5/00 Primary

  Methods or arrangements for data conversion without changing the order or content of the data handled · CPC title

• G06F2205/00

  Indexing scheme relating to group G06F5/00; Methods or arrangements for data conversion without changing the order or content of the data handled · CPC title