Montgomery multiplier with dual independent channels
AssigneeIntel Corporation
InventorMichael D. Ruehle
Life of this patent
Estimating the term…
Abstract
A linear systolic array Montgomery multiplier circuit that concurrently processes two separate Montgomery multiplications on alternate clock cycles, without a requirement to have any common parameters between the two multiplications. Multiples of two different parameters are stored in storage elements for each multiplication. Two sets of these multiples, one set for each of the two multiplications, are stored in separate storage banks and accessed on alternate clock cycles by each processing element in the array. Two sequences of control codes for the two multiplications are interleaved as they are fed into a first processing element.
Claims19
An apparatus comprising:
- a first storage element in a processing element of a linear systolic array Montgomery multiplier to store a first set of values, a selected one of the first set of values to be used for a first computation, and to store a second set of values, a selected one of the second set of values to be used for a second computation, wherein the first storage element comprises a first bank of storage locations to store the first set of values and a second bank of storage locations to store the second set of values;
- a second storage element in the processing element to store a third set of values, a selected one of the third set of values to be used for the first computation, and to store a fourth set of values, a selected one of the fourth set of values to be used for the second computation;
- and
- processing logic in the processing element coupled to the first and second storage elements to perform the first computation during a first clock cycle and to perform the second computation during a second clock cycle immediately following the first clock cycle.
An apparatus comprising:
- a chain of serially-connected processing elements in a linear systolic array Montgomery multiplier circuit to perform a first Montgomery multiplication in a first Montgomery multiplier channel and to perform a second Montgomery multiplication in a second Montgomery multiplier channel;
- and
- a controller coupled to the chain to provide a first set of parameters and control codes to the chain to perform the first Montgomery multiplication and to provide a second set of parameters and control codes to the chain to perform the second Montgomery multiplication, wherein the controller is further to provide a first channel selection value to perform the first Montgomery multiplication and a second channel selection value to perform the second Montgomery multiplication.
A system comprising:
- a processor;
- a main memory coupled to the processor;
- a plurality of processing elements in a linear systolic array Montgomery multiplier circuit coupled to the processor, the plurality of processing elements connected together in a chain of processing elements to perform a first Montgomery multiplication during a first set of clock cycles and to perform a second Montgomery multiplication during a second set of clock cycles interleaved with the first set of clock cycles;
- and
- a controller coupled to the chain to provide a first set of parameters and control codes to the chain during the first set of clock cycles to perform the first Montgomery multiplication and to provide a second set of parameters and control codes to the chain during the second set of clock cycles to perform the second Montgomery multiplication.
A method comprising:
- storing multiples of first and second parameters in a linear systolic array, a selected one of the first parameters and a selected one of the second parameters to be used to perform a first Montgomery multiplication;
- storing multiples of third and fourth parameters in the linear systolic array, a selected one of the third parameters and a selected one of the fourth parameters to be used to perform a second Montgomery multiplication, the selected ones of the third and fourth parameters having different values than the selected ones of the first and second parameters;
- and
- performing the first and second Montgomery multiplications concurrently,
- wherein said performing concurrently comprises
- providing a first set of control codes to the linear systolic array to control the first Montgomery multiplication;
- providing a second set of control codes to the linear systolic array to control the second Montgomery multiplication;
- and
- interleaving the first set of control codes with the second set of control codes as said first and second sets are provided to the linear systolic array.
A machine-readable medium that provides instructions, which when executed by a set of one or more processors, cause said set of processors to perform operations comprising:
- providing first, second, third, and fourth parameters to a Montgomery multiplier;
- causing the Montgomery multiplier to store multiples of the first and second parameters in processing elements of a linear systolic array;
- causing the Montgomery multiplier to store multiples of the third and fourth parameters in the processing elements of the linear systolic array, the third and fourth parameters having different values than the first and second parameters;
- and
- causing the Montgomery multiplier to perform the first and second Montgomery multiplications concurrently using selected ones of the multiples of the first, second, third and fourth parameters;
- wherein said causing the Montgomery multiplier to perform comprises providing a first set of control codes to the linear systolic array to control the first Montgomery multiplication;
- providing a second set of control codes to the linear systolic array to control the second Montgomery multiplication;
- and
- interleaving the first set of control codes with the second set of control codes as said first and second sets are provided to the linear systolic array.
Dependencies are inferred from the claim text.