John Hart - US grants

Professor Hart will carry out numerical and theoretical modeling, as well as further laboratory experiments, on the transition between various ordered and chaotic states in a two- layer baroclinic rotating fluid. The numerical modeling will address the extensive laboratory data sets on transitions between steady, periodic, and chaotic (aperiodic) types of motion arising from baroclinic instability on the f-plane, as well as on the polar B-plane. Of particular interest is the role of the rigid sidewall boundary condition in the transition process. Its presence leads to a horizontal shear of the basic flow, a modification to the basic eigenfunctions of the linear free-slip problem, and the possibility of flow separation. Theoretical and experimental studies will focus on the processes that may destabilize the simple steady and vacillatory regimes that are observed in laboratory experiments, and which are successfully predicted by low-order (and/or weakly nonlinear) quasi-geostrophic theory. In addition to the role of the viscous sidewall, two potentially destabilizing mechanisms of interest in atmospheric and ocean sciences are periodic and topographic forcing. The action of these physical effects on the B-plane finite-amplitude baroclinic instability problem will be investigated through the use of laboratory and numerical models.//

In this project the P.I will carry out a laboratory study of oscillatory fluid flow over varying bottom topography. A stratified fluid will be contained in a rotating cylinder, with the rotation rate varied periodically about a mean value. Both barotropic and baroclinic oscillatory flow over slopes, hills, and valleys formed in the bottom of the cylinder will be investigated for the fluctuating and mean responses over a wide range of parameters. The data will be used for testing theoretical ideas, as well as the results of numerical models.

The mechanisms by which eddies are generated along coastal boundary by a fluctuating wind stress are studied by means of combined laboratory experiments and numerical models. Various types of wind forcing and bottom topography will be used in the experiments.

Implicit surfaces are shapes described by the points where a function is zero. Sphere tracing is a recently developed method for rendering implicit surfaces that operates on implicit functions that indicate the distance to the implicit surface. Such implicit functions are developed for common modeling primitives, CSG operations, some blends, and some domain transformations which deform objects, but many other surfaces, such as offset surfaces, and other operations, blends and deformation remain. Sphere tracing is a robust efficient implicit surface rendering algorithm. It ray traces implicit surfaces by tracking along each ray by the distance to the implicit surface, as reported by the implicit function. This iteration converges on the first ray-surface intersection. Sphere tracing also provides an area sampling method for antialiasing. Enhancements to sphere tracing include the sphere buffer which allows sphere tracing to capitalize on spatial coherence, spatial partition, and a method for eliminating all iteration from implicit surface rendering. Also addressed are the problems of animating implicit surfaces, particularly the consistent texturing of an implicit surface as it deforms, possibly changing genus.

9422044 Fischer This award is to purchase high-performance networking and computing equipment which will be dedicated to support research in computer and information science and engineering. The equipment will be used for several research projects, including the following: Video compression algorithms will be developed for packet-switched networks, emphasizing robustness to packet loss and development of quantization methods that achieve most of the available granular and entropy gains. Distributed algorithms for computer vision will be developed, including techniques for parallel verification of hypotheses in three-dimensional object recognition, and techniques for high-performance sampling of discrete Markov Random Field models. A "virtual reality VCR" system, which was proposed as a mechanism for image-based recording and immersive playback of virtual environments, with particular emphasis on scientific documentation, will be prototyped. Finally, new techniques will be developed for recurrent design and automatic recurrent modeling of shapes in natural images. ***

