Configuring a programmable integrated circuit device to perform matrix multiplication

• US 8,626,815 B1
• Filed: 03/03/2009
• Issued: 01/07/2014
• Est. Priority Date: 07/14/2008
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Abad, Farley
• Assistant Examiner(s): Yu, Henry
• Application Number:
  US12/396,739
• Time in Patent Office: 1,771 Days
• Field of Search: None
• 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

In a matrix multiplication in which each element of the resultant matrix is the dot product of a row of a first matrix and a column of a second matrix, each row and column can be broken into manageable blocks, with each block loaded in turn to compute a smaller dot product, and then the results can be added together to obtain the desired row-column dot product. The earliest results for each dot product are saved for a number of clock cycles equal to the number of portions into which each row or column is divided. The results are then added to provide an element of the resultant matrix. To avoid repeated loading and unloading of the same data, all multiplications involving a particular row-block can be performed upon loading that row-block, with the results cached until other multiplications for the resultant elements that use the cached results are complete.

Claims

1. A method of configuring a programmable integrated circuit device to perform multiplication of a first multiplicand matrix by a second multiplicand matrix to form a resultant matrix, wherein said first multiplicand matrix has a first number of rows and a second number of columns, said second multiplicand matrix has said second number of rows and a third number of columns, and said resultant matrix has a number of elements equal to a product of said first and third numbers, said method comprising:

configuring logic of said programmable integrated circuit device as a fourth number of multipliers, wherein said fourth number is one-Nth of said second number;

configuring logic of said programmable integrated circuit device to break down each respective row of said first multiplicand matrix into N row-blocks and to break down each respective column of said second multiplicand matrix into N column-blocks, and to use said fourth number of multipliers to form a respective dot-product of each of said row-blocks with a respective one of said column-blocks to form N partial dot products of each respective row of said first multiplicand matrix and a corresponding respective column of said second multiplicand matrix, wherein;

each said row-block comprises more than one element of said respective row and fewer than all elements of said respective row, and each said column-block comprises more than one element of said respective column and fewer than all elements of said respective column, and

all respective ones of said partial dot products involving each respective one of said row-blocks and all of said column-blocks being formed before forming any partial dot product involving any other one of said row-blocks;

configuring logic of said programmable integrated circuit device to save each of said N partial dot products until all of said N partial dot products have been computed; and

configuring logic of said programmable integrated circuit device to add said N partial dot products to provide an element of said resultant matrix corresponding to said respective row of said first multiplicand matrix and said corresponding respective column of said second multiplicand matrix.

2. The method of claim 1 wherein said configuring said logic of said programmable integrated circuit device to save each of said N partial dot products comprises configuring said logic of said programmable integrated circuit device as at least one cache memory.

3. The method of claim 2 wherein said configuring said logic of said programmable integrated circuit device as at least one cache memory comprises configuring said logic of said programmable integrated circuit device as N cache memories for each dimension of said resultant matrix.

4. The method of claim 1 wherein:

said configuring logic of said programmable integrated circuit device to break down each respective row of said first multiplicand matrix into N row-blocks and to break down each respective column of said second multiplicand matrix into N column-blocks comprises configuring a first N random access memory blocks to store said row-blocks and a second N random access memory blocks to store said column-blocks; and

bandwidth of each said multiplier exceeds bandwidth of said memory blocks in at least one of said first N random access memory blocks and said second N random access memory blocks;

said method further comprising;

configuring logic of said programmable integrated circuit device as a respective plurality of buffers for each of said random access memory blocks in said at least one of said first N random access memory blocks and said second N random access memory blocks, thereby enabling multiple read operations for reading data from said at least one of said first N random access memory blocks and said second N random access memory blocks for input to said multipliers.

5. The method of claim 1 wherein said configuring logic of said programmable integrated circuit device as a fourth number of multipliers comprises configuring said logic to use dedicated multipliers of said programmable integrated circuit device.

6. The method of claim 1 wherein said configuring logic of said programmable integrated circuit device to add said N partial dot products comprises configuring said logic to use dedicated adders of said programmable integrated circuit device.

7. A programmable integrated circuit device configured to perform multiplication of a first multiplicand matrix by a second multiplicand matrix to form a resultant matrix, wherein said first multiplicand matrix has a first number of rows and a second number of columns, said second multiplicand matrix has said second number of rows and a third number of columns, and said resultant matrix has a number of elements equal to a product of said first and third numbers, said programmable integrated circuit device comprising:

