Publications

Abstract not provided.

We are pleased to submit our efforts in parallelizing the PRONTO application suite for con- sideration in the SuParCup 99 competition. PRONTO is a finite element transient dynamics simulator which includes a smoothed particle hydrodynamics (SPH) capability; it is similar in scope to the well-known DYNA, PamCrash, and ABAQUS codes. Our efforts over the last few years have produced a fully parallel version of the entire PRONTO code which (1) runs fast and scalably on thousands of processors, (2) has performed the largest finite-element transient dynamics simulations we are aware of, and (3) includes several new parallel algorithmic ideas that have solved some difficult problems associated with contact detection and SPH scalability. We motivate this work, describe the novel algorithmic advances, give performance numbers for PRONTO running on Sandia's Intel Teraflop machine, and highlight two prototypical large-scale computations we have performed with the parallel code. We have successfully parallelized a large-scale production transient dynamics code with a novel algorithmic approach that utilizes multiple decompositions for different key segments of the computations. To be able to simulate a more than ten million element model in a few tenths of second per timestep is unprecedented for solid dynamics simulations, especially when full global contact searches are required. The key reason is our new algorithmic ideas for efficiently parallelizing the contact detection stage. To our knowledge scalability of this computation had never before been demonstrated on more than 64 processors. This has enabled parallel PRONTO to become the only solid dynamics code we are aware of that can run effectively on 1000s of processors. More importantly, our parallel performance compares very favorably to the original serial PRONTO code which is optimized for vector supercomputers. On the container crush problem, a Teraflop node is as fast as a single processor of the Cray Jedi. This means that on the Teraflop machine we can now run simulations with tens of millions of elements thousands of times faster than we could on the Jedi! This is enabling transient dynamics simulations of unprecedented scale and fidelity. Not only can previous applications be run with vastly improved resolution and speed, but qualitatively new and different analyses have been made possible.

Single-level parallel optimization approaches, those in which either the simulation code executes in parallel or the optimiza- tion algorithm invokes multiple simultaneous single-processor analyses, have been investigated previously and been shown to be effective in reducing the time required to compute optimal solutions. However, these approaches have clear performance limita- tions that prevent effective scaling with the thousands of processors available in massively parallel supercomputers. In more recent work, a capability has been developed for multilevel parallelism in which multiple instances of multiprocessor simulations are coordinated simultaneously. This implementation employs a master-slave approach using the Message Passing Interface (MPI) within the DAKOTA software toolkit. Mathematical analysis on achieving peak efficiency in multilevel parallelism has shown that the most effective processor partitioning scheme is the one that limits the size of multiprocessor simulations in favor of concurrent execution of multiple simulations. That is, if both coarse-grained and fine-grained parallelism can be exploited, then preference should be given to the coarse-grained parallelism. This analysis was verified in multilevel paralIel computatiorud experiments on networks of workstations (NOWS) and on the Intel TeraFLOPS massively parallel supercomputer. In current work, methods for exploiting additional coarse-grained parallelism in optimization are being investigated so that fine-grained efficiency losses can be further minimized. These activities are focusing on both algorithmic coarse-grained parallel- ism (multiple independent function evaluations) through the development of speculative gradient methods and concurrent iterator strategies and on function evaluation coarse-grained parallelism (multiple separable simulations within a function evaluation) through the development of general partitioning and nested synchronization facilities. The net result is a total of four separate lev- els of parallelism which can minimize efficiency losses and achieve near linear scaling on massively parallel computers.

Abstract not provided.

Calculations can naturally be described as graphs in which vertices represent computation and edges reflect data dependencies. By partitioning the vertices of a graph, the calculation can be divided among processors of a parallel computer. However, the standard methodology for graph partitioning minimizes the wrong metric and lacks expressibility. We survey several recently proposed alternatives and discuss their relative merits.

Evolutionary pattern search algorithms (EPSAs) are a class of evolutionary algorithms (EAs) that have convergence guarantees on a broad class of nonconvex continuous problems. In previous work we have analyzed the empirical performance of EPSAs. This paper revisits that analysis and extends it to a more general model of mutation. We experimentally evaluate how the choice of the set of mutation offsets affects optimization performance for EPSAs. Additionally, we compare EPSAs to self-adaptive EAs with respect to robustness and rate of optimization. All experiments employ a suite of test functions representing a range of modality and number of multiple minima.