Current fractal tools lack the level of control necessary to model specific natural structures. For example, many fractal models of trees have been constructed, but given a particular tree, it would be difficult to represent the tree's specific shape using current models of fractal modeling. The recurrent modeling project identifies three aspects to this problem, and attempts to solve each with several new fractal modeling tools. Objective I: Recurrent Model Representation. Recurrent modeling strives to elevate fractal representation to the level of sophistication that smooth surfaces enjoy in computer-aided geometric design by translating their classical self-referential representation into standard implicit and parametric forms. Recurrent modeling also attempts "procedural geometric instancing," and enhancement of the classic object instancing paradigm that enables it to more efficiently represent the development fractal models currently specified by L-systems. Objective II: Interactive Recurrent Modeling. Recurrent modeling extends the tools of computer-aided geometric design to fractal geometry. A direct manipulation interface provides real time feedback in the fractal modeling process. The implicit formulation from the previous objective allows the application of standard blending formulations specifically designed for natural modeling. Extending constructive solid geometry to include fractal models supports the construction of complex shapes from primitives. Objective III: Automatic Recurrent Modeling. Recurrent modeling attacks the inverse problem of fractal geometry: "find the parameters of a fractal model that approximates a given shape" from the domain of model-based computer vision. The second PI is an NSF-supported model-based computer vision researcher. His unique perspective on this problem resulted in a new solution, called "similarity hashing". Similarity hashing successfully detects self-similarity and returns the paramete rs of the selfsimilar model in initial tests. Recurrent modeling continues this research to develop an automated system for discovering selfaffinity in natural structures. The new tools recurrent modeling proposes would impact the fields of computer graphics and forest science. The new tools would represent highly detailed geometrics, such as a forest and crops. Such models would have applications in image synthesis, particularly in animation, virtual environments, physically- based modeling and remote sensing. As the smooth representations of computer-aided geometric design aid manufacturers, the efficient representations of detail proposed by recurrent modeling representations would aid the study of the environment. ***

Abstract Hart, John E. University of Colorado ATM-9714221 Title: Studies of Rotating Fluids The objective of this research is a critical examination of theories and modeling techniques relevant to atmospheric dynamics, by means of laboratory experiments on mechanically driven rotating fluids. Detailed measurements of velocity fields in single-layer and two-layer systems will be made using high resolution particle image velocimetry and laser doppler anemometry. The data will test theories of baroclinic wave chaos, Reynolds stress closure models of turbulence, and subgrid scale modeling methods currently used in meteorological large eddy simulations. Most of the experiments will take place in a rotating cylinder, with fluid motions being driven mechanically by a differentially rotating lid. This system has advantages of simplicity, the presence of a homogeneous direction, the ability to study a large range of Reynolds numbers (l03 to order 106), the suitability for use of particle image velocimetry, and the relative ease of comparing model predictions with the experimentaldata. Experiments on two-layer flows will focus on asymmetries in the baroclinic instability and chaos problems. An extensive set of experiments on single-layer flows will provide a categorization of instabilities on the sidewall, as well as data on separation and instability in the top and bottom boundary layers. Preliminary work has shown that this three-parameter system has numerous instabilities, mixed in with vertically erupting horizontal boundary layers. These phenomena are important for understanding the behavior of boundary layers under atmospheric vortices. Detailed characteristics of the flows will be compared with results from axisymmetric numerical simulations and linear instability theory. Fundamental studies such as these underlie future improvements in numerical models of atmospheric motions.

9911033
Hart, John
Association for Computing Machinery

Special Project: The Story of Computer Graphics' Documentary Project


ACM/SIGGRAPH will produce a video documenting the history of computer graphics. The video will be premiered at SIGGRAPH '99 in August 1999 held in Los Angeles. The video will be produced in High Definition broadcast format allowing distribution in multiple formats such as NTSC and PAL. The project has two volunteer Executive Producers: John Hart, responsible for SIGGRAPH coordination, and Carl Machover, responsible for content. A distinguished content advisory committee consisting of Gwen Bell, Nelson Max, Chase Chasen, Dick Phillips, Alan Chesnais, Patric Prince, Nick England and Alvy Ray Smith helped map out content. The treatment includes interviews with pioneers in the field. Footage of early accomplishments will be part of the video. The video is expected to communicate to a wide audience the accomplishments of computer graphics ranging from interactive graphics systems and text formatting to movie art such as StarTrek. The video will be distributed to educational circles and is expected to encourage young people to try science and technology career paths.

PI: Hart
Proposal Number: 0002345

Funds are provided for numerical and rotating tank experiments to investigate thermocline dynamics. The basic set-up is a rotating tank with a differentially rotating upper lid and cooling at the lateral boundaries. The upper lid is maintained hot and the lower lid is maintained cold. (Flux conditions at the bottom and sidewalls can also be prescribed.) The structure of the flow in laboratory simulations will be examined as a function of parameter space over ranges inaccessible to numerical simulation. The stability of a rim current, observed in preliminary experiments, under continuously stratified conditions will be investigated. Response to seasonal forcing, time scales long compared to the rotation time scale, will also be investigated. It is anticipated that these experiments will illuminate the dynamics of upper ocean's response to combined wind and buoyancy forcing, a question which is central to physical oceanography.

