Abstract
This chapter shows several new programming strategies based on tasking to parallelize sparse linear algebra kernels. The reader will explore different approaches to improve the performance of these kernels thanks to a better workload distribution and comprehension of the data layout. This will be accomplished through the study of some of the most popular and widely used sparse operations, such as SpMV (sparse matrix vector multiplication), GTSV (triangular solve), or CG (conjugate gradient). Those strategies have been tested on multicore systems. Some of them equipped GPU devices, showcasing how to overcome the peculiarities of task-based parallelized kernels in the context of sparse linear algebra computations.
TopSparse Matrix-Vector Multiplication (Spmv)
The sparse matrix-vector product (SpMV) is defined as:𝑦:= 𝛼𝐴𝑥 + 𝛽𝑦,where 𝑥 and y are dense vectors, 𝛼 and 𝛽 are scalars, and 𝐴 is a sparse matrix. In this section, several strategies are proposed in order to parallelize the SpMV kernel, which operates on an input matrix stored in CSR format (Langr, 2016).
SpMV is characterized by being a highly unbalanced operation. Due to the sparse nature of the input matrix, the access pattern to the elements turns out to be non-uniform. This aspect has been tackled in literature from two main perspectives: proposing several storage formats for the input matrix and designing different implementations for the SpMV kernel in order to palliate this effect. This section is focused on the implementation of task-based strategies to parallelize the kernel and balance the computations among the cores. The reader will find, along with the explanation of the strategies, performance results for 12 matrices from the SuiteSparse Matrix Collection (Davis, 2011), formerly the University of Florida Sparse Matrix Collection, that illustrate the behavior of each technique. Matrices are named m1 to m12 and categorized as unbalanced (m4, m5, m7 and m12) or balanced matrices (m1-m3, m6, m8-m11), depending on the variability of non-zeros per row (See Figure 1). Moreover, reference results from Intel MKL single-threaded and multi-threaded SpMV kernels are included.
Figure 1. Input matrices from the SuitSparse Matrix Collection (Davis & Hu, 2011)
Key Terms in this Chapter
Final Clause: Regarding a task, specifies it as the last one in that branch of the DAG. If nested tasks exist, they will not be created if the final clause evaluates as true.
Weak-Dependencies: Relaxation of the data dependencies existing between child and parent tasks, allowing the execution of the former even before the parent’s dependencies are fulfilled.
Dependencies: Conditions to be fulfilled before one task can be executed.
Tasks: Unit of execution with a variable workload in a multi-tasking environment.
Nesting: Structure that contains one or more similar structures, isolating the inner ones from the outer scope, e.g., a task that contains more tasks.