SEARCH · Engineering Papers

Results for “lookahead”

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.

SourceResearch connectionFrom yearThrough year

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

At least 19 records

All sources NASA NTRS DOE OSTI

NASA NTRS1994

Checkpoint-based forward recovery using lookahead execution and rollback validation in parallel and distributed systems

This thesis studies a forward recovery strategy using checkpointing and optimistic execution in parallel and distributed systems. The approach uses replicated tasks executing on different processors for forwared recovery and checkpoint comparison for error detection. To reduce overall redundancy, this approach employs a lower static redundancy in the common error-free situation to detect error than the standard N Module Redundancy scheme (NMR) does to mask off errors. For the rare occurrence of an error, this approach uses some extra redundancy for recovery. To reduce the run-time recovery overhead, look-ahead processes are used to advance computation speculatively and a rollback process is used to produce a diagnosis for correct look-ahead processes without rollback of the whole system. Both analytical and experimental evaluation have shown that this strategy can provide a nearly error-free execution time even under faults with a lower average redundancy than NMR.

Long, Junsheng↗

NASA NTRS1988

Parallel discrete-event simulation of FCFS stochastic queueing networks

Physical systems are inherently parallel. Intuition suggests that simulations of these systems may be amenable to parallel execution. The parallel execution of a discrete-event simulation requires careful synchronization of processes in order to ensure the execution's correctness; this synchronization can degrade performance. Largely negative results were recently reported in a study which used a well-known synchronization method on queueing network simulations. Discussed here is a synchronization method (appointments), which has proven itself to be effective on simulations of FCFS queueing networks. The key concept behind appointments is the provision of lookahead. Lookahead is a prediction on a processor's future behavior, based on an analysis of the processor's simulation state. It is shown how lookahead can be computed for FCFS queueing network simulations, give performance data that demonstrates the method's effectiveness under moderate to heavy loads, and discuss performance tradeoffs between the quality of lookahead, and the cost of computing lookahead.

Nicol, David M.↗

NASA NTRS1997

Parallel Proximity Detection for Computer Simulation

The present invention discloses a system for performing proximity detection in computer simulations on parallel processing architectures utilizing a distribution list which includes movers and sensor coverages which check in and out of grids. Each mover maintains a list of sensors that detect the mover's motion as the mover and sensor coverages check in and out of the grids. Fuzzy grids are includes by fuzzy resolution parameters to allow movers and sensor coverages to check in and out of grids without computing exact grid crossings. The movers check in and out of grids while moving sensors periodically inform the grids of their coverage. In addition, a lookahead function is also included for providing a generalized capability without making any limiting assumptions about the particular application to which it is applied. The lookahead function is initiated so that risk-free synchronization strategies never roll back grid events. The lookahead function adds fixed delays as events are scheduled for objects on other nodes.

Steinman, Jeffrey S.↗

NASA NTRS1998

Parallel Proximity Detection for Computer Simulations

The present invention discloses a system for performing proximity detection in computer simulations on parallel processing architectures utilizing a distribution list which includes movers and sensor coverages which check in and out of grids. Each mover maintains a list of sensors that detect the mover's motion as the mover and sensor coverages check in and out of the grids. Fuzzy grids are included by fuzzy resolution parameters to allow movers and sensor coverages to check in and out of grids without computing exact grid crossings. The movers check in and out of grids while moving sensors periodically inform the grids of their coverage. In addition, a lookahead function is also included for providing a generalized capability without making any limiting assumptions about the particular application to which it is applied. The lookahead function is initiated so that risk-free synchronization strategies never roll back grid events. The lookahead function adds fixed delays as events are scheduled for objects on other nodes.

Steinman, Jeffrey S.↗

NASA NTRS1990

A conservative approach to parallelizing the Sharks World simulation

Parallelizing a benchmark problem for parallel simulation, the Sharks World, is described. The described solution is conservative, in the sense that no state information is saved, and no 'rollbacks' occur. The used approach illustrates both the principal advantage and principal disadvantage of conservative parallel simulation. The advantage is that by exploiting lookahead an approach was found that dramatically improves the serial execution time, and also achieves excellent speedups. The disadvantage is that if the model rules are changed in such a way that the lookahead is destroyed, it is difficult to modify the solution to accommodate the changes.

Nicol, David M.↗

NASA NTRS1990

A comparison of two fast binary adder configurations

