Search NASA⌕ Search

SEARCH · Search NASA

Results for “execution”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS1989

Coordinating the activities of a planner and an execution agent

A research program was defined that will explore the link between planning and execution systems. A simple scenario was defined in which a very capable off-line planning system interacts with the user and a smaller, less capable, on-line real-time system executing plans and reacting to faults. However, the on-line execution system may have a more flexible representation of the plans it is executing. This imbalance in the capabilities of the two agents involved should clarify some of the research objectives and give an experimental framework for the work. The task is to investigate the knowledge representations and communication protocols needed to link a user stating some requirements for a task to be carried out through a planning system to the (remote) execution agent that can carry out the user's wishes. The notion that a single representation can encapsulate the expression of the user's requirements, the capabilities for action, the communication to the execution agent, the successful or faulty response from the execution agent and the means of keeping the user informed, is examined. Methods of creating plan patches to update the plans separately held by each of the parties involved to keep them in step as they each react to changing circumstances in real-time is investigated. This involves the specification of plan patch attachment points that can be understood by the recipient. Transaction based methods are also investigated for coordinating the activities of the planner with those of the execution agent and user. The trial application area for the research is in the command and control of an advanced Earth Observation Space Platform.

Tate, Austin↗
NASA NTRS2003

Execution-Based Model Checking of Interrupt-Based Systems

Execution-based model checking (EMC) is a verification technique based on executing a multi-threaded/multiprocess program repeatedly in a systematic manner in order to explore the different interleavings of the program. This is in contrast to traditional model checking, where a model of a system is analyzed Several execution-based model-checking tools exist at this point, such as for example Verisoft and Java PathFinder. The most common formal specification languages used by EMC tools are un- timed, either just assertions, or linear-time temporal logic (LTL). An alternative verification technique is Runtime Execution Monitoring (REM), which is based on monitor- ing the execution of a program, checking that the execution trace conforms to a requirement specification. The Temporal Rover and DBRover are such tools. They provide a very rich specification language, being an extension of LTL with real-time constraints and time-series. We show how execution-based model checking, combined with runtime execution monitoring, can be used for the verification of a large class of safety critical systems commonly known as interrupt-based systems. The proposed approach is novel in that: (i) it supports model checking of a large class of applications not practically verifiable using conventional EMC tools, (ii) it supports verification of LTL assertions extended with real-time and time-series constraints, and (iii) it supports the verification of custom schedulers.

Drusinsky, Doron↗
NASA NTRS2003

Identifying Executable Plans

Generating plans for execution imposes a different set of requirements on the planning process than those imposed by planning alone. In highly unpredictable execution environments, a fully-grounded plan may become inconsistent frequently when the world fails to behave as expected. Intelligent execution permits making decisions when the most up-to-date information is available, ensuring fewer failures. Planning should acknowledge the capabilities of the execution system, both to ensure robust execution in the face of uncertainty, which also relieves the planner of the burden of making premature commitments. We present Plan Identification Functions (PIFs), which formalize what it means for a plan to be executable, md are used in conjunction with a complete model of system behavior to halt the planning process when an executable plan is found. We describe the implementation of plan identification functions for a temporal, constraint-based planner. This particular implementation allows the description of many different plan identification functions. characteristics crf the ~xec~~tieonfvii r~nm-enft,h e best plan to hand to the execution system will contain more or less commitment and information.

Bedrax-Weiss, Tania↗
NASA NTRS2009

A Survey of New Trends in Symbolic Execution for Software Testing and Analysis

Symbolic execution is a well-known program analysis technique which represents values of program inputs with symbolic values instead of concrete (initialized) data and executes the program by manipulating program expressions involving the symbolic values. Symbolic execution has been proposed over three decades ago but recently it has found renewed interest in the research community, due in part to the progress in decision procedures, availability of powerful computers and new algorithmic developments. We provide a survey of some of the new research trends in symbolic execution, with particular emphasis on applications to test generation and program analysis. We first describe an approach that handles complex programming constructs such as input data structures, arrays, as well as multi-threading. We follow with a discussion of abstraction techniques that can be used to limit the (possibly infinite) number of symbolic configurations that need to be analyzed for the symbolic execution of looping programs. Furthermore, we describe recent hybrid techniques that combine concrete and symbolic execution to overcome some of the inherent limitations of symbolic execution, such as handling native code or availability of decision procedures for the application domain. Finally, we give a short survey of interesting new applications, such as predictive testing, invariant inference, program repair, analysis of parallel numerical programs and differential symbolic execution.

