CAREER: Scalable Sparse Linear Algebra for Extreme-Scale Data Analytics and Scientific Computing

Michigan State University, East Lansing MI

Investigators

Abstract

This project addresses several technical challenges and develops a computing infrastructure to enable solving very large scientific problems that require high end computing such as for physics and material sciences ("scientific computing") and for analyzing patterns within huge amounts of data such as those generated by social media ("big data analytics"). A unifying computational motif in the seemingly disparate fields of big data analytics and scientific computing is that the models currently used to solve the relevant problems often result in large amount of data with significant, irregular gaps (technically known as "sparse matrices"). The scale of solving such problems typically require execution on massively parallel computers. Due to the unique characteristics associated with sparse matrix computations, achieving high performance and scalability is challenging. This project aims to develop an extensive set of scalable sparse matrix algorithms and software to address such challenges. By significantly improving the productivity of domain scientists working on big data analytics and scientific computing, this project serves the national interest, as stated by NSF's mission: to promote the progress of science; to advance the national health, prosperity and welfare; or to secure the national defense. Research plans are tightly integrated with educational and outreach objectives at various levels. The centerpiece of the outreach efforts is a Computer Science summer school and mentorship plans for high school students. To tackle the challenges presented by the increasingly deep memory hierarchies of modern computer architectures that include cache, high-bandwidth device memories (HBM), DRAM, and non-volatile random access memory (NVRAM) and facilitate high performance execution of sparse matrix computations, a comprehensive research plan is explored. The centerpiece of this project is a data-flow middleware with a simple application programming interface, called DeepSparse, that aims to support a wide variety of sparse solvers, while ensuring architecture and performance portability. DeepSparse converts a given sparse solver code into a directed acyclic graph (DAG) where nodes represent computational tasks and edges represent the data-flow between tasks. Novel DAG partitioning and scheduling algorithms, which are also extended to their hypergraph counterparts, are developed to ensure that data movement between memory layers is minimized during execution of the task graph. Performance models based on the extended Roofline model and innovative memory management schemes that draw upon ideas from disk storage systems are explored to ensure high bandwidth and low latency access to sparse solver data on NVRAM devices. All software and tools developed in this research are distributed as open source projects for a broad impact. Overall, goals of this project are well aligned with the National Strategic Computing Initiative, which aims to foster innovations that can bring the fields of big data analytics and scientific computing closer. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.