Optimal testing-policies for intermittent faults

Periodic tests for intermittent faults are scheduled at times kT (k=1, 2, . . .). The mean number of tests and the mean time to detect faults are derived. Optimal testing times to minimize the mean cost and to maximize the probabilities of detecting the first fault are discussed. Both perfect and imperfect test models are discussed     

Performance evaluation of a reconfiguration-algorithm for memoryarrays containing clustered faults

Reconfiguration of memory arrays using spare rows and columns is useful for yield-enhancement of memories. This paper presents a reconfiguration algorithm (QRCF) for memories that contain clustered faults. QRCF operates in a branch and bound fashion similar to known optimal algorithms that require exponential time. However, QRCF repairs faults in clusters rather than individually. Since many faults are repaired simultaneously, the execution-time of QRCF does not become prohibitive even for large memories containing many faults. The performance of QRCF is evaluated under a probabilistic model for clustered faults in a memory array. For a special case of the fault model, QRCF solves the reconfiguration problem exactly in polynomial time. In the general case, QRCF produces an optimal solution with high probability. The algorithm is also evaluated through simulation. The performance and execution-time of QRCF on arrays containing clustered faults are compared with other approximation algorithms and with an optimal algorithm. The simulation results show that QRCF outperforms previous approximation algorithms by a wide margin and performs nearly as well as the optimal algorithm with an execution-time that is orders of magnitude less     

Test for detection and location of intermittent faults incombinational circuits

Faults in combinational circuits are either permanent or intermittent. Intermittent faults tend to be environment-dependent; hence altering the environment might rectify these faults. These faults can be detected by applying random input-vectors (IV). The existence of random intermittent faults might require applying more random IV before detection. The detection of permanent faults requires fewer random IV but correction demands location and replacement of the faulty device, if repair is not feasible. Thus correction of a permanent fault costs more than that of an intermittent fault. The correction cost can be reduced by detecting the type of fault. Since most operational failures in a circuit are due to intermittent faults, it is very important to detect the type of fault in order to find a cheaper solution. This paper discusses the behavior of permanent and intermittent faults in combinational circuits, and introduces a test-detection model (TDM) for these faults. The error latency for an intermittent fault is derived. Two test-strategies are intermixed in the model: random testing for fault-detection, and deterministic testing for deciding on the type of fault. The activity of intermittent faults that requires the minimum number of IV for detection is emphasized. Simulation is used to demonstrate the validity of TDM. Although the variables required in TDM can be difficult to evaluate, estimation of their values is not impossible. A worst-case analysis can always be adopted, where variables are easily evaluated, to find an upper bound on the error latency; thus detection of an intermittent fault is assured with a very high probability. The cost-saving offered by intermittent-fault corrections shows the practical aspect of TDM     

Optimal release policy for hyper-geometric distributionsoftware-reliability growth model

The hyper-geometric distribution software-reliability growth model (HGDM) can estimate the number of initial faults in a software program. An important problem in software development is to determine when to stop testing and then release the software. This paper mainly investigates the optimal software release policies which minimize the mean total software cost and satisfy the software-reliability requirement based on the HGDM. The optimal software release times are determined and shown to be finite. A numerical example illustrates these optimal software release policies     

Optimal fault margin in a computer system

This paper suggests a stochastic model how to determine a fault margin in a computer system, who fails when the total number of hidden faults exceeds a threshold level N of tolerance: A fault occurs at a non-homogeneous Poisson process, and (i) becomes system failure with probability p₁, (ii) becomes hidden fault with probability p₂ and is accumulated, or (iii) is removed with probability p₃. The expected cost rate to system failure is derived, and an optimal number N^* to minimize it is discussed. A numerical example is finally given.     

An integrated routing and admission control mechanism for real‐time multicast connection establishment