Pasareanu, Corina S.↗
NASA NTRS2011

Directed Incremental Symbolic Execution

The last few years have seen a resurgence of interest in the use of symbolic execution -- a program analysis technique developed more than three decades ago to analyze program execution paths. Scaling symbolic execution and other path-sensitive analysis techniques to large systems remains challenging despite recent algorithmic and technological advances. An alternative to solving the problem of scalability is to reduce the scope of the analysis. One approach that is widely studied in the context of regression analysis is to analyze the differences between two related program versions. While such an approach is intuitive in theory, finding efficient and precise ways to identify program differences, and characterize their effects on how the program executes has proved challenging in practice. In this paper, we present Directed Incremental Symbolic Execution (DiSE), a novel technique for detecting and characterizing the effects of program changes. The novelty of DiSE is to combine the efficiencies of static analysis techniques to compute program difference information with the precision of symbolic execution to explore program execution paths and generate path conditions affected by the differences. DiSE is a complementary technique to other reduction or bounding techniques developed to improve symbolic execution. Furthermore, DiSE does not require analysis results to be carried forward as the software evolves -- only the source code for two related program versions is required. A case-study of our implementation of DiSE illustrates its effectiveness at detecting and characterizing the effects of program changes.

Person, Suzette↗
DOE OSTI2025

A cross-platform execution engine for the quantum intermediate representation

Hybrid languages like the quantum intermediate representation (QIR) are essential for programming systems that mix quantum and conventional computing models, while execution of these programs is often deferred to a system-specific implementation. Here, we develop the QIR Execution Engine (QIR-EE) for parsing, interpreting, and executing QIR across multiple hardware platforms. QIR-EE uses LLVM to execute hybrid instructions specifying quantum programs and, by design, presents extension points that support customized runtime and hardware environments. We demonstrate an implementation that uses the XACC quantum hardware-accelerator library to dispatch prototypical quantum programs on different commercial quantum platforms and numerical simulators, and we validate execution of QIR-EE on IonQ, Quantinuum, and IBM hardware. Our results highlight the efficiency of hybrid executable architectures for handling mixed instructions, managing mixed data, and integrating with quantum computing frameworks to realize cross-platform execution.

LLVM↗
NASA NTRS2006

A Discussion of the Discrete Fourier Transform Execution on a Typical Desktop PC

This paper will discuss and compare the execution times of three examples of the Discrete Fourier Transform (DFT). The first two examples will demonstrate the direct implementation of the algorithm. In the first example, the Fourier coefficients are generated at the execution of the DFT. In the second example, the coefficients are generated prior to execution and the DFT coefficients are indexed at execution. The last example will demonstrate the Cooley- Tukey algorithm, better known as the Fast Fourier Transform. All examples were written in C executed on a PC using a Pentium 4 running at 1.7 Ghz. As a function of N, the total complex data size, the direct implementation DFT executes, as expected at order of N2 and the FFT executes at order of N log2 N. At N=16K, there is an increase in processing time beyond what is expected. This is not caused by implementation but is a consequence of the effect that machine architecture and memory hierarchy has on implementation. This paper will include a brief overview of digital signal processing, along with a discussion of contemporary work with discrete Fourier processing.

White, Michael J.↗
NASA NTRS2012

Memoized Symbolic Execution

This paper introduces memoized symbolic execution (Memoise), a novel approach for more efficient application of forward symbolic execution, which is a well-studied technique for systematic exploration of program behaviors based on bounded execution paths. Our key insight is that application of symbolic execution often requires several successive runs of the technique on largely similar underlying problems, e.g., running it once to check a program to find a bug, fixing the bug, and running it again to check the modified program. Memoise introduces a trie-based data structure that stores the key elements of a run of symbolic execution. Maintenance of the trie during successive runs allows re-use of previously computed results of symbolic execution without the need for re-computing them as is traditionally done. Experiments using our prototype embodiment of Memoise show the benefits it holds in various standard scenarios of using symbolic execution, e.g., with iterative deepening of exploration depth, to perform regression analysis, or to enhance coverage.