With National Science Foundation support Dr. John Hart will collect samples of prehistoric common beans (Phaseolus vulgaris) excavated in archaeological sites in Eastern North America and submit them to the University of Arizona AMS radiocarbon laboratory for chronometric dating. Because of small sample size requirements, AMS permits individual beans to be directly dated. This stands in contrast to other methods where larger sample size requirements preclude direct dating of this type. The issue of the spread of agriculture is of great interest to many archaeologists. When Europeans arrived in North America they found that most Native Americans relied on agriculture and that normally maize, beans and squash were cultivated in single fields and together these provided the necessary essential nutrients. While the diffusion of maize and squash are relatively well known, considerable less work has focused on beans. Likely domesticated in Middle America neither the path nor timing of their spread is understood and preliminary data surprisingly suggest their arrival at significantly different times in Eastern North America. Given the complementary role in the diet one would expect that the association between the three domesticates would be relatively old, but such appears not to be the case. Archaeologists have generally assumed that the development of cultural complexity and spread of agriculture occurred together and that the reliable and rich subsistence provided by domesticates played a causal role in this process. However in North America such appears not to be true and agriculture predates the growth of complex society by a significant interval. Thus archaeologists wish to understand when and how domesticates spread and thus approach the subsistence-complexity question on solid chronological ground. The dates obtained by Dr. Hart will provide much needed information. The results will be of interest to, and widely used by, many archaeologists. They will shed important new light on the prehistory of Native American peoples.

The performance of graphic processors is outpacing the performance of general processors, in fact cubing the growth curve. It has been recently shown that some graphics algorithms can be performed in new ways on the graphics processor, using a novel technique known as multipass programming. Multipass programming treats the graphics processor as a SIMD processor acting on a data array stored in the screen's pixels, with each operation applied as an image-processing pass. The proposed research will extend this concept further not only within the graphics community, but also for the scientific computing and general computing communities, by developing a multipass programming language general enough to support both graphical and non-graphical programs. Existing problems of numerical range and precision will be overcome, and the fidelity of the resulting numerical implementations analyzed.

Work in multipass algorithms for procedural shading will be continued our, and multipass programming applied to radiosity and physically-based animation. Multipass programming will also be extended to applications outside of computer graphics, including solving linear systems, the finite element method and computational fluid dynamics.

If graphics processors continue to grow at the current rate, they will attain a four teraflop performance at the end of the proposed funding period. During this growth period a library of programming techniques and applications that will harness this otherwise untapped source of high-performance computing power will be developed. The result will be richer graphics, more realistic virtual environments, more natural simulated motion, and the ability to perform sophisticated supercomputing simulations on consumer-level personal computers.

Computer power has increased dramatically over the past decade and has allowed computational fluid dynamics (CFD) researchers to more accurately simulate many types of complex flow. These simulations have enabled great leaps forward in the design and safety of ships, airplanes, automobiles, and other vehicles. However, this new power has also yielded terabytes of data, and CFD researchers now face a very difficult task in trying to find, extract, and analyze important flow features (e.g., time varying vortices, shock waves) buried within these monstrous datasets. Unlike the explosive growth in computer power, visualization tools for very large datasets have evolved modestly and cannot yet help with these tasks significantly. In particular, since detailed visualization of such large datasets is impractical, CFD researchers must work at a very cumbersome, low level to dice their datasets into workable pieces.

CFD researchers desperately need new techniques that simplify and automate the iterative process of finding the appropriate portion of their data set. They need a system that will allow the user to articulate appropriate types of features of interest, provide a compact representation of those features, and effectively visualize the feature information locally. The system will have to overcome the challenges of loading a sufficient portion of the data set over a network connection into a desktop machine, mapping the entire data set to a visual representation, and rendering the results at interactive rates.

