SI2-SSI: Collaborative Research: ParaTreet: Parallel Software for Spatial Trees in Simulation and Analysis

许多科学和可视化方法都涉及到将它们正在处理的数据组织成层次结构（也称为“树”）。这些应用和方法包括：在重力影响下运动的粒子的天文模拟、空间数据分析（即描述物体在空间中的相对位置的数据）、虚拟环境的逼真渲染、通过激光扫描重建表面、模拟物理物体运动时的碰撞检测等等。树形数据结构和用于处理这些结构的算法在这些应用程序中被大量使用，因为它们有助于使这些应用程序在超级计算机上运行得更快。然而，实现基于树的算法可能需要大量的努力，特别是在现代高度并行的计算机上。该项目将创建ParaTreet，这是一个并行树的软件工具包，将使此类应用程序能够快速开发。并行方面的细节将对程序员隐藏，他们将能够快速评估不同树和算法的相对优点，即使应用于大型数据集和非常计算密集型的应用程序。将这样一个抽象和可扩展的框架与可移植的自适应运行时系统相结合，将使科学家能够有效地使用从小型集群到千万亿级机器的并行硬件，用于各种基于树的应用程序。该项目将证明这种方法的可行性，并产生社区采用该技术的证据。如果成功，该项目将使NSF资助的研究人员能够更快地解决科学问题，并解决更复杂的问题，从而服务于NSF的科学使命。这个项目建立在计算天文学的现有合作和ChaNGa （Charm N-body GrAvity solver）代码中的软件基础之上。ChaNGa是一个软件包，可以执行无碰撞的n体模拟，并可以在共同运动坐标中执行具有周期性边界条件的宇宙学模拟或孤立恒星系统的模拟。该项目将通过名为ParaTreet的并行树工具包和相关应用程序扩展ChaNGa，这将允许科学家有效地利用小型集群和非常大的超级计算机进行并行树计算。ParaTreet中的关键数据结构是一个基于异步软件的树数据缓存，它维护远程树数据的回写本地副本。我们计划支持多种空间分解方法和相关树，包括oct树、kd树、inside-outside树、ball树、r树及其组合。不同的树在不同的应用环境中是有用的，该软件将允许相对容易地评估它们的相对优点。该框架将支持多种并行工作分解方法，包括基于空间填充曲线的并行工作分解方法，并支持并行工作在运行时的动态重排。支持的算法将包括Barnes-Hut的各种多极扩展、数据聚类、碰撞检测、表面重建、射线相交等。该软件在Charm++框架中包含一组动态负载平衡策略，可以针对特定的问题结构进行调优。它还包括对加速器集群的支持，比如gpgpu。该项目将证明这种方法的可行性，并产生社区采用该技术的证据。

Many scientific and visualization methods involve organizing the data they are processing into a hierarchy (also known as a "tree"). These applications and methods include: astronomical simulations of particles moving under the influence of gravity, analysis of spatial data (that is, data that describes objects with respect to their relative position in space), photorealistic rendering of virtual environments,reconstruction of surfaces from laser scans, collision detection when simulating the movement of physical objects, and many others. Tree data structures, and the algorithms used to work on these structures, are heavily used in these applications because they help to make these applications run much faster on supercomputers. However, implementing tree-based algorithms can require a significant effort, particularly on modern highly parallel computers. This project will create ParaTreet, a software toolkit for parallel trees, that will enable rapid development of such applications. Details of the parallel aspects will be hidden from the programmer, who will be able to quickly evaluate the relative merits of different trees and algorithms even when applied to large datasets and very computation-intensive applications. The combination of such an abstract and extensible framework with a portable adaptive runtime system will allow scientists to effectively use parallel hardware ranging from small clusters to petascale-class machines, for a wide variety of tree-based applications. This project will demonstrate the feasibility of such an approach as well as generate evidence of community adoption of this technology. If successful, this project will enable NSF-supported researchers to solve science problems faster as well as to tackle more complex problems, thus serving NSF's science mission.This project builds upon an existing collaboration on Computational Astronomy and the resultant software base in the ChaNGa (Charm N-body GrAvity solver) code. ChaNGa is a software package that performs collisionless N-body simulations, and can perform cosmological simulations with periodic boundary conditions in co-moving coordinates or simulations of isolated stellar systems. This project will extend ChaNGa with a parallel tree toolkit called ParaTreet and associated applications, that will allow scientists to effectively utilize small clusters as well as very large supercomputers for parallel tree-based calculations. The key data structure in ParaTreet is an asynchronous software-based tree data cache, which maintains a writeback local copy of remote tree data. We plan to support a variety of spatial decomposition methods and the associated trees, including Oct-trees, KD-trees, inside-outside trees, ball trees, R-trees, and their combinations. Different trees are useful in different application circumstances, and the software will allow their relative merits to be evaluated with relative ease. The framework will support a variety of parallel work decomposition methods, including those based on space filling curves, and support dynamic rearrangement of parallel work at runtime. The algorithms supported will range from Barnes-Hut with various multipole expansions, data clustering, collision detection, surface reconstruction, ray intersection, etc. The software includes a collection of dynamic load balancing strategies in the Charm++ framework that can be tuned for specific problem structures. It also includes support for clusters of accelerators, such as GPGPUs. This project will demonstrate the feasibility of such an approach as well as generate evidence of community adoption of this technology.