SEARCH · Search NASA

Results for “Queues”

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 289 records · Page 16

All sources NASA NTRS DOE OSTI

NASA NTRS1989

Indirect addressing and load balancing for faster solution to Mandelbrot Set on SIMD architectures

SIMD computers with local indirect addressing allow programs to have queues and buffers, making certain kinds of problems much more efficient. Examined here are a class of problems characterized by computations on data points where the computation is identical, but the convergence rate is data dependent. Normally, in this situation, the algorithm time is governed by the maximum number of iterations required by each point. Using indirect addressing allows a processor to proceed to the next data point when it is done, reducing the overall number of iterations required to approach the mean convergence rate when a sufficiently large problem set is solved. Load balancing techniques can be applied for additional performance improvement. Simulations of this technique applied to solving Mandelbrot Sets indicate significant performance gains.

Tomboulian, Sherryl↗

NASA NTRS1988

A multiprocessor airborne lidar data system

A new multiprocessor data acquisition system was developed for the existing Airborne Oceanographic Lidar (AOL). This implementation simultaneously utilizes five single board 68010 microcomputers, the UNIX system V operating system, and the real time executive VRTX. The original data acquisition system was implemented on a Hewlett Packard HP 21-MX 16 bit minicomputer using a multi-tasking real time operating system and a mixture of assembly and FORTRAN languages. The present collection of data sources produce data at widely varied rates and require varied amounts of burdensome real time processing and formatting. It was decided to replace the aging HP 21-MX minicomputer with a multiprocessor system. A new and flexible recording format was devised and implemented to accommodate the constantly changing sensor configuration. A central feature of this data system is the minimization of non-remote sensing bus traffic. Therefore, it is highly desirable that each micro be capable of functioning as much as possible on-card or via private peripherals. The bus is used primarily for the transfer of remote sensing data to or from the buffer queue.

Wright, C. W.↗

NASA NTRS1989

Load sharing in distributed real-time systems with state-change broadcasts

A decentralized dynamic load-sharing (LS) method based on state-change broadcasts is proposed for a distributed real-time system. Whenever the state of a node changes from underloaded to fully loaded and vice versa, the node broadcasts this change to a set of nodes, called a buddy set, in the system. The performance of the method is evaluated with both analytic modeling and simulation. It is modeled first by an embedded Markov chain for which numerical solutions are derived. The model solutions are then used to calculate the distribution of queue lengths at the nodes and the probability of meeting task deadlines. The analytical results show that buddy sets of 10 nodes outperform those of less than 10 nodes, and the incremental benefit gained from increasing the buddy set size beyond 15 nodes is insignificant. These and other analytical results are verified by simulation. The proposed LS method is shown to meet task deadlines with a very high probability.

Shin, Kang G.↗

NASA NTRS1989

Extended observability of linear time-invariant systems under recurrent loss of output data

Recurrent loss of sensor data in integrated control systems of an advanced aircraft may occur under different operating conditions that include detected frame errors and queue saturation in computer networks, and bad data suppression in signal processing. This paper presents an extension of the concept of observability based on a set of randomly selected nonconsecutive outputs in finite-dimensional, linear, time-invariant systems. Conditions for testing extended observability have been established.

Luck, Rogelio↗

NASA NTRS1990

Serial Escape System For Aircraft Crews

Emergency escape system for aircraft and aerospace vehicles ejects up to seven crewmembers, one by one, within 120 s. Intended for emergencies in which disabled craft still in stable flight at no more than 220 kn (113 m/s) equivalent airspeed and sinking no faster than 110 ft/s (33.5 m/s) at altitudes up to 50,000 ft (15.2 km). Ejection rockets load themselves from magazine after each crewmember ejected. Jumpmaster queues other crewmembers and helps them position themselves on egress ramp. Rockets pull crewmembers clear of aircraft structure. Provides orderly, controlled exit and avoids ditching at sea or landing in rough terrain.

Wood, Kenneth E.↗

NASA NTRS1990

Extensibility and limitations of FDDI