This project will attack these CFD visualization problems by developing techniques for creating and using a procedural abstraction for a dataset. The major research objectives are to:
1. Detect features (e.g. shocks) in complex flows using topological operators.
2. Characterize the data relative to these features using a procedural representation consisting of implicit models and free-form deformations.
3. Adapt the procedural representation to the appropriate level of detail using multi-resolution techniques.
4. Encapsulate domain-specific knowledge as metadata to explore these extremely large datasets.
5. Visualize the data directly from the procedural representation.
6. Verify the accuracy of the procedural representation by tracking approximation error.
7. Apply these techniques to the large-scale computational flow simulation problems currently studied at Stanford and Mississippi State University.
The resulting system will allow CFD researchers to work more effectively by interactively exploring their data to pinpoint the features of interest. Moreover, the results of this project will provide solutions not only for CFD researchers, but also for a wide variety of other visualization challenges and applications. The project's main goal is to develop techniques that allow visualization exploration, feature detection, extraction, and analysis at a higher, more effective level through the use of procedural data abstraction and representation.

Efficient reasoning about three-dimensional visibility is a challenging problem in many research areas and applications, including computer graphics (radiosity, virtual reality walkthroughs), robotics (sensor-based navigation, visual surveillance), computer vision (recognition, model building), architecture, urban planning, and visualization in computational biology. Visibility issues have been considered for four decades in these areas however, most early work has focused on computing visibility from a single viewpoint, while modern techniques require more global visibility information. Global visibility describes the visibility relationships etween objects that are more complex than points: visibility from a volumetric region of space, limits of umbra and penumbra with respect to an extended light source, mutual visibility etween pairs of objects, and loci of structural changes of visibility.

Although great strides have een made in understanding visibility through the introduction of visibility space partitions and the visibility complex, they have so far had little impact on applications. This is due to several reasons: 1) worst-case theoretical complexity bounds are discouraging 2) there are many degenerate cases that must be handled, making it difficult to make robust implementations 3) equivalences in visibility lead to a four-dimensional cell decomposition, which is difficult to visualize 4) cells can be extremely complicated (some include holes).

This work will make 3D visibility computations practical by approaching the problem in two parallel, integrated tracks. One involves the investigation of several key issues that will make 3D visibility algorithms more attractive and practical in applications: 1) performing practical complexity analysis that captures the expected performance for models that are typically used in applications, as opposed to theoretical worst-case ounds derived from uncommon pathological cases 2) rather than taking a generic "precompute and return everything" approach, we would like the amount of precomputation, information stored in data structures, and extraction algorithms to be nicely tailored to the number of queries and the type of information arises in a particular application 3) traversal through the space of visibility rays will be facilitated through the development of decomposition algorithms based on critical events and Morse theory 4) we will develop techniques for reasoning about the evolving shadow space (set of points not visible), which is required for many problems that involve moving viewpoints.

The second track involves the development of a 3D visibility library ased on robust visibility primitives. We expect to make an immediate impact on applications by making this library available for free to other researchers. The library will serve both as a helpful visualization and evaluation tool during the development of the research, and as a way to stimulate other interest and applications of 3D visibility after the work is completed. This effort, combined with the understanding gained from investigating the key visibility issues, is expected to make a broad impact on a wide array of applications that depend on efficient processing of visibility information.

Laboratory experiments are carried out on three fluid systems that manifest processes important in the dynamics of terrestrial and planetary atmospheres: (1) Nonlinear waves and turbulence in a rotating cylinder driven by a differentially rotating lid. Instabilities in this system lead to rotating waves that deviate from smooth circular or elliptical shape by having sharp corners. These so-called "polygonal" waves are similar in appearance to waves observed in hurricane eyewalls and in the polar atmosphere of Saturn. (2) Instability and wave formation in a rotating hydraulic jump. A circular hydraulic jump in a rotating outflow layer is an alternative mechanism for the formation of polygonal waves. (3) The structure and mechanics of precessing mean flows in turbulent rotating convection. Direct measurements of eddy stresses and mean flow profiles will explain the mechanism of mean-flow generation in rotating turbulent convection.

