Binary polynomial multiplier

• US 7,599,981 B2
• Filed: 02/21/2001
• Issued: 10/06/2009
• Est. Priority Date: 02/21/2001
• Status: Active Grant

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Ekner, Hartvig W. J., Stribaek, Morten, Laursen, Soeren R. F.
• Primary Examiner(s): Do, Chat C
• Application Number:
  US09/788,670
• Publication Number:
  US 20060190518A1
• Time in Patent Office: 3,149 Days
• Field of Search: 708620-632, 708491-492, 708/493, 708/490, 708/520
• US Class Current: 708/625
• CPC Class Codes: G06F 7/57 Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations G06F7/49, G06F7/491 take precedence
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A multiply unit includes support for arithmetic operations, binary polynomial operations, and permutations. To this end, the multiply unit may include an input data path that receives input operands, an arithmetic multiplier connected to receive the input operands, a binary polynomial multiplier having components separate and distinct from the arithmetic multiplier and connected to receive the one or more input operands, and a multiply unit output data path connected to receive an output of the arithmetic multiplier and connected to receive an output of the binary polynomial multiplier. The multiply unit also may include permutation logic that performs permutation operations on the input operands.

Claims

1. A programmable CPU multiplier responsive to instructions dedicated to polynomial operations, comprising:

an array unit responsive to instructions dedicated to polynomial operations, the array unit having;

a first array that is used to perform arithmetic multiplication, the first array having a first result output and a second result output; and

a second array that is used to perform binary polynomial multiplication, the second array having a third result output; and

a carry propagation adder having a first input, a second input, and an output, wherein

the first input of the carry propagation adder is selectively coupled to the first result output of the first array,

the second input of the carry propagation adder is selectively coupled to the second result output of the first array and the third result output of the second array, and

the output of the carry propagation adder is stored in a register to provide an output of the polynomial operations.

2. The programmable CPU multiplier of claim 1, further comprising:

a first multiplexer coupled to the first result output of the first array;

a first register coupled between an output of the first multiplexer and the first input of the carry propagation adder;

a second multiplexer coupled to the second result output of the first array; and

a second register coupled between an output of the second multiplexer and the second input of the carry propagation adder.

3. The programmable CPU multiplier of claim 2, wherein the third result output of the second array is coupled to an input of the second multiplexer.

4. The programmable CPU multiplier of claim 2, wherein an output of the first register is coupled to an input of the first array and an input of the second array.

5. The programmable CPU multiplier of claim 2, wherein an output of the second register is coupled to an input of the first array.

6. The programmable CPU multiplier of claim 1, wherein the first array includes a plurality of carry-save adders arranged in a tree structure.

7. The programmable CPU multiplier of claim 1, wherein the first array is a Wallace tree multiplier array.

8. The programmable CPU multiplier of claim 1, wherein the first array is a 32-bit by 16-bit array.

9. The programmable CPU multiplier of claim 1, wherein the second array is a 32-bit by 16-bit array.

10. The programmable CPU multiplier of claim 1, wherein the processor performs 32-bit by 32-bit multiplications.

11. The programmable CPU multiplier of claim 1, wherein the processor multiplies a first operand and a second operand to form a resultant value, the first operand being provided to a first input of the first array and the second operand being provided to a second input of the first array, and wherein the resultant value is available at an output of the carry propagation adder.

12. The programmable CPU multiplier of claim 1, wherein the processor multiplies a first polynomial value and a second polynomial value to form a resultant value, the first polynomial value being provided to a first input of the second array and the second polynomial value being provided to a second input of the second array, and wherein the resultant value is available at an output of the carry propagation adder.

13. A tangible computer-readable storage medium comprising a programmable CPU multiplier responsive to instructions dedicated to polynomial operations embodied in software, the programmable CPU multiplier comprising:

an array unit responsive to instructions dedicated to polynomial operations, the array unit having;

a first array that is used to perform arithmetic multiplication, the first array having a first result output and a second result output; and

a second array that is used to perform binary polynomial multiplication, the second array having a third result output; and

a carry propagation adder having a first input, a second input, and an output, wherein

the first input of the carry propagation adder is selectively coupled to the first result output of the first array,

the second input of the carry propagation adder is selectively coupled to the second result output of the first array and the third result output of the second array, and

the output of the carry propagation adder is stored in a register to provide an output of the polynomial operations.

14. The tangible computer-readable storage medium of claim 13, wherein the programmable CPU multiplier embodied in software further comprises:

a first multiplexer coupled to the first result output of the first array;