Conditional sum and binary lookahead carry are two methods for performing fast binary addition. These methods are quite different, but the adders have a common feature that makes them interesting to compare. Both adders have the carry generating logic implemented as a binary tree, which grows in depth as log(sub 2) n,n equals the number of bits in the adder. The delay in the carry paths also grows in proportion to log(sub 2) n. This paper shows that the Transmission-Gate Conditional-Sum adder and the binary lookahead carry adder have the same speed of addition, but that the conditional sum adder requires only 46 percent of the area.

Canaris, J.↗

NASA NTRS2005

Learning for autonomous navigation : extrapolating from underfoot to the far field

Autonomous off-road navigation of robotic ground vehicles has important applications on Earth and in space exploration. Progress in this domain has been retarded by the limited lookahead range of 3-D sensors and by the difficulty of preprogramming systems to understand the traversability of the wide variety of terrain they can encounter. Enabling robots to learn from experience may alleviate both of these problems. We define two paradigms for this, learning from 3-D geometry and learning from proprioception, and describe initial instantiations of them we have developed under DARPA and NASA programs. Field test results show promise for learning traversability of vegetated terrain, learning to extend the lookahead range of the vision system, and learning how slip varies with slope.

autonomous robots↗

NASA NTRS2021

Using Intelligent Targeting to increase the science return of a Smart Ice Storm Hunting Radar

Smart Ice Cloud Sensing (SMICES) is a small-sat concept in which a radar intelligently targets ice storms based on information collected by a lookahead radiometer. Often space observations are performed by continuously collecting data from an instrument aimed at nadir (e.g. directly below the space platform). However, if the platform has the ability to assess science utility of features being overflown, an intelligent measurement scheme can improve science return. This can be achieved by controlling the on/off state of the instrument if it is not able to continuously operate (e.g. due to energy or thermal constraints), and by allowing the instrument to view off nadir if it has pointing capabilities.In the case of SMICES, power constraints and the rarity of storms means that with blind nadir targeting SMICES would collect a limited amount of ice storm radar data. The algorithms proposed acquire measurements to maximize acquired high interest storms while concurrently collecting a background sampling of all features. We use a cloud classification system to identify five different cloud types. Six algorithms ranging from “blind” to more selective are described and results from evaluation on a dataset of 13 ground swaths covering 72,399,600 km2 of data are presented. This data is from high quality science simulations that contain all five cloud types and multiple storms. When utilizing the radiometer’s lookahead and the full range of the radar the results show a 23.7x and 1.9x increase over the base algorithm in the most and second most important cloud types respectively.

Cooke, Caitlyn↗

NASA NTRS1978

FPLA mechanization of arithmetic elements to produce A + B or to pass A only

A 4-bit and a 3-bit adder are described which can be implemented under special hardware restrictions. The chip to be used is field-programmable logic array (FPLA) with 12 input lines, 50 AND gates inside, and output through only 6 OR gates. The context in which it is being used requires an enable function which can suppress one of the two numbers to be added. The 3-bit enabled adder is compatible with lookahead-carry mechanizations using the 74S182.

Wallis, D. E.↗

NASA NTRS1990

Performance bounds on parallel self-initiating discrete-event

The use is considered of massively parallel architectures to execute discrete-event simulations of what is termed self-initiating models. A logical process in a self-initiating model schedules its own state re-evaluation times, independently of any other logical process, and sends its new state to other logical processes following the re-evaluation. The interest is in the effects of that communication on synchronization. The performance is considered of various synchronization protocols by deriving upper and lower bounds on optimal performance, upper bounds on Time Warp's performance, and lower bounds on the performance of a new conservative protocol. The analysis of Time Warp includes the overhead costs of state-saving and rollback. The analysis points out sufficient conditions for the conservative protocol to outperform Time Warp. The analysis also quantifies the sensitivity of performance to message fan-out, lookahead ability, and the probability distributions underlying the simulation.

Nicol, David M.↗

NASA NTRS1990

The cost of conservative synchronization in parallel discrete event simulations

The performance of a synchronous conservative parallel discrete-event simulation protocol is analyzed. The class of simulation models considered is oriented around a physical domain and possesses a limited ability to predict future behavior. A stochastic model is used to show that as the volume of simulation activity in the model increases relative to a fixed architecture, the complexity of the average per-event overhead due to synchronization, event list manipulation, lookahead calculations, and processor idle time approach the complexity of the average per-event overhead of a serial simulation. The method is therefore within a constant factor of optimal. The analysis demonstrates that on large problems--those for which parallel processing is ideally suited--there is often enough parallel workload so that processors are not usually idle. The viability of the method is also demonstrated empirically, showing how good performance is achieved on large problems using a thirty-two node Intel iPSC/2 distributed memory multiprocessor.