There are two major difficulties in real‐time multicast connection setup. One is the design of an efficient distributed routing algorithm which optimizes the network cost of routing trees under the real‐time constraints. The other is the integration of routing with admission control into one single phase of operations. This paper presents a real‐time multicast connection setup mechanism, which integrates multicast routing with real‐time admission control. The proposed mechanism performs the real‐time admission tests on a cost optimal tree (COT) and a shortest path tree (SPT) in parallel, aiming at optimizing network cost of the routing tree under real‐time constraints. It has the following important features: (1) it is fully distributed; (2) it achieves sub‐optimal network cost of routing trees; (3) it takes less time and less network messages for a connection setup. Copyright © 2001 John Wiley & Sons, Ltd.     

测试不可靠条件下基于量子进化算法的测试优化选择

测试优化选择是复杂电子系统测试性设计中的一个重要问题.首先从测试容差的角度分析了测试发生漏检和虚警的原因,在此基础上建立了测试不可靠条件下一种新的测试选择模型,模型以测试代价、漏检代价和虚警代价之和最小为优化目标,以故障检测率和故障隔离率为约束条件;然后提出一种改进的量子进化算法对模型求解,该算法通过改进一种已有可靠测试选择算法而成,包括种群初始化、适应度计算和种群的进化策略.最后通过两个仿真实例验证了求解算法及模型的有效性和优越性.     

Seek Control to Suppress Vibrations of Hard Disk Drives Using Adaptive Filtering

A method to generate an optimal seek trajectory for a hard disk drive using an adaptive filtering technique is presented in this paper. The method minimizes seek-settling vibrations induced by the actuator vibration modes while maintaining the maximum control input. The cost function to minimize is a sum of square error of the position error signal at settling. Since the error equation is quadratic, a simple least-square algorithm can generate an optimal trajectory and the global optimum is guaranteed. The seek time overhead compared to bang-bang control is characterized by the order of the resulting finite-impulse-response (FIR) filter. The resulting performance is demonstrated by both benchmark simulations and experiments using a hard disk drive.     

A time optimal wavelength rerouting algorithm for dynamic trafficin WDM networks

In this paper, we consider wavelength rerouting in wavelength routed wavelength division multiplexed (WDM) networks with circuit switching, wherein lightpaths between source-destination pairs are dynamically established and released in response to a random pattern of arriving connection requests and connection holding times. The wavelength continuity constraint imposed by WDM networks leads to poor blocking performance. Wavelength rerouting is a viable and cost effective mechanism that ran improve the blocking performance by rearranging certain existing lightpaths to accommodate a new request. Recently, a rerouting scheme called “parallel move-to-vacant wavelength retuning (MTV-WR)” with many attractive features such as shorter disruption period and simple switching control, and a polynomial time rerouting algorithm, for this scheme, to minimize the weighted number of rerouted lightpaths have been proposed. This paper presents a time optimal rerouting algorithm for wavelength-routed WDM networks with parallel MTV-WR rerouting scheme. The algorithm requires only O(N²W) time units to minimize the weighted number of existing lightpaths to be rerouted, where N is the number of nodes in the network and W is the number of wavelength channels available on a fiber link. Our algorithm is an improvement over the earlier algorithm proposed in that it requires O(N³W+N²W²) time units, which is not time optimal. The simulation results show that our algorithm improves the blocking performance considerably and only very few lightpaths are required to be rerouted per rerouting. It is also established through simulation that our algorithm is faster than the earlier rerouting algorithm by measuring the time required for processing connection requests for different networks     

一种改进的多播路由算法

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗。DDSP(Destination-Driven Shortest Path)算法是一个性能较好,计算效率较高的低代价最短路径树算法,在该算法基础上,通过改进结点的搜索过程,提出一种改进的快速低代价最短路径树算法。由算法分析和实验比较得出,改进算法的计算效率高于DDSP算法,且算法构造的最短路径树的性能也优于DDSP算法构造的树．     

Evaluation of optimal-reliability indices for electricaldistribution systems

A method to calculate the optimal values of reliability indices for a load point in an electrical distribution system is presented. The problem is formulated as an optimization problem and solved by the gradient projection method; the objective is to minimize interruption cost. The algorithm is very useful and powerful for extending the existing network and planning new networks. It has been tested on a practical system (the Port-Fouad power network), and the results are discussed. Once the optimal reliability indices are determined, modification of the system by equipment replacement and future system planning can be done in such a way that the interruption cost is minimized     

