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

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

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.