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-trees，KD-trees，inside-outside trees，ball trees，R-trees及其组合。不同的树在不同的应用环境中是有用的，软件将允许相对容易地评估它们的相对优点。该框架将支持各种并行工作分解方法，包括那些基于空间填充曲线，并支持在运行时的并行工作的动态重排。支持的算法将从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.