Yang, Guowei↗
NASA NTRS2018

System and Method for Executing Operations Specified in a Procedure Language

A system for executing a procedure includes a procedure execution engine. The procedure execution engine is configured to translate a procedure defined via a procedure language to natural language statements corresponding to the operations specified by the procedure language. The procedure execution engine is also configured to generate a user interface for controlling execution of the procedure, and to display the natural language statements via the user interface. The procedure execution engine is further configured to indicate progress of execution of the procedure, via the user interface, based on the displayed natural language statements.

Kortenkamp, David Michael↗
NASA NTRS2022

Analyzing the Efficacy of Flexible Execution, Replanning, and Plan Optimization for a Planetary Lander

Plan execution in unknown environments poses a number of challenges: uncertainty in domain modeling, stochasticity at execution time, and the presence of exogenous events. These challenges motivate an integrated approach to planning and execution that is able to respond intelligently to variation. We examine this problem in the context of the Europa Lander mission concept, and evaluate a planning and execution framework that responds to feedback and task failure using two techniques: flexible execution and replanning with plan optimization. We develop a theoretical framework to estimate gains from these techniques, and we compare these predictions to empirical results generated in simulation. These results indicate that an integrated approach to planning and execution leveraging flexible execution, replanning, and utility maximization shows significant promise for future tightly-constrained space missions that must address significant uncertainty.

Chien, Steve↗
NASA NTRS2021

Analyzing the Efficacy of Flexible Execution, Replanning, and Plan Optimization for a Planetary Lander

Plan execution in unknown environments poses a number of challenges: uncertainty in domain modeling, stochasticity at execution time, and the presence of exogenous events. These challenges motivate an integrated approach to planning and execution that is able to respond intelligently to variation. We examine this problem in the context of the Europa Lander mission concept, and propose a planning and execution framework that responds to feedback and task failure using two techniques: flexible execution and replanning with plan optimization. We develop a theoretical framework to predict the value of each of these techniques, and we compare these predictions to empirical results generated in simulation. We demonstrate that an integrated approach to planning and execution that is grounded in flexible execution, replanning, and utility maximization will be an enabling technology for future tightly-constrained planetary surface missions.

Chien, Steve↗
NASA NTRS2022

Analyzing the Efficacy of Flexible Execution, Replanning, and Plan Optimization for a Planetary Lander

Plan execution in unknown environments poses a number of challenges: uncertainty in domain modeling, stochasticity at execution time, and the presence of exogenous events. These challenges motivate an integrated approach to planning and execution that is able to respond intelligently to variation. We examine this problem in the context of the Europa Lander mission concept, and propose a planning and execution framework that responds to feedback and task failure using two techniques: flexible execution and replanning with plan optimization. We develop a theoretical framework to predict the value of each of these techniques, and we compare these predictions to empirical results generated in simulation. We demonstrate that an integrated approach to planning and execution that is grounded in flexible execution, replanning, and utility maximization will be an enabling technology for future tightly-constrained planetary surface missions.

Basich, Connor↗
NASA NTRS1973

DIALOG: An executive computer program for linking independent programs

A very large scale computer programming procedure called the DIALOG Executive System has been developed for the Univac 1100 series computers. The executive computer program, DIALOG, controls the sequence of execution and data management function for a library of independent computer programs. Communication of common information is accomplished by DIALOG through a dynamically constructed and maintained data base of common information. The unique feature of the DIALOG Executive System is the manner in which computer programs are linked. Each program maintains its individual identity and as such is unaware of its contribution to the large scale program. This feature makes any computer program a candidate for use with the DIALOG Executive System. The installation and use of the DIALOG Executive System are described at Johnson Space Center.

Glatt, C. R.↗
NASA NTRS1995

The relation of scalability and execution time