These experiments provide data on nonlinear flows analogous to those in the atmosphere that are difficult to obtain by any other means. Moreover, they give the information needed to evaluate small-scale turbulence parameterization in large-eddy simulations (LES) of geophysical flows. Controlled laboratory experiments that involve constraints similar to those in the atmosphere (particularly rotation and stratification) provide a valuable testing ground. These and similar laboratory experiments are used in graduate and undergraduate classes to demonstrate fundamental fluid processes of relevance to atmospheric science.

DMS-0310446
John C. Hart, Michael T. Heath, Xiangmin Jiao, and John M. Sullivan

This collaborative project funded under DMS-0310642 and
DMS-0310354 is a CARGO full team award made under solicitation
http://www.nsf.gov/pubs/2002/nsf02155/nsf02155.htm.

Level sets represent a moving interface surface implicitly, which
naturally accommodates singularities and topology changes, but at the
expense of a wasteful volumetric Eulerian representation that provides no
control over the topology of the level set. Our project will develop new
methods for tracking interfaces using a more efficient Lagrangian surface
mesh. Through careful prediction of instabilities and topology changes,
we will address the numerical, geometric, and topological difficulties
that have plagued previous Lagrangian approaches to interface propagation.
The result will be faster and more compact simulations of the motion of
interface surfaces, as well as the ability to detect and control changes
in their topology.

Moving boundary or interface surfaces are an integral part of a wide
variety of physical phenomena, such as solidification, extrusion,
multiphase flow, and fluid-solid interaction. Numerical simulations of
such phenomena require reliable and efficient methods for propagating and
tracking such moving surfaces. The focus of our project is to develop
new methods that provide greater control over surface propagation while
also attaining greater computational efficiency than existing methods.
One specific application we will consider is the simulation of combustion
in solid propellant rocket motors, which is the primary focus of UIUC's
Center for Simulation of Advanced Rockets (CSAR). This work will result
in more efficient and more accurate virtual prototyping of rocket motor
designs, leading to safer and more efficient solid rocket boosters,
such as those powering the U.S. Space Shuttle.

This SGER builds off previous NSF-funded work in developing new algorithms for graphics processors (GPUs) in areas such as ray tracing, matrix multiplication, radiosity and radiative heat transfer, subsurface scattering, radiance transfer, clustering, scene graph processing, and dynamic adaptive surface sampling. Advances in these areas allow the PI to propose focused exploration in goal-directed parameterization and investigate optimization methods for mapping meshed surfaces to a planar domain based on new metrics. Specifically, work is proposed to extend the current support for dynamic multiresolution meshed atlas to include capability to deal with moving surface domains in an interactive model context with no loss of detail. That work is balanced with the aforementioned work in developing application-driven metrics.

