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

University Of Maryland, College Park, College Park MD

Investigators

Abstract

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.