High performance QR decomposition systems and methods
Based on a Modified Gram-Schmidt (MGS) algorithm, QR decomposition techniques are optimized for parallel structures that provide arithmetic-logic unit (ALU) to ALU connectivity. The techniques utilize a different loop organization, but the dependent functional sequences of the algorithm are unchanged, thereby reducing likelihood of affecting error analysis and/or numerical stability. Some integrated circuit devices (e.g., FPGA) may implement hard floating-point (HFP) circuitry, such as a digital signal processing (DSP) block, distributed memories, and/or flexible internal connectivity, which can support the discussed high performance matrix arithmetic.
1. An integrated circuit device, comprising:
a memory device communicatively coupled to circuitry, wherein:
the memory device stores an input matrix, having dimensions of size-n;
the circuitry comprises:
a multiply-add datapath communicatively coupled to an output of the memory device;
a dot product datapath communicatively coupled to an output of the multiply-add datapath, via a feed-forward coupling; and
one or more elementary function blocks communicatively coupled to an output of the dot product datapath; and
the circuitry comprises a hardware arrangement that utilizes both the multiply-add datapath and the dot product datapath at the same time to process the input matrix.
2. The integrated circuit device of claim 1 , comprising:
circuitry implemented to receive the input matrix;
circuitry implemented to perform a QR decomposition of the input matrix; and
circuitry implemented to provide a result of the QR decomposition.
3. The integrated circuit device of claim 2 , wherein:
a Q matrix and an R matrix are calculated at the same time; and
wherein only the Q matrix is stored.
4. The integrated circuit of claim 2 , wherein the integrated circuit comprises:
one or more compute cores that utilize the QR decomposition.
5. The integrated circuit of claim 4 , wherein the one or more compute cores comprise:
a size-n dot product compute core, a size-n multiply-add compute core, a division compute core, an inverse square-root compute core, or any combination thereof.
6. The integrated circuit of claim 4 , wherein the one or more compute cores comprise: a size-m dot product compute core, a size-m multiply-add compute core, a division compute core, an inverse square-root compute core, or any combination thereof;
wherein the size-m cores are a smaller dimension than the size-n, and multiple cycles are required to process one iteration of a vector.
7. The integrated circuit device of claim 1 , comprising:
a first feedback path communicatively from a node between the multiply-add datapath and the dot product datapath to an input of the memory device; and
a second feedback path communicatively coupled from an output of the one or more elementary function blocks to a first input of the multiply-add datapath.
8. The integrated circuit device of claim 7 , wherein:
data from the output of the multiply-add datapath is written to the input of the memory device and an input of the dot product datapath simultaneously.
9. The integrated circuit device of claim 8 , wherein:
circuitry between the output of the one or more elementary function blocks and a second input of the multiply-add datapath delays data output from the one or more elementary function blocks by a variable number of clock cycles.
10. The integrated circuit device of claim 9 , wherein:
the multiply-add datapath may be bypassed and data sent directly to the dot product datapath by zeroing the second input of the multiply-add datapath, and writing the data to the first input of the multiply-add datapath.
11. A tangible, non-transitory, machine-readable medium, comprising machine-readable instructions that, when executed by one or more processors, cause the processors to:
generate one or more compute cores of a programmable integrated circuit, wherein the one or more compute cores are coupled to a memory device which stores an input matrix, having dimensions of size-n, wherein the one or more compute cores utilize a multiply-add datapath communicatively coupled to an output of the memory device, a dot product datapath communicatively coupled to an output of the multiply-add datapath, and one or more elementary function blocks communicatively coupled to an output of the dot product datapath in order to perform a QR decomposition of the input matrix to obtain computational results, wherein the multiply-add datapath and the dot product datapath are used at the same time to perform the QR decomposition of the input matrix; and
provide the one or more compute cores for implementation on the programmable integrated circuit.
12. The machine-readable medium of claim 11 , wherein the programmable integrated circuit comprises a field programmable gate array.
13. The machine-readable medium of claim 11 , wherein the one or more compute cores comprise:
a size-n dot product compute core, a size-n multiply-add compute core, a division compute core, an inverse square-root compute core, or any combination thereof.
14. The machine-readable medium of claim 11 , wherein the one or more compute cores comprise: a size-m dot product compute core, a size-m multiply-add compute core, a division compute core, an inverse square-root compute core, or any combination thereof;
wherein the size-m cores are a smaller dimension than the size-n, and multiple cycles are required to process one iteration of a vector.
15. A hardware implemented method, comprising:
storing an input matrix in a memory device;
communicatively coupling a multiply-add datapath to an output of the memory device;
communicatively coupling a dot product datapath to an output of the multiply-add data path;
communicatively coupling one or more elementary function blocks to an output of the dot product datapath; and
performing a QR decomposition of the input matrix to obtain computational results, using the multiply-add datapath, the dot product datapath, and the one or more elementary function blocks, wherein the multiply-add datapath and the dot product datapath are used at the same time to perform the QR decomposition of the input matrix.
16. The hardware implemented method of claim 15 , comprising:
writing data from the output of the multiply-add datapath to an input of the memory device and an input of the dot product datapath simultaneously.
17. The hardware implemented method of claim 16 , comprising:
delaying the data by a variable number of clock cycles between an output of the one or more elementary function blocks and an input of the multiply-add datapath.
18. The hardware implemented method of claim 15 , comprising:
bypassing the multiply-add datapath and sending data directly to the dot product datapath by zeroing a first input of the multiply-add datapath, and writing the data to a second input of the multiply-add datapath.
19. The hardware implemented method of claim 15 , comprising:
calculating a Q matrix and an R matrix at the same time; and
wherein only the Q matrix is stored.
20. The hardware implemented method of claim 15 , comprising:
utilizing the QR decomposition via one or more compute cores.