Past Awardee

Energy Efficient Sparse Solvers

Luke Olson

College: Engineering
Award year: 2012-2013

Sparse matrix computations, such as sparse matrix-matrix or sparse matrix-vector products, play a major role in a wide variety of scientific simulations. The solution to sparse linear systems

Ax = b (1)

in particular poses a major computational challenge, and represents a significant portion of the total simulation time and ultimately power consumption of a machine. As simulations and high-performance computing environments increase in scale, the inefficiencies in the sparse matrix solves and computations will be even more pronounced. Further, increased heterogeneity in the system will add to the complexity of these computations, however also offering an opportunity to expose sparse matrix computations to multiple layers of parallelism, thus enabling more efficient computations. The goal of this fellowship is to initiate research in the direction of energy efficient sparse solvers.

Our conventional assessment of the performance of sparse iterative solvers is insufficient as we move to large-scale heterogeneous architectures. Optimal or near-optimal convergence to a solution is only one aspect in the quality of a method, and while floating point operations and total memory transfers give a more descriptive cost of a solver, the total energy consumption of a particular approach provides an additional view of the impact of the solver. In this project, we focus on developing sparse solvers with optimal accuracy per watt. For most problems, the size and sparsity of A in (1) precludes to use of a direct approach. Instead an iterative approach is necessary. Here, we consider algebraic multigrid (AMG), which is a flexible framework for developing an iterative sparse matrix solver and relies on a hierarchical approach, thus reducing the size of the problem. The advantage of a multilevel algebraic approach is that it is potentially problem independent, and is also tunable in terms of memory footprint and use of computational resources. This flexibility translates in to an opportunity to develop a highly energy efficient approach to solving sparse matrix problems.