1 of 20

Cholesky Decomposition

July 2024

ABC

OCP ODSA HPC & AI Modularity

2 of 20

References

Cholesky Factorization on SIMD multi-core architectures, Florian Lemaitre, Benjamin Counturier, Lionel Lacassagne, HAL,2017. https://hal.science/hal-01550129

A Reconfigurable Processing Element for Cholesky Decomposition and Matrix Inversion, Aki Happonen, Adrian Burian, Erwin Hemming, 2005, https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=684fdee32b3dc8c9d8a888e032f7e6c64bfa17f4

Sparse Cholesky Factorization on FPGA using Parameterized model, Yichun Sun, Hengzhu Liu, Tong Zhou, https://onlinelibrary.wiley.com/doi/10.1155/2017/3021591

NOTE: This is not a comprehensive lit search/survey

3 of 20

Cholesky Factorization

Source:[1]

4 of 20

Cholesky Factorization

Floating points operation[1]

5 of 20

Cholesky Factorization FPGA architecture Implementation

12 bit FPGA implementation[2]

6 of 20

Cholesky Factorization FPGA architecture Implementation

12 bit FPGA implementation[2]

LUT Log2Dec Architecture

Control command

7 of 20

Cholesky Factorization architecture Implementation

Vector architecture [3]

The computation modules are Fet_num, Sqrt_Div, and Mul_Sub. The storage components include 5 FIFOs (First Input First Output, implemented by RAM) and RAMs for increasing buffer when data is transforming. Fet_num gets data from F_FIFO (it stores frontal matrix which is F_j in Algorithm 3) and Uc_FIFO (it stores update matrix which is the output F_j in Algorithm 4) and combines with the data and the index that is located in data to finish extended addition operation. Then the operation in Sqrt_Div module starts up. The operation in Sqrt_Div is to finish the decomposition of column, which includes division and extraction of a root. The implementation of division and extraction of a root are based on SRT algorithm (it is usually called Digit Recurrence algorithm) and they share the implementation of SRT algorithm. Lt_FIFO stores the results of L(t, j). The output data from Sqrt_Div is divided into two parts: L(∗, j) is the final results and it is stored in L_FIFO. L(k, j) is stored in LRAM for updating. Data in LRAM is for Mul_Sub to generate update matrix. Mul_Sub includes multiplication and subtraction operation. Algorithm 4 is implemented in this module. The initial data in Cholesky factorization is obtained from DDR memory and the results after factorization are also stored in DDR.

8 of 20

Cholesky Factorization architecture Implementation

Cmod and Cdiv Processing Elements

Cmod Processing Elements [3]

Cdiv Processing Elements [3]

9 of 20

Cholesky Factorization architecture Implementation

Vector Version of Cholesky Algorithm[3]

Algorithm 4: Updating algorithm of front matrix Fj

Algorithm 3: Multifrontal Cholesky algorithm in vector version

10 of 20

Choesky Factorization Architecture

Execution of Cdiv with Mlane in PE

11 of 20

Performance Analysis

The analysis of sparse Cholesky factorization performance[3]

12 of 20

Evaluation dataset

nd24k

13 of 20

Evaluation dataset

nd3k

14 of 20

Evaluation dataset

shipsec1

15 of 20

Evaluation dataset

Trefethen_20000b

16 of 20

Performance Analysis

M=1;k=1 [3]

m is the number of PEs and k is the number of modules in one PE.

17 of 20

Performance Analysis

M=1;k=2 [3]

18 of 20

Performance Analysis

M=2;k=1 [3]

19 of 20

Performance Analysis

M=2;k=2 [3]

20 of 20

Performance Comparison

HSL_MA87 solver for multicore CPU platforms ; the GPU version of CHOLMOD solver for CPU-GPU platforms; subtree-based parallel methods for CPU-GPU platforms; Ours denotes prior art[3].
HSL_MA87, CHOLMOD, and GPU is 2.5 GHz, 3.2 GHz, and 2.93 GHz . Prior Art[3] frequency is 200 MHz.