Improving performance and energy of parallel sparse computations through hybrid linear solvers and model-driven optimization

Parallel sparse computations encompass a wide range of applications including high performance computing (HPC) and more recently desktop applications. Though diverse, these applications share the trait of irregular data accesses leading to poor performance and increased energy consumption. Irregular data access has become an even greater concern for applications as computer systems have more computational cores that share complex levels of memory. Accesses within these levels are penalized based on the distance between core and memory, and may affect the performance of other threads. In order to mitigate challenges with parallel sparse computations, this work considers two parts, namely, hybrid linear solvers and model-driven performance optimization.;The first part considers methods of improving hybrid sparse linear solvers. Many large parallel simulations rely on repeated solves of sparse linear systems. These solves become a bottleneck if they are not completed in a timely manner using limited memory. Furthermore, sparse linear systems from large simulations may be ill-conditioned to some degree, and fast iterative methods may not be efficient. In such cases, direct solvers that rely on factorization are preferred, but come with some additional cost in both execution time and memory. An alternative to direct solvers is the use of hybrid solvers that use a combination of iterative and direct methods. We present work that demonstrates how hybrid solvers can be used efficiently to solve for multiple right-hand side vectors and two novel hybrid solver formulations, called substituted factorization, that may outperform direct solvers in both execution time and memory required.;The second part considers model-driven optimization of parallel sparse computation applications. With more cores sharing resources in a shared-memory system, tasks, such as tuning, optimizing, and profiling, become more difficult. Ideally, developers want to identify segments of code that are poor-performing and lack efficient energy use for both new and large legacy codes. Segments defined by a particular performance and power usage are commonly known as phases. This part presents a model-driven method for identifying unique phases in an application that relies on Hidden Markov Models (HMMs). Models from this method provide information on which segments have particular traits, length of time spent in a phase, and transition between phases. We use this phase-aware method to correctly identify phases with a bad performance to power ratio that is resulting in high energy. By identifying phases, we demonstrate how a static schedule for dynamic voltage and frequency scaling can be constructed that reduces the energy of these applications.