Cholesky decomposition in an integrated circuit device
AssigneeAltera Corporation
InventorsLei Xu, Martin Langhammer
Life of this patent
Estimating the term…
Abstract
Efficient and scalable circuitry for performing Cholesky decomposition is based on two types of processing elements. A first type of processing element provides inverse square root and multiplication operations. A second type of processing element includes a first computation path for outputting an inner product difference element and a second computation path for outputting an inner product element. Processing elements of the first and second type may be cascaded to achieve a decomposition of a matrix of an arbitrary size. The circuitry is flexible to allow different throughput requirements, and can be optimized to reduce latency and resource consumption.
Claims21
Circuitry for decomposing an input matrix, the circuitry comprising:
- a plurality of processing elements of a first type for outputting respective elements of a triangulated resultant matrix;
- and
- a plurality of processing elements of a second type respectively coupled to outputs of the plurality of processing elements of the first type, for outputting respective inner product elements corresponding to respective elements of said resultant matrix, wherein each of the inner product elements is a single number.
A method of configuring a programmable integrated circuit device for triangulating an input matrix to create a resultant matrix, said method comprising:
- configuring logic of said programmable integrated circuit device as a plurality of processing elements of a first type for outputting respective elements of the resultant matrix;
- and
- configuring logic of said programmable integrated circuit device as a plurality of processing elements of a second type, coupled to outputs of the plurality of processing elements of the first type, for outputting respective product elements of said resultant matrix corresponding to respective elements of said input matrix, whereby:
- each processing element of the plurality of processing elements of the second type comprises a first and second computation path,
- the first computation path being operable to add or subtract a product of respective elements of the resultant matrix from a respective element of the input matrix to output a respective product difference element, and
- the second computation path being operable to combine respective elements of the resultant matrix to output a respective inner product element, wherein the respective inner product element is a single number.
A method for decomposing an input matrix, the method comprising:
- outputting, with a plurality of processing elements of a first type, respective elements of a triangulated resultant matrix;
- and
- outputting, with a plurality of processing elements of a second type, respective inner product elements corresponding to respective elements of said resultant matrix, wherein the processing elements of the second type are respectively coupled to outputs of the plurality of processing elements of the first type, wherein each of the respective inner product elements is a single number.
Dependencies are inferred from the claim text.