README

RACE-Recursive Algebraic Coloring Engine is a graph library serving two main functionalities:

Coloring	Temporal blocking
Parallelization of sparse matrix kernels having distance-k (k>=1) dependencies.	Allows for cache blocking of multiple calls of a sparse kernel.
For example kernels like Gauss-Seidel, SpMTV, SymmSpMV and Kaczmarz.	For example the matrix power kernel (MPK) where multiple SpMVs are used.

RACE works on the graph of the matrix and is an algebraic approach. Several techniques have been implemented in RACE to boost the runtime performance of the kernels on modern CPUs. The input to RACE is the graph (matrix), the targetted optimization (coloring or temporal blocking) and paramters related to targetted optimization.

FEATURES

• Hardware friendly
• Solve Distance-1, Distance-2 dependencies in kernels and allows to cache block MPK-style kernels
• Supports pre-processing and processing phase
• Easy parallelisation and blocking, user needs to just supply serial kernel
• Support for CRS data format

How to build RACE?

• git clone git@bitbucket.org:essex/race.git
• cd race && mkdir build && cd build
• CC=$(C\_COMPILER) CXX=$(CXX\_COMPILER) cmake .. -DCMAKE_INSTALL_PREFIX=(where to install)
• Configure the library using ccmake . (if needed)
• make
• make install
• Library Dependencies : hwloc, Intel SpMP, GAP. The libraries will be cloned and installed if needed.
• When using RACE library, use CMAKE find_package to get the proper linking flags for the library.

Want to try RACE?

RACE provides examples to illustrate the usage and easiness of using the RACE library. Please see the example folder.

Working of RACE coloring

Citing RACE

If you are using RACE for coloring please use the following reference:

• C. L. Alappat, G. Hager, O. Schenk, J. Thies, A. Basermann, A. R. Bishop, H. Fehske, and G. Wellein: A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication, published in ACM TOPC journal. doi:10.1145/3399732

If you are using RACE for matrix power or temporal blocking of sparse matrices please use the following reference:

• C. L. Alappat, G. Hager, O. Schenk, and G. Wellein: Level-based Blocking for Sparse Matrices: Sparse Matrix-Power-Vector Multiplication. Accepted for publication in IEEE TPDS. Preprint: arXiv:2205.01598

Further Reading

• A poster on RACE was presented at SC'18. The poster and abstract can be found here.
• A short paper on RACE showing how it can be used to parallelise an eigen value solver can be found here. The paper won the second place in ACM SRC 2019.