RII Track-4:NSF: Relational Algebra on Heterogeneous Extreme-scale Systems

RII Track-4：NSF：异构极端规模系统上的关系代数

• 批准号: 2132013
• 负责人: Sidharth kumar
• 金额: $ 26.48万
• 依托单位: University of Alabama at Birmingham
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-02-01 至 2024-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2132013&HistoricalAwards=false
• 关键词: RII; Track; NSF; Relational; Algebra

Relational algebra (RA) forms a basis of primitive operations such as join, projection, aggregation, and selection that transform one or more input relations (i.e., database tables) into an output relation. It can be used to implement algorithms in graph analytics, deductive databases, program analysis, satisfiability, constraint solving, and machine learning. High-performance RA has the potential to extract vast untapped parallelism from critical applications. Despite this great expressive power, investigation of RA within the HPC community has been limited and significant advances are needed to scale RA on next-generation HPC systems. This work will advance the state of art by developing novel algorithms for massively parallel relational algebra on exascale HPC systems such as the Aurora supercomputer at Argonne National Laboratory (ANL). In the context of heterogeneous systems (i.e., those using multiple distinct compute paradigms in concert, like Aurora), this work will address key scaling concerns including workload decomposition, load balancing, communication, and I/O. This work will establish foundations for long-term collaboration with ANL towards the development of foundational theory, practical implementations, and rigorous evaluations of parallel RA. The project will support a graduate student from an underrepresented minority and lay groundwork for a high-impact dissertation.Owing to increasing inter-network data-movement costs and power constraints, exascale systems are increasingly shifting toward heterogeneous computing environments, with CPUs being coupled with coprocessors such as GPUs. Aurora Supercomputer at Argonne national lab is an example of a leadership-class heterogeneous system; every Aurora node is equipped with multiple GPU co-processors. This work will lead to the development of parallel algorithms for RA, in the context of Aurora specifically and heterogeneous systems more broadly, over three key phases: (1) development of core RA algorithms for multi-GPU nodes; (2) extending these algorithms to supercomputers with many nodes, like Aurora; (3) extending the whole compute process to include scalable parallel IO. First, phase (1) will require investigating three technical approaches for the RA itself, extending them to multi-GPU nodes: (i) radix-hash, (ii) sort-merge, and (iii) nested-loop. Second, in phase (2) the work will investigate inter-node balancing of RA primitives and techniques to minimize data movement across multi-node systems. Finally, in phase (3) a customized parallel IO system and storage model will be developed that will take into account the deepening memory hierarchy available on modern supercomputers. These innovations across three phases will be evaluated using the ALCF supercomputer Aurora, using three application domains: graph mining, static program analysis, and deductive databases for scientific simulations. With exascale insight, this research is poised to create a new generation of applications based on relational algebra.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.

关系代数（RA）形成诸如连接、投影、聚合和选择之类的基本操作的基础，这些基本操作将一个或多个输入关系（即，数据库表）转换为输出关系。它可用于实现图分析、演绎数据库、程序分析、可满足性、约束求解和机器学习中的算法。高性能RA具有从关键应用程序中提取大量未开发并行性的潜力。尽管有这种强大的表达能力，但在HPC社区内对RA的调查仍然有限，需要在下一代HPC系统上扩展RA。这项工作将通过开发用于exascale HPC系统（如阿贡国家实验室（ANL）的Aurora超级计算机）的大规模并行关系代数的新算法来推进最新技术。在异构系统的上下文中（即，那些使用多个不同计算范例的人，如Aurora），这项工作将解决关键的扩展问题，包括工作负载分解，负载平衡，通信和I/O。这项工作将建立与ANL长期合作的基础，以发展基础理论，实际实施和严格评估并行RA。该项目将支持一名来自代表性不足的少数民族的研究生，并为一篇具有高影响力的论文奠定基础。由于网络间数据移动成本和功耗限制的增加，兆级系统越来越多地转向异构计算环境，CPU与GPU等协处理器相结合。阿贡国家实验室的Aurora超级计算机是领先级异构系统的一个例子;每个Aurora节点都配备了多个GPU协处理器。这项工作将导致RA的并行算法的开发，在Aurora的具体背景下和更广泛的异构系统中，在三个关键阶段：（1）多GPU节点的核心RA算法的开发;（2）将这些算法扩展到具有许多节点的超级计算机，如Aurora;（3）扩展整个计算过程，包括可扩展的并行IO。首先，阶段（1）需要研究RA本身的三种技术方法，将其扩展到多GPU节点：（i）基数哈希，（ii）排序合并，以及（iii）嵌套循环。其次，在阶段（2）中，工作将调查RA原语的节点间平衡和技术，以最大限度地减少跨多节点系统的数据移动。最后，在阶段（3）中，将开发一个定制的并行IO系统和存储模型，该模型将考虑现代超级计算机上可用的深化存储器层次结构。这些创新将使用ALCF超级计算机Aurora进行评估，使用三个应用领域：图挖掘，静态程序分析和演绎数据库进行科学模拟。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Accelerating Datalog applications with cuDF

• DOI: 10.1109/ia356718.2022.00012
• 发表时间: 2022-11
• 期刊: 2022 IEEE/ACM Workshop on Irregular Applications: Architectures and Algorithms (IA3)
• 作者: Ahmedur Rahman Shovon;Landon Dyken;Oded Green;Thomas Gilray;Sidharth Kumar

Towards Iterative Relational Algebra on the GPU

• 发表时间: 2023
• 作者: Ahmedur Rahman Shovon;Thomas Gilray;Kristopher K. Micinski;Sidharth Kumar

Optimizing the Bruck Algorithm for Non-uniform All-to-all Communication

优化非均匀全对全通信的布鲁克算法

• DOI: 10.1145/3502181.3531468
• 发表时间: 2022
• 期刊: The 31st International Symposium on High-Performance Parallel and Distributed Computing
• 作者: Fan, Ke;Gilray, Thomas;Pascucci, Valerio;Huang, Xuan;Micinski, Kristopher;Kumar, Sidharth
• 通讯作者: Kumar, Sidharth

GraphWaGu: GPU Powered Large Scale Graph Layout Computation and Rendering for the Web.

GraphWaGu：GPU 驱动的大规模网络图形布局计算和渲染。

• 发表时间: 2022
• 期刊: Eurographics Symposium on Parallel Graphics and Visualization
• 作者: Landon Dyken, Pravin Poudel

Communication-Avoiding Recursive Aggregation

• DOI: 10.1109/cluster52292.2023.00024
• 发表时间: 2023-10
• 期刊: 2023 IEEE International Conference on Cluster Computing (CLUSTER)
• 作者: Yihao Sun;Sidharth Kumar;Thomas Gilray;Kristopher K. Micinski