SEARCH · Search NASA

Results for “Processor scheduling”

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 73 records · Page 4

All sources NASA NTRS DOE OSTI

NASA NTRS1972

Job-mix modeling and system analysis of an aerospace multiprocessor.

An aerospace guidance computer organization, consisting of multiple processors and memory units attached to a central time-multiplexed data bus, is described. A job mix for this type of computer is obtained by analysis of Apollo mission programs. Multiprocessor performance is then analyzed using: 1) queuing theory, under certain 'limiting case' assumptions; 2) Markov process methods; and 3) system simulation. Results of the analyses indicate: 1) Markov process analysis is a useful and efficient predictor of simulation results; 2) efficient job execution is not seriously impaired even when the system is so overloaded that new jobs are inordinately delayed in starting; 3) job scheduling is significant in determining system performance; and 4) a system having many slow processors may or may not perform better than a system of equal power having few fast processors, but will not perform significantly worse.

Mallach, E. G.↗

NASA NTRS1990

Optimal parallel evaluation of AND trees

A quantitative analysis based on both preemptive and nonpreemptive critical-path scheduling algorithms is presently conducted for the optimal degree of parallelism required in evaluating a given AND tree. The optimal degree of parallelism is found to depend on problem complexity, precedence-graph shape, and task-time distribution along each path. In addition to demonstrating the optimality of the preemptive critical-path scheduling algorithm for evaluating an arbitrary AND tree on a fixed number of processors, the possibility of efficiently ascertaining tight bounds on the number of processors for optimal processor-time efficiency is illustrated.

Wah, Benjamin W.↗

NASA NTRS2004

Optimizing Mars Airplane Trajectory with the Application Navigation System

Planning complex missions requires a number of programs to be executed in concert. The Application Navigation System (ANS), developed in the NAS Division, can execute many interdependent programs in a distributed environment. We show that the ANS simplifies user effort and reduces time in optimization of the trajectory of a martian airplane. We use a software package, Cart3D, to evaluate trajectories and a shortest path algorithm to determine the optimal trajectory. ANS employs the GridScape to represent the dynamic state of the available computer resources. Then, ANS uses a scheduler to dynamically assign ready task to machine resources and the GridScape for tracking available resources and forecasting completion time of running tasks. We demonstrate system capability to schedule and run the trajectory optimization application with efficiency exceeding 60% on 64 processors.

Frumkin, Michael↗

NASA NTRS1993

A dataflow analysis tool for parallel processing of algorithms

A graph-theoretic design process and software tool is presented for selecting a multiprocessing scheduling solution for a class of computational problems. The problems of interest are those that can be described using a dataflow graph and are intended to be executed repetitively on a set of identical parallel processors. Typical applications include signal processing and control law problems. Graph analysis techniques are introduced and shown to effectively determine performance bounds, scheduling constraints, and resource requirements. The software tool is shown to facilitate the application of the design process to a given problem.

Jones, Robert L., III↗

NASA NTRS1986

Stanford Hardware Development Program

Architectures for high performance, digital signal processing, particularly for high resolution, wide band spectrum analysis were developed. These developments are intended to provide instrumentation for NASA's Search for Extraterrestrial Intelligence (SETI) program. The real time signal processing is both formal and experimental. The efficient organization and optimal scheduling of signal processing algorithms were investigated. The work is complemented by efforts in processor architecture design and implementation. A high resolution, multichannel spectrometer that incorporates special purpose microcoded signal processors is being tested. A general purpose signal processor for the data from the multichannel spectrometer was designed to function as the processing element in a highly concurrent machine. The processor performance required for the spectrometer is in the range of 1000 to 10,000 million instructions per second (MIPS). Multiple node processor configurations, where each node performs at 100 MIPS, are sought. The nodes are microprogrammable and are interconnected through a network with high bandwidth for neighboring nodes, and medium bandwidth for nodes at larger distance. The implementation of both the current mutlichannel spectrometer and the signal processor as Very Large Scale Integration CMOS chip sets was commenced.

Peterson, A.↗

NASA NTRS1986

EOS: A project to investigate the design and construction of real-time distributed embedded operating systems

The EOS project is investigating the design and construction of a family of real-time distributed embedded operating systems for reliable, distributed aerospace applications. Using the real-time programming techniques developed in co-operation with NASA in earlier research, the project staff is building a kernel for a multiple processor networked system. The first six months of the grant included a study of scheduling in an object-oriented system, the design philosophy of the kernel, and the architectural overview of the operating system. In this report, the operating system and kernel concepts are described. An environment for the experiments has been built and several of the key concepts of the system have been prototyped. The kernel and operating system is intended to support future experimental studies in multiprocessing, load-balancing, routing, software fault-tolerance, distributed data base design, and real-time processing.