Recently two standards for Metropolitan Area Networks (MANs), Fiber Distributed Data Interface (FDDI) and Distributed Queue Dual Bus (DQDB), have emerged as the primary competitors for the MAN arena. Great interest exists in building higher speed networks which support large numbers of node and greater distance, and it is not clear what types of protocols are needed for this type of environment. There is some question as to whether or not these MAN standards can be extended to such environments. The extensibility of FDDI to the Gbps range and a long distance environment is investigated. Specification parameters which affect performance are shown and a measure is provided for predicting utilization of FDDI. A comparison of FDDI at 100 Mbps and 1 Gbps is presented. Some specific problems with FDDI are addressed and modifications which improve the viability of FDDI in such high speed networks are investigated.

Game, David↗

NASA NTRS1990

Fairness problems at the media access level for high-speed networks

Most lower speed (approx. 10 Mbps) local area networks use adaptive or random access protocols like Ethernet. Others at higher speed use demand assignment like token or slotted rings. These include Cambridge ring and electronic token ring systems. Fairness issues in representatives of such protocols are discussed. In particular, Fiber Distributed Data Interface (FDDI) was selected as a demand access protocol using tokens, Carrier Sensed Multiple Access/Ring Network (CSMA/RN) a random access protocol, and Distributed Queue Dual Bus (DQDB) a demand access protocol using reservations. Fairness at the media access level was the focus, i.e., attaining access or being excessively delayed when a message is queued to be sent as a function of network location. Within that framework, the essential fairness of FDDI was observed along with severe fairness problems in DQDB and some problems for CSMA/RN. Several modifications were investigated and their ameliorative effect is shown. Finally, a unified presentation which allows comparisons of the three protocols' fairness when normalized to their capacity is given.

Maly, Kurt J.↗

NASA NTRS1989

Computer architecture evaluation for structural dynamics computations: Project summary

The intent of the proposed effort is the examination of the impact of the elements of parallel architectures on the performance realized in a parallel computation. To this end, three major projects are developed: a language for the expression of high level parallelism, a statistical technique for the synthesis of multicomputer interconnection networks based upon performance prediction, and a queueing model for the analysis of shared memory hierarchies.

Standley, Hilda M.↗

NASA NTRS1989

Analysis of random drop for gateway congestion control

Lately, the growing demand on the Internet has prompted the need for more effective congestion control policies. Currently No Gateway Policy is used to relieve and signal congestion, which leads to unfair service to the individual users and a degradation of overall network performance. Network simulation was used to illustrate the character of Internet congestion and its causes. A newly proposed gateway congestion control policy, called Random Drop, was considered as a promising solution to the pressing problem. Random Drop relieves resource congestion upon buffer overflow by choosing a random packet from the service queue to be dropped. The random choice should result in a drop distribution proportional to the bandwidth distribution among all contending TCP connections, thus applying the necessary fairness. Nonetheless, the simulation experiments demonstrate several shortcomings with this policy. Because Random Drop is a congestion control policy, which is not applied until congestion has already occurred, it usually results in a high drop rate that hurts too many connections including well-behaved ones. Even though the number of packets dropped is different from one connection to another depending on the buffer utilization upon overflow, the TCP recovery overhead is high enough to neutralize these differences, causing unfair congestion penalties. Besides, the drop distribution itself is an inaccurate representation of the average bandwidth distribution, missing much important information about the bandwidth utilization between buffer overflow events. A modification of Random Drop to do congestion avoidance by applying the policy early was also proposed. Early Random Drop has the advantage of avoiding the high drop rate of buffer overflow. The early application of the policy removes the pressure of congestion relief and allows more accurate signaling of congestion. To be used effectively, algorithms for the dynamic adjustment of the parameters of Early Random Drop to suite the current network load must still be developed.

Hashem, Emam Salaheddin↗

NASA NTRS1989

Modeling and analysis of multiprocessor architectures

Some technologies developed for system level modeling and analysis of algorithms/architectures using an architecture design and development system are reviewed. Modeling and analysis is described with attention given to modeling constraints and analysis using constrained software graphs. An example is presented of an ADAS graph and its associated attributes, such as firing delay, token consume rate, token produce rate, firing threshold, firing condition, arc queue lengths, associated C or Ada functional model, and stochastic behavior.

