Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximate computing”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 469 records · Page 26
All sourcesNASA NTRSDOE OSTI
NASA NTRS2013

Regression Verification Using Impact Summaries

Regression verification techniques are used to prove equivalence of syntactically similar programs. Checking equivalence of large programs, however, can be computationally expensive. Existing regression verification techniques rely on abstraction and decomposition techniques to reduce the computational effort of checking equivalence of the entire program. These techniques are sound but not complete. In this work, we propose a novel approach to improve scalability of regression verification by classifying the program behaviors generated during symbolic execution as either impacted or unimpacted. Our technique uses a combination of static analysis and symbolic execution to generate summaries of impacted program behaviors. The impact summaries are then checked for equivalence using an o-the-shelf decision procedure. We prove that our approach is both sound and complete for sequential programs, with respect to the depth bound of symbolic execution. Our evaluation on a set of sequential C artifacts shows that reducing the size of the summaries can help reduce the cost of software equivalence checking. Various reduction, abstraction, and compositional techniques have been developed to help scale software verification techniques to industrial-sized systems. Although such techniques have greatly increased the size and complexity of systems that can be checked, analysis of large software systems remains costly. Regression analysis techniques, e.g., regression testing [16], regression model checking [22], and regression verification [19], restrict the scope of the analysis by leveraging the differences between program versions. These techniques are based on the idea that if code is checked early in development, then subsequent versions can be checked against a prior (checked) version, leveraging the results of the previous analysis to reduce analysis cost of the current version. Regression verification addresses the problem of proving equivalence of closely related program versions [19]. These techniques compare two programs with a large degree of syntactic similarity to prove that portions of one program version are equivalent to the other. Regression verification can be used for guaranteeing backward compatibility, and for showing behavioral equivalence in programs with syntactic differences, e.g., when a program is refactored to improve its performance, maintainability, or readability. Existing regression verification techniques leverage similarities between program versions by using abstraction and decomposition techniques to improve scalability of the analysis [10, 12, 19]. The abstractions and decomposition in the these techniques, e.g., summaries of unchanged code [12] or semantically equivalent methods [19], compute an over-approximation of the program behaviors. The equivalence checking results of these techniques are sound but not complete-they may characterize programs as not functionally equivalent when, in fact, they are equivalent. In this work we describe a novel approach that leverages the impact of the differences between two programs for scaling regression verification. We partition program behaviors of each version into (a) behaviors impacted by the changes and (b) behaviors not impacted (unimpacted) by the changes. Only the impacted program behaviors are used during equivalence checking. We then prove that checking equivalence of the impacted program behaviors is equivalent to checking equivalence of all program behaviors for a given depth bound. In this work we use symbolic execution to generate the program behaviors and leverage control- and data-dependence information to facilitate the partitioning of program behaviors. The impacted program behaviors are termed as impact summaries. The dependence analyses that facilitate the generation of the impact summaries, we believe, could be used in conjunction with other abstraction and decomposition based approaches, [10, 12], as a complementary reduction technique. An evaluation of our regression verification technique shows that our approach is capable of leveraging similarities between program versions to reduce the size of the queries and the time required to check for logical equivalence. The main contributions of this work are: - A regression verification technique to generate impact summaries that can be checked for functional equivalence using an off-the-shelf decision procedure. - A proof that our approach is sound and complete with respect to the depth bound of symbolic execution. - An implementation of our technique using the LLVMcompiler infrastructure, the klee Symbolic Virtual Machine [4], and a variety of Satisfiability Modulo Theory (SMT) solvers, e.g., STP [7] and Z3 [6]. - An empirical evaluation on a set of C artifacts which shows that the use of impact summaries can reduce the cost of regression verification.

Backes, John↗
NASA NTRS2019

IKOS: Sound Static Program Analysis

