This paper presents a convergence theory for evolutionary pattern search algorithms (EPSAs). EPSAs are self-adapting evolutionary algorithms that modify the step size of the mutation operator in response to the success of previous optimization steps. Previously, the authors have proven a stationary point convergence theory for EPSAs for which the step size is not allowed to increase. The present analysis generalizes this analysis to prove a convergence theory for EPSAs that are allowed to both increase and decrease the step size. This convergence theory is based on an extension of the convergence theory for generalized pattern search methods.
This paper presents an experimental evaluation of evolutionary pattern search algorithms (EPSAs). Our experimental evaluation of EPSAs indicates that EPSAs can achieve similar performance to EAs on challenging global optimization problems. Additionally, we describe a stopping rule for EPSAs that reliably terminated them near a stationary point of the objective function. The ability for EPSAs to reliably terminate near stationary points offers a practical advantage over other EAs, which are typically stopped by heuristic stopping rules or simple bounds on the number of iterations. Our experiments also illustrate how the rate of the crossover operator can influence the tradeoff between the number of iterations before termination and the quality of the solution found by an EPSA.
Graph partitioning is an important abstraction used in solving many scientific computing problems. Unfortunately, the standard partitioning model does not incorporate considerations that are important in many settings. We address this by describing a generalized partitioning model which incorporates the notion of partition skew and is applicable to a variety of problems. We then develop enhancements to several important partitioning algorithms necessary to solve the generalized partitioning problem. Finally we demonstrate the benefit of employing several of these generalized methods to static decomposition of parallel computing problems.
Finite-difference, prestack depth migrations offers significant improvements over Kirchhoff methods in imaging near or under salt structures. We have implemented a finite-difference prestack depth migration algorithm for use on massively parallel computers which is discussed. The image quality of the finite-difference scheme has been investigated and suggested improvements are discussed.
A key to reducing the risks and costs of associated with oil and gas exploration is the fast, accurate imaging of complex geologies, such as salt domes in the Gulf of Mexico and overthrust regions in U.S. onshore regions. Pre-stack depth migration generally yields the most accurate images, and one approach to this is to solve the scalar-wave equation using finite differences. Current industry computational capabilities are insufficient for the application of finite-difference, 3-D, prestack, depth-migration algorithms. High performance computers and state-of-the-art algorithms and software are required to meet this need. As part of an ongoing ACT1 project funded by the U.S. Department of Energy, we have developed a finite-difference, 3-D prestack, depth-migration code for massively parallel computer systems. The goal of this work is to demonstrate that massively parallel computers (thousands of processors) can be used efficiently for seismic imaging, and that sufficient computing power exists (or soon will exist) to make finite-difference, prestack, depth migration practical for oil and gas exploration.
Tera Computer and Sandia National Laboratories have completed a CRADA, which examined the Tera Multi-Threaded Architecture (MTA) for use with large codes of importance to industry and DOE. The MTA is an innovative architecture that uses parallelism to mask latency between memories and processors. The physical implementation is a parallel computer with high cross-section bandwidth and GaAs processors designed by Tera, which support many small computation threads and fast, lightweight context switches between them. When any thread blocks while waiting for memory accesses to complete, another thread immediately begins execution so that high CPU utilization is maintained. The Tera MTA parallel computer has a single, global address space, which is appealing when porting existing applications to a parallel computer. This ease of porting is further enabled by compiler technology that helps break computations into parallel threads. DOE and Sandia National Laboratories were interested in working with Tera to further develop this computing concept. While Tera Computer would continue the hardware development and compiler research, Sandia National Laboratories would work with Tera to ensure that their compilers worked well with important Sandia codes, most particularly CTH, a shock physics code used for weapon safety computations. In addition to that important code, Sandia National Laboratories would complete research on a robotic path planning code, SANDROS, which is important in manufacturing applications, and would evaluate the MTA performance on this code. Finally, Sandia would work directly with Tera to develop 3D visualization codes, which would be appropriate for use with the MTA. Each of these tasks has been completed to the extent possible, given that Tera has just completed the MTA hardware. All of the CRADA work had to be done on simulators.
Networks at major computational organizations are becoming increasingly complex. The introduction of large massively parallel computers and supercomputers with gigabyte memories are requiring greater and greater bandwidth for network data transfers to widely dispersed clients. For networks to provide adequate data transfer services to high performance computers and remote users connected to them, the networking components must be optimized from a combination of internal and external performance criteria. This paper describes research done at Sandia National Laboratories to model network data services and to visualize the flow of data from source to sink when using the data services.
The Hierarchical High-Performance Storage System (HPSS) Testbed project at Sandia National Laboratories was part of a research collaboration between industry, national research centers, and national laboratories to develop mass storage system software that would scale to meet the capacity and performance required by supercomputer and massively parallel computational environments. This report describes the software that was developed within this collaboration as a result of a cooperative research and development agreement between Sandia National Laboratories and International Business Machines (IBM) Corporation, Government Systems.
The author presents a final report on a Laboratory-Directed Research and Development (LDRD) project, Innovative Computing for Diagnoses from Medical, Magnetic-Resonance Imaging, performed during fiscal years 1992 and 1993. The project defined a role for high-performance computing in surgery: the supercomputer can automatically summarize the three-dimensional extents of lesions and other clinically-relevant structures, and can deliver these summaries to workstation-based, augmented-reality environments at the clinical site. The author developed methods and software to make these summaries from the digital data already acquired using clinical, magnetic-resonance machines. In joint work with Albuquerque`s Department of Veterans Affairs Hospital, the author applied this work, and obtained a basis for planning, for rehearsal, and for guidance during surgery.
Inverse protein folding concerns the identification of an amino acid sequence that folds to a given structure. Sequence design problems attempt to avoid the apparent difficulty of inverse protein folding by defining an energy that can be minimized to find protein-like sequences. The authors evaluate the practical relevance of two sequence design problems by analyzing their computation complexity. They show that the canonical method of sequence design is intractable, and describe approximation algorithms for this problem. The authors also describe an efficient algorithm that exactly solves the grand canonical method. The analysis shows how sequence design problems can fail to reduce the difficulty of the inverse protein folding problem, and highlights the need to analyze these problems to evaluate their practical relevance.
A discrete element computer program named DMC{_}BLAST (Distinct Motion Code) has been under development since 1987 for modeling rock blasting. This program employs explicit time integration and uses spherical or cylindrical elements that are represented as circles in 2-D. DMC{_}BLAST calculations compare favorably with data from actual bench blasts. The blast modeling capabilities of DMC{_}BLAST have been expanded to include independently dipping geologic layers, top surface, bottom surface and pit floor. The pit can also now be defined using coordinates based on the toe of the bench. A method for modeling decked explosives has been developed which allows accurate treatment of the inert materials (stemming) in the explosive column and approximate treatment of different explosives in the same blasthole. A DMC{_}BLAST user can specify decking through a specific geologic layer with either inert material or a different explosive. Another new feature of DMC{_}BLAST is specification of an uplift angle which is the angle between the normal to the blasthole and a vector defining the direction of explosive loading on particles adjacent to the blasthole. A buffer (choke) blast capability has been added for situations where previously blasted material is adjacent to the free face of the bench preventing any significant lateral motion during the blast.
For the past few years, the Minnesota Department of Corrections, assisted by Sandia National Laboratories, has developed a set of standards for perimeter security at medium, close, and maximum custody correctional facilities in the state. During this process, the threat to perimeter security was examined and concepts about correctional perimeter security were developed. This presentation and paper will review the outcomes of this effort, some of the lessons learned, and the concepts developed during this process and in the course of working with architects, engineers and construction firms as the state upgraded perimeter security at some facilities and planned new construction at other facilities.
A mathematical framework is developed for the study of materials containing axisymmetric inclusions or flaws such as ellipsoidal voids, penny-shaped cracks, or fibers of circular cross-section. The general case of nonuniform statistical distributions of such heterogeneities is attacked by first considering a spatially uniform distribution of flaws that are all oriented in the same direction. Assuming an isotropic substrate, the macroscopic material properties of this simpler microstructure naturally should be transversely isotropic. An orthogonal basis for the linear subspace consisting of all double-symmetric transversely-isotropic fourth-order tensors associated with a given material vector is applied to deduce the explicit functional dependence of the material properties of these aligned materials on the shared symmetry axis. The aligned and uniform microstructure seems geometrically simple enough that the macroscopic transversely isotropic properties could be derived in closed form. Since the resulting properties are transversely isotropic, the analyst must therefore be able to identify the appropriate coefficients of the transverse basis. Once these functions are identified, a principle of superposition of strain rates ay be applied to define an expectation integral for the composite properties of a material containing arbitrary anisotropic distributions of axisymmetric inhomogeneities. A proposal for coupling plastic anisotropy to the elastic anisotropy is presented in which the composite yield surface is interpreted as a distortion of the isotropic substrate yield surface; the distortion directions are coupled to the elastic anisotropy directions. Finally, some commonly assumed properties (such as major symmetry) of the Cauchy tangent stiffness tensor are shown to be inappropriate for large distortions of anisotropic materials.
Consider mapping a regular i x j quadrilateral mesh of a rectangle onto a surface. The quality of the mapped mesh of the surface depends heavily on which vertices of the surface correspond to corners of the rectangle. The authors problem is, given an n-sided surface, chose as corners four vertices such that the surface resembles a rectangle with corners at those vertices. Note that n could be quite large, and the length and width of the rectangle, i and j, are not prespecified. In general, there is either a goal number or a prescribed number of mesh edges for each bounding curve of the surface. The goals affect the quality of the mesh, and the prescribed edges may make finding a feasible set of corners difficult. The algorithm need only work for surfaces that are roughly rectangular, particular those without large reflex angles, as otherwise an unstructured meshing algorithm is used instead. The authors report on the theory and implementation of algorithms for this problem. They also given an overview of a solution to a related problem called interval assignment: given a complex of surfaces sharing curves, globally assign the number of mesh edges or intervals for each curve such that it is possible to mesh each surface according to its prescribed quadrilateral meshing algorithm, and assigned and user-prescribed boundary mesh edges and corners. They also note a practical, constructive technique that relies on interval assignment that can generate a quadrilateral mesh of a complex of surfaces such that a compatible hexahedral mesh of the enclosed volume exists.
In this work, high-energy electron beam brazing of a ceramic part is modeled numerically. The part considered consists of a ceramic cylinder and disk between which is sandwiched an annular washer of braze material. An electron beam impinges on the disk, melting the braze metal. The resulting coupled electron-photon and thermal transport equations are solved using Monte Carlo and finite element techniques respectively. Results indicate that increased electron beam current decreases the time required to melt the braze while increasing temperature gradients in the ceramic near the braze. Furnace brazing was also simulated and predicted results indicate increased processing times relative to electron beam brazing.
This research project used Pad++, a user interface originally developed by Jim Holland. The objective was to explore the utility of that user interface to large databases of information such as those found on the World Wide Web. A web browser based on Pad++ was developed in the first year of this project The first year results, including the human factors were documented in a video and were presented at a SNL-wide seminar. The second year of this research project focused on applying the results of the first year research. The work in the second year involves using Pad++ as a basis for tools to manage large complicated web sites. Pad++ is ideally suited to this complex activity. A prototype was developed, which presents Web relationships in 3D hyperspace, following research from the Geometry Center at the University of Minnesota. Various human factors studies were completed, which indicate Pad++ web browsers allow users to comprehend 23% faster than when using Netscape.
The corrections system in the U.S. is supervising over five million offenders. This number is rising fast and so are the direct and indirect costs to society. To improve supervision and reduce the cost of parole and probation, first generation home arrest systems were introduced in 1987. While these systems proved to be helpful to the corrections system, their scope is rather limited because they only cover an offender at a single location and provide only a partial time coverage. To correct the limitations of first-generation systems, second-generation wide area continuous electronic offender monitoring systems, designed to monitor the offender at all times and locations, are now on the drawing board. These systems use radio frequency location technology to track the position of offenders. The challenge for this technology is the development of reliable personal locator devices that are small, lightweight, with long operational battery life, and indoors/outdoors accuracy of 100 meters or less. At the center of a second-generation system is a database that specifies the offender`s home, workplace, commute, and time the offender should be found in each. The database could also define areas from which the offender is excluded. To test compliance, the system would compare the observed coordinates of the offender with the stored location for a given time interval. Database logfiles will also enable law enforcement to determine if a monitored offender was present at a crime scene and thus include or exclude the offender as a potential suspect.
This report presents, Aspen. Sandia National Laboratories is developing this new agent-based microeconomic simulation model of the U.S. economy. The model is notable because it allows a large number of individual economic agents to be modeled at a high level of detail and with a great degree of freedom. Some features of Aspen are (a) a sophisticated message-passing system that allows individual pairs of agents to communicate, (b) the use of genetic algorithms to simulate the learning of certain agents, and (c) a detailed financial sector that includes a banking system and a bond market. Results from runs of the model are also presented.
Findings from a four-year study by an international benchmarking group in the comparison of computational methods for evaluating burnup credit in criticality safety analyses are presented in this paper. Approximately 20 participants from 11 countries have provided results for most problems. Four detailed benchmark problems for Pressurized Water Reactor (PWR) fuel have been completed and are summarized in this paper. Preliminary results from current work addressing burnup credit for Boiling Water Reactor (BWR) fuel will also be discussed as well as planned activities for additional benchmarks including Mixed-Oxide (MOX) fuels, subcritical benchmarks, international databases, and other activities.
Transient dynamics simulations are commonly used to model phenomena such as car crashes, underwater explosions, and the response of shipping containers to high-speed impacts. Physical objects in such a simulation are typically represented by Lagrangian meshes because the meshes can move and deform with the objects as they undergo stress. Fluids (gasoline, water) or fluid-like materials (earth) in the simulation can be modeled using the techniques of smoothed particle hydrodynamics. Implementing a hybrid mesh/particle model on a massively parallel computer poses several difficult challenges. One challenge is to simultaneously parallelize and load-balance both the mesh and particle portions of the computation. A second challenge is to efficiently detect the contacts that occur within the deforming mesh and between mesh elements and particles as the simulation proceeds. These contacts impart forces to the mesh elements and particles which must be computed at each timestep to accurately capture the physics of interest. In this paper we describe new parallel algorithms for smoothed particle hydrodynamics and contact detection which turn out to have several key features in common. Additionally, we describe how to join the new algorithms with traditional parallel finite element techniques to create an integrated particle/mesh transient dynamics simulation. Our approach to this problem differs from previous work in that we use three different parallel decompositions, a static one for the finite element analysis and dynamic ones for particles and for contact detection. We have implemented our ideas in a parallel version of the transient dynamics code PRONTO-3D and present results for the code running on a large Intel Paragon.
This manual describes the use of MPSalsa, an unstructured finite element (FE) code for solving chemically reacting flow problems on massively parallel computers. MPSalsa has been written to enable the rigorous modeling of the complex geometry and physics found in engineering systems that exhibit coupled fluid flow, heat transfer, mass transfer, and detailed reactions. In addition, considerable effort has been made to ensure that the code makes efficient use of the computational resources of massively parallel (MP), distributed memory architectures in a way that is nearly transparent to the user. The result is the ability to simultaneously model both three-dimensional geometries and flow as well as detailed reaction chemistry in a timely manner on MT computers, an ability we believe to be unique. MPSalsa has been designed to allow the experienced researcher considerable flexibility in modeling a system. Any combination of the momentum equations, energy balance, and an arbitrary number of species mass balances can be solved. The physical and transport properties can be specified as constants, as functions, or taken from the Chemkin library and associated database. Any of the standard set of boundary conditions and source terms can be adapted by writing user functions, for which templates and examples exist.
This paper considers the protein structure prediction problem for lattice and off-lattice protein folding models that explicitly represent side chains. Lattice models of proteins have proven extremely useful tools for reasoning about protein folding in unrestricted continuous space through analogy. This paper provides the first illustration of how rigorous algorithmic analyses of lattice models can lead to rigorous algorithmic analyses of off-lattice models. The authors consider two side chain models: a lattice model that generalizes the HP model (Dill 85) to explicitly represent side chains on the cubic lattice, and a new off-lattice model, the HP Tangent Spheres Side Chain model (HP-TSSC), that generalizes this model further by representing the backbone and side chains of proteins with tangent spheres. They describe algorithms for both of these models with mathematically guaranteed error bounds. In particular, the authors describe a linear time performance guaranteed approximation algorithm for the HP side chain model that constructs conformations whose energy is better than 865 of optimal in a face centered cubic lattice, and they demonstrate how this provides a 70% performance guarantee for the HP-TSSC model. This is the first algorithm in the literature for off-lattice protein structure prediction that has a rigorous performance guarantee. The analysis of the HP-TSSC model builds off of the work of Dancik and Hannenhalli who have developed a 16/30 approximation algorithm for the HP model on the hexagonal close packed lattice. Further, the analysis provides a mathematical methodology for transferring performance guarantees on lattices to off-lattice models. These results partially answer the open question of Karplus et al. concerning the complexity of protein folding models that include side chains.
A set of model interface guidelines, called MIG, is presented as a means by which any compliant numerical material model can be rapidly installed into any parent code without having to modify the model subroutines. Here, {open_quotes}model{close_quotes} usually means a material model such as one that computes stress as a function of strain, though the term may be extended to any numerical operation. {open_quotes}Parent code{close_quotes} means a hydrocode, finite element code, etc. which uses the model and enforces, say, the fundamental laws of motion and thermodynamics. MIG requires the model developer (who creates the model package) to specify model needs in a standardized but flexible way. MIG includes a dictionary of technical terms that allows developers and parent code architects to share a common vocabulary when specifying field variables. For portability, database management is the responsibility of the parent code. Input/output occurs via structured calling arguments. As much model information as possible (such as the lists of required inputs, as well as lists of precharacterized material data and special needs) is supplied by the model developer in an ASCII text file. Every MIG-compliant model also has three required subroutines to check data, to request extra field variables, and to perform model physics. To date, the MIG scheme has proven flexible in beta installations of a simple yield model, plus a more complicated viscodamage yield model, three electromechanical models, and a complicated anisotropic microcrack constitutive model. The MIG yield model has been successfully installed using identical subroutines in three vectorized parent codes and one parallel C++ code, all predicting comparable results. By maintaining one model for many codes, MIG facilitates code-to-code comparisons and reduces duplication of effort, thereby reducing the cost of installing and sharing models in diverse new codes.
A unifying framework is developed for the analysis of brittle materials. Heretofore diverse classes of models result from different choices for unspecified coefficient and distribution functions in the unified theory. Material response is described in terms of expectation integrals of transverse symmetry tensors. First, a canonical body containing cracks of all the same orientation is argued to possess macroscopic transverse isotropy. An orthogonal basis for the linear subspace consisting of all double-symmetric transversely-isotropic fourth-order tensors associated with a given material vector is introduced and applied to deduce the explicit functional dependence of the compliance of such contrived materials on the shared crack orientation. A principle of superposition of strain rates is used to write the compliance for a more realistic material consisting of cracks of random size and orientation as an expectation integral of the transverse compliance for each orientation times the joint distribution function for the size and orientation. Utilizing an evolving (initially exponential) size- dependence in the joint distribution, the general theory gives unprecedented agreement with measurements of the dynamic response of alumina to impact loading, especially upon release where the calculations predict the development of considerable deformation- induced anisotropy, challenging the conventional notion of shocks as isotropic phenomena.
This paper describes the design, implementation and performance of a port of the Argonne National Laboratory/Mississippi State University MPICH implementation of the Message Passing Interface standard to the Cray T3D massively parallel processing system. A description of the factors influencing the design and the various stages of implementation are presented. Performance results revealing superior bandwidth and comparable latency as compared to other full message passing systems on the T3D are shown. Further planned improvements and optimizations, including an analysis of a port to the T3E, are mentioned.