logic configured as a fourth number of multipliers, wherein said fourth number is one-Nth of said second number;

logic configured to break down each respective row of said first multiplicand matrix into N row-blocks and to break down each respective column of said second multiplicand matrix into N column-blocks, and to use said fourth number of multipliers to form a respective dot-product of each of said row-blocks with a respective one of said column-blocks to form N partial dot products of each respective row of said first multiplicand matrix and a corresponding respective column of said second multiplicand matrix, wherein;

each said row-block comprises more than one element of said respective row and fewer than all elements of said respective row, and each said column-block comprises more than one element of said respective column and fewer than all elements of said respective column, and

said logic configured to use said fourth number of multipliers is configured to form all respective ones of said partial dot products involving each respective one of said row-blocks and all of said column-blocks, before forming any partial dot product involving any other one of said row-blocks;

logic configured to save each of said N partial dot products until all of said N partial dot products have been computed; and

logic configured to add said N partial dot products to provide an element of said resultant matrix corresponding to said respective row of said first multiplicand matrix and said corresponding respective column of said second multiplicand matrix.

8. The configured programmable integrated circuit device of claim 7 wherein said logic configured to save each of said N partial dot products comprises logic configured as at least one cache memory.

9. The configured programmable integrated circuit device of claim 8 wherein said logic configured as at least one cache memory comprises logic configured as N cache memories for each dimension of said resultant matrix.

10. The configured programmable integrated circuit device of claim 7 wherein:

said logic configured to break down each respective row of said first multiplicand matrix into N row-blocks and to break down each respective column of said second multiplicand matrix into N column-blocks comprises a first N random access memory blocks configured to store said row-blocks and a second N random access memory blocks configured to store said column-blocks; and

bandwidth of each said multiplier exceeds bandwidth of said memory blocks in at least one of said first N random access memory blocks and said second N random access memory blocks;

said configured programmable integrated circuit device further comprising;

logic configured as a respective plurality of buffers for each of said random access memory blocks in said at least one of said first N random access memory blocks and said second N random access memory blocks, thereby enabling multiple read operations for reading data from said at least one of said first N random access memory blocks and said second N random access memory blocks for input to said multipliers.

11. The configured programmable integrated circuit device of claim 10 wherein said logic configured as a respective plurality of buffers comprises a plurality of registers.

12. The configured programmable integrated circuit device of claim 7 wherein said logic configured as a fourth number of multipliers comprises logic configured to use dedicated multipliers of said programmable integrated circuit device.

13. The configured programmable integrated circuit device of claim 7 wherein said logic configured to add said N partial dot products comprises logic configured to use dedicated adders of said programmable integrated circuit device.

14. A non-transitory machine-readable data storage medium encoded with machine-executable instructions for configuring a programmable integrated circuit device to execute a method of configuring a programmable integrated circuit device to perform multiplication of a first multiplicand matrix by a second multiplicand matrix to form a resultant matrix, wherein said first multiplicand matrix has a first number of rows and a second number of columns, said second multiplicand matrix has said second number of rows and a third number of columns, and said resultant matrix has a number of elements equal to a product of said first and third numbers, said instructions comprising:

instructions to configure logic of said programmable integrated circuit device as a fourth number of multipliers, wherein said fourth number is one-Nth of said second number;

instructions to configure logic of said programmable integrated circuit device to break down each respective row of said first multiplicand matrix into N row-blocks and to break down each respective column of said second multiplicand matrix into N column-blocks, and to use said fourth number of multipliers to form a respective dot-product of each of said row-blocks with a respective one of said column-blocks to form N partial dot products of each respective row of said first multiplicand matrix and a corresponding respective column of said second multiplicand matrix, wherein;

each said row-block comprises more than one element of said respective row and fewer than all elements of said respective row, and each said column-block comprises more than one element of said respective column and fewer than all elements of said respective column, and

said instructions to configure said logic of said programmable integrated circuit device to use said fourth number of multipliers comprise instructions to configure said logic of said programmable integrated circuit device to form all respective ones of said partial dot products involving each respective one of said row-blocks and all of said column-blocks, before forming any partial dot product involving any other one of said row-blocks;

instructions to configure logic of said programmable integrated circuit device to save each of said N partial dot products until all of said N partial dot products have been computed; and