The goal of this project is to develop methods enabling the visual exploration of large, complex, non-planar graphs. New algorithms are being developed for coarsening graphs that preserve the overall structure of the graph while greatly reducing its complexity. These algorithmic techniques allow for building multi-scale representations that make traditional graph analysis and data mining operations far more efficient. They also provide a basis for advanced visual exploration of complex graphs. In addition, this project is also seeking to leverage the latest advances in computer graphics hardware and rendering technology to generate graph visualizations of the greatest possible clarity in real time, so that a user can interactively explore and understand the most structurally intricate of graph structures.
These technologies have broad application in many diverse and important domains, including protein function analysis, social network understanding, communication network design, data mining, and security market analysis. The new visualization methods are implemented in software systems developed in this project and released under an open source license to aid others in research and development projects. The software, publications and other information on this project can be accessed on the Web site (http://graphics.cs.uiuc.edu/~garland/research/graphs.html).

The Lagrangian Coherent Structures (LCS) software elements developed by this project will provide a valuable tool set for fluid mechanics research to extract new discoveries from the vast and growing body of computational and experimental fluid mechanics data. The computation of LCS enables a systematic approach to accurately characterize transport phenomena in complex systems that pose insurmountable challenges to traditional Eulerian approaches. Prior, ah hoc implementations of LCS have already helped in important, real-world challenges including, tracking pollutants in the ocean, developing novel diagnoses and therapies for cardiovascular disease, and helping airplanes to avoid turbulence. We will produce an open LCS software system to provide a modular, extensible and flexible infrastructure to broaden the community of scientists and engineers that benefit from LCS, in problems ranging from fluid dynamics to general dynamical systems. Prof. Shadden will lead the LCS algorithm design and numerical analysis, and Prof. Hart will oversee the package's architectural design and the efficient parallel implementation of its elements.

This project will create InvertNet, an on-line virtual museum comprising >50 million insect and related arthropod specimens housed at 22 Midwestern institutions, focusing on the research theme of effects of land use changes on the biota of the Great Lakes and upper Mississippi River drainage basins. These collections document 160 years of environmental change and are an invaluable and irreplaceable resource but, at present, are largely inaccessible to scientists and the general public. Most previous efforts to capture and disseminate invertebrate collection data have focused on label data alone. InvertNet will use advanced digitization and networking technologies to capture and display 2D and 3D images of specimens and labels, and incorporate them into a searchable database. These new techniques should reduce the cost of digitizing insect specimens substantially.

By allowing users to find and view detailed images of specimens of particular species and their associated data labels, InvertNet will provide universal access to collections previously restricted to researchers. It will include links to the popular BugGuide.net insect identification website and to other biodiversity data portals used by researchers, educators, and the general public. This will facilitate and support many aspects of biological research and education, including species discovery and identification, pest management, ecology and biogeography. InvertNet will serve as a model, applicable to other kinds of biological collections, for the use of efficient, computer-assisted procedures to increase the speed and accuracy of collection data capture. This award is made as part of the National Resource for Digitization of Biological Collections through the Advancing Digitization of Biological Collections program and all data resulting from this award will be available through the national resource.

DESCRIPTION (provided by applicant): Falls among the elderly are a considerable health concern and the leading cause of injury death. Fear of falling can be equally devastating leading to a loss of confidence, restriction of physical activities, and social isolation. Lateral sway while walking, in addition to other gait parameters, have been shown to be associated with a history of falls among the elderly. We propose the development of a wearable sensor system capable of identifying sway and gait parameters associated with fall likelihood and of providing corrective feedback. The system will characterize several parameter of sway and gait during standing on one leg and walking. The biofeedback system, consisting of auditory and vibratory feedback modules, will provide feedback to reduce the 'unsafe'sway. During the proposed study, the robustness and sensitivity of measurements will be established, and the effectiveness of the biofeedback system will be evaluated. The system will be capable of continuous monitoring and will be discrete so that it can be worn continuously, and hence increase confidence and the quality of life among elderly susceptible to falls. Lastly, in future, the system can be used in the clinics as a tool for evaluating the risks of falls, and training users to better maintain their balance. PUBLIC HEALTH RELEVANCE: Evaluating fall risks can prevent falls and improve the quality of health-care. A wearable biofeedback system that can monitor the risks of falls, and train users to improve their balance and stability will enhance significantly the quality of life in the elderly and will prevent many injuries caused by falls. It can further be used as a clinical tool for objective assessment and evaluation of gait, and risks of falls.

This grant is a planning grant to fund the conceptualization of an institute for software infrastructure for sustained innovation. It funds the planning of the technical and organizational aspects. To understand community requirements, it involves workshops and outreach to gather community requirements.

To fully understand the behavior of a complex physical phenomenon such as a burning building, it is often necessary to understand both large-scale effects such as the buildup of heat on each floor, and small-scale effects, such as how a steal beam in the foundation deforms as it gets hotter. Computational simulations that study such effects in tandem are called "multi-scale" simulations, and are exceedingly difficult to write. This is because the computational models that represent the different scales differ widely, and the software components used to simulate each scale are often incompatible. Combining these disparate components requires painstaking and error prone programmer labor.

This project will conceptualize an institute devoted to providing solutions to scientists investigating multi-scale problems. The project centers around reaching out to computational scientists and computer systems researchers to determine both what kinds of programming abstractions may be useful for different computational models and how to best adapt existing abstractions to the challenges of multi-scale simulation. The goal is to enable the establishment of an institute that will study the use of various programming abstractions to bridge the gap between differing software components, hence easing the pain of writing multi-scale simulations. The ultimate effect will be to allow multi-scale systems to be simulated accurately and efficiently, providing deeper insights into the behavior of complex physical systems.

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.