Evolutionary programs (EPs) and evolutionary pattern search algorithms (EPSAS) are two general classes of evolutionary methods for optimizing on continuous domains. The relative performance of these methods has been evaluated on standard global optimization test functions, and these results suggest that EPSAs more robustly converge to near-optimal solutions than EPs. In this paper we evaluate the relative performance of EPSAs and EPs on a real-world application: flexible ligand binding in the Autodock docking software. We compare the performance of these methods on a suite of docking test problems. Our results confirm that EPSAs and EPs have comparable performance, and they suggest that EPSAs may be more robust on larger, more complex problems.

Techniques for modeling oil well sand production have been developed using the formulations for superquadric discrete elements and Darcy fluid flow. Discrete element models are generated using the new technique of particle cloning. Discrete element sources and sinks allow simulation of sand production from the initial state through the transition to an equilibrium state where particles are created and removed at the same rate.

Evolutionary algorithms have been successfully applied to a variety of molecular structure prediction problems. In this paper we reconsider the design of genetic algorithms that have been applied to a simple protein structure prediction problem. Our analysis considers the impact of several algorithmic factors for this problem: the confirmational representation, the energy formulation and the way in which infeasible conformations are penalized, Further we empirically evaluated the impact of these factors on a small set of polymer sequences. Our analysis leads to specific recommendations for both GAs as well as other heuristic methods for solving PSP on the HP model.

This report documents a data collection where we recorded redundant range image data from multiple views of a simple scene, and recorded accurate survey measurements of the same scene. Collecting these data was a focus of the research project Automated Geometric Model Builder Using Range Image Sensor Data (96-0384), supported by Sandia's Laboratory-Directed Research and Development (LDRD) Program during fiscal years 1996, 1997, and 1998. The data described here are available from the authors on CDROM, or electronically over the Internet. Included in this data distribution are Computer-Aided Design (CAD) models we constructed from the survey measurements. The CAD models are compatible with the SolidWorks 98 Plus system, the modern Computer-Aided Design software system that is central to Sandia's DeskTop Engineering Project (DTEP). Integration of our measurements (as built) with the constructive geometry process of the CAD system (as designed) delivers on a vision of the research project. This report on our final data collection will also serve as a final report on the project.

A response surface methodology-based technique is presented for treating discretization error in non-deterministic analysis. The response surface, or metamodel, is estimated from computer experiments which vary both uncertain physical parameters and the fidelity of the computational mesh. The resultant metamodel is then used to propagate the variabilities in the continuous input parameters, while the mesh size is taken to zero, its asymptotic limit. With respect to mesh size, the metamodel is equivalent to Richardson extrapolation, in which solutions on coarser and finer meshes are used to estimate discretization error. The method is demonstrated on a one dimensional prismatic bar, in which uncertainty in the third vibration frequency is estimated by propagating variations in material modulus, density, and bar length. The results demonstrate the efficiency of the method for combining non-deterministic analysis with error estimation to obtain estimates of total simulation uncertainty. The results also show the relative sensitivity of failure estimates to solution bias errors in a reliability analysis, particularly when the physical variability of the system is low.

In this paper we evaluate the design of the hybrid evolutionary algorithms (EAs) that are currently used to perform flexible ligand binding in the Autodock docking software. Hybrid EAs incorporate specialized operators that exploit domain-specific features to accelerate an EA's search. We consider hybrid EAs that use an integrated local search operator to reline individuals within each iteration of the search. We evaluate several factors that impact the efficacy of a hybrid EA, and we propose new hybrid EAs that provide more robust convergence to low-energy docking configurations than the methods currently available in Autodock.

Many applications produce three-dimensional points that must be further processed to generate a surface. Surface reconstruction algorithms that start with a set of unorganized points are extremely time-consuming. Often, however, points are generated such that there is additional information available to the reconstruction algorithm. We present a specialized algorithm for surface reconstruction that is three orders of magnitude faster than algorithms for the general case. In addition to sample point locations, our algorithm starts with normal information and knowledge of each point's neighbors. Our algorithm produces a localized approximation to the surface by creating a star-shaped triangulation between a point and a subset of its nearest neighbors. This surface patch is extended by locally triangulating each of the points along the edge of the patch. As each edge point is triangulated, it is removed from the edge and new edge points along the patch's edge are inserted in its place. The updated edge spirals out over the surface until the edge encounters a surface boundary and stops growing in that direction, or until the edge reduces to a small hole that fills itself in.

A computational procedure for extracting substructure-by-substructure flexibility properties from global modal parameters is presented. The present procedure consists of two key features: an element-based direct flexibility method, which uniquely determines the global flexibility without resorting to case-dependent redundancy selections, and the projection of kinematically inadmissible modes that are contained in the iterated substructural matrices. The direct flexibility method is used as the basis of an inverse problem, whose goal is to determine substructural flexibilities given the global flexibility, geometrically determined substructural rigid-body modes, and the local-to-global assembly operators. The resulting procedure, given accurate global flexibility, extracts the exact element-by-element substructural flexibilities for determinate structures. For indeterminate structures, the accuracy depends on the iteration tolerance limits. The procedure is illustrated using both simple and complex numerical examples and appears to be effective for structural applications such as damage localization and finite element model reconciliation.

Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem. © Springer-Verlag 1999.

Dual control volume grand canonical molecular dynamics (DCV-GCMD) is a boundary-driven non-equilibrium molecular dynamics technique for simulating gradient driven diffusion in multi-component systems. Two control volumes are established at opposite ends of the simulation box. Constant temperature and chemical potential of diffusing species are imposed in the control volumes. This results in stable chemical potential gradients and steady-state diffusion fluxes in the region between the control volumes. We present results and detailed analysis for a new constant-pressure variant of the DCV-GCMD method in which one of the diffusing species for which a steady-state diffusion flux exists does not have to be inserted or deIeted. Constant temperature, pressure and chemical potential of all diffusing species except one are imposed in the control volumes. The constant-pressure method can be applied to situations in which insertion and deletion of large molecules would be prohibitively difficult. As an exampIe, we used the method to shnulate diffusion in a biruuy mixture of spherical particles with a 2:1 size ratio. Steady-state diffusion fluxes of both diffbsi.ng species were established. The constant-pressure diffision coefficients agreed closely with the results of the standard constant-volume calculations. In addition, we show how the concentration, chemical potential and flux profiles can be used to calculate kwd binary and Maxwell-Stefim diffusion coefficients. In the case of the 2:1 size ratio mixture, we found that the binary dlffision coefficients were asymmetric and composition dependent, whereas the Maxwell-Stefan diffision coefficients changed very little with composition and were symmetric. This last result verified that the Gibbs-Duhem relation was satisfied locally, thus validating the assumption of local equilibrium.

A phase-field model for grain growth is briefly described. In this model, a poly-crystalline microstructure is represented by multiple structural order parameter fields whose temporal and spatial evolutions follow the time-dependent Ginzburg-Landau (TDGL) equations. Results from phase-field simulations of two-dimensional (2D) grain growth will be summarized and preliminary results on three-dimensional (3D) grain growth will be presented. The physical interpretation of the structural order parameter fields and the efficient and accurate semi-implicit Fourier spectral method for solving the TDGL equations will be briefly discussed.

Electronic structure calculations frequently invoke periodic boundary conditions to solve for electrostatic potentials. For systems that are electronically charged, or contain dipole (or higher) moments, this artifice introduces spurious potentials due to the interactions between the system and multipole moments of its periodic images in aperiodic directions. I describe a method to properly handle the multipole moments of the electron density in electronic structure calculations using periodic boundary conditions. The density for which an electrostatic potential is to be evaluated is divided into two pieces. A local density is constructed that matches the desired moments of the full density, and its potential computed treating this density as isolated. With the density of this local moment countercharge removed from the full density, the remainder density lacks the troublesome moments and its electrostatic potential can be evaluated accurately using periodic boundary conditions.

A discrete element computer program named DMC_BLAST (Distinct Motion Code) has been under development since 1987 for modeling rock blasting (Preece & Taylor, 1989). This program employs explicit time integration and uses spherical or cylindrical elements that are represented as circles in two dimensions. DMC_BLAST calculations compare favorably with data from actual bench blasts (Preece et al, 1993). Coal seam chilling refers to the shattering of a significant portion of the coal leaving unusable fines. It is also refereed to as coal damage. Chilling is caused during a blast by a combination of explosive shock energy and movement of the adjacent rock. Chilling can be minimized by leaving a buffer zone between the bottom of the blastholes and the coal seam or by changing the blast design to decrease the powder factor or by a combination of both. Blast design in coal mine cast blasting is usually a compromise between coal damage and rock fragmentation and movement (heave). In this paper the damage to coal seams from rock movement is examined using the discrete element computer code DMC_BLAST. A rock material strength option has been incorporated into DMC_BLAST by placing bonds/links between the spherical particles used to model the rock. These bonds tie the particles together but can be broken when the tensile, compressive or shear stress in the bond exceeds the defined strength. This capability has been applied to predict coal seam damage, particularly at the toe of a cast blast where drag forces exerted by movement of the overlying rock can adversely effect the top of the coal at the bench face. A simulation of coal mine cast blasting has been performed with special attention being paid to the strength of the coal and its behavior at t he bench face during movement of the overlying material.

This paper describes a method of modeling swarms of UAVs and/or fighter aircraft using particle simulation concepts. Recent investigations into the use of genetic algorithms to design neural networks for the control of autonomous vehicles (i.e., robots) led to the examination of methods of simulating large collections of robots. This paper describes the successful implementation of a model of swarm dynamics using particle simulation concepts. Several examples of the complex behaviors achieved in a target/interceptor scenario are presented.

The ability to image complex geologies such as salt domes in the Gulf of Mexico and thrusts in mountainous regions is essential for reducing the risk associated with oil exploration. Imaging these structures, however, is computationally expensive as datasets can be terabytes in size. Traditional ray-tracing migration methods cannot handle complex velocity variations commonly found near such salt structures. Instead the authors use the full 3D acoustic wave equation, discretized via a finite difference algorithm. They reduce the cost of solving the apraxial wave equation by a number of numerical techniques including the method of fractional steps and pipelining the tridiagonal solves. The imaging code, Salvo, uses both frequency parallelism (generally 90% efficient) and spatial parallelism (65% efficient). Salvo has been tested on synthetic and real data and produces clear images of the subsurface even beneath complicated salt structures.

The National Institute of Justice has tasked their Satellite Facility at Sandia National Laboratories and their Southeast Regional Technology Center in Charleston, South Carolina to devise new procedures and tools for helping correctional facilities to assess their security vulnerabilities. Thus, a team is visiting selected correctional facilities and performing vulnerability assessments. A vulnerability assessment helps to identi~ the easiest paths for inmate escape, for introduction of contraband such as drugs or weapons, for unexpected intrusion fi-om outside of the facility, and for the perpetration of violent acts on other inmates and correctional employees, In addition, the vulnerability assessment helps to quantify the security risks for the facility. From these initial assessments will come better procedures for performing vulnerability assessments in general at other correctional facilities, as well as the development of tools to assist with the performance of such vulnerability assessments.

Distributed systems have been studied for twenty years and are now coming into wider use as fast networks and powerful workstations become more readily available. In many respects a massively parallel computer resembles a network of workstations and it is tempting to port a distributed operating system to such a machine. However, there are significant differences between these two environments and a parallel operating system is needed to get the best performance out of a massively parallel system. This report characterizes the differences between distributed systems, networks of workstations, and massively parallel systems and analyzes the impact of these differences on operating system design. In the second part of the report, we introduce Puma, an operating system specifically developed for massively parallel systems. We describe Puma portals, the basic building blocks for message passing paradigms implemented on top of Puma, and show how the differences observed in the first part of the report have influenced the design and implementation of Puma.

This white paper presents the initial requirements for developing a new computer model for simulating the effects of extreme acts of terrorism in the United States. General characteristics of the model are proposed and the level of effort to prepare a complete written description of the model, prior to coding, is detailed. The model would simulate the decision processes and interactions of complex U. S. systems engaged in responding to and recovering from four types of terrorist incidents. The incident scenarios span the space of extreme acts of terrorism that have the potential to affect not only the impacted area, but also the entire nation. The model would be useful to decision-makers in assessing and analyzing the vulnerability of the nation's complex infrastructures, in prioritizing resources to reduce risk, and in planning strategies for immediate response and for subsequent recovery from terrorist incidents.

Phase encoding of shot records provides a means of imaging a number of shots within a single migration. This results in a reduction in the required computation for a complete image, a reduction by the number of shots used in each individual migration, trading this increase in speed for additional noise in the resulting image. Some methods for phase encoding have been shown to limit this noise to a tolerable range when combining several shots, enabling speed ups of a factor of a few. In this paper, the authors present a use of phase encoding which allows faster imaging by an order of magnitude or more, with the additional benefit that the individual migrations can be stopped whenever the answer is good enough. This approach may ultimately render 3-D frequency-domain prestack depth migration cost effective.