A novel graph transformation strategy for optimizing SpTRSV on CPUs

Abstract

Sparse triangular solve (SpTRSV) is an extensively studied computational kernel. An important obstacle in parallel SpTRSV implementations is that in some parts of a sparse matrix the computation is serial. By transforming the dependency graph, it is possible to increase the parallelism of the parts that lack it. In this work, we present a novel graph transformation strategy to increase the parallelism degree of a sparse matrix and compare it to our previous strategy. It is seen that our transformation strategy can provide a speedup as high as 1.42x$$ 1.42x $$.