`QRD` Sample

The QRD reference design demonstrates high-performance QR decomposition of real and complex matrices on an FPGA.

Area	Description
What you will learn	How to implement a high performance FPGA version of QR decomposition algorithm.
Time to complete	1 hr (not including compile time)
Category	Reference Designs and End to End

Purpose

This FPGA reference design demonstrates QR decomposition of matrices of complex/real numbers, a common operation employed in linear algebra. Matrix A (input) is decomposed into a product of an orthogonal matrix Q and an upper triangular matrix R.

The algorithms employed by the reference design are the Gram-Schmidt process QR decomposition algorithm and the thin QR factorization method. The original algorithm has been modified and optimized for performance on FPGAs in this implementation.

QR decomposition is used extensively in signal processing applications such as beamforming, multiple-input multiple-output (MIMO) processing, and Space Time Adaptive Processing (STAP).

Note: Read the QR decomposition Wikipedia article for more information on the algorithms.

Prerequisites

This sample is part of the FPGA code samples. It is categorized as a Tier 4 sample that demonstrates a reference design.

flowchart LR
   tier1("Tier 1: Get Started")
   tier2("Tier 2: Explore the Fundamentals")
   tier3("Tier 3: Explore the Advanced Techniques")
   tier4("Tier 4: Explore the Reference Designs")

   tier1 --> tier2 --> tier3 --> tier4

   style tier1 fill:#0071c1,stroke:#0071c1,stroke-width:1px,color:#fff
   style tier2 fill:#0071c1,stroke:#0071c1,stroke-width:1px,color:#fff
   style tier3 fill:#0071c1,stroke:#0071c1,stroke-width:1px,color:#fff
   style tier4 fill:#f96,stroke:#333,stroke-width:1px,color:#fff

Loading

Find more information about how to navigate this part of the code samples in the FPGA top-level README.md. You can also find more information about troubleshooting build errors, links to selected documentation, etc.

Optimized for	Description
OS	Ubuntu* 20.04 RHEL/CentOS 8 SUSE* 15 Windows* 10, 11 Windows Server* 2019
Hardware	Intel® Agilex® 7, Arria® 10, and Stratix® 10 FPGAs
Software	Intel® oneAPI DPC++/C++ Compiler

Note: Even though the Intel DPC++/C++ oneAPI compiler is enough to compile for emulation, generating reports and generating RTL, there are extra software requirements for the simulation flow and FPGA compiles.

For using the simulator flow, Intel® Quartus® Prime Pro Edition and one of the following simulators must be installed and accessible through your PATH:

Questa*-Intel® FPGA Edition

Questa*-Intel® FPGA Starter Edition

ModelSim® SE

When using the hardware compile flow, Intel® Quartus® Prime Pro Edition must be installed and accessible through your PATH.

⚠️ Make sure you add the device files associated with the FPGA that you are targeting to your Intel® Quartus® Prime installation.

⚠️ This code sample may fail to compile with the Intel® oneAPI DPC++/C++ Compiler 2024.2 due to a known bug which will be fixed in a patch. Information about the patch will be available on https://www.intel.com/content/www/us/en/developer/tools/oneapi/fpga.html

Performance

Performance results are based on testing as of May 14, 2024.

Note: Refer to the Performance Disclaimers section for important performance information.

Device	Throughput
Intel® FPGA SmartNIC N6001-PL	50k matrices/s for complex matrices of size 128 * 128

Key Implementation Details

The QR decomposition algorithm factors a complex m × n matrix, where m ≥ n. The algorithm computes the vector dot product of two columns of the matrix. In our FPGA implementation, the dot product is computed in a loop over the column's m elements. The loop is unrolled fully to maximize throughput. The m complex multiplication operations are performed in parallel on the FPGA followed by sequential additions to compute the dot product result.

With this optimization, our FPGA implementation requires 4m DSPs to compute the complex floating point dot product or 2m DSPs for the real case. The matrix size is constrained by the total FPGA DSP resources available.

By default, the design is parameterized to process 128 × 128 matrices on complex floating-point datatype; however, the design can process matrices from 4 x 4 to 512 x 512.

To optimize the performance-critical loop in its algorithm, the design leverages concepts discussed in the following FPGA tutorials:

Triangular Loop Optimization (triangular_loop)
Explicit Pipelining with fpga_reg (fpga_register)
Loop ivdep Attribute (loop_ivdep)
Unrolling Loops (loop_unroll)

The key optimization techniques used are as follows:

Refactoring the original Gram-Schmidt algorithm to merge two dot products into one, reducing the total number of dot products needed to three from two. This helps us reduce the DSPs required for the implementation.
Converting the nested loop into a single merged loop and applying Triangular Loop optimizations. This allows us to generate a design that is very well pipelined.
Fully vectorizing the dot products using loop unrolling.
Using an efficient memory banking scheme to generate high performance hardware.
Using the fpga_reg attribute to insert more pipeline stages where needed to improve the frequency achieved by the design.

Compiler Flags Used

Flag	Description
`-Xshardware`	Target FPGA hardware (as opposed to FPGA emulator)
`-Xsclock=360MHz`	The FPGA backend attempts to achieve 360 MHz
`-Xsparallel=2`	Use 2 cores when compiling the bitstream through Intel® Quartus®
`-Xsseed`	Specifies the Intel® Quartus® compile seed, to yield slightly higher fmax

Additionaly, the cmake build system can be configured using the following parameters:

cmake option	Description
`-DSET_ROWS_COMPONENT`	Specifies the number of rows of the matrix
`-DSET_COLS_COMPONENT`	Specifies the number of columns of the matrix
`-DSET_FIXED_ITERATIONS`	Used to set the ivdep safelen attribute for the performance critical triangular loop
`-DSET_COMPLEX`	Used to select between the complex and real QR decomposition (complex is the default)

Note: The values for seed, -DSET_FIXED_ITERATIONS, -DSET_ROWS_COMPONENT, -DSET_COLS_COMPONENT and -DSET_COMPLEX depend on the board being targeted.

Build the `QRD` Design

Note: When working with the command-line interface (CLI), you should configure the oneAPI toolkits using environment variables. Set up your CLI environment by sourcing the setvars script located in the root of your oneAPI installation every time you open a new terminal window. This practice ensures that your compiler, libraries, and tools are ready for development.

Linux*:

For system wide installations: . /opt/intel/oneapi/setvars.sh

For private installations: . ~/intel/oneapi/setvars.sh

For non-POSIX shells, like csh, use the following command: bash -c 'source <install-dir>/setvars.sh ; exec csh'

Windows*:

C:\"Program Files (x86)"\Intel\oneAPI\setvars.bat

Windows PowerShell*, use the following command: cmd.exe "/K" '"C:\Program Files (x86)\Intel\oneAPI\setvars.bat" && powershell'

For more information on configuring environment variables, see Use the setvars Script with Linux* or macOS* or Use the setvars Script with Windows*.

On Linux*

Change to the sample directory.
Configure the build system for the Agilex® 7 device family, which is the default.
```
mkdir build
cd build
cmake ..
```
Note: You can change the default target by using the command:
```
cmake .. -DFPGA_DEVICE=<FPGA device family or FPGA part number>
```
Alternatively, you can target an explicit FPGA board variant and BSP by using the following command:
```
cmake .. -DFPGA_DEVICE=<board-support-package>:<board-variant> -DIS_BSP=1
```
The build system will try to infer the FPGA family from the BSP name. If it can't, an extra option needs to be passed to cmake: -DDEVICE_FLAG=[A10|S10|Agilex7] Note: You can poll your system for available BSPs using the aoc -list-boards command. The board list that is printed out will be of the form
```
$> aoc -list-boards
Board list:
  <board-variant>
     Board Package: <path/to/board/package>/board-support-package
  <board-variant2>
     Board Package: <path/to/board/package>/board-support-package
```
You will only be able to run an executable on the FPGA if you specified a BSP.
Compile the design. (The provided targets match the recommended development flow.)
1. Compile for emulation (fast compile time, targets emulated FPGA device).
```
make fpga_emu
```
2. Compile for simulation (fast compile time, targets simulator FPGA device):
```
make fpga_sim
```
3. Generate HTML performance report.
```
make report
```
  The report resides at qrd_report/reports/report.html.
4. Compile for FPGA hardware (longer compile time, targets FPGA device).
```
make fpga
```

On Windows*

Change to the sample directory.
Configure the build system for the Agilex® 7 device family, which is the default.
```
mkdir build
cd build
cmake -G "NMake Makefiles" ..
```

Note: You can change the default target by using the command:
cmake -G "NMake Makefiles" .. -DFPGA_DEVICE=<FPGA device family or FPGA part number>
Alternatively, you can target an explicit FPGA board variant and BSP by using the following command:
cmake -G "NMake Makefiles" .. -DFPGA_DEVICE=<board-support-package>:<board-variant> -DIS_BSP=1
The build system will try to infer the FPGA family from the BSP name. If it can't, an extra option needs to be passed to cmake: -DDEVICE_FLAG=[A10|S10|Agilex7] Note: You can poll your system for available BSPs using the aoc -list-boards command. The board list that is printed out will be of the form
$> aoc -list-boards
Board list:
  <board-variant>
     Board Package: <path/to/board/package>/board-support-package
  <board-variant2>
     Board Package: <path/to/board/package>/board-support-package