IKOS (Inference Kernel for Open Static Analyzers) is a static analyzer for C/C++ based on the theory of Abstract Interpretation. It can detect or prove the absence of runtime errors (e.g, buffer overflows, integer overflows, null pointer dereferences, etc.) in the source code. IKOS uses Abstract Interpretation techniques to compute an over-approximation of all the reachable states of the program, thus it cannot miss a bug. In this talk, I will give an overview of the tool, then show how to apply it to a large software. I will present ikos-view, a web interface to examine the analysis results. I will discuss about methods to improve the analysis, such as adding code annotations, modeling library functions, and avoiding specific code patterns.

Arthaud, Maxime↗
NASA NTRS1972

Optimization of thermal protection systems for the space shuttle vehicle. Volume 1: Final report

A study performed to continue development of computational techniques for the Space Shuttle Thermal Protection System is reported. The resulting computer code was used to perform some additional optimization studies on several TPS configurations. The program was developed in Fortran 4 for the CDC 6400, and it was converted to Fortran 5 to be used for the Univac 1108. The computational methodology is developed in modular fashion to facilitate changes and updating of the techniques and to allow overlaying the computer code to fit into approximately 131,000 octal words of core storage. The program logic involves subroutines which handle input and output of information between computer and user, thermodynamic stress, dynamic, and weight/estimate analyses of a variety of panel configurations. These include metallic, ablative, RSI (with and without an underlying phase change material), and a thermodynamic analysis only of carbon-carbon systems applied to the leading edge and flat cover panels. Two different thermodynamic analyses are used. The first is a two-dimensional, explicit precedure with variable time steps which is used to describe the behavior of metallic and carbon-carbon leading edges. The second is a one-dimensional implicity technique used to predict temperature in the charring ablator and the noncharring RSI. The latter analysis is performed simply by suppressing the chemical reactions and pyrolysis of the TPS material.

Source record↗
NASA NTRS1981

Survey of the supporting research and technology for the thermal protection of the Galileo Probe

The Galileo Probe, which is scheduled to be launched in 1985 and to enter the hydrogen-helium atmosphere of Jupiter up to 1,475 days later, presents thermal protection problems that are far more difficult than those experienced in previous planetary entry missions. The high entry speed of the Probe will cause forebody heating rates orders of magnitude greater than those encountered in the Apollo and Pioneer Venus missions, severe afterbody heating from base-flow radiation, and thermochemical ablation rates for carbon phenolic that rival the free-stream mass flux. This paper presents a comprehensive survey of the experimental work and computational research that provide technological support for the Probe's heat-shield design effort. The survey includes atmospheric modeling; both approximate and first-principle computations of flow fields and heat-shield material response; base heating; turbulence modelling; new computational techniques; experimental heating and materials studies; code validation efforts; and a set of 'consensus' first-principle flow-field solutions through the entry maneuver, with predictions of the corresponding thermal protection requirements.

Howe, J. T.↗
NASA NTRS2011

Fast Approximate Broadband Phase Retrieval for Segmented Systems

Broadband phase retrieval needed when: a) Narrow spectral filters are unavailable. b) Dim sources. c) Low throughput due to misalignment. d) Short exposures times. i.e., Pointing instability (space); and Atmospheric instability (ground based AO). Traditional approach is computationally burdensome for extreme bandwidths. Approximate approach: a) Substitute monochromatic model. b) Blur model and data. Test case performance: a) approx.270x reduction in computational cost for FGS-like test case. b) Good accuracy for monolithic system. c) Acceptable accuracy for segmented systems. i.e., Reduced by diffraction and Reduced by higher order segment model.

Jurling, Alden S.↗
NASA NTRS1972

The least squares process of MEDIA for computing DRVID calibration polynomials

