Algorithmic approaches for enhancing speedup, energy and resiliency measures of sparse scientific computations
Padma Raghavan, Manu Shantharam · 2012
High performance computing systems have increasingly complex node and network architectures including non-uniform memory subsystems, heterogeneous processors and hierarchical interconnects. The performance of scientific applications that run on such systems depends on several factors including memory access pattern, memory bandwidth, load balancing and resiliency. Consequently, optimizing the performance of scientific applications for high performance computing systems is challenging. We seek to address this challenge for applications involving sparse scientific computations because such computations form the basis for solving many large-scale models of physical phenomena. In this thesis, we seek to understand the interplay between sparse scientific applications and hardware, and develop algorithmic approaches to improve performance measures and resiliency for sparse scientific computations. We organize the thesis into two parts. The first part concerns developing algorithmic approaches to enhance the performance of sparse scientific computations and has two main contributions: (i) a new sparse matrix representation and a corresponding sparse matrix vector multiplication (SpMV) algorithm that enhances performance of the SpMV operation and (ii) speedup-aware processor partitioning algorithms to manage sparse scientific workloads efficiently. The second part concerns analyzing the impact of transient errors on sparse scientific computing and developing a fault tolerant algorithm, and has two main results: (i) characterizing the impact of a single transient error on iterative methods and (ii) a new sparse checksum encoded algorithm-based fault tolerance technique for the preconditioned conjugate gradients method. In Chapter 2, we focus on SpMV, which is at the heart of many scientific applications involving sparse linear system solution. We develop a new sparse matrix representation and a corresponding SpMV algorithm that exploits the dense substructures that are inherently present in many sparse matrices derived from partial differential equation models. We show that our SpMV algorithm reduces the total number of load operations and enhances locality in accesses to the vector, consequently, improving the SpMV performance on average by a third compared to the traditional compressed sparse row scheme on the Intel Nehalem processor. In Chapter 3, we consider improving the performance sparse scientific workloads that are commonly executed on high performance computing systems. We observe many applications in such workloads do not scale linearly with the number of cores, providing diminishing gains in execution time for larger numbers of cores. For a workload comprising multiple such applications, it is beneficial from system perspective to reduce system energy consumption and decrease workload completion time. We develop speedup-aware processor partitioning algorithms that exploit individual application scaling features and optimize processor allocations per application. Our results indicate that the speedup-aware algorithms can reduce workload completion time by as much as half and decrease the total energy consumption of the workload by more than half on 128 cores of the Intel Nehalem processor, compared to executing each application within the workload on all 128 cores one after the other. In Chapter 4, we analyze the impact of silent data corruption due to a single transient error on sparse scientific computations, in particular, on sparse linear system solution. Transient errors result in bit flips in memory and errors in logic circuit output, leaving the computing system state corrupt. We provide a theoretical analysis of the impact of a single transient error on sparse linear system solution. Our analysis indicates that a single transient error during an SpMV operation can corrupt the entire resultant vector in a relatively short sequence of SpMV operations. Furthermore, our evaluations show that execution time of sparse linear system solution could increase by a factor as high as 200 or more, in the event of a transient error. In Chapter 5, we focus on enhancing the resiliency of sparse linear system solution. We develop a new sparse checksum encoded algorithm-based fault tolerance technique for the preconditioned conjugate gradients (PCG) method, a widely used method for sparse linear system solution. We prove that our technique detects a single error in all the key operations within the method, including SpMV, vector operations and the application of a preconditioner through sparse triangular solution, when the linear system has a coefficient matrix that is symmetric positive definite and strictly diagonally dominant. Additionally, the overheads of using our fault tolerance technique are low, eleven percent on average in the event of no error and three percent in the event of a single error within PCG, when compared to having no fault tolerance for the PCG method. Our thesis demonstrates an opportunity space to optimize sparse scientific applications for performance and resiliency on HPC systems. We develop new algorithmic formulations that enhance performance and resiliency of sparse scientific computations. Looking forward, we expect the opportunity space to grow with evolving applications and hardware, and much work remains to be done in optimizing scientific applications for various performance measures.