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

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

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.