RACE-Recursive Algebraic Coloring Engine is a graph coloring library that helps in parallelization of sparse matrix kernels having distance-k (k>=1) dependencies.RACE uses a recursive level based method for coloring.

This repository has a pre-compiled library of RACE provided and several example kernels (with loop-carried dependencies) which can be run with the help of RACE library.


  • Hardware friendly
  • Solve Distance-1 & Distance-2 dependencies kernels
  • Supports pre-processing and processing phase
  • Easy parallelisation, user needs to just supply serial kernel
  • Support for CRS and SELL-C-sigma data formats
  • Self-pinning

How to build RACE examples?

  • git clone
  • cd race && mkdir build && cd build
  • Configure the library using ccmake . (if needed)
  • make
  • Library Dependencies : hwloc (will be cloned and installed if not found)

How to run RACE examples?

RACE provides examples to illustrate the usage and easiness of using the RACE library. To try it out:

  • make
  • To run: ./race -m [matrix file] -c [nthreads]
  • To get other options use: ./race -h

Artifact Description for experiment runs

  • Most of the matrices (24) where taken from SparseSuite Matrix collection (
  • Rest of the matrices (4) from quantum physics can be generated using GHOST and PHYSICS framework (
  • Performance reported is the mean of 1000 iterations
  • Internally library pins the thread and FILL type pinning strategy was used
  • For level construction RCM from Intel SpMP library was used (switch on RACE_USE_SPMP in the CMake configuration option)
  • The efficiency of each stage in recursion was set to 80%
  • So runs are as such: RACE_EFFICIENCY=80,80 OMP_NUM_THREADS=[nthreads] taskset -c 0-$((nthreads-1)) ./race -m [matrix file] -c [nthreads] -i 1000

RACE working

Screenshot Scrrentshot