Campbell, R. H.↗

NASA NTRS1993

Isomorphic routing on a toroidal mesh

We study a routing problem that arises on SIMD parallel architectures whose communication network forms a toroidal mesh. We assume there exists a set of k message descriptors (xi, yi), where (xi, yi) indicates that the ith message's recipient is offset from its sender by xi hops in one mesh dimension, and yi hops in the other. Every processor has k messages to send, and all processors use the same set of message routing descriptors. The SIMD constraint implies that at any routing step, every processor is actively routing messages with the same descriptors as any other processor. We call this isomorphic routing. Our objective is to find the isomorphic routing schedule with least makespan. We consider a number of variations on the problem, yielding complexity results from O(k) to NP-complete. Most of our results follow after we transform the problem into a scheduling problem, where it is related to other well-known scheduling problems.

Mao, Weizhen↗

NASA NTRS1987

Comparing the Performance of Two Dynamic Load Distribution Methods

Parallel processing of symbolic computations on a message-passing multi-processor presents one challenge: To effectively utilize the available processors, the load must be distributed uniformly to all the processors. However, the structure of these computations cannot be predicted in advance. go, static scheduling methods are not applicable. In this paper, we compare the performance of two dynamic, distributed load balancing methods with extensive simulation studies. The two schemes are: the Contracting Within a Neighborhood (CWN) scheme proposed by us, and the Gradient Model proposed by Lin and Keller. We conclude that although simpler, the CWN is significantly more effective at distributing the work than the Gradient model.

Kale, L. V.↗

NASA NTRS1995

Concept Designed and Developed for Distortion- Tolerant, High-Stability Engine Control

Engine Control Future aircraft turbine engines, both commercial and military, must be able to successfully accommodate expected increased levels of steady-state and dynamic engine-face distortion. Advanced tactical aircraft are likely to use thrust vectoring to enhance their maneuverability. As a result, the engines will see more extreme aircraft angles-of-attack and sideslip levels than are currently encountered with present-day aircraft. Also, the mixed-compression inlets needed for the High Speed Civil Transport will likely encounter disturbances similar to those seen by tactical aircraft, in addition to planar pulse, inlet buzz, and high distortion levels at low flight speed and off-design operation. The current approach of incorporating a sufficient component design stall margin to tolerate these increased levels of distortion would significantly reduce performance. The objective of the High Stability Engine Control (HISTEC) program is to design, develop, and flight demonstrate an advanced, high-stability, integrated engine-control system that uses measurement-based, real-time estimates of distortion to enhance engine stability. The resulting distortion-tolerant control reduces the required design stall margin, with a corresponding increase in performance and decrease in fuel burn. The HISTEC concept has been designed and developed, and the software implementing the concept has successfully accommodated time-varying distortion. The NASA Lewis Research Center is currently overseeing the development and validation of the hardware and software necessary to flight test the HISTEC concept. HISTEC is a contracted effort with Pratt & Whitney of West Palm Beach, Florida. The HISTEC approach includes two major systems: A Distortion Estimation System (DES) and Stability Management Control (SMC). DES is an aircraft-mounted, high-speed processor that estimates the amount and type of distortion present and its effect on the engine. It uses high-response pressure measurements at the engine face to calculate indicators of the type and extent of distortion in real time. From these indicators, DES determines the effects of distortion on the propulsion systems and the corresponding engine match point necessary to accommodate it. DES output consists of fan and compressor pressure ratio trim commands that are passed to the SMC. In addition, DES uses maneuver information, consisting of angle-of-attack and sideslip from the flight control, to anticipate high inlet distortion conditions. The SMC, which is contained in the engine-mounted, Improved Digital Electronic Engine Control (IDEEC), includes advanced control laws to directly control the fan and compressor transient operating line (pressure ratio). These advanced control laws, with a multivariable design, have the potential for higher bandwidth and the resulting more precise control of engine match. The ability to measure and assess the distortion effects in real time coupled with a high-response controller improves engine stability at high levels of distortion. The software algorithms implementing DES have been designed, developed, and demonstrated, and integration testing of the DES and SMC software has been completed. The results show that the HISTEC system will be able to sense inlet distortion, determine the effect on engine stability, and accommodate distortion by maintaining an adequate margin for engine surge. The Pratt &Whitney Comprehensive Engine Diagnostic Unit was chosen as the DES processor. An instrumented inlet case for sensing distortion was designed and fabricated. HISTEC is scheduled for flight test on the ACTIVE F-15 aircraft at the NASA Dryden Flight Research Center in Edwards, California, in late 1996.