Scalability has been used extensively as a de facto performance criterion for evaluating parallel algorithms and architectures. However, for many, scalability has theoretical interests only since it does not reveal execution time. In this paper, the relation between scalability and execution time is carefully studied. Results show that the isospeed scalability well characterizes the variation of execution time: smaller scalability leads to larger execution time, the same scalability leads to the same execution time, etc. Three algorithms from scientific computing are implemented on an Intel Paragon and an IBM SP2 parallel computer. Experimental and theoretical results show that scalability is an important, distinct metric for parallel and distributed systems, and may be as important as execution time in a scalable parallel and distributed environment.

Sun, Xian-He↗
NASA NTRS2002

Resource Selection Using Execution and Queue Wait Time Predictions

Computational grids provide users with many possible places to execute their applications. We wish to help users select where to run their applications by providing predictions of the execution times of applications on space shared parallel computers and predictions of when scheduling systems for such parallel computers will start applications. Our predictions are based on instance based learning techniques and simulations of scheduling algorithms. We find that our execution time prediction techniques have an average error of 37 percent of the execution times for trace data recorded from SGI Origins at NASA Ames Research Center and that this error is 67 percent lower than the error of user estimates. We also find that the error when predicting how long applications will wait in scheduling queues is 95 percent of mean queue wait times when using our execution time predictions and this is 57 percent lower than if we use user execution time estimates.

Warren, Smith↗
NASA NTRS2002

Resource Selection Using Execution and Queue Wait Time Predictions

Computational grids provide users with many possible places to execute their applications. We wish to help users select where to run their applications by providing predictions of the execution times of applications on space shared parallel computers and predictions of when scheduling systems for such parallel computers will start applications. Our predictions are based on instance based learning techniques and simulations of scheduling algorithms. We find that our execution time prediction techniques have an average error of 37 percent of the execution times for trace data recorded from SGI Origins at NASA Ames Research Center and that this error is 67 percent lower than the error of user estimates. We also find that the error when predicting how long applications will wait in scheduling queues is 95 percent of mean queue wait times when using our execution time predictions and this is 57 percent lower than if we use user execution time estimates.

Smith, Warren↗
NASA NTRS2011

Executable Architecture Research at Old Dominion University

Executable Architectures allow the evaluation of system architectures not only regarding their static, but also their dynamic behavior. However, the systems engineering community do not agree on a common formal specification of executable architectures. To close this gap and identify necessary elements of an executable architecture, a modeling language, and a modeling formalism is topic of ongoing PhD research. In addition, systems are generally defined and applied in an operational context to provide capabilities and enable missions. To maximize the benefits of executable architectures, a second PhD effort introduces the idea of creating an executable context in addition to the executable architecture. The results move the validation of architectures from the current information domain into the knowledge domain and improve the reliability of such validation efforts. The paper presents research and results of both doctoral research efforts and puts them into a common context of state-of-the-art of systems engineering methods supporting more agility.

Tolk, Andreas↗
NASA NTRS2014

Statistical Symbolic Execution with Informed Sampling

Symbolic execution techniques have been proposed recently for the probabilistic analysis of programs. These techniques seek to quantify the likelihood of reaching program events of interest, e.g., assert violations. They have many promising applications but have scalability issues due to high computational demand. To address this challenge, we propose a statistical symbolic execution technique that performs Monte Carlo sampling of the symbolic program paths and uses the obtained information for Bayesian estimation and hypothesis testing with respect to the probability of reaching the target events. To speed up the convergence of the statistical analysis, we propose Informed Sampling, an iterative symbolic execution that first explores the paths that have high statistical significance, prunes them from the state space and guides the execution towards less likely paths. The technique combines Bayesian estimation with a partial exact analysis for the pruned paths leading to provably improved convergence of the statistical analysis. We have implemented statistical symbolic execution with in- formed sampling in the Symbolic PathFinder tool. We show experimentally that the informed sampling obtains more precise results and converges faster than a purely statistical analysis and may also be more efficient than an exact symbolic analysis. When the latter does not terminate symbolic execution with informed sampling can give meaningful results under the same time and memory limits.

Reliability↗