You will only be able to run an executable on the FPGA if you specified a BSP.

Compile the design. (The provided targets match the recommended development flow.)
1. Compile for emulation (fast compile time, targets emulated FPGA device).
```
nmake fpga_emu
```
2. Compile for simulation (fast compile time, targets simulator FPGA device):
```
nmake fpga_sim
```
3. Generate HTML performance report.
```
nmake report
```
  The report resides at qrd_report.a.prj/reports/report.html.
4. Compile for FPGA hardware (longer compile time, targets FPGA device).
```
nmake fpga
```

Note: If you encounter any issues with long paths when compiling under Windows*, you may have to create your 'build' directory in a shorter path, for example C:\samples\build. You can then run cmake from that directory, and provide cmake with the full path to your sample directory, for example:
C:\samples\build> cmake -G "NMake Makefiles" C:\long\path\to\code\sample\CMakeLists.txt

Run the `QRD` Design

Configurable Parameters

Argument	Description
`<num>`	(Optional) Specifies the number of times to repeat the decomposition of a set of 8 matrices (only 1 matrix when running simulation). Its default value is 16 for the emulation flow, 1 for the simulation flow and 819200 for the FPGA flow.

You can perform the QR decomposition of the set of matrices repeatedly. This step performs the following:

Generates the set of random matrices.
Computes the QR decomposition of the set of matrices.
Repeats the decomposition multiple times (specified as a command line argument) to evaluate performance.

On Linux

Run the sample on the FPGA emulator (the kernel executes on the CPU).
```
export CL_CONFIG_CPU_FORCE_PRIVATE_MEM_SIZE=32MB
./qrd.fpga_emu
```
- Increase the amount of memory that the emulator runtime is permitted to allocate by exporting the CL_CONFIG_CPU_FORCE_PRIVATE_MEM_SIZE environment variable before running the executable.

Run the sample on the FPGA simulator.

CL_CONTEXT_MPSIM_DEVICE_INTELFPGA=1 ./qrd.fpga_sim

Run the sample on the FPGA device (only if you ran cmake with -DFPGA_DEVICE=<board-support-package>:<board-variant>).
```
./qrd.fpga
```

On Windows

Run the sample on the FPGA emulator (the kernel executes on the CPU).
```
set CL_CONFIG_CPU_FORCE_PRIVATE_MEM_SIZE=32MB
qrd.fpga_emu.exe
```
- Increase the amount of memory that the emulator runtime is permitted to allocate by setting the CL_CONFIG_CPU_FORCE_PRIVATE_MEM_SIZE environment variable before running the executable.

Run the sample on the FPGA simulator.

set CL_CONTEXT_MPSIM_DEVICE_INTELFPGA=1
qrd.fpga_sim.exe
set CL_CONTEXT_MPSIM_DEVICE_INTELFPGA=

Note: Hardware runs are not supported on Windows.

Example Output

Example output when running on Intel® FPGA SmartNIC N6001-PL for the decomposition of 8 matrices 819200 times (each matrix consisting of 128x128 complex numbers).

Running on device: ofs_n6001 : Intel OFS Platform (ofs_ee00000)
Generating 8 random complex matrices of size 128x128 
Running QR decomposition of 8 matrices 819200 times
   Total duration:   130.636 s
Throughput: 50.1669k matrices/s
Verifying results...
PASSED

License

Code samples are licensed under the MIT license. See License.txt for details.

Third party program Licenses can be found here: third-party-programs.txt.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

README.md

README.md

`QRD` Sample

Purpose

Prerequisites

Performance

Key Implementation Details

Compiler Flags Used

Build the `QRD` Design

On Linux*

On Windows*

Run the `QRD` Design

Configurable Parameters

On Linux

On Windows

Example Output

License

Files

README.md

Latest commit

History

README.md

File metadata and controls

QRD Sample

Purpose

Prerequisites

Performance

Key Implementation Details

Compiler Flags Used

Build the QRD Design

On Linux*

On Windows*

Run the QRD Design

Configurable Parameters

On Linux

On Windows

Example Output

License

`QRD` Sample

Build the `QRD` Design

Run the `QRD` Design