Matrix operations in an integrated circuit device

• US 8,577,951 B1
• Filed: 08/19/2010
• Issued: 11/05/2013
• Est. Priority Date: 08/19/2010
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US12/859,449
• Time in Patent Office: 1,174 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

Circuitry can be provided in a fixed logic device, or can be configured into a programmable integrated circuit device such as a programmable logic device (PLD) to perform vector-based matrix operations for matrices of arbitrary size, up to a predetermined maximum size. The circuitry may be used where input row vectors of a matrix are to be combined—e.g., by multiplication—with the same initial vector, which may be one of the rows. Column memories may be provided to hold the input matrix data, so that each row may be read by simultaneously accessing the same index in each column memory. In accordance with the invention, the number of column memories may be less than the actual number of columns so that multiple physical “row access” operations are used to access each logical row. A “circular latch” may be provided to hold the initial vector.

Claims

1. Matrix operations circuitry for performing a vector operation on an input matrix having a first number of columns, said vector operation including operations combining one row of said matrix and each row of said matrix, said matrix operations circuitry comprising:

a first set of a second number of column memories, said second number being smaller than said first number, whereby at least one row of said input matrix is stored in multiple rows of said column memories;

a vector operations circuit that performs said operations combining a selected row of said matrix and each row of said matrix;

a first set of first input registers equal in number to said second number, for inputting each said row to said vector operations circuit from said column memories;

a first set of second input registers equal in number to said second number, for inputting said one row to said vector operations circuit;

a first circular latch for storing said one row; and

selection circuitry for circulating values from said selected row between said first set of second input registers and said first circular latch.

2. The matrix operations circuitry of claim 1 further comprising, for performing complex operations:

a second set of said second number of column memories for storing an imaginary part of said input matrix;

a second set of first input registers equal in number to said second number, for inputting an imaginary part of each said row to said vector operations circuit from said column memories;

a second set of second input registers equal in number to said second number, for inputting an imaginary part of said one row to said vector operations circuit; and

a second circular latch for storing an imaginary part of said one row;

wherein;

said selection circuitry further circulates values from an imaginary part of said selected row between said second set of second input registers and said second circular latch.

3. The matrix operations circuitry of claim 1 further comprises preprocessing circuitry that performs a preprocessing operation on said selected row.

4. The matrix operations circuitry of claim 3 wherein said preprocessing circuitry performs said preprocessing operation during loading of said selected row into said column memories.

5. The matrix operations circuitry of claim 4 wherein said preprocessing circuitry performs said preprocessing operation after loading of said selected row into said column memories.

6. The matrix operations circuitry of claim 3 wherein:

said preprocessing operation is an operation that also is performed later in said vector operation; and

said preprocessing circuitry also is used to perform said preprocessing operation later in said vector operation.

7. The matrix operations circuitry of claim 1 wherein:

said circular latch comprises a plurality of memories arranged in a number of circular latch columns equal to said second number, and a number of circular latch rows equal to said multiple rows; and

said selection circuitry comprises multiplexing circuitry for selectably accepting input into each of at least some of said circular latch rows from one of (a) another of said circular latch rows, and (b) said second input registers.

8. A method of configuring a programmable integrated circuit device as matrix operations circuitry for performing a vector operation on an input matrix having a first number of columns, said vector operation including operations combining one row of said matrix and each row of said matrix, said method comprising:

configuring logic of said programmable integrated circuit device as a first set of a second number of column memories, said second number being smaller than said first number, whereby at least one row of said input matrix is stored in multiple rows of said column memories;

configuring logic of said programmable integrated circuit device as a vector operations circuit that performs said operations combining a selected row of said matrix and each row of said matrix;

configuring logic of said programmable integrated circuit device as a first set of first input registers equal in number to said second number, for inputting each said row to said vector operations circuit from said column memories;

configuring logic of said programmable integrated circuit device as a first set of second input registers equal in number to said second number, for inputting said one row to said vector operations circuit;

configuring logic of said programmable integrated circuit device as a first circular latch for storing said one row; and

configuring logic of said programmable integrated circuit device as selection circuitry for circulating values from said selected row between said first set of second input registers and said first circular latch.

9. The method of claim 8 further comprising, for configuring said programmable integrated circuit device to perform complex operations:

configuring logic of said programmable integrated circuit device as a second set of said second number of column memories for storing an imaginary part of said input matrix;

configuring logic of said programmable integrated circuit device as a second set of first input registers equal in number to said second number, for inputting an imaginary part of each said row to said vector operations circuit from said column memories;

configuring logic of said programmable integrated circuit device as a second set of second input registers equal in number to said second number, for inputting an imaginary part of said one row to said vector operations circuit; and

configuring logic of said programmable integrated circuit device as a second circular latch for storing an imaginary part of said one row;

wherein;

said selection circuitry further circulates values from an imaginary part of said selected row between said second set of second input registers and said second circular latch.

