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

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

• 批准号: 1550329
• 负责人: Orion Lawlor
• 金额: $ 5.43万
• 依托单位: University of Alaska Fairbanks Campus
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1550329&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-Body n-Body solver）的现有计算天文学和结果软件基础的现有合作。 Changa是一个执行无碰撞N体模拟的软件包，可以在共同移动的坐标或模拟中进行周期性边界条件进行宇宙学模拟。该项目将使用称为Paratreet和相关应用程序的平行树工具包扩展Changa，这将使科学家能够有效地利用小簇以及非常大的超级计算机来基于平行树的计算。 Paratreet中的关键数据结构是基于软件的树数据缓存，它维护了远程树数据的写入本地副本。我们计划支持各种空间分解方法和相关的树木，包括Oct-Strees，Kd-Trees，Inses Outsex Trees，Ball Trees，R-Trees及其组合。不同的树木在不同的应用环境中很有用，该软件将允许相对轻松地评估其相对优点。该框架将支持各种并行的工作分解方法，包括基于空间填充曲线的方法，并支持运行时并行工作的动态重排。所支持的算法的范围将从具有各种多物扩展，数据聚类，碰撞检测，表面重建，射线相交等的Barnes-HUT范围。该软件包括魅力++框架中的动态负载平衡策略的集合，这些策略可以调整为特定问题结构。它还包括对GPGPU等加速器簇的支持。该项目将证明这种方法的可行性，并产生社区采用该技术的证据。