Efficient multiplication of small matrices using SIMD registers

• US 20040122887A1
• Filed: 12/20/2002
• Published: 06/24/2004
• Est. Priority Date: 12/20/2002
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Macy, William W.
• Application Number:
  US10/327,445
• Publication Number:
  US 20040122887A1
• Time in Patent Office: Days
• US Class Current: 708/607
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

Abstract

An example of a matrix multiplication method that reduces calculation times on SIMD processors is described. The matrix multiplication requires loading each diagonal of the multiplicand matrix c into a different register of a processor, and loading a multiplier matrix a into at least one register in column order. Multiplication and addition elements in each column of multiplier matrix a in the register are selectively shifted to by shifting one element, with the last element of a column shifted to the front of the column. Diagonals of the multiplicand c matrix are multiplied by columns of the multiplier a matrix, with their product being added to the sum of products for columns of a result matrix.

Claims

1. A matrix multiplication method, comprising:

loading each diagonal of the multiplicand matrix c into processor accessible memory,

loading a multiplier matrix a into processor accessible memory in column order,

shifting elements in each column of multiplier matrix a in the register by shifting one element, with the last element of a column shifted to the front of the column, and

multiplying diagonals of the multiplicand c matrix by columns of the multiplier a matrix, with their product being added to the sum of products for columns of a result matrix.

2. The method according to claim 1, wherein the processor accessible memory is a SIMD register.

3. The method according to claim 2, further comprising loading a diagonal into multiple SIMD registers of the processor.

4. The method according to claim 1, wherein the multiplier a matrix is adjusted in length prior to multiplying with diagonals of the multiplicand c matrix by stacking copies of multiplier matrix a on top of each other so columns are aligned and a top row of a copy is below a bottom row and any other copy to extend each column.

5. The method according to claim 1, wherein the multiplicand matrix C diagonal is shorter than multiplier matrix a column.

6. The method according to claim 1, wherein the multiplicand matrix C diagonal is longer than multiplier matrix a column.

7. The method according to claim 1, wherein shifting the elements further comprises multiplying columns of a by a diagonal of c;

and shifting and multiplying columns of a by a next diagonal of c in a predetermined order

8. The method according to claim 1, wherein shifting the elements further comprises rotating elements using a byte shuffle operation.

9. The method according to claim 1, wherein each element is a byte.

10. The method according to claim 1, wherein multiplying diagonals further comprises application of a MAC operation.

11. An article comprising a storage medium having stored thereon instructions that when executed by a machine result in:

loading each diagonal of the multiplicand matrix c into processor accessible memory,

loading a multiplier matrix a into processor accessible memory in column order,

shifting the elements in each column of multiplier matrix a in the register by shifting one element, with the last element of a column shifted to the front of the column, and

multiplying diagonals of the multiplicand c matrix by columns of the multiplier a matrix, with their product being added to the sum of products for columns of a result matrix.

12. The article comprising a storage medium having stored thereon instructions of claim 11, wherein the processor accessible memory is a SIMD register.

13. The article comprising a storage medium having stored thereon instructions of claim 12, wherein a diagonal is loaded into multiple SIMD registers of the processor

14. The article comprising a storage medium having stored thereon instructions of claim 11, wherein the multiplier a matrix is adjusted in length prior to multiplying with diagonals of the multiplicand c matrix by stacking copies of multiplier matrix a on top of each other so columns are aligned and a top row of a copy is below a bottom row and any other copy to extend each column.

15. The article comprising a storage medium having stored thereon instructions of claim 11, wherein the multiplicand matrix c diagonal is shorter than multiplier matrix a column.

16. The article comprising a storage medium having stored thereon instructions of claim 11, wherein the multiplicand matrix c diagonal is longer than multiplier matrix a column.

17. The article comprising a storage medium having stored thereon instructions of claim 11, wherein shifting the multiplication and addition elements further comprises multiplying columns of a by a diagonal of c;

and shifting and multiplying columns of a by a next diagonal of c in a predetermined order

18. The article comprising a storage medium having stored thereon instructions of claim 11, wherein shifting the multiplication and addition elements further comprises rotating elements using a byte shuffle operation.

19. The article comprising a storage medium having stored thereon instructions of claim 11, wherein multiplying diagonals further comprises application of a MAC operation.

20. The article comprising a storage medium having stored thereon instructions of claim 11, wherein each element is a byte.

21. A system comprising

a processor having registers that load each diagonal of the multiplicand matrix c into processor accessible memory, with a multiplier matrix a loaded into processor accessible memory in column order, and

control logic to shift the multiplication and addition elements in each column of multiplier matrix a in the registers by shifting one element, with the last element of a column shifted to the front of the column, and multiply diagonals of the multiplicand c matrix by columns of the multiplier a matrix, with their product being added to the sum of products for columns of a result matrix.

22. The system according to claim 21, wherein the processor accessible memory is a SIMD register.

23. The system according to claim 22, further comprising loading a diagonal into multiple SIMD registers of the processor.

24. The system according to claim 21, wherein the multiplier a matrix is adjusted in length prior to multiplying with diagonals of the multiplicand c matrix by stacking copies of multiplier matrix a on top of each other so columns are aligned and a top row of a copy is below a bottom row and any other copy to extend each column.

25. The system according to claim 21, wherein the multiplicand matrix c diagonal is shorter than multiplier matrix a column.

26. The system according to claim 21, wherein the multiplicand matrix c diagonal is longer than multiplier matrix a column.

27. The system according to claim 21, wherein control logic to shift the multiplication and additional elements further comprises multiplying columns of a by a diagonal of c;

and shifting and multiplying columns of a by a next diagonal of c in a predetermined order

28. The system according to claim 21, wherein control logic to shift the multiplication and addition elements further comprises rotating elements using a byte shuffle operation.

29. The system according to claim 21, wherein each element is a byte.

30. The system according to claim 21, wherein multiplying diagonals further comprises application of a MAC operation.