Cholesky Example

The algorithm
The cholesky factorization is a matrix operation commonly used to solve normal equations in linear least squares problems. It mainly calculates a triangular matrix (L) from a symetric and positive definite matrix A. The product of this tiriangular matrix L and its transposed copy is A:


Note this description is just a simple overview to introduce the user to this algorithm. For more details about the algorithm this may be useful.

The source code for CellSs
The following code is the main algorithm of a blocked Cholesky factorization. The matrix A is organized in blocks of NB x NB floats, with a total of DIM x DIM blocks. The annotated application primitives (tasks) operate on these blocks. This is a requirement of CellSs programming model in order to make the tasks of enough granularity.


In each iteration only red and blue parts are updated. The bloq_upd tasks are syrk and gemm, which update the red and blue parts in this order. The following figure graphically describes how the different primitives operate upon the matrix blocks.


Each function performs a block operation which can be annotated in order to be executed in an SPU as tasks.


Some results


  • Scalability
The reference for the scalability result is calculated based on the time required by the application using 1 SPE.


  • Performance
The following graph shows the performance of the algorithm in comparison with the machine's peak.
 

Theoretical Peak 230,4 GFlops for 8 SPEs.
 

Source Files
Download Cholesky source files