10. The method of claim 8 further comprising configuring logic of said programmable integrated circuit device as preprocessing circuitry that performs a preprocessing operation on said selected row.

11. The method of claim 10 wherein said configuring logic of said programmable integrated circuit device as preprocessing circuitry comprises configuring logic of said programmable integrated circuit device to perform said preprocessing operation during loading of said selected row into said column memories.

12. The method of claim 11 wherein said configuring logic of said programmable integrated circuit device as preprocessing circuitry comprises configuring logic of said programmable integrated circuit device to perform said preprocessing operation after loading of said selected row into said column memories.

13. The method of claim 10 wherein:

said preprocessing operation is an operation that also is performed later in said vector operation; and

said configuring logic of said programmable integrated circuit device as preprocessing circuitry comprises configuring logic of said programmable integrated circuit device to perform said preprocessing operation later in said vector operation.

14. The method of claim 8 wherein:

configuring logic of said programmable integrated circuit device as a first circular latch comprises configuring a plurality of memories arranged in a number of circular latch columns equal to said second number, and a number of circular latch rows equal to said multiple rows; and

configuring logic of said programmable integrated circuit device as selection circuitry for circulating values from said selected row between said first set of second input registers and said first circular latch comprises configuring multiplexing circuitry for selectably accepting input into each of at least some of said circular latch rows from one of (a) another of said circular latch rows, and (b) said second input registers.

15. A machine-readable data memory medium encoded with machine-executable instructions for configuring a programmable integrated circuit device as matrix operations circuitry for performing a vector operation on an input matrix having a first number of columns, said vector operation including operations combining one row of said matrix and each row of said matrix, said instructions comprising:

instructions to configure logic of said programmable integrated circuit device as a first set of a second number of column memories, said second number being smaller than said first number, whereby at least one row of said input matrix is stored in multiple rows of said column memories;

instructions to configure logic of said programmable integrated circuit device as a vector operations circuit that performs said operations combining a selected row of said matrix and each row of said matrix;

instructions to configure logic of said programmable integrated circuit device as a first set of first input registers equal in number to said second number, for inputting each said row to said vector operations circuit from said column memories;

instructions to configure logic of said programmable integrated circuit device as a first set of second input registers equal in number to said second number, for inputting said one row to said vector operations circuit;

instructions to configure logic of said programmable integrated circuit device as a first circular latch for storing said one row; and

instructions to configure logic of said programmable integrated circuit device as selection circuitry for circulating values from said selected row between said first set of second input registers and said first circular latch.

16. The machine-readable data memory medium of claim 15 wherein, for configuring said programmable integrated circuit device to perform complex operations, said instructions further comprise:

instructions to configure logic of said programmable integrated circuit device as a second set of said second number of column memories for storing an imaginary part of said input matrix;

instructions to configure logic of said programmable integrated circuit device as a second set of first input registers equal in number to said second number, for inputting an imaginary part of each said row to said vector operations circuit from said column memories;

instructions to configure logic of said programmable integrated circuit device as a second set of second input registers equal in number to said second number, for inputting an imaginary part of said one row to said vector operations circuit;

instructions to configure logic of said programmable integrated circuit device as a second circular latch for storing an imaginary part of said one row; and

instructions to configure said selection circuitry to circulates values from an imaginary part of said selected row between said second set of second input registers and said second circular latch.

17. The machine-readable data memory medium of claim 16 wherein said instructions further comprise instructions to configure logic of said programmable integrated circuit device as preprocessing circuitry that performs a preprocessing operation on said selected row.

18. The machine-readable data memory medium of claim 17 wherein said instructions to configure logic of said programmable integrated circuit device as preprocessing circuitry comprise instructions to configure logic of said programmable integrated circuit device to perform said preprocessing operation during loading of said selected row into said column memories.

19. The machine-readable data memory medium of claim 18 wherein said instructions to configure logic of said programmable integrated circuit device as preprocessing circuitry comprise instructions to configure logic of said programmable integrated circuit device to perform said preprocessing operation after loading of said selected row into said column memories.

20. The machine-readable data memory medium of claim 17 wherein:

said preprocessing operation is an operation that also is performed later in said vector operation; and

said instructions to configure logic of said programmable integrated circuit device as preprocessing circuitry comprise instructions to configure logic of said programmable integrated circuit device to perform said preprocessing operation later in said vector operation.

21. The machine-readable data memory medium of claim 15 wherein:

said instructions to configure logic of said programmable integrated circuit device as a first circular latch comprise instructions to configure a plurality of memories arranged in a number of circular latch columns equal to said second number, and a number of circular latch rows equal to said multiple rows; and

said instructions to configure logic of said programmable integrated circuit device as selection circuitry for circulating values from said selected row between said first set of second input registers and said first circular latch comprise instructions to configure multiplexing circuitry for selectably accepting input into each of at least some of said circular latch rows from one of (a) another of said circular latch rows, and (b) said second input registers.