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

职业：用于超大规模数据分析和科学计算的可扩展稀疏线性代数

• 批准号: 1845208
• 负责人: Metin Aktulga
• 金额: $ 50万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-02-15 至 2025-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1845208&HistoricalAwards=false
• 关键词: CAREER; Scalable; Sparse; Linear; Algebra

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.

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

项目成果

DeepSparse: A Task-Parallel Framework for SparseSolvers on Deep Memory Architectures

• DOI: 10.1109/hipc.2019.00052
• 发表时间: 2019-12
• 期刊: 2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC)
• 作者: Md. Afibuzzaman;F. Rabbi;M. Özkaya;H. Aktulga;Ümit V. Çatalyürek

A Portable Sparse Solver Framework for Large Matrices on Heterogeneous Architectures

异构架构上大型矩阵的便携式稀疏求解器框架

• 发表时间: 2023
• 期刊: and Analytics (HiPC
• 作者: Rabbi, Fazlay;Daley, Christopher S.;Catalyurek, Umit V.;Aktulga, Hasan Metin
• 通讯作者: Aktulga, Hasan Metin

An Evaluation of Task-Parallel Frameworks for Sparse Solvers on Multicore and Manycore CPU Architectures

多核和众核 CPU 架构上稀疏求解器任务并行框架的评估

• DOI: 10.1145/3472456.3472476
• 发表时间: 2021
• 期刊: ICPP 2021: 50th International Conference on Parallel Processing
• 作者: Alperen, Abdullah;Afibuzzaman, Md;Rabbi, Fazlay;Ozkaya, M. Yusuf;Catalyurek, Umit;Aktulga, Hasan Metin
• 通讯作者: Aktulga, Hasan Metin

Evaluation of Directive-Based GPU Programming Models on a Block Eigensolver with Consideration of Large Sparse Matrices

考虑大型稀疏矩阵的块特征求解器上基于指令的 GPU 编程模型的评估

• DOI: 10.1007/978-3-030-49943-3_4
• 发表时间: 2020
• 期刊: Lecture Notes in Computer Science: Accelerator Programming Using Directives (WACCPD 2019
• 作者: Rabbi, Fazlay;Daley, Christopher S.;Aktulga, Hasan Metin;Wright, Nicholas J.
• 通讯作者: Wright, Nicholas J.