instructions to configure logic of said programmable integrated circuit device to add said N partial dot products to provide an element of said resultant matrix corresponding to said respective row of said first multiplicand matrix and said corresponding respective column of said second multiplicand matrix.

15. The non-transitory machine-readable data storage medium of claim 14 wherein said instructions to configure said logic of said programmable integrated circuit device to save each of said N partial dot products comprises instructions to configure said logic of said programmable integrated circuit device as at least one cache memory.

16. The non-transitory machine-readable data storage medium of claim 15 wherein said instructions to configure said logic of said programmable integrated circuit device as at least one cache memory comprises instructions to configure said logic of said programmable integrated circuit device as N cache memories for each dimension of said resultant matrix.

17. The non-transitory machine-readable data storage medium of claim 14 wherein:

said instructions to configure logic of said programmable integrated circuit device to break down each respective row of said first multiplicand matrix into N row-blocks and to break down each respective column of said second multiplicand matrix into N column-blocks comprises instructions to configure a first N random access memory blocks to store said row-blocks and a second N random access memory blocks to store said column-blocks;

bandwidth of each said multiplier exceeds bandwidth of each said cache memory; and

said instructions further comprise instructions to configure logic of said programmable integrated circuit device as a respective plurality of buffers for each of said cache memories for at least one dimension of said resultant matrix, thereby enabling multiple read operations for reading data from said cache memories for input to said multipliers.

18. The non-transitory machine-readable data storage medium of claim 14 wherein said instructions to configure logic of said programmable integrated circuit device as a fourth number of multipliers comprises instructions to 5 configure said logic to use dedicated multipliers of said programmable integrated circuit device.

19. The non-transitory machine-readable data storage medium of claim 14 wherein said instructions to configure logic of said programmable integrated circuit device to add said N partial dot products comprises instructions to configure said logic to use dedicated adders of said programmable integrated circuit device.

20. Circuitry for performing multiplication of a first multiplicand matrix by a second multiplicand matrix to form a resultant matrix, wherein said first multiplicand matrix has a first number of rows and a second number of columns, said second multiplicand matrix has said second number of rows and a third number of columns, and said resultant matrix has a number of elements equal to a product of said first and third numbers, said circuitry comprising:

a fourth number of multipliers, wherein said fourth number is one-Nth of said second number;

logic configured to break down each respective row of said first multiplicand matrix into N row-blocks and to break down each respective column of said second multiplicand matrix into N column-blocks, and to use said fourth number of multipliers to form a respective dot-product of each of said row-blocks with a respective one of said column-blocks to form N partial dot products of each respective row of said first multiplicand matrix and a corresponding respective column of said second multiplicand matrix, wherein;

each said row-block comprises more than one element of said respective row and fewer than all elements of said respective row, and each said column-block comprises more than one element of said respective column and fewer than all elements of said respective column, and

said logic configured to use said fourth number of multipliers is configured to form all respective ones of said partial dot products involving each respective one of said row-blocks and all of said column-blocks, before forming any partial dot product involving any other one of said row-blocks;

memory for saving each of said N partial dot products until all of said N partial dot products have been computed; and

circuitry for adding said N partial dot products to provide an element of said resultant matrix corresponding to said respective row of said first multiplicand matrix and said corresponding respective column of said second multiplicand matrix.

21. The circuitry of claim 20 wherein said memory comprises at least one cache memory.

22. The circuitry of claim 21 wherein said memory comprises N cache memories for each dimension of said resultant matrix.

23. The circuitry of claim 20 wherein:

said logic configured to break down each respective row of said first multiplicand matrix into N row-blocks and to break down each respective column of said second multiplicand matrix into N column-blocks comprises a first N random access memory blocks configured to store said row-blocks and a second N random access memory blocks configured to store said column-blocks; and

bandwidth of each said multiplier exceeds bandwidth of each said cache memory;

said circuitry further comprising;

a respective plurality of buffers for each of said random access memory blocks in said at least one of said first N random access memory blocks and said second N random access memory blocks, thereby enabling multiple read operations for reading data from said at least one of said first N random access memory blocks and said second N random access memory blocks for input to said multipliers.

24. The circuitry of claim 23 wherein each said plurality of buffers comprises a plurality of registers.

25. The circuitry of claim 20 comprising a plurality of dynamically selectable cache memories, wherein N of said plurality of cache memories are dynamically configurable as said memory.