OAC Core: Small: Collaborative Research: Scalable distributed algorithms for tree structured astronomical data

OAC 核心：小型：协作研究：树结构天文数据的可扩展分布式算法

• 批准号: 1910428
• 负责人: Laxmikant Kale
• 金额: $ 35万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910428&HistoricalAwards=false
• 关键词: OAC; Core; Small; Collaborative; Research

Spatial astronomical data is often extremely large and it is highly non-uniformly distributed. Algorithms that deal with such data have to be parallelized over large distributed memory supercomputers to deal with its size. The non-uniformity in the spatial distribution can be extreme, with some regions of space having million times more particles than other similar size regions. This creates significant challenges for scalable and efficient performance, as well as for the productive programming of such algorithms. Yet, the field of computational astronomy increasingly needs such scalable algorithms in the coming era. The raw computing capability unleashed by modern PetaFLOP/s and ExaFLOP/s computers, respectively, executing up to quadrillions and quintillions of calculations per second, is making it potentially feasible to get answers via simulations to some fundamental questions in the field, including those of galaxy formation and the properties of dark matter and dark energy. As the Large Synoptic Survey Telescope maps out the entire visible sky every few nights, it is expected to generate more than 10 terabytes per day, and this data needs to be analyzed in a timely fashion to fulfill its scientific goals of discovering hazardous asteroids, new minor planets, and exploding stars. This project provides new techniques and tools for researchers to use for high-performance simulations of non-uniform data. This enables previously untenable computer simulations to be done by astrophysicists, unlocking new insights and answering questions about the nature of the cosmos. The results are also used as case studies and educational material in classes taught by the investigators. Additionally, the project aim to involve women and undergraduate students in performing this research, continuing their experience of having done so in the past. This project thus aligns with the NSF's mission: to promote the progress of science and to advance the national health, prosperity and welfare. This project aims at developing novel parallel algorithms, data structures, and application demonstrations for computational problems involving data organized into hierarchical trees. A canonical example of such a domain is astronomical data, where particles representing clustered mass (stars or galaxies) are spread over the space of a simulation box or survey field in a highly non-uniform manner. Organizing them into trees, with multiple alternative tree organizations possible, including k-d trees, octrees, space-filling-curve based trees, etc., allows the efficient computation of various quantities such as gravitational forces, densities (and therefore hydrodynamics), two-point or three-point correlations, etc. The optimum choice of tree structure and algorithm depends both on the problem and the parameters of the parallel machine. The research methods used will include complexity analysis and, more significantly, empirical comparisons over a range of possible application scenarios including particle distributions and classes of traversals and algorithms. This will include formulation of algorithms and their implementations on parallel machines. The main outcomes of this project will be research papers describing effective algorithms and comparison and evaluation of particle decomposition techniques and tree types. This project is funded by the Office of Advanced Cyberinfrastructure in the Directorate for Computer and Information Science and Engineering and the Division of Astronomical Sciences in the Directorate for Mathematical & Physical Sciences.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.

空间天文数据往往是非常大的，它是高度不均匀分布。处理此类数据的算法必须在大型分布式内存超级计算机上并行化，以处理其大小。空间分布的不均匀性可能是极端的，某些空间区域的粒子数量是其他类似大小区域的百万倍。这为可伸缩和高效的性能以及此类算法的生产性编程带来了重大挑战。然而，在未来的时代，计算天文学领域越来越需要这种可扩展的算法。现代PetaFLOP/s和ExaFLOP/s计算机所释放的原始计算能力，分别每秒执行高达千万亿次和千万亿次的计算，使得通过模拟得到该领域一些基本问题的答案成为可能，包括星系形成和暗物质和暗能量的性质。由于大型综合巡天望远镜每隔几个晚上就会绘制整个可见天空，预计每天将产生超过10tb的数据，这些数据需要及时分析，以实现发现危险小行星、新的小行星和爆炸恒星的科学目标。该项目为研究人员提供了用于非均匀数据的高性能模拟的新技术和工具。这使得以前站不住脚的计算机模拟可以由天体物理学家完成，解锁新的见解并回答有关宇宙本质的问题。调查结果也被用作案例研究和调查人员授课的教育材料。此外，该项目的目的是让妇女和本科生参与这项研究，继续他们过去这样做的经验。因此，该项目符合美国国家科学基金会的使命：促进科学进步，促进国家健康、繁荣和福利。该项目旨在开发新的并行算法、数据结构和应用演示，以解决涉及分层树数据组织的计算问题。这种领域的一个典型例子是天文数据，其中代表群集质量（恒星或星系）的粒子以高度不均匀的方式分布在模拟盒或调查领域的空间中。将它们组织成树，可能有多种可选的树组织，包括k-d树，八叉树，基于空间填充曲线的树等，可以有效地计算各种数量，如引力，密度（因此是流体动力学），两点或三点相关性等。树形结构和算法的最优选择既取决于问题本身，也取决于并联机构的参数。使用的研究方法将包括复杂性分析，更重要的是，对一系列可能的应用场景进行经验比较，包括粒子分布和遍历和算法的类别。这将包括算法的制定及其在并行机器上的实现。该项目的主要成果将是描述有效算法的研究论文，以及粒子分解技术和树类型的比较和评估。该项目由计算机与信息科学与工程理事会的高级网络基础设施办公室和数学与物理科学理事会的天文科学部资助。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

ParaTreeT: A Fast, General Framework for Spatial Tree Traversal

ParaTreeT：一种快速、通用的空间树遍历框架

• DOI: 10.1109/ipdps53621.2022.00079
• 发表时间: 2022
• 期刊: 2022 IEEE IPDPS
• 作者: Hutter, Joseph;Szaday, Justin;Choi, Jaemin;Liu, Simeng;Kale, Laxmikant;Wallace, Spencer;Quinn, Thomas
• 通讯作者: Quinn, Thomas