Yalamanchili, S.↗

NASA NTRS1990

Discrete event simulation tool for analysis of qualitative models of continuous processing systems

An artificial intelligence design and qualitative modeling tool is disclosed for creating computer models and simulating continuous activities, functions, and/or behavior using developed discrete event techniques. Conveniently, the tool is organized in four modules: library design module, model construction module, simulation module, and experimentation and analysis. The library design module supports the building of library knowledge including component classes and elements pertinent to a particular domain of continuous activities, functions, and behavior being modeled. The continuous behavior is defined discretely with respect to invocation statements, effect statements, and time delays. The functionality of the components is defined in terms of variable cluster instances, independent processes, and modes, further defined in terms of mode transition processes and mode dependent processes. Model construction utilizes the hierarchy of libraries and connects them with appropriate relations. The simulation executes a specialized initialization routine and executes events in a manner that includes selective inherency of characteristics through a time and event schema until the event queue in the simulator is emptied. The experimentation and analysis module supports analysis through the generation of appropriate log files and graphics developments and includes the ability of log file comparisons.

Malin, Jane T.↗

NASA NTRS1991

Dynamic resource allocation scheme for distributed heterogeneous computer systems

This invention relates to a resource allocation in computer systems, and more particularly, to a method and associated apparatus for shortening response time and improving efficiency of a heterogeneous distributed networked computer system by reallocating the jobs queued up for busy nodes to idle, or less-busy nodes. In accordance with the algorithm (SIDA for short), the load-sharing is initiated by the server device in a manner such that extra overhead in not imposed on the system during heavily-loaded conditions. The algorithm employed in the present invention uses a dual-mode, server-initiated approach. Jobs are transferred from heavily burdened nodes (i.e., over a high threshold limit) to low burdened nodes at the initiation of the receiving node when: (1) a job finishes at a node which is burdened below a pre-established threshold level, or (2) a node is idle for a period of time as established by a wakeup timer at the node. The invention uses a combination of the local queue length and the local service rate ratio at each node as the workload indicator.

Liu, Howard T.↗

NASA NTRS1991

Synthesizing a protocol converter from executable protocol traces

