AbstractsEngineering

Algebraic multigrid methods for large, sparse linear systems are central to many computational simulations. Parallel algorithms for such solvers are generally decomposed into coarse-grain tasks suitable for distributed computers with traditional processing cores. Accelerating multigrid methods on massively parallel throughput-oriented processors, on the other hand, demands algorithms with abundant fine-grained parallelism. In this dissertation we analyze and decompose the smoothed aggregation algebraic multigrid method into parallel primitives effectively mapped to emerging architectures. Our formulation is performed in two phases, the first building on high-level generic abstractions to construct our solver in a architecture agnostic manner. Though effective we show that performance is severely limited by irregular sparse matrix operations, most notably sparse matrix-matrix multiplication. In the second phase, we address this performance bottleneck using novel techniques to optimize irregular sparse matrix operations. This dissertation is also concerned with irregular graph operations necessary to partition sparse matrices into disjoint sets for parallel processing. We apply our solver to accelerate eigenvector computations necessary during spectral partitioning methods and find that performance is limited by multigrid construction. We propose and analyze a novel strategy to accelerate graph Laplacian eigenvector computations by combining iterative methods, namely blocked Lanczos, with breadth first search operations on graphs. By basing our partitioner on primitives with substantial parallelism we demonstrate notable performance improvement compared with generic eigensolvers.