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

SI2-SSI：协作研究：Paratreet：仿真和分析中的空间树并行软件

• 批准号: 1550234
• 负责人: Thomas Quinn
• 金额: $ 14万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1550234&HistoricalAwards=false
• 关键词: SI2; SSI; Collaborative; Research; Paratreet

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.

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