Source record↗

NASA NTRS1990

A distributed agent architecture for real-time knowledge-based systems: Real-time expert systems project, phase 1

We propose a distributed agent architecture (DAA) that can support a variety of paradigms based on both traditional real-time computing and artificial intelligence. DAA consists of distributed agents that are classified into two categories: reactive and cognitive. Reactive agents can be implemented directly in Ada to meet hard real-time requirements and be deployed on on-board embedded processors. A traditional real-time computing methodology under consideration is the rate monotonic theory that can guarantee schedulability based on analytical methods. AI techniques under consideration for reactive agents are approximate or anytime reasoning that can be implemented using Bayesian belief networks as in Guardian. Cognitive agents are traditional expert systems that can be implemented in ART-Ada to meet soft real-time requirements. During the initial design of cognitive agents, it is critical to consider the migration path that would allow initial deployment on ground-based workstations with eventual deployment on on-board processors. ART-Ada technology enables this migration while Lisp-based technologies make it difficult if not impossible. In addition to reactive and cognitive agents, a meta-level agent would be needed to coordinate multiple agents and to provide meta-level control.

Lee, S. Daniel↗

NASA NTRS1995

Design tool for multiprocessor scheduling and evaluation of iterative dataflow algorithms

A graph-theoretic design process and software tool is defined for selecting a multiprocessing scheduling solution for a class of computational problems. The problems of interest are those that can be described with a dataflow graph and are intended to be executed repetitively on a set of identical processors. Typical applications include signal processing and control law problems. Graph-search algorithms and analysis techniques are introduced and shown to effectively determine performance bounds, scheduling constraints, and resource requirements. The software tool applies the design process to a given problem and includes performance optimization through the inclusion of additional precedence constraints among the schedulable tasks.

Jones, Robert L., III↗

NASA NTRS1973

Modification and updating of the Manned Activity Scheduling System (MASS) for shuttle and shuttle payloads analysis. Volume 1: Model specifications

The LRC MASS was modified and updated to include logic for efficient analysis of space shuttle payload operations. All MASS computer models were reviewed for compatibility with, and applicability to, the shuttle sortie mission. The MASS modification efforts were concentrated on two computer programs, the general scheduling model (GSM) and one day model (ODM). A new computer program, the DAYLIB Tape Processor, was developed to update the link between the GSM and ODM. The resulting MASS is an operationally efficient analytical tool that will allow a rapid assessment of shuttle and shuttle payload operations.

Ring, R. C.↗

NASA NTRS1984

Development and analysis of the Software Implemented Fault-Tolerance (SIFT) computer

SIFT (Software Implemented Fault Tolerance) is an experimental, fault-tolerant computer system designed to meet the extreme reliability requirements for safety-critical functions in advanced aircraft. Errors are masked by performing a majority voting operation over the results of identical computations, and faulty processors are removed from service by reassigning computations to the nonfaulty processors. This scheme has been implemented in a special architecture using a set of standard Bendix BDX930 processors, augmented by a special asynchronous-broadcast communication interface that provides direct, processor to processor communication among all processors. Fault isolation is accomplished in hardware; all other fault-tolerance functions, together with scheduling and synchronization are implemented exclusively by executive system software. The system reliability is predicted by a Markov model. Mathematical consistency of the system software with respect to the reliability model has been partially verified, using recently developed tools for machine-aided proof of program correctness.

Goldberg, J.↗

NASA NTRS1993

The application of multiple instruction retry to VLIW architectures using compiler generated hazard-free code

In this paper, we describe the development of compiler assisted multiple instruction word retry for VLIW architectures. Compiler generated hazard-free code with different degrees of rollback capability is compacted by a trace scheduling algorithm. Performances are compared under three parameters: N, the rollback distance for uni-processors; P, the number of functional units; and Np, the rollback distance for VLIW architectures. In the majority of benchmarks examined, for fixed P and Np, the larger N tends to generate compacted code with better performance.

Chen, Shyh-Kwei↗

NASA NTRS2013

Adoption of Test Driven Development and Continuous Integration for the Development of the Trick Simulation Toolkit

