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

该项目解决了几个技术挑战，并开发了一个计算基础设施，以解决需要高端计算的非常大的科学问题，如物理和材料科学(“科学计算”)，并用于分析大量数据中的模式，如由社交媒体产生的数据(“大数据分析”)。在大数据分析和科学计算这两个看似截然不同的领域，一个统一的计算主题是，目前用于解决相关问题的模型往往会产生大量具有显著、不规则差距的数据(从技术上讲，这被称为“稀疏矩阵”)。解决这类问题的规模通常需要在大规模并行计算机上执行。由于稀疏矩阵计算的独特特性，实现高性能和可伸缩性是具有挑战性的。该项目旨在开发一套广泛的可伸缩稀疏矩阵算法和软件来应对这些挑战。通过显著提高从事大数据分析和科学计算的领域科学家的生产率，该项目符合国家利益，正如NSF的使命所述：促进科学进步；促进国家健康、繁荣和福利；或保障国防安全。研究计划与各级的教育和推广目标紧密结合。外展工作的核心是为高中生开设计算机科学暑期学校和导师计划。为了应对现代计算机体系结构(包括高速缓存、高带宽设备存储器(HBM)、DRAM和非易失性随机存取存储器(NVRAM))日益深入的存储器层次结构所带来的挑战，并促进稀疏矩阵计算的高性能执行，探索了一种全面的研究计划。该项目的核心是一个数据流中间件，它具有一个简单的应用程序编程接口，称为DeepSparse，旨在支持各种稀疏解算器，同时确保体系结构和性能可移植性。DeepSparse将给定的稀疏求解器代码转换为有向无环图(DAG)，其中节点表示计算任务，边表示任务之间的数据流。开发了新的DAG分区和调度算法，这些算法也被扩展到它们的超图对应物，以确保在任务图执行期间存储层之间的数据移动最小化。研究了基于扩展顶线模型的性能模型和借鉴磁盘存储系统思想的创新内存管理方案，以确保对NVRAM设备上的稀疏解算器数据的高带宽和低延迟访问。本研究开发的所有软件和工具都是作为开源项目分发的，具有广泛的影响。总体而言，该项目的目标与国家战略计算倡议非常一致，该倡议旨在促进能够拉近大数据分析和科学计算领域的创新。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.