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。这项工作将通过在百亿亿级 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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（7）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Communication-Avoiding Recursive Aggregation

避免通信的递归聚合

DOI：
10.1109/cluster52292.2023.00024
发表时间：
2023-10-31
期刊：
2023 IEEE International Conference on Cluster Computing (CLUSTER)
影响因子：
0
作者：
Yihao Sun;Sidharth Kumar;Thomas Gilray;Kristopher K. Micinski
通讯作者：
Kristopher K. Micinski

Towards Iterative Relational ALgebra on the GPU

在 GPU 上实现迭代关系代数

DOI：
发表时间：
2023-07
期刊：
USENIX ATC
影响因子：
0
作者：
Ahmedur Rahman Shovon; Thomas Gilray
通讯作者：
Thomas Gilray

Accelerating Datalog applications with cuDF.

使用 cuDF 加速数据记录应用程序。

DOI：
发表时间：
2022-01
期刊：
12th Workshop on Irregular Applications: Architectures and Algorithms
影响因子：
0
作者：
Shovon, Ahmedur Rahman;Dyken, Landon Richard;Green, Oded;Gilray, Thomas;Kumar, Sidharth
通讯作者：
Kumar, Sidharth

A Visual Guide to MPI All-to-all

MPI 全面可视化指南