SPEED UP BIG-NUMBER MULTIPLICATION USING SINGLE INSTRUCTION MULTIPLE DATA (SIMD) ARCHITECTURES

• US 20130332707A1
• Filed: 06/07/2012
• Published: 12/12/2013
• Est. Priority Date: 06/07/2012
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: GUERON, Shay, KRASNOV, Vlad
• Application Number:
  US13/491,141
• Publication Number:
  US 20130332707A1
• Time in Patent Office: Days
• US Class Current: 712/222
• CPC Class Codes: G06F 7/5324 partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/3893 controlled in tandem, e.g. multiplier-accumulator

Abstract

A processing apparatus may be configured to include logic to generate a first set of vectors based on a first integer and a second set of vectors based on a second integer, logic to calculate sub products by multiplying the first set of vectors to the second set of vectors, logic to split each sub product into a first half and a second half and logic to generate a final result by adding together all first and second halves at respective digit positions.

Claims

1. A processor comprising:

logic to generate a first set of vectors based on a first integer A and a second set of vectors based on a second integer B;

logic to calculate sub products by multiplying the first set of vectors to the second set of vectors;

logic to split each sub product into a first half and a second half; and

logic to generate a final result of A times B by adding together all first and second halves at respective digit positions.

2. The processor of claim 1, wherein the first and second integers A and B are represented as n-digit numbers A={a_n-1 . . . a₁ a₀} and B={b_n-1 . . . b₁ b₀} with a base being a radix 2^k.

3. The processor of claim 2, wherein the processor implements at least one r-digit SIMD register and one SIMD multiplication instruction for the r-digit SIMD register.

4. The processor of claim 3, wherein the SIMD multiplication instruction multiplies unsigned double word elements in one xmm register by unsigned double word elements in another xmm register and produces quardword results.

5. The processor of claim 4, wherein the first set of vectors include two vectors A0 and A1 formed by replacing odd digits of the first integer A with zeros (A0={0 a_n-2 . . . 0 a₂ 0 a₀}) and shifting the first integer A by one digit and then replacing even digits of the shifted first integer A with zeros (A1={0 a_n-1 . . . 0 a₃ 0 a₁}), and the second set of vectors include a plurality of vector Bi={bi . . . bi bi bi};

0≦

i<

n.

6. The processor of claim 5, wherein each sub product A0×

Bi and A1×

Bi for 0≦

i<

n are split into upper and lower halves as;

A0×

Bi_l={0(a_n-2×

b_i)_l . . . 0(a₂×

b_i)_l0(a₀×

b_i)_l};

0≦

i<

n,

A0×

Bi_h={0(a_n-2×

b_i)_h . . . 0(a₂×

b_i)_h0(a₀×

b_i)_h};

0≦

i<

n,

A1×

Bi_l={0(a_n-1×

b_i)_l . . . 0(a₃×

b_i)_l0(a₁×

b_i)_l};

0≦

i<

n,

A1×

Bi_h={0(a_n-1×

b_i)_h . . . 0(a₃×

b_i)_h0(a₁×

b_i)_h};

0≦

i<

n,

and these upper and lower halves are aligned at respective digit positions and added together to produce the final result.

7. A method comprising:

generate a first set of vectors based on a first integer and a second set of vectors based on a second integer;

calculate sub products by multiplying the first set of vectors to the second set of vectors;

split each sub product into a first half and a second half; and

generate a final result by adding together all first and second halves at respective digit positions.

8. The method of claim 7, wherein the first and second integers A and B are represented as n-digit numbers A={a_n-1 . . . a₁ a₀} and B={b_n-1 . . . b₁ b₀} with a base being a radix 2^k.

9. The method of claim 8, wherein the processor implements at least one r-digit SIMD register and one SIMD multiplication instruction for the r-digit SIMD register.

10. The method of claim 9, wherein the SIMD multiplication instruction multiplies unsigned double word elements in one xmm register by unsigned double word elements in another xmm register and produces quardword results.

11. The method of claim 10, wherein the first set of vectors include two vectors A0 and A1 formed by replacing odd digits of the first integer A with zeros (A0={0 a_n-2 . . . 0 a₂ 0 a₀}) and shifting the first integer A by one digit and then replacing even digits of the shifted first integer A with zeros (A1={0 a_n-1 . . . 0 a₃ 0 a₁}), and the second set of vectors include a plurality of vector Bi={bi . . . bi bi bi};

0≦

i<

n.

12. The method of claim 11, wherein each sub product A0×

Bi and A1×

Bi for 0≦

i<

n are split into upper and lower halves as;

A0×

Bi_l={0(a_n-2×

b_i)_l . . . 0(a₂×

b_i)_l0(a₀×

b_i)_l};

0≦

i<

n,

A0×

Bi_h={0(a_n-2×

b_i)_h . . . 0(a₂×

b_i)_h0(a₀×

b_i)_h};

0≦

i<

n,

A1×

