Runtime Aggregation of Recursion Relations

摘要

In many modern algorithms, relatively regular problems are encoded using flexible general purpose data structures. To obtain satisfactory performance on distributed memory architectures, it is often necessary to reconstruct and exploit the underlying dependency structure. The authors present a method to partition loops that have runtime dependencies that resemble uniform recurrence equations. Loops of this type are often found, among other places, in solving sparse triangular linear systems for preconditioning in Krylov space iterative linear system solvers. (kr)