a first register coupled between an output of the first multiplexer and the first input of the carry propagation adder;

a second multiplexer coupled to the second result output of the first array; and

a second register coupled between an output of the second multiplexer and the second input of the carry propagation adder.

15. The tangible computer-readable storage medium of claim 14, wherein the third result output of the second array is coupled to an input of the second multiplexer.

16. The tangible computer-readable storage medium of claim 15, wherein an output of the first register is coupled to an input of the first array and an input of the second array.

17. The tangible computer-readable storage medium of claim 15, wherein an output of the second register is coupled to an input of the first array.

18. The tangible computer-readable storage medium of claim 13, wherein the first array includes a plurality of carry-save adders arranged in a tree structure.

19. The tangible computer-readable storage medium of claim 13, wherein the first array is a Wallace tree multiplier array.

20. The tangible computer-readable storage medium of claim 13, wherein the first array is a 32-bit by 16-bit array.

21. The tangible computer-readable storage medium of claim 13, wherein the second array is a 32-bit by 16-bit array.

22. The tangible computer-readable storage medium of claim 13, wherein the programmable CPU multiplier performs 32-bit by 32-bit multiplications.

23. The tangible computer-readable storage medium of claim 13, wherein the programmable CPU multiplier multiplies a first operand and a second operand to form a resultant value, the first operand being provided to a first input of the first array and the second operand being provided to a second input of the first array, and wherein the resultant value is available at an output of the carry propagation adder.

24. The tangible computer-readable storage medium of claim 13, wherein the programmable CPU multiplier multiplies a first polynomial value and a second polynomial value to form a resultant value, the first polynomial value being provided to a first input of the second array and the second polynomial value being provided to a second input of the second array, and wherein the resultant value is available at an output of the carry propagation adder.

25. The tangible computer-readable storage medium of claim 13, wherein the programmable CPU multiplier is embodied in hardware description language software.

26. The tangible computer-readable storage medium of claim 13, wherein the programmable CPU multiplier is embodied in one of Verilog hardware description language software and VHDL hardware description language software.

27. A system, comprising:

a processor for performing multiplication, the processor including;

an execution unit responsive to a first set of instructions, and

a multiply-divide unit, responsive to a second set of instructions dedicated to polynomial operations, the multiply-divide unit comprising;

an array unit in the processor for performing multiplication having;

a first array that is used to perform arithmetic multiplication, the first array having a first result output and a second result output, and

a second array that is used to perform binary polynomial multiplication, the second array having a third result output, and

a carry propagation adder having a first input, a second input, and an output, wherein

the first input of the carry propagation adder is selectively coupled to the first result output of the first array,

the second input of the carry propagation adder is selectively coupled to the second result output of the first array and the third result output of the second array, and

the output of the carry propagation adder is stored in a register to provide an output of the polynomial operations; and

a memory coupled to the processor to store the first and second set of instructions.

28. The system of claim 27, wherein the multiply-divide unit further comprises:

a first multiplexer coupled to the first result output of the first array;

a first register coupled between an output of the first multiplexer and the first input of the carry propagation adder;

a second multiplexer coupled to the second result output of the first array; and

a second register coupled between an output of the second multiplexer and the second input of the carry propagation adder.

29. The system of claim 28, wherein the third result output of the second array is coupled to an input of the second multiplexer.

30. The system of claim 29, wherein an output of the first register is coupled to an input of the first array and an input of the second array.

31. The system of claim 29, wherein an output of the second register is coupled to an input of the first array.

32. The system of claim 27, wherein the first array includes a plurality of carry-save adders arranged in a tree structure.

33. The system of claim 27, wherein the first array is a Wallace tree multiplier array.

34. The system of claim 27, wherein the first array is a 32-bit by 16-bit array.

35. The system of claim 27, wherein the second array is a 32-bit by 16-bit array.

36. The system of claim 27, wherein the multiply-divide unit performs 32-bit by 32-bit multiplications.

37. The system of claim 27, wherein the multiply-divide unit multiplies a first operand and a second operand to form a resultant value, the first operand being provided to a first input of the first array and the second operand being provided to a second input of the first array, and wherein the resultant value is available at an output of the carry propagation adder.

38. The system of claim 27, wherein the multiply-divide unit multiplies a first polynomial value and a second polynomial value to form a resultant value, the first polynomial value being provided to a first input of the second array and the second polynomial value being provided to a second input of the second array, and wherein the resultant value is available at an output of the carry propagation adder.

39. The system of claim 27, wherein operation of the multiply-divide unit is decoupled from operation of the execution unit.