Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A Recursive Algebraic Coloring Technique for Hardware-Efficient
  Symmetric Sparse Matrix-Vector Multiplication   The symmetric sparse matrix-vector multiplication (SymmSpMV) is an important
building block for many numerical linear algebra kernel operations or graph
traversal applications. Parallelizing SymmSpMV on today's multicore platforms
with up to 100 cores is difficult due to the need to manage conflicting updates
on the result vector. Coloring approaches can be used to solve this problem
without data duplication, but existing coloring algorithms do not take load
balancing and deep memory hierarchies into account, hampering scalability and
full-chip performance. In this work, we propose the recursive algebraic
coloring engine (RACE), a novel coloring algorithm and open-source library
implementation, which eliminates the shortcomings of previous coloring methods
in terms of hardware efficiency and parallelization overhead. We describe the
level construction, distance-k coloring, and load balancing steps in RACE, use
it to parallelize SymmSpMV, and compare its performance on 31 sparse matrices
with other state-of-the-art coloring techniques and Intel MKL on two modern
multicore processors. RACE outperforms all other approaches substantially and
behaves in accordance with the Roofline model. Outliers are discussed and
analyzed in detail. While we focus on SymmSpMV in this paper, our algorithm and
software is applicable to any sparse matrix operation with data dependencies
that can be resolved by distance-k coloring.

28
The categories of this paper are: alg-geom
0
The categories of this paper are: hep-ph
2
The categories of this paper are: math
14
The categories of this paper are: math-ph
27
The categories of this paper are: comp-gas
25
The categories of this paper are: patt-sol
24
The categories of this paper are: dg-ga
32
The categories of this paper are: atom-ph
5
The categories of this paper are: gr-qc
3
The categories of this paper are: physics
16
The categories of this paper are: stat
4
The categories of this paper are: cond-mat
29
The categories of this paper are: funct-an
21
The categories of this paper are: adap-org
22
The categories of this paper are: chao-dyn
26
The categories of this paper are: bayes-an