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

空间天文数据往往非常庞大，而且分布高度不均匀。处理这类数据的算法必须在大型分布式内存超级计算机上并行化，以处理其大小。空间分布的不均匀可能是极端的，一些空间区域的粒子比其他类似大小区域的粒子多出数百万倍。这给可伸缩和高效的性能以及此类算法的高效编程带来了巨大的挑战。然而，在即将到来的时代，计算天文学领域越来越需要这样的可伸缩算法。现代的Petaflop/S和Exaflop/S计算机分别每秒执行高达万亿和五万亿次的计算，所释放的原始计算能力使通过模拟获得该领域一些基本问题的答案成为可能，这些问题包括星系形成以及暗物质和暗能量的性质。由于大型天文观测望远镜每隔几个晚上就会绘制出整个可见天空，预计每天将产生超过10TB的数据，这些数据需要及时分析，以实现其发现危险小行星、新的小行星和正在爆炸的恒星的科学目标。该项目为研究人员提供了新的技术和工具，用于非均匀数据的高性能模拟。这使得以前站不住脚的计算机模拟可以由天体物理学家完成，解锁新的洞察力并回答关于宇宙本质的问题。调查结果也被用作案例研究和调查人员授课的教育材料。此外，该项目旨在让女性和本科生参与这项研究，延续她们过去这样做的经验。因此，该项目与国家科学基金会的使命相一致：促进科学进步，促进国民健康、繁荣和福利。该项目旨在开发新的并行算法、数据结构和应用程序演示，以解决涉及组织到层次树中的数据的计算问题。这种领域的一个典型例子是天文数据，其中代表星团质量(恒星或星系)的粒子以高度不均匀的方式散布在模拟箱或勘测场的空间中。将它们组织成树，可能有多种可选的树组织，包括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.