Bi_l={0(a_n-1×

b_i)_l . . . 0(a₃×

b_i)_l0(a₁×

b_i)_l};

0≦

i<

n,

A1×

Bi_h={0(a_n-1×

b_i)_h . . . 0(a₃×

b_i)_h0(a₁×

b_i)_h};

0≦

i<

n,

and these upper and lower halves are aligned at respective digit positions and added together to produce the final result.

13. A system comprising:

a random access memory to store an application program; and

a processor comprising;

at least one processor core configured to execute the application program to;

generate a first set of vectors based on a first integer and a second set of vectors based on a second integer;

calculate sub products by multiplying the first set of vectors to the second set of vectors;

split each sub product into a first half and a second half; and

generate a final result by adding together all first and second halves at respective digit positions.

14. The system of claim 13, wherein the first and second integers A and B be represented as n-digit numbers A={a_n-1 . . . a₁ a₀} and B={b_n-1 . . . b₁ b₀} with a base being a radix 2^k.

15. The system of claim 14, wherein the processor implements at least one r-digit SIMD register and one SIMD multiplication instruction for the r-digit SIMD register.

16. The system of claim 15, wherein the SIMD multiplication instruction multiplies unsigned double word elements in one xmm register by unsigned double word elements in another xmm register and produces quardword results.

17. The system of claim 16, wherein the first set of vectors include two vectors A0 and A1 formed by replacing odd digits of the first integer A with zeros (A0={0 a_n-2 . . . 0 a₂ 0 a₀}) and shifting the first integer A by one digit and then replacing even digits of the shifted first integer A with zeros (A1={0 a_n-1 . . . 0 a₃ 0 a₁}), and the second set of vectors include a plurality of vector Bi={bi . . . bi bi bi};

0≦

i<

n.

18. The system of claim 17, wherein each sub product A0×

Bi and A1×

Bi for 0≦

i<

n are split into upper and lower halves as;

A0×

Bi_l={0(a_n-2×

b_i)_l . . . 0(a₂×

b_i)_l0(a₀×

b_i)_l};

0≦

i<

n,

A0×

Bi_h={0(a_n-2×

b_i)_h . . . 0(a₂×

b_i)_h0(a₀×

b_i)_h};

0≦

i<

n,

A1×

Bi_l={0(a_n-1×

b_i)_l . . . 0(a₃×

b_i)_l0(a₁×

b_i)_l};

0≦

i<

n,

A1×

Bi_h={0(a_n-1×

b_i)_h . . . 0(a₃×

b_i)_h0(a₁×

b_i)_h};

0≦

i<

n,

and these upper and lower halves are aligned at respective digit positions and added together to produce the final result.

19. A non-transitory machine-readable medium having stored thereon instructions for causing a processor to execute a method, the method comprising:

generate a first set of vectors based on a first integer and a second set of vectors based on a second integer;

calculate sub products by multiplying the first set of vectors to the second set of vectors;

split each sub product into a first half and a second half; and

generate a final result by adding together all first and second halves at respective digit positions.

20. The non-transitory machine-readable medium of claim 19, wherein the first and second integers A and B are represented as n-digit numbers A={a_n-1 . . . a₁ a₀} and B={b_n-1 . . . b₁ b₀} with a base being a radix 2^k.

21. The non-transitory machine-readable medium of claim 20, wherein the processor implements at least one r-digit SIMD register and one SIMD multiplication instruction for the r-digit SIMD register.

22. The non-transitory machine-readable medium of claim 21, wherein the SIMD multiplication instruction multiplies unsigned double word elements in one xmm register by unsigned double word elements in another xmm register and produces quardword results.

23. The non-transitory machine-readable medium of claim 22, wherein the first set of vectors include two vectors A0 and A1 formed by replacing odd digits of the first integer A with zeros (A0={0 a_n-2 . . . 0 a₂ 0 a₀}) and shifting the first integer A by one digit and then replacing even digits of the shifted first integer A with zeros (A1={0 a_n-1 . . . 0 a₃ 0 a₁}), and the second set of vectors include a plurality of vector Bi={bi . . . bi bi bi};

0≦

i<

n.

24. The non-transitory machine-readable medium of claim 23, wherein each sub product A0×

Bi and A1×

Bi for 0≦

i<

n are split into upper and lower halves as;

A0×

Bi_l={0(a_n-2×

b_i)_l . . . 0(a₂×

b_i)_l0(a₀×

b_i)_l};

0≦

i<

n,

A0×

Bi_h={0(a_n-2×

b_i)_h . . . 0(a₂×

b_i)_h0(a₀×

b_i)_h};

0≦

i<

n,

A1×

Bi_l={0(a_n-1×

b_i)_l . . . 0(a₃×

b_i)_l0(a₁×

b_i)_l};

0≦

i<

n,

A1×

Bi_h={0(a_n-1×

b_i)_h . . . 0(a₃×

b_i)_h0(a₁×

b_i)_h};

0≦

i<

n,

and these upper and lower halves are aligned at respective digit positions and added together to produce the final result.