  Sparse Triangular Solve (SpTRSV) is an important computational kernel used in
the solution of sparse linear algebra systems in many scientific and
engineering applications. It is diffcult to parallelize SpTRSV in today's
architectures. The limited parallelism due to the dependencies between
calculations and the irregular nature of the computations require an effective
load balancing and synchronization mechanism approach. In this work, we present
a novel graph transformation method where the equation representing a row is
rewritten to break the dependencies. Using this approach, we propose a
dependency graph transformation and code generation framework that increases
the parallelism of the parts of a sparse matrix where it is scarce, reducing
the need for synchronization points. In addition, the proposed framework
generates specialized code for the transformed dependency graph on CPUs using
domain-specific optimizations.
