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.