Optimal and near-optimal algorithms for multiple fault diagnosiswith unreliable tests

We consider the problem of constructing optimal and near-optimal multiple fault diagnosis (MFD) in bipartite systems with unreliable (imperfect) tests. It is known that exact computation of conditional probabilities for MFD is NP hard. The novel feature of our diagnostic algorithms is the use of Lagrangian relaxation and subgradient optimization methods to provide: 1) near optimal solutions for the MFD problem and 2) upper bounds for an optimal branch and bound algorithm. The proposed method is illustrated using several examples. Computational results indicate the following: 1) our algorithm has superior computational performance to the existing algorithms (approximately three orders of magnitude improvement over the algorithm by Z. Binglin et al. (1993)); 2) near optimal algorithm generates the most likely candidates with a very high accuracy; 3) our algorithm can find the most likely candidates in systems with as many as 1000 faults     

Une approche basée sur la programmation par contraintes pour affecter des cellules à des commutateurs dans les réseaux cellulaires pour mobiles

This paper discusses the problem of assigning cells to switches in mobile networks. It can be summed up as finding an optimal assignment of cells to switches in order to minimize a cost function composed of the cost of handoff between cells and the cost of cabling between cells and switches. We propose here an algorithm based on constraint programming for this problem. The choice of this method is motivated by its active use of constraints in the search for solutions, which in turn leads to the reduction of the search space and the difficulty of the problem. We introduce a new Constraint Optimization Problem model for assigning cells to switches, a definition of a lower bound on the cost of each cell and a development of search strategies, leading to an efficient way of finding the best solutions. Results showed that our algorithm leads to an optimum solution for medium size networks and can find good solutions for large size networks.     

Software-reliability growth model: primary-failures generatesecondary-faults under imperfect debugging

Little work has been done on extending existing models with imperfect debugging to the more realistic situation where new faults are generated from unsuccessful attempts at removing faults completely. This paper presents a software-reliability growth model which incorporates the possibility of introducing new faults into a software system due to the imperfect debugging of the original faults in the system. The original faults manifest themselves as primary failures and are assumed to be distributed as a nonhomogeneous Poisson process (NHPP). Imperfect debugging of each primary failure induces a secondary failure which is assumed to occur in a delayed sense from the occurrence time of the primary failure. The mean total number of failures, comprising the primary and secondary failures, is obtained. The authors also develop a cost model and consider some optimal release-policies based on the model. Parameters are estimated using maximum likelihood and a numerical example is presented     

Algorithms for optimal scheduling and management of hidden Markovmodel sensors

The author considers a hidden Markov model (HMM) where a single Markov chain is observed by a number of noisy sensors. Due to computational or communication constraints, at each time instant, one can select only one of the noisy sensors. The sensor scheduling problem involves designing algorithms for choosing dynamically at each time instant which sensor to select to provide the next measurement. Each measurement has an associated measurement cost. The problem is to select an optimal measurement scheduling policy to minimize a cost function of estimation errors and measurement costs. The optimal measurement policy is solved via stochastic dynamic programming. Sensor management issues and suboptimal scheduling algorithms are also presented. A numerical example that deals with the aircraft identification problem is presented     

An optimal checkpointing-strategy for real-time control systemsunder transient faults

Real-time computer systems are often used in harsh environments, such as aerospace, and in industry. Such systems are subject to many transient faults while in operation. Checkpointing enables a reduction in the recovery time from a transient fault by saving intermediate states of a task in a reliable storage facility, and then, on detection of a fault, restoring from a previously stored state. The interval between checkpoints affects the execution time of the task. Whereas inserting more checkpoints and reducing the interval between them reduces the reprocessing time after faults, checkpoints have associated execution costs, and inserting extra checkpoints increases the overall task execution time. Thus, a trade-off between the reprocessing time and the checkpointing overhead leads to an optimal checkpoint placement strategy that optimizes certain performance measures. Real-time control systems are characterized by a timely, and correct, execution of iterative tasks within deadlines. The reliability is the probability that a system functions according to its specification over a period of time. This paper reports on the reliability of a checkpointed real-time control system, where any errors are detected at the checkpointing time. The reliability is used as a performance measure to find the optimal checkpointing strategy. For a single-task control system, the reliability equation over a mission time is derived using the Markov model. Detecting errors at the checkpointing time makes reliability jitter with the number of checkpoints. This forces the need to apply other search algorithms to find the optimal number of checkpoints. By considering the properties of the reliability jittering, a simple algorithm is provided to find the optimal checkpoints effectively. Finally, the reliability model is extended to include multiple tasks by a task allocation algorithm     