Nicol, David M.↗

NASA NTRS1990

Conservative parallel simulation of priority class queueing networks

A conservative synchronization protocol is described for the parallel simulation of queueing networks having C job priority classes, where a job's class is fixed. This problem has long vexed designers of conservative synchronization protocols because of its seemingly poor ability to compute lookahead: the time of the next departure. For, a job in service having low priority can be preempted at any time by an arrival having higher priority and an arbitrarily small service time. The solution is to skew the event generation activity so that the events for higher priority jobs are generated farther ahead in simulated time than lower priority jobs. Thus, when a lower priority job enters service for the first time, all the higher priority jobs that may preempt it are already known and the job's departure time can be exactly predicted. Finally, the protocol was analyzed and it was demonstrated that good performance can be expected on the simulation of large queueing networks.

Nicol, David M.↗

NASA NTRS1992

Conservative parallel simulation of priority class queueing networks

Nicol, David↗

NASA NTRS1992

Scheduling and rescheduling with iterative repair

This paper describes the GERRY scheduling and rescheduling system being applied to coordinate Space Shuttle Ground Processing. The system uses constraint-based iterative repair, a technique that starts with a complete but possibly flawed schedule and iteratively improves it by using constraint knowledge within repair heuristics. In this paper we explore the tradeoff between the informedness and the computational cost of several repair heuristics. We show empirically that some knowledge can greatly improve the convergence speed of a repair-based system, but that too much knowledge, such as the knowledge embodied within the MIN-CONFLICTS lookahead heuristic, can overwhelm a system and result in degraded performance.

Zweben, Monte↗

NASA NTRS1991

Implementing forward recovery using checkpointing in distributed systems

The paper describes the implementation of a forward recovery scheme using checkpoints and replicated tasks. The implementation is based on the concept of lookahead execution and rollback validation. In the experiment, two tasks are selected for the normal execution and one for rollback validation. It is shown that the recovery strategy has nearly error-free execution time and an average redundancy lower than TMR.

Long, Junsheng↗

NASA NTRS1996

ORION Low Cost Laser Analysis

We show that laser-target interaction physics demands the shortest laser pulse of which hardware is capable (but not less than 100 ps) in the ORION ground-based laser concept. We compare two leading ways to achieve such pulses - SRS/SBS cascade compression and grating compression - with the standard MOPA approach, and conclude that the first of these is most robust. However, the state of the art in laser devices will require a year or two to implement these ideas. We present a pulse format and beam footprint protocol which will solve the conflict between relativistic lookahead and beam tilt and should permit all-laser active acquisition and tracking in ORION.

Phipps, Claude R.↗

NASA NTRS1996

Intelligent Planning and Scheduling for Controlled Life Support Systems

Planning in Controlled Ecological Life Support Systems (CELSS) requires special look ahead capabilities due to the complex and long-term dynamic behavior of biological systems. This project characterizes the behavior of CELSS, identifies the requirements of intelligent planning systems for CELSS, proposes the decomposition of the planning task into short-term and long-term planning, and studies the crop scheduling problem as an initial approach to long-term planning. CELSS is studied in the realm of Chaos. The amount of biomass in the system is modeled using a bounded quadratic iterator. The results suggests that closed ecological systems can exhibit periodic behavior when imposed external or artificial control. The main characteristics of CELSS from the planning and scheduling perspective are discussed and requirements for planning systems are given. Crop scheduling problem is identified as an important component of the required long-term lookahead capabilities of a CELSS planner. The main characteristics of crop scheduling are described and a model is proposed to represent the problem. A surrogate measure of the probability of survival is developed. The measure reflects the absolute deviation of the vital reservoir levels from their nominal values. The solution space is generated using a probability distribution which captures both knowledge about the system and the current state of affairs at each decision epoch. This probability distribution is used in the context of an evolution paradigm. The concepts developed serve as the basis for the development of a simple crop scheduling tool which is used to demonstrate its usefulness in the design and operation of CELSS.

Leon, V. Jorge↗

NASA NTRS2005

Learning for autonomous navigation

robotics↗