Communicating finite state machines (CFSM's) with FIFO (first in, first out) queues are used to model a protocol converter. A protocol conversion algorithm is developed and presented for the CSFM model of the protocols A and B. A converter H for protocols A = (A0, A1) and B = (B0, B1) is viewed as a black box such that H is between sender A0 and receiver B1. This gives a resulting protocol X = (A0, H, B1). The conversion algorithm requires a specification of the message relationships between the messages of protocols A and B. It is assumed that protocols A and B have the required progress properties. The algorithm includes a search for related messages from the two protocols in an FIFO from a composite space formed by a Cartesian cross-product of state spaces A1 and B0. The search produces finite-length traces which are combined to form a state machine H, which is examined for freedom from unspecified receptions, deadlocks, and livelocks. A protocol conversion example demonstrates the applicability of the algorithm.

Rajagopal, Murali↗

NASA NTRS1990

Evaluating scheduling algorithms for traffic with heterogeneous performance objectives

Two types of network traffic are considered: traffic with deadlines, for which the most important performance objective is based on loss rate, and packets without deadlines, for which the most important performance objective is based on mean delay. An optimal scheduling algorithm is presented to minimize weighted loss rate and weighted mean delay in the queues that form at the switches and at the network access points of a packet-switched network, where weights reflect the relative importance of packets. Although not practical for implementation, the algorithm is intended as a standard for the comparison of the performance of other scheduling algorithms. The algorithm is more general and lower computational complexity than previously published algorithms, enabling performance evaluation of some important scenarios that could not previously have been considered. Using the optimal performance results of this algorithm, the performance of the first-come-first-served, static priority, and earliest deadline first scheduling algorithms is evaluated. The results suggest that network efficiency could be improved by using a more sophisticated heuristic scheduling algorithm rather than one of the aforementioned algorithms.

Peha, Jon M.↗

NASA NTRS1991

Markov reward processes

Numerous applications in the area of computer system analysis can be effectively studied with Markov reward models. These models describe the behavior of the system with a continuous-time Markov chain, where a reward rate is associated with each state. In a reliability/availability model, upstates may have reward rate 1 and down states may have reward rate zero associated with them. In a queueing model, the number of jobs of certain type in a given state may be the reward rate attached to that state. In a combined model of performance and reliability, the reward rate of a state may be the computational capacity, or a related performance measure. Expected steady-state reward rate and expected instantaneous reward rate are clearly useful measures of the Markov reward model. More generally, the distribution of accumulated reward or time-averaged reward over a finite time interval may be determined from the solution of the Markov reward model. This information is of great practical significance in situations where the workload can be well characterized (deterministically, or by continuous functions e.g., distributions). The design process in the development of a computer system is an expensive and long term endeavor. For aerospace applications the reliability of the computer system is essential, as is the ability to complete critical workloads in a well defined real time interval. Consequently, effective modeling of such systems must take into account both performance and reliability. This fact motivates our use of Markov reward models to aid in the development and evaluation of fault tolerant computer systems.

Smith, R. M.↗

NASA NTRS1990

SEL Ada reuse analysis and representations

Overall, it was revealed that the pattern of Ada reuse has evolved from initial reuse of utility components into reuse of generalized application architectures. Utility components were both domain-independent utilities, such as queues and stacks, and domain-specific utilities, such as those that implement spacecraft orbit and attitude mathematical functions and physics or astronomical models. The level of reuse was significantly increased with the development of a generalized telemetry simulator architecture. The use of Ada generics significantly increased the level of verbatum reuse, which is due to the ability, using Ada generics, to parameterize the aspects of design that are configurable during reuse. A key factor in implementing generalized architectures was the ability to use generic subprogram parameters to tailor parts of the algorithm embedded within the architecture. The use of object oriented design (in which objects model real world entities) significantly improved the modularity for reuse. Encapsulating into packages the data and operations associated with common real world entities creates natural building blocks for reuse.

Kester, Rush↗

NASA NTRS1991

Solution to the indexing problem of frequency domain simulation experiments

A frequency domain simulation experiment is one in which selected system parameters are oscillated sinusoidally to induce oscillations in one or more system statistics of interest. A spectral (Fourier) analysis of these induced oscillations is then performed. To perform this spectral analysis, all oscillation frequencies must be referenced to a common, independent variable - an oscillation index. In a discrete-event simulation, the global simulation clock is the most natural choice for the oscillation index. However, past efforts to reference all frequencies to the simulation clock generally yielded unsatisfactory results. The reason for these unsatisfactory results is explained in this paper and a new methodology which uses the simulation clock as the oscillation index is presented. Techniques for implementing this new methodology are demonstrated by performing a frequency domain simulation experiment for a network of queues.

Mitra, Mousumi↗

NASA NTRS1992

A simple, effective media access protocol system for integrated, high data rate networks

The operation and performance of a dual media access protocol for integrated, gigabit networks are described. Unlike other dual protocols, each protocol supports a different class of traffic. The Carrier Sensed Multiple Access-Ring Network (CSMA/RN) protocol and the Circulating Reservation Packet (CRP) protocol support asynchronous and synchronous traffic, respectively. The two protocols operate with minimal impact upon each other. Performance information demonstrates that they support a complete range of integrated traffic loads, do not require call setup/termination or a special node for synchronous traffic control, and provide effective pre-use and recovery. The CRP also provides guaranteed access and fairness control for the asynchronous system. The paper demonstrates that the CSMA-CRP system fulfills many of the requirements for gigabit LAN-MAN networks most effectively and simply. To accomplish this, CSMA-CRP features are compared against similar ring and bus systems, such as Cambridge Fast Ring, Metaring, Cyclic Reservation Multiple Access, and Distributed Dual Queue Data Bus (DQDB).

Foudriat, E. C.↗