A process is described and evaluated for computing a least squares polynomial approximation of data points in which the optimum degree of the polynomial is automatically determined. An iterative smoothing technique is used to replace every point with the value taken on by a moving least squares polynomial computed from a subset of points centered at the point to be replaced. The optimum degree of the resulting polynomial approximation is determined by analyzing the finite differences of each successive set of smoothed points. To evaluate the process, both artificially constructed data and actual Mariner Mars 1971 (MM'71) tracking data are used. This process was incorporated into a transmission media calibration computer program (MEDIA), which calibrates radiometric data to overcome the effects on the tracking signal of charged particle media. MEDIA was used in support of MM'71.

Leavitt, R. K.↗
NASA NTRSDate not supplied

A Multilevel Approach For SolvingLarge-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization

Quantum approximate optimization is one ofthe promising candidates for useful quantum computation,particularly in the context of finding approximate solutionsto Quadratic Unconstrained Binary Optimization (QUBO)problems. However, the existing quantum processing units(QPUs) are of relatively small size, and canonical mappingsof QUBO via the Ising model require one qubit per vari-able, rendering direct large-scale optimization infeasible.In classical optimization, a general strategy for addressingmany large-scale problems is via multilevel/multigrid meth-ods, where the large target problem is iteratively coarsenedand the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentallytest how existing QPUs perform when used as a sub-solverwithin such a multilevel strategy. To this aim, we com-bine and extend (via additional classical processing steps)the recently proposed Noise-Directed Adaptive Remapping(NDAR) and Quantum Relax&Round (QRR) algorithms.We first demonstrate the effectiveness of our heuristicextensions on Rigetti’s superconducting transmon deviceAnkaa-2. We find approximate solutions to10instances offully connected82-qubit Sherrington-Kirkpatrick graphswith random integer-valued coefficients obtaining normal-ized approximation ratios (ARs) in the range∼0.98−1.0,and the same class with real-valued coefficients (ARs∼0.94−1.0). Then, we implement the extended NDAR andQRR algorithms as subsolvers in the multilevel algorithmfor6large-scale graphs with at most∼27,000variables.In practice, the QPU (with classical post-processing steps)is used to find approximate solutions to dozens of at most82-qubit problems, which are iteratively used to constructthe global solution. We observe that quantum optimizationresults are competitive in terms of the quality of solutionswhen compared to classical heuristics used as subsolverswithin the multilevel approach.Reproducibility: source code and data are available at[TBA upon acceptance]

quantum computing↗
NASA NTRS1999

A Solar Radiation Parameterization for Atmospheric Studies

The solar radiation parameterization (CLIRAD-SW) developed at the Goddard Climate and Radiation Branch for application to atmospheric models are described. It includes the absorption by water vapor, O3, O2, CO2, clouds, and aerosols and the scattering by clouds, aerosols, and gases. Depending upon the nature of absorption, different approaches are applied to different absorbers. In the ultraviolet and visible regions, the spectrum is divided into 8 bands, and single O3 absorption coefficient and Rayleigh scattering coefficient are used for each band. In the infrared, the spectrum is divided into 3 bands, and the k-distribution method is applied for water vapor absorption. The flux reduction due to O2 is derived from a simple function, while the flux reduction due to CO2 is derived from precomputed tables. Cloud single-scattering properties are parameterized, separately for liquid drops and ice, as functions of water amount and effective particle size. A maximum-random approximation is adopted for the overlapping of clouds at different heights. Fluxes are computed using the Delta-Eddington approximation.

Chou, Ming-Dah↗
NASA NTRS2011

Fast Image Texture Classification Using Decision Trees

Texture analysis would permit improved autonomous, onboard science data interpretation for adaptive navigation, sampling, and downlink decisions. These analyses would assist with terrain analysis and instrument placement in both macroscopic and microscopic image data products. Unfortunately, most state-of-the-art texture analysis demands computationally expensive convolutions of filters involving many floating-point operations. This makes them infeasible for radiation- hardened computers and spaceflight hardware. A new method approximates traditional texture classification of each image pixel with a fast decision-tree classifier. The classifier uses image features derived from simple filtering operations involving integer arithmetic. The texture analysis method is therefore amenable to implementation on FPGA (field-programmable gate array) hardware. Image features based on the "integral image" transform produce descriptive and efficient texture descriptors. Training the decision tree on a set of training data yields a classification scheme that produces reasonable approximations of optimal "texton" analysis at a fraction of the computational cost. A decision-tree learning algorithm employing the traditional k-means criterion of inter-cluster variance is used to learn tree structure from training data. The result is an efficient and accurate summary of surface morphology in images. This work is an evolutionary advance that unites several previous algorithms (k-means clustering, integral images, decision trees) and applies them to a new problem domain (morphology analysis for autonomous science during remote exploration). Advantages include order-of-magnitude improvements in runtime, feasibility for FPGA hardware, and significant improvements in texture classification accuracy.

Thompson, David R.↗
NASA NTRS1989

Euler solvers for transonic applications

The 1980s may well be called the Euler era of applied aerodynamics. Computer codes based on discrete approximations of the Euler equations are now routinely used to obtain solutions of transonic flow problems in which the effects of entropy and vorticity production are significant. Such codes can even predict separation from a sharp edge, owing to the inclusion of artificial dissipation, intended to lend numerical stability to the calculation but at the same time enforcing the Kutta condition. One effect not correctly predictable by Euler codes is the separation from a smooth surface, and neither is viscous drag; for these some form of the Navier-Stokes equation is needed. It, therefore, comes as no surprise to observe that the Navier-Stokes has already begun before Euler solutions were fully exploited. Moreover, most numerical developments for the Euler equations are now constrained by the requirement that the techniques introduced, notably artificial dissipation, must not interfere with the new physics added when going from an Euler to a full Navier-Stokes approximation. In order to appreciate the contributions of Euler solvers to the understanding of transonic aerodynamics, it is useful to review the components of these computational tools. Space discretization, time- or pseudo-time marching and boundary procedures, the essential constituents are discussed. The subject of grid generation and grid adaptation to the solution are touched upon only where relevant. A list of unanswered questions and an outlook for the future are covered.

Vanleer, Bram↗
NASA NTRS2006

An Accuracy Evaluation of Unstructured Node-Centred Finite Volume Methods

Node-centred edge-based finite volume approximations are very common in computational fluid dynamics since they are assumed to run on structured, unstructured and even on mixed grids. We analyse the accuracy properties of both first and second derivative approximations and conclude that these schemes can not be used on arbitrary grids as is often assumed. For the Euler equations first-order accuracy can be obtained if care is taken when constructing the grid. For the Navier-Stokes equations, the grid restrictions are so severe that these finite volume schemes have little advantage over structured finite difference schemes. Our theoretical results are verified through extensive computations.

Svard, Magnus↗
NASA NTRS1980

A comparison of transport algorithms for premixed, laminar steady state flames

The effects of different methods of approximating multispecies transport phenomena in models of premixed, laminar, steady state flames were studied. Five approximation methods that span a wide range of computational complexity were developed. Identical data for individual species properties were used for each method. Each approximation method is employed in the numerical solution of a set of five H2-02-N2 flames. For each flame the computed species and temperature profiles, as well as the computed flame speeds, are found to be very nearly independent of the approximation method used. This does not indicate that transport phenomena are unimportant, but rather that the selection of the input values for the individual species transport properties is more important than the selection of the method used to approximate the multispecies transport. Based on these results, a sixth approximation method was developed that is computationally efficient and provides results extremely close to the most sophisticated and precise method used.

Coffee, T. P.↗
NASA NTRS1985

Numerical solutions of 3-dimensional Navier-Stokes equations for closed bluff-bodies

The Navier-Stokes equations are solved numerically. These equations are unsteady, compressible, viscous, and three-dimensional without neglecting any terms. The time dependency of the governing equations allows the solution to progress naturally for an arbitrary initial guess to an asymptotic steady state, if one exists. The equations are transformed from physical coordinates to the computational coordinates, allowing the solution of the governing equations in a rectangular parallelepiped domain. The equations are solved by the MacCormack time-split technique which is vectorized and programmed to run on the CDc VPS 32 computer. The codes are written in 32-bit (half word) FORTRAN, which provides an approximate factor of two decreasing in computational time and doubles the memory size compared to the 54-bit word size.

Abolhassani, J. S.↗
NASA NTRS1993

Asteroid orbit determination using Bayesian probabilities

Bayesian a priori and a posteriori probability densities are employed to determine asteroid orbital elements from optical astrometric observations. For near-earth asteroids and Jupiter Trojans, the two-body approximation can yield grossly erroneous uncertainty estimates because of the scattering effect of close planetary encounters or prolonged weak planetary perturbations. For main-belt asteroids, the two-body approximation works efficiently, from which it is inferred that, although the ephemeris must be computed from an integrated orbit, only approximate partial derivatives are needed to attain sufficient accuracy in predicting ephemeris uncertainties. The semimajor and semiminor axes of the 2D 1-sigma sky-plane uncertainty ellipse during the years 1993 to 2005 in the many-body and two-body linear approximations are shown.

Muinonen, Karri↗
NASA NTRS1989

Computers boost structural technology

Derived from matrix methods of structural analysis and finite element methods developed over the last three decades, computational structures technology (CST) blends computer science, numerical analysis, and approximation theory into structural analysis and synthesis. Recent significant advances in CST include stochastic-based modeling, strategies for performing large-scale structural calculations on new computing systems, and the integration of CST with other disciplinary modules for multidisciplinary analysis and design. New methodologies have been developed at NASA for integrated fluid-thermal structural analysis and integrated aerodynamic-structure-control design. The need for multiple views of data for different modules also led to the development of a number of sophisticated data-base management systems. For CST to play a role in the future development of structures technology and in the multidisciplinary design of future flight vehicles, major advances and computational tools are needed in a number of key areas.

Noor, Ahmed K.↗
NASA NTRS1984

Three-dimensional viscous flows with large secondary velocity

A new system of approximation equations is derived for three-dimensional steady viscous compressible flows in which a primary-flow direction is present, but in which both transverse velocity components can be large. Previous approaches which address simplification of the steady Navier-Stokes equations are discussed, and a new approach is proposed. The transverse velocity vector which corrects a given potential flow has been decomposed into potential and rotational components. It is found that the potential-velocity vector may be assumed small, whereas the rotational-velocity vector may be assumed small, whereas the rotational velocity vector and hence the composite secondary flow can be of order unity. This assumption leads to a system of governing equations whose characteristic polynomial has a non-elliptic form for arbitrary Mach numbers. The resulting non-elliptic approximation equations can be solved as an initial/boundary-value problem. Computed results confirm the small scalar-potential approximation.

Briley, W. R.↗
NASA NTRS1991

Ionosphere-exosphere coupling through charge exchange and momentum transfer in hydrogen-proton collisions

The implications of a traditional assumption of exospheric physics, that collisions of hydrogen atoms and protons preferentially result in charge exchange with negligible momentum transfer are examined. Initially adopted as a necessary convenience to accommodate limited computer resources in exosphere model calculations, this approximation results in a direct transformation of the proton velocity distribution into a hot component of neutral hydrogen. With expanding computational facilities, the need for the approximation has passed. As the first step toward its replacement with a realistic, quantum mechanical model of the H - H(+) collision process, differential and cumulative cross sections were calculated for quantum elastic scattering of indistinguishable nuclei for a fine grid of encounter energies and scattering angles. These data are used to study the nature of ionosphere-exosphere coupling through H - H(+) collisions, and to demonstrate that the distribution of velocities of scattered H produced in the traditional exospheric charge exchange approximation, as well as that arising from an alternative, fluid dynamic approach, leads to unacceptable abundances of coronal atoms in long-term, highly elliptic trajectories.

Hodges, R. R., Jr.↗