A tabu search algorithm for routing optimization in mobile ad-hoc networks

In this paper, we propose a routing optimization algorithm to efficiently determine an optimal path from a source to a destination in mobile ad-hoc networks. To determine an optimal path for the nodes is important for transmitting data between nodes in densely deployed networks. In order to efficiently transmit data to its destination, the appropriate routing algorithms must be implemented in mobile ad-hoc networks. The proposed algorithm is designed by using a tabu search mechanism that is a representative meta-heuristic algorithm. The proposed tabu search algorithm carries out two neighborhood generating operations in order to determine an optimal path and minimize algorithm execution time. We compare the proposed tabu search algorithm with other meta-heuristic algorithms, which are the genetic algorithm and the simulated annealing, in terms of the routing cost and algorithm execution time. The comparison results show that the proposed tabu search algorithm outperforms the other algorithms and that it is suitable for adapting the routing optimization problem.     

An Exact approach for Complete Test Set Generation of Toffoli-Fredkin-Peres based Reversible Circuits

Reversible logic has gained interest of researchers worldwide for its ultra-low power and high speed computing abilities in the future quantum information processing. Testing of these circuits is important for ensuring high reliability of their operation. In this work, we propose an ATPG algorithm for reversible circuits using an exact approach to generate CTS (Complete Test Set) which can detect single stuck-at faults, multiple stuck-at faults, repeated gate fault, partial and complete missing gate faults which are very useful logical fault models for reversible logic to model any physical defect. Proposed algorithm can be used to test a reversible circuit designed with k-CNOT, Peres and Fredkin gates. Through extensive experiments, we have validated our proposed algorithm for several benchmark circuits and other circuits with family of reversible gates. This algorithm produces a minimal and complete test set while reducing test generation time as compared to existing state-of-the-art algorithms. A testing tool is developed satisfying the purpose of generating all possible CTS’s indicating the simulation time, number of levels and gates in the circuit. This paper also contributes to the detection and removal of redundant faults for optimal test set generation.     

Test Planning for Core-based Integrated Circuits under Power Constraints

This paper addresses reduction of test cost for core-based non-stacked integrated circuits (ICs) and stacked integrated circuits (SICs) by test planning, under power constraint. Test planning involves co-optimization of cost associated with test time and test hardware. Test architecture is considered compliant with IEEE 1149.1 standard. A cost model is presented for calculating the cost of any test plan for a given non-stacked IC and a SIC. An algorithm is proposed for minimizing the cost. Experiments are performed with several ITC’02 benchmark circuits to compare the efficiency of the proposed power constrained test planning algorithm against near optimal results obtained with Simulated Annealing. Results validate test cost obtained by the proposed algorithm are very close to those obtained with Simulated Annealing, at significantly lower computation time.     

基于变分模式分解和门循环单元的电子系统间歇故障严重程度评估方法

针对电子系统间歇故障信号受噪声影响大且冗余信息多,导致深度神经网络模型对间歇故障严重程度评估能力受限的问题,该文提出一种基于变分模式分解和门循环单元(VMD-GRU)的间歇故障严重程度评估方法。先通过变分模式分解(VMD)对间歇故障信号进行自适应分解得到所有固有模式函数(IMF)分量,再对IMF分量进行相似度分析选择敏感分量,并利用微分增强型能量算子构建严重程度敏感因子。最后,利用严重程度敏感因子训练门循环单元(GRU)循环神经网络评估模型。通过对电子系统的关键电路注入不同严重程度的间歇故障进行评估,结果表明该方法有较强的间歇故障严重程度评估能力,评估结果更加准确有效。