This paper describes the adoption of a Test Driven Development approach and a Continuous Integration System in the development of the Trick Simulation Toolkit, a generic simulation development environment for creating high fidelity training and engineering simulations at the NASA/Johnson Space Center and many other NASA facilities. It describes what was learned and the significant benefits seen, such as fast, thorough, and clear test feedback every time code is checked-in to the code repository. It also describes a system that encourages development of code that is much more flexible, maintainable, and reliable. The Trick Simulation Toolkit development environment provides a common architecture for user-defined simulations. Trick builds executable simulations using user-supplied simulation-definition files (S_define) and user supplied "model code". For each Trick-based simulation, Trick automatically provides job scheduling, checkpoint / restore, data-recording, interactive variable manipulation (variable server), and an input-processor. Also included are tools for plotting recorded data and various other supporting tools and libraries. Trick is written in C/C++ and Java and supports both Linux and MacOSX. Prior to adopting this new development approach, Trick testing consisted primarily of running a few large simulations, with the hope that their complexity and scale would exercise most of Trick's code and expose any recently introduced bugs. Unsurprising, this approach yielded inconsistent results. It was obvious that a more systematic, thorough approach was required. After seeing examples of some Java-based projects that used the JUnit test framework, similar test frameworks for C and C++ were sought. Several were found, all clearly inspired by JUnit. Googletest, a freely available Open source testing framework, was selected as the most appropriate and capable. The new approach was implemented while rewriting the Trick memory management component, to eliminate a fundamental design flaw. The benefits became obvious almost immediately, not just in the correctness of the individual functions and classes but also in the correctness and flexibility being added to the overall design. Creating code to be testable, and testing as it was created resulted not only in better working code, but also in better-organized, flexible, and readable (i.e., articulate) code. This was, in essence the Test-driven development (TDD) methodology created by Kent Beck. Seeing the benefits of Test Driven Development, other Trick components were refactored to make them more testable and tests were designed and implemented for them.

Penn, John M.↗

NASA NTRS1989

Efficient mapping algorithms for scheduling robot inverse dynamics computation on a multiprocessor system

Two efficient mapping algorithms for scheduling the robot inverse dynamics computation consisting of m computational modules with precedence relationship to be executed on a multiprocessor system consisting of p identical homogeneous processors with processor and communication costs to achieve minimum computation time are presented. An objective function is defined in terms of the sum of the processor finishing time and the interprocessor communication time. The minimax optimization is performed on the objective function to obtain the best mapping. This mapping problem can be formulated as a combination of the graph partitioning and the scheduling problems; both have been known to be NP-complete. Thus, to speed up the searching for a solution, two heuristic algorithms were proposed to obtain fast but suboptimal mapping solutions. The first algorithm utilizes the level and the communication intensity of the task modules to construct an ordered priority list of ready modules and the module assignment is performed by a weighted bipartite matching algorithm. For a near-optimal mapping solution, the problem can be solved by the heuristic algorithm with simulated annealing. These proposed optimization algorithms can solve various large-scale problems within a reasonable time. Computer simulations were performed to evaluate and verify the performance and the validity of the proposed mapping algorithms. Finally, experiments for computing the inverse dynamics of a six-jointed PUMA-like manipulator based on the Newton-Euler dynamic equations were implemented on an NCUBE/ten hypercube computer to verify the proposed mapping algorithms. Computer simulation and experimental results are compared and discussed.

Lee, C. S. G.↗

NASA NTRS1989

Run-time scheduling and execution of loops on message passing machines

Sparse system solvers and general purpose codes for solving partial differential equations are examples of the many types of problems whose irregularity can result in poor performance on distributed memory machines. Often, the data structures used in these problems are very flexible. Crucial details concerning loop dependences are encoded in these structures rather than being explicitly represented in the program. Good methods for parallelizing and partitioning these types of problems require assignment of computations in rather arbitrary ways. Naive implementations of programs on distributed memory machines requiring general loop partitions can be extremely inefficient. Instead, the scheduling mechanism needs to capture the data reference patterns of the loops in order to partition the problem. First, the indices assigned to each processor must be locally numbered. Next, it is necessary to precompute what information is needed by each processor at various points in the computation. The precomputed information is then used to generate an execution template designed to carry out the computation, communication, and partitioning of data, in an optimized manner. The design is presented for a general preprocessor and schedule executer, the structures of which do not vary, even though the details of the computation and of the type of information are problem dependent.

Crowley, Kay↗

NASA NTRS1990

Run-time scheduling and execution of loops on message passing machines

Saltz, Joel↗