Search NASA⌕ Search

Engineering topics

Shin, K. G.

Publications and source records attributed to Shin, K. G..

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1986

On scheduling tasks with a quick recovery from failure

Multiprocessors used in life-critical real-time systems must recover quickly from failure. Part of this recovery consists of switching to a new task schedule which ensures that hard deadlines for critical tasks continue to be met. A dynamic programming algorithm is presented that ensures that backup, or contingency, schedules can be efficiently embedded within the original, 'primary' schedule to ensure that hard deadlines continue to be met in the face of up to a given maximum number of processor failures. Several illustrative examples are included.

Krishna, C. M.↗
NASA NTRS1986

Measurement and application of fault latency

The time interval between the occurrence of a fault and the detection of the error caused by the fault is divided by the generation of that error into two parts: fault latency and error latency. Since the moment of error generation is not directly observable, all related works in the literature have dealt with only the sum of fault and error latencies, thereby making the analysis of their separate effects impossible. To remedy this deficiency, (1) a new methodology for indirectly measuring fault latency is presented; the distribution of fault latency is derived from the methodology; and (3) the knowledge of fault latency is applied to the analysis of two important examples. The proposed methodology has been implemented for measuring fault latency in the Fault-Tolerant Multiprocessor (FTMP) at the NASA Airlab. The experimental results show wide variations in the mean fault latencies of different function circuits within FTMP. Also, the measured distributions of fault latency are shown to have monotone hazard rates. Consequently, Gamma and Weibull distributions are selected for the least-squares fit as the distribution of fault latency.

Shin, K. G.↗
NASA NTRS1985

Integrated analysis of error detection and recovery

An integrated modeling and analysis of error detection and recovery is presented. When fault latency and/or error latency exist, the system may suffer from multiple faults or error propagations which seriously deteriorate the fault-tolerant capability. Several detection models that enable analysis of the effect of detection mechanisms on the subsequent error handling operations and the overall system reliability were developed. Following detection of the faulty unit and reconfiguration of the system, the contaminated processes or tasks have to be recovered. The strategies of error recovery employed depend on the detection mechanisms and the available redundancy. Several recovery methods including the rollback recovery are considered. The recovery overhead is evaluated as an index of the capabilities of the detection and reconfiguration mechanisms.

Shin, K. G.↗
NASA NTRS1985

Modeling and measurement of fault-tolerant multiprocessors

The workload effects on computer performance are addressed first for a highly reliable unibus multiprocessor used in real-time control. As an approach to studing these effects, a modified Stochastic Petri Net (SPN) is used to describe the synchronous operation of the multiprocessor system. From this model the vital components affecting performance can be determined. However, because of the complexity in solving the modified SPN, a simpler model, i.e., a closed priority queuing network, is constructed that represents the same critical aspects. The use of this model for a specific application requires the partitioning of the workload into job classes. It is shown that the steady state solution of the queuing model directly produces useful results. The use of this model in evaluating an existing system, the Fault Tolerant Multiprocessor (FTMP) at the NASA AIRLAB, is outlined with some experimental results. Also addressed is the technique of measuring fault latency, an important microscopic system parameter. Most related works have assumed no or a negligible fault latency and then performed approximate analyses. To eliminate this deficiency, a new methodology for indirectly measuring fault latency is presented.

Shin, K. G.↗
NASA NTRS1985

Ensuring fault tolerance of phase-locked clocks

Processors within a real-time multiprocessor system must be synchronized with as little overhead as possible. Although synchronization can be achieved via both software (e.g., interactive convergence and interactive consistency algorithms) and hardware (e.g., multistage synchronizers and phase-locked clocks), phase-locked clocks are most attractive due to their small overheads. Despite the fact that synchronization of the multiprocessor system with phase-locked clocks is totally different in nature from the interactive consistency algorithm, it is presently proven that it must satisfy the same condition, N equal to or greater than 3m + 1, where N is the total number of clocks in the multiprocessor system and m is the maximum number of faults tolerable. Also presented are results showing how to design phase-locked clocks so as to be impervious up to a given arbitrary number of malicious failures.

Krishna, C. M.↗
NASA NTRS1985

A unified method for evaluating real-time computer controllers and its application

A real time control system consists of a synergistic pair, that is, a controlled process and a controller computer. Performance measures for real time controller computers are defined on the basis of the nature of this synergistic pair. A case study of a typical critical controlled process is presented in the context of new performance measures that express the performance of both controlled processes and real time controllers (taken as a unit) on the basis of a single variable: controller response time. Controller response time is a function of current system state, system failure rate, electrical and/or magnetic interference, etc., and is therefore a random variable. Control overhead is expressed as a monotonically nondecreasing function of the response time and the system suffers catastrophic failure, or dynamic failure, if the response time for a control task exceeds the corresponding system hard deadline, if any. A rigorous probabilistic approach is used to estimate the performance measures. The controlled process chosen for study is an aircraft in the final stages of descent, just prior to landing. First, the performance measures for the controller are presented. Secondly, control algorithms for solving the landing problem are discussed and finally the impact of the performance measures on the problem is analyzed.

Shin, K. G.↗
NASA NTRS1984

Evaluation of error recovery blocks used for cooperating processes

It is pointed out that the increasing computation power and rapidly falling cost of microprocessors and memories have given an impetus to the development of distributed computing systems. There are a number of potential benefits. A number of issues have to be resolved, however, before the full potential of a distributed processing system can be realized. The present investigation is concerned with one such issue, taking into account the effectiveness of implementing recovery blocks (RB's) in backward error recovery for a set of cooperating processes. A quantitative evaluation of three different recovery blocks employed in backward error recovery for concurrent processing is performed.

Shin, K. G.↗
NASA NTRS1984

Characterization of real-time computers

A real-time system consists of a computer controller and controlled processes. Despite the synergistic relationship between these two components, they have been traditionally designed and analyzed independently of and separately from each other; namely, computer controllers by computer scientists/engineers and controlled processes by control scientists. As a remedy for this problem, in this report real-time computers are characterized by performance measures based on computer controller response time that are: (1) congruent to the real-time applications, (2) able to offer an objective comparison of rival computer systems, and (3) experimentally measurable/determinable. These measures, unlike others, provide the real-time computer controller with a natural link to controlled processes. In order to demonstrate their utility and power, these measures are first determined for example controlled processes on the basis of control performance functionals. They are then used for two important real-time multiprocessor design applications - the number-power tradeoff and fault-masking and synchronization.

Shin, K. G.↗
NASA NTRS1984

Error detection process - Model, design, and its impact on computer performance

An analytical model is developed for computer error detection processes and applied to estimate their influence on system performance. Faults in the hardware, not in the design, are assumed to be the potential cause of transition to erroneous states during normal operations. The classification properties and associated recovery methods of error detection are discussed. The probability of obtaining an unreliable result is evaluated, along with the resulting computational loss. Error detection during design is considered and a feasible design space is outlined. Extension of the methods to account for the effects of extant multiple faults is indicated.

Shin, K. G.↗
NASA NTRS1984

Design and evaluation of a fault-tolerant multiprocessor using hardware recovery blocks

Attention is given to the design and evaluation of a fault-tolerant multiprocessor whose rollback recovery mechanism is based on hardware recovery blocks constructed by consecutive state-save operations and several state-save units in every processor and memory module. Upon detection of failure, the multiprocessor reconfigures itself to replace the faulty module and the process originally assigned to the faulty module retreats to one of the previously saved states, in order to resume fault-free execution. A mathematical model is proposed for the calculation of multistep rollback recovery coverage and the risk of restart when all available saved states are exhausted. The mean and the variance of task execution time with the occurrence of rollbacks and/or restarts are evaluated.

Lee, Y.-H.↗
NASA NTRS1983

Synchronization and fault-masking in redundant real-time systems

A real time computer may fail because of massive component failures or not responding quickly enough to satisfy real time requirements. An increase in redundancy - a conventional means of improving reliability - can improve the former but can - in some cases - degrade the latter considerably due to the overhead associated with redundancy management, namely the time delay resulting from synchronization and voting/interactive consistency techniques. The implications of synchronization and voting/interactive consistency algorithms in N-modular clusters on reliability are considered. All these studies were carried out in the context of real time applications. As a demonstrative example, we have analyzed results from experiments conducted at the NASA Airlab on the Software Implemented Fault Tolerance (SIFT) computer. This analysis has indeed indicated that in most real time applications, it is better to employ hardware synchronization instead of software synchronization and not allow reconfiguration.

Krishna, C. M.↗
NASA NTRS1983

Optimal design and use of retry in fault tolerant real-time computer systems

A new method to determin an optimal retry policy and for use in retry of fault characterization is presented. An optimal retry policy for a given fault characteristic, which determines the maximum allowable retry durations to minimize the total task completion time was derived. The combined fault characterization and retry decision, in which the characteristics of fault are estimated simultaneously with the determination of the optimal retry policy were carried out. Two solution approaches were developed, one based on the point estimation and the other on the Bayes sequential decision. The maximum likelihood estimators are used for the first approach, and the backward induction for testing hypotheses in the second approach. Numerical examples in which all the durations associated with faults have monotone hazard functions, e.g., exponential, Weibull and gamma distributions are presented. These are standard distributions commonly used for modeling analysis and faults.

Lee, Y. H.↗
NASA NTRS1983

Queueing analysis of a canonical model of real-time multiprocessors

A logical classification of multiprocessor structures from the point of view of control applications is presented. A computation of the response time distribution for a canonical model of a real time multiprocessor is presented. The multiprocessor is approximated by a blocking model. Two separate models are derived: one created from the system's point of view, and the other from the point of view of an incoming task.

Krishna, C. M.↗
NASA NTRS1982

Design and evaluation of a fault-tolerant multiprocessor using hardware recovery blocks

A fault-tolerant multiprocessor with a rollback recovery mechanism is discussed. The rollback mechanism is based on the hardware recovery block which is a hardware equivalent to the software recovery block. The hardware recovery block is constructed by consecutive state-save operations and several state-save units in every processor and memory module. When a fault is detected, the multiprocessor reconfigures itself to replace the faulty component and then the process originally assigned to the faulty component retreats to one of the previously saved states in order to resume fault-free execution. A mathematical model is proposed to calculate both the coverage of multi-step rollback recovery and the risk of restart. A performance evaluation in terms of task execution time is also presented.

Lee, Y. H.↗
NASA NTRS1982

Performance measures for multiprocessor controllers

Performance measures to characterize fault tolerant multiprocessors used in the control of critical processes are considered. Our performance indices are based on controller response time. By relating this to the needs of the application, we have been able to derive indices that faithfully reflect the performance of the multiprocessor in the context of the application, that permit the objective comparison of rival computer systems, and that can either be definitively estimated or objectively measured. An example of a controller in an idealized satellite application is provided.

Krishna, C. M.↗
NASA NTRS1982

Analysis of backward error recovery for concurrent processes with recovery blocks

Three different methods of implementing recovery blocks (RB's). These are the asynchronous, synchronous, and the pseudo recovery point implementations. Pseudo recovery points so that unbounded rollback may be avoided while maintaining process autonomy are proposed. Probabilistic models for analyzing these three methods under standard assumptions in computer performance analysis, i.e., exponential distributions for related random variables were developed. The interval between two successive recovery lines for asynchronous RB's mean loss in computation power for the synchronized method, and additional overhead and rollback distance in case PRP's are used were estimated.

Shin, K. G.↗