Projects‎ > ‎

GPU Computing

Project description

The sparse matrix storage scheme (format) has great
impact on performance and scalability of the sparse matrix-vector
multiplication operation and other iterative algorithms for sparse
matrix computations. Ideal format ensures minimal memory storage
requirements, maximum utilization of floating point vector units,
maximum utilization of cache memories, and enables load balanced
parallelization of the algorithms on massively parallel systems.

State of the art

Several sparse matrix formats have been proposed and some are due to their
simplicity widely used, such as Compressed Sparse Row/Column (CSR/CSC) or
Jagged Diagonal Storage (JDS) formats. The feasibility of particular
format is given mainly by the sparsity pattern of a matrix. Sparse
matrices often contain dense submatrices (blocks). Therefore, some formats
use blocking techniques which exploit knowledge about clustering of matrix
non-zero entries. These blocking formats like SPARSITY, CARB, or M-CARB or
based on based on quadtree storage scheme, may give significantly better
performance of the algorithms on sparse matrices than allows the CSR
format, due to eliminating memory read stalls, consuming less memory, 
allowing a better use of registers, and improving vector unit utilization.
But these specialized and efficient formats have also some drawbacks. They
suffer from a large transformation overhead, are designed only for a
limited set of matrix operations, or do not support fast adding or
removing nonzero elements.

Future research

This project goal is to conduct research of new sparse-matrix formats
for massively parallel architectures with the goal to address these
trade-offs and develop optimization heuristics for using these formats for
sparse matrix operations. The project will build on the results
of the dissertation thesis of Ivan.Šimeček.
These sparse-matrix formats should be used for efficient implementation of
numerical linear algebra operations like LU factorization or eigensolvers.

Soucre codes

pripadne odkaz na zdrojaky