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

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

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.