Algorithms for higher order accuracy modeling of kinematic behavior within the ALEGRA framework are presented. These techniques improve the behavior of the code when kinematic errors are found, ensure orthonormality of the rotation tensor at each time step, and increase the accuracy of the Lagrangian stretch and rotation tensor update algorithm. The implementation of these improvements in ALEGRA is described. A short discussion of issues related to improving the accuracy of the stress update procedures is also included.
Solidification and blood flow seemingly have little in common, but each involves a fluid in contact with a deformable solid. In these systems, the solid-fluid interface moves as the solid advects and deforms, often traversing the entire domain of interest. Currently, these problems cannot be simulated without innumerable expensive remeshing steps, mesh manipulations or decoupling the solid and fluid motion. Despite the wealth of progress recently made in mechanics modeling, this glaring inadequacy persists. We propose a new technique that tracks the interface implicitly and circumvents the need for remeshing and remapping the solution onto the new mesh. The solid-fluid boundary is tracked with a level set algorithm that changes the equation type dynamically depending on the phases present. This novel approach to coupled mechanics problems promises to give accurate stresses, displacements and velocities in both phases, simultaneously.
High throughput instruments and analysis techniques are required in order to make good use of the genomic sequences that have recently become available for many species, including humans. These instruments and methods must work with tens of thousands of genes simultaneously, and must be able to identify the small subsets of those genes that are implicated in the observed phenotypes, or, for instance, in responses to therapies. Microarrays represent one such high throughput method, which continue to find increasingly broad application. This project has improved microarray technology in several important areas. First, we developed the hyperspectral scanner, which has discovered and diagnosed numerous flaws in techniques broadly employed by microarray researchers. Second, we used a series of statistically designed experiments to identify and correct errors in our microarray data to dramatically improve the accuracy, precision, and repeatability of the microarray gene expression data. Third, our research developed new informatics techniques to identify genes with significantly different expression levels. Finally, natural language processing techniques were applied to improve our ability to make use of online literature annotating the important genes. In combination, this research has improved the reliability and precision of laboratory methods and instruments, while also enabling substantially faster analysis and discovery.
ALEGRA is an arbitrary Lagrangian-Eulerian finite element code that emphasizes large distortion and shock propagation in inviscid fluids and solids. This document describes user options for modeling magnetohydrodynamic, thermal conduction, and radiation emission effects.
Wireless communication networks are highly resource-constrained; thus many security protocols which work in other settings may not be efficient enough for use in wireless environments. This report considers a variety of cryptographic techniques which enable secure, authenticated communication when resources such as processor speed, battery power, memory, and bandwidth are tightly limited.
We present here the details of the implementation of the parallel tempering Monte Carlo technique into a LAMMPS, a heavily used massively parallel molecular dynamics code at Sandia. This technique allows for many replicas of a system to be run at different simulation temperatures. At various points in the simulation, configurations can be swapped between different temperature environments and then continued. This allows for large regions of energy space to be sampled very quickly, and allows for minimum energy configurations to emerge in very complex systems, such as large biomolecular systems. By including this algorithm into an existing code, we immediately gain all of the previous work that had been put into LAMMPS, and allow this technique to quickly be available to the entire Sandia and international LAMMPS community. Finally, we present an example of this code applied to folding a small protein.
Genetic programming is a powerful methodology for automatically producing solutions to problems in a variety of domains. It has been used successfully to develop behaviors for RoboCup soccer players and simple combat agents. We will attempt to use genetic programming to solve a problem in the domain of strategic combat, keeping in mind the end goal of developing sophisticated behaviors for compound defense and infiltration. The simplified problem at hand is that of two armed agents in a small room, containing obstacles, fighting against each other for survival. The base case and three changes are considered: a memory of positions using stacks, context-dependent genetic programming, and strongly typed genetic programming. Our work demonstrates slight improvements from the first two techniques, and no significant improvement from the last.
This report is based on the Statement of Work (SOW) describing the various requirements for delivering 3 new supercomputer system to Sandia National Laboratories (Sandia) as part of the Department of Energy's (DOE) Accelerated Strategic Computing Initiative (ASCI) program. This system is named Red Storm and will be a distributed memory, massively parallel processor (MPP) machine built primarily out of commodity parts. The requirements presented here distill extensive architectural and design experience accumulated over a decade and a half of research, development and production operation of similar machines at Sandia. Red Storm will have an unusually high bandwidth, low latency interconnect, specially designed hardware and software reliability features, a light weight kernel compute node operating system and the ability to rapidly switch major sections of the machine between classified and unclassified computing environments. Particular attention has been paid to architectural balance in the design of Red Storm, and it is therefore expected to achieve an atypically high fraction of its peak speed of 41 TeraOPS on real scientific computing applications. In addition, Red Storm is designed to be upgradeable to many times this initial peak capability while still retaining appropriate balance in key design dimensions. Installation of the Red Storm computer system at Sandia's New Mexico site is planned for 2004, and it is expected that the system will be operated for a minimum of five years following installation.
The Sandia Petaflops Planner is a tool for projecting the design and performance of parallel supercomputers into the future. The mathematical basis of these projections is the International Technology Roadmap for Semiconductors (ITRS, or a detailed version of Moore's Law) and DOE balance factors for supercomputer procurements. The planner is capable of various forms of scenario analysis, cost estimation, and technology analysis. The tool is described along with technology conclusions regarding PFLOPS-level supercomputers in the upcoming decade.
The Computational Plant or Cplant is a commodity-based distributed-memory supercomputer under development at Sandia National Laboratories. Distributed-memory supercomputers run many parallel programs simultaneously. Users submit their programs to a job queue. When a job is scheduled to run, it is assigned to a set of available processors. Job runtime depends not only on the number of processors but also on the particular set of processors assigned to it. Jobs should be allocated to localized clusters of processors to minimize communication costs and to avoid bandwidth contention caused by overlapping jobs. This report introduces new allocation strategies and performance metrics based on space-filling curves and one dimensional allocation strategies. These algorithms are general and simple. Preliminary simulations and Cplant experiments indicate that both space-filling curves and one-dimensional packing improve processor locality compared to the sorted free list strategy previously used on Cplant. These new allocation strategies are implemented in Release 2.0 of the Cplant System Software that was phased into the Cplant systems at Sandia by May 2002. Experimental results then demonstrated that the average number of communication hops between the processors allocated to a job strongly correlates with the job's completion time. This report also gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures. The associated clustering problem is as follows: Given n points in {Re}d, find k points that minimize their average pairwise L{sub 1} distance. Exact and approximate algorithms are given for these optimization problems. One of these algorithms has been implemented on Cplant and will be included in Cplant System Software, Version 2.1, to be released. In more preliminary work, we suggest improvements to the scheduler separate from the allocator.
This report summarizes the results of a three-year LDRD project on prognostics and health management. System failure over some future time interval (an alternative definition is the capability to predict the remaining useful life of a system). Prognostics are integrated with health monitoring (through inspections, sensors, etc.) to provide an overall PHM capability that optimizes maintenance actions and results in higher availability at a lower cost. Our goal in this research was to develop PHM tools that could be applied to a wide variety of equipment (repairable, non-repairable, manufacturing, weapons, battlefield equipment, etc.) and require minimal customization to move from one system to the next. Thus, our approach was to develop a toolkit of reusable software objects/components and architecture for their use. We have developed two software tools: an Evidence Engine and a Consequence Engine. The Evidence Engine integrates information from a variety of sources in order to take into account all the evidence that impacts a prognosis for system health. The Evidence Engine has the capability for feature extraction, trend detection, information fusion through Bayesian Belief Networks (BBN), and estimation of remaining useful life. The Consequence Engine involves algorithms to analyze the consequences of various maintenance actions. The Consequence Engine takes as input a maintenance and use schedule, spares information, and time-to-failure data on components, then generates maintenance and failure events, and evaluates performance measures such as equipment availability, mission capable rate, time to failure, and cost. This report summarizes the capabilities we have developed, describes the approach and architecture of the two engines, and provides examples of their use. 'Prognostics' refers to the capability to predict the probability of
A fundamental challenge for all communication systems, engineered or living, is the problem of achieving efficient, secure, and error-free communication over noisy channels. Information theoretic principals have been used to develop effective coding theory algorithms to successfully transmit information in engineering systems. Living systems also successfully transmit biological information through genetic processes such as replication, transcription, and translation, where the genome of an organism is the contents of the transmission. Decoding of received bit streams is fairly straightforward when the channel encoding algorithms are efficient and known. If the encoding scheme is unknown or part of the data is missing or intercepted, how would one design a viable decoder for the received transmission? For such systems blind reconstruction of the encoding/decoding system would be a vital step in recovering the original message. Communication engineers may not frequently encounter this situation, but for computational biologists and biotechnologist this is an immediate challenge. The goal of this work is to develop methods for detecting and reconstructing the encoder/decoder system for engineered and biological data. Building on Sandia's strengths in discrete mathematics, algorithms, and communication theory, we use linear programming and will use evolutionary computing techniques to construct efficient algorithms for modeling the coding system for minimally errored engineered data stream and genomic regulatory DNA and RNA sequences. The objective for the initial phase of this project is to construct solid parallels between biological literature and fundamental elements of communication theory. In this light, the milestones for FY2003 were focused on defining genetic channel characteristics and providing an initial approximation for key parameters, including coding rate, memory length, and minimum distance values. A secondary objective addressed the question of determining similar parameters for a received, noisy, error-control encoded data set. In addition to these goals, we initiated exploration of algorithmic approaches to determine if a data set could be approximated with an error-control code and performed initial investigations into optimization based methodologies for extracting the encoding algorithm given the coding rate of an encoded noise-free and noisy data stream.
Evidence for the existence of discrete sub-movements underlying continuous human movement has motivated many attempts to "extract" them. Although they produce visually convincing results, all of the methodologies that have been employed are prone to produce spurious decompositions. Examples of potential failures are given. A branch-and-bound algorithm for submovement extraction, capable of global nonlinear minimization (and hence capable of avoiding spurious decompositions), is developed and demonstrated.
If we are to build a supercomputer with a speed of 10{sup 15} floating operations per second (1 PetaFLOPS), interconnect technology will need to be improved considerably over what it is today. In this report, we explore one possible interconnect design for such a network. The guiding principle in this design is the optimization of all components for the finiteness of the speed of light. To achieve a linear speedup in time over well-tested supercomputers of todays' designs will require scaling up of processor power and bandwidth and scaling down of latency. Latency scaling is the most challenging: it requires a 100 ns user-to-user latency for messages traveling the full diameter of the machine. To meet this constraint requires simultaneously minimizing wire length through 3D packaging, new low-latency electrical signaling mechanisms, extremely fast routers, and new network interfaces. In this report, we outline approaches and implementations that will meet the requirements when implemented as a system. No technology breakthroughs are required.
High-resolution finite volume methods for solving systems of conservation laws have been widely embraced in research areas ranging from astrophysics to geophysics and aero-thermodynamics. These methods are typically at least second-order accurate in space and time, deliver non-oscillatory solutions in the presence of near discontinuities, e.g., shocks, and introduce minimal dispersive and diffusive effects. High-resolution methods promise to provide greatly enhanced solution methods for Sandia's mainstream shock hydrodynamics and compressible flow applications, and they admit the possibility of a generalized framework for treating multi-physics problems such as the coupled hydrodynamics, electro-magnetics and radiative transport found in Z pinch physics. In this work, we describe initial efforts to develop a generalized 'black-box' conservation law framework based on modern high-resolution methods and implemented in an object-oriented software framework. The framework is based on the solution of systems of general non-linear hyperbolic conservation laws using Godunov-type central schemes. In our initial efforts, we have focused on central or central-upwind schemes that can be implemented with only a knowledge of the physical flux function and the minimal/maximal eigenvalues of the Jacobian of the flux functions, i.e., they do not rely on extensive Riemann decompositions. Initial experimentation with high-resolution central schemes suggests that contact discontinuities with the concomitant linearly degenerate eigenvalues of the flux Jacobian do not pose algorithmic difficulties. However, central schemes can produce significant smearing of contact discontinuities and excessive dissipation for rotational flows. Comparisons between 'black-box' central schemes and the piecewise parabolic method (PPM), which relies heavily on a Riemann decomposition, shows that roughly equivalent accuracy can be achieved for the same computational cost with both methods. However, PPM clearly outperforms the central schemes in terms of accuracy at a given grid resolution and the cost of additional complexity in the numerical flux functions. Overall we have observed that the finite volume schemes, implemented within a well-designed framework, are extremely efficient with (potentially) very low memory storage. Finally, we have found by computational experiment that second and third-order strong-stability preserving (SSP) time integration methods with the number of stages greater than the order provide a useful enhanced stability region. However, we observe that non-SSP and non-optimal SSP schemes with SSP factors less than one can still be very useful if used with time-steps below the standard CFL limit. The 'well-designed' integration schemes that we have examined appear to perform well in all instances where the time step is maintained below the standard physical CFL limit.
An understanding of the dynamics of z-pinch wire array explosion and collapse is of critical interest to the development and future of pulsed power inertial confinement fusion experiments. Experimental results clearly show the extreme three-dimensional nature of the wire explosion and collapse process. The physics of this process can be approximated by the resistive magnetohydrodynamic (MHD) equations augmented by thermal and radiative transport modeling. Z-pinch MHD physics is dominated by material regions whose conductivity properties vary drastically as material passes from solid through melt into plasma regimes. At the same time void regions between the wires are modeled as regions of very low conductivity. This challenging physical situation requires a sophisticated three-dimensional modeling approach matched by sufficient computational resources to make progress in predictive modeling and improved physical understanding.
This paper describes a methodology for implementing disk-less cluster systems using the Network File System (NFS) that scales to thousands of nodes. This method has been successfully deployed and is currently in use on several production systems at Sandia National Labs. This paper will outline our methodology and implementation, discuss hardware and software considerations in detail and present cluster configurations with performance numbers for various management operations like booting.
A new capability for modeling thin-shell structures within the coupled Euler-Lagrange code, Zapotec, is under development. The new algorithm creates an artificial material interface for the Eulerian portion of the problem by expanding a Lagrangian shell element such that it has an effective thickness that spans one or more Eulerian cells. The algorithm implementation is discussed along with several examples involving blast loading on plates.
Implicit time integration coupled with SUPG discretization in space leads to additional terms that provide consistency and improve the phase accuracy for convection dominated flows. Recently, it has been suggested that for small Courant numbers these terms may dominate the streamline diffusion term, ostensibly causing destabilization of the SUPG method. While consistent with a straightforward finite element stability analysis, this contention is not supported by computational experiments and contradicts earlier Von-Neumann stability analyses of the semidiscrete SUPG equations. This prompts us to re-examine finite element stability of the fully discrete SUPG equations. A careful analysis of the additional terms reveals that, regardless of the time step size, they are always dominated by the consistent mass matrix. Consequently, SUPG cannot be destabilized for small Courant numbers. Numerical results that illustrate our conclusions are reported.
A recently developed Centroidal Voronoi Tessellation (CVT) unstructured sampling method is investigated here to assess its suitability for use in statistical sampling and function integration. CVT efficiently generates a highly uniform distribution of sample points over arbitrarily shaped M-Dimensional parameter spaces. It has recently been shown on several 2-D test problems to provide superior point distributions for generating locally conforming response surfaces. In this paper, its performance as a statistical sampling and function integration method is compared to that of Latin-Hypercube Sampling (LHS) and Simple Random Sampling (SRS) Monte Carlo methods, and Halton and Hammersley quasi-Monte-Carlo sequence methods. Specifically, sampling efficiencies are compared for function integration and for resolving various statistics of response in a 2-D test problem. It is found that on balance CVT performs best of all these sampling methods on our test problems.
Broadcasting messages through the earth is a daunting task. Indeed, broadcasting a normal telephone conversion through the earth by wireless means is impossible with todays technology. Most of us don't care, but some do. Industries that drill into the earth need wireless communication to broadcast navigation parameters. This allows them to steer their drill bits. They also need information about the natural formation that they are drilling. Measurements of parameters such as pressure, temperature, and gamma radiation levels can tell them if they have found a valuable resource such as a geothermal reservoir or a stratum bearing natural gas. Wireless communication methods are available to the drilling industry. Information is broadcast via either pressure waves in the drilling fluid or electromagnetic waves in the earth and well tubing. Data transmission can only travel one way at rates around a few baud. Given that normal Internet telephone modems operate near 20,000 baud, these data rates are truly very slow. Moreover, communication is often interrupted or permanently blocked by drilling conditions or natural formation properties. Here we describe a tool that communicates with stress waves traveling through the steel drill pipe and production tubing in the well. It's based on an old idea called Acoustic Telemetry. But what we present here is more than an idea. This tool exists, it's drilled several wells, and it works. Currently, it's the first and only acoustic telemetry tool that can withstand the drilling environment. It broadcasts one way over a limited range at much faster rates than existing methods, but we also know how build a system that can communicate both up and down wells of indefinite length.
This report presents a perspective on the role of code comparison activities in verification and validation. We formally define the act of code comparison as the Code Comparison Principle (CCP) and investigate its application in both verification and validation. One of our primary conclusions is that the use of code comparisons for validation is improper and dangerous. We also conclude that while code comparisons may be argued to provide a beneficial component in code verification activities, there are higher quality code verification tasks that should take precedence. Finally, we provide a process for application of the CCP that we believe is minimal for achieving benefit in verification processes.
We seek to understand which supercomputer architecture will be best for supercomputers at the Petaflops scale and beyond. The process we use is to predict the cost and performance of several leading architectures at various years in the future. The basis for predicting the future is an expanded version of Moore's Law called the International Technology Roadmap for Semiconductors (ITRS). We abstract leading supercomputer architectures into chips connected by wires, where the chips and wires have electrical parameters predicted by the ITRS. We then compute the cost of a supercomputer system and the run time on a key problem of interest to the DOE (radiation transport). These calculations are parameterized by the time into the future and the technology expected to be available at that point. We find the new advanced architectures have substantial performance advantages but conventional designs are likely to be less expensive (due to economies of scale). We do not find a universal ''winner'', but instead the right architectural choice is likely to involve non-technical factors such as the availability of capital and how long people are willing to wait for results.