# US 10,872,130 B2 · High performance QR decomposition systems and methods

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,872,130 B2
- Document ID: US10872130B2
- Status: Granted
- Kind: B2
- Application number: 15/692,659
- Filed: 2017-08-31
- Published: 2018-10-04
- Granted: 2020-12-22
- Earliest claimed: 2017-04-04
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Martin Langhammer
- Web page: https://patentgrep.com/patent/US10872130B2

## CPC

- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 7/50: Adding; Subtracting (G06F7/483 - G06F7/491, G06F7/544 - G06F7/556 take precedence)
- H03K 19/1733: {Controllable logic circuits (H03K19/177 takes precedence)}
- H03K 19/17704: the logic functions being realised by the interconnection of rows and columns
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03K: PULSE TECHNIQUE (measuring pulse characteristics G01R; modulating sinusoidal oscillations with pulses H03C; transmission of digital information H04L; discriminator circuits detecting phase difference between two signals by counting or integrating cycles of oscillation H03D3/04; automatic control, starting, synchronisation or stabilisation of generators of electronic oscillations or pulses where the type of generator is irrelevant or unspecified H03L; coding, decoding or code conversion, in general H03M)

## Abstract

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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 2)

The integrated circuit of claim 2, wherein the integrated circuit comprises:
one or more compute cores that utilize the QR decomposition.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 4)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 9)

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.

### Claim 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.

### Claim 12 (depends on 11)

The machine-readable medium of claim 11, wherein the programmable integrated circuit comprises a field programmable gate array.

### Claim 13 (depends on 11)

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.

### Claim 14 (depends on 11)

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.

### Claim 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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 15)

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.

### Claim 19 (depends on 15)

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.

### Claim 20 (depends on 15)

The hardware implemented method of claim 15, comprising:
utilizing the QR decomposition via one or more compute cores.