An ROBDD-Based Combinatorial Method for the Evaluation of Yield of Defect-Tolerant Systems-on-Chip

In this paper, we develop a combinatorial method for the evaluation of the functional yield of defect-tolerant systems-on-chip (SoC). The method assumes that random manufacturing defects are produced according to a model in which defects cause the failure of given components of the system following a distribution common to all defects. The distribution of the number of defects is arbitrary. The yield is obtained by conditioning on the number of defects that result in the failure of some component and performing recursive computations over a reduced ordered binary decision diagram (ROBDD) representation of the fault-tree function of the system. The method has excellent error control. Numerical experiments seem to indicate that the method is efficient and, with some exceptions, allows the analysis with affordable computational resources of systems with very large numbers of components.      

ROBDD complexity analysis for XOR/XNOR min-terms

This paper discusses the complexity of reduced ordered binary decision diagrams (ROBDDs) for Boolean functions with XOR/XNOR min-terms. Knowing the number of variables and the number of product terms of Boolean function containing only XOR/XNOR min-terms, one can predict the number of nodes in its ROBDD representation without building the binary decision diagram (BDD). A mathematical model for this prediction has been developed. This model can be used to find the maximum number of nodes for a given number of variables. Theoretical and experimental results are reported to underline the efficiency of this approach. The experimental results show that even though the XOR/XNOR min-terms cannot be simplified using Boolean laws or any other simplification method leading to a better min-term representation, the ROBDD will perform the simplification using the ROBDD reduction rules. The required memory is analysed for different methods of representation, and this analysis showed that ROBDDs are memory efficient structures to store and represent large numbers of XOR/XNOR min-terms in Boolean functions.     

Best ROBDD variable ordering for functions with disjunctivedecompositions

The problem of finding a variable ordering to minimise the size of a reduced ordered binary decision diagrams (ROBDD) is considered for functions possessing disjunctive decompositions. An example is presented showing that the best ordering for a function with a disjunctive decomposition cannot always be directly determined from the best orderings for the component functions     

CMOS集成电路中Glitch Power的分析方法研究

在集成电路中器件延迟数学模型的基础上,介绍了如何利用定时布尔函数和定时有序二值决策图对集成电路Glitch Power进行分析;借助CUDD软件包,构建了电路的Timed-OBDD表达形式,对一些典型的BenchMark进行了仿真.     

Reliability block diagrams and “Petri” nets

A transformation algorithm is given to find a “Petri” net representation corresponding to a reliability block diagram. Several examples are given to illustrate the dynamic character of this representation. As an application we derive probability expressions from the “Petri” net representation.     

OBDD-based evaluation of k-terminal network reliability

An efficient approach to determining the reliability of an undirected k-terminal network based on 2-terminal reliability functions is presented. First, a feasible set of (k-1) terminal-pairs is chosen, and the 2-terminal reliability functions of the (k-1) terminal-pairs are generated based on the edge expansion diagram using an OBDD (ordered binary decision diagram). Then the k-terminal reliability function can be efficiently constructed by combining these (k-1) reliability expressions with the Boolean and operation. Because building 2-terminal reliability functions and reducing redundant computations by merging reliability functions can be done very efficiently, the proposed approaches are much faster than those which directly expand the entire network or directly factor the k-terminal networks. The effectiveness of this approach is demonstrated by performing experiments on several large benchmark networks. An example of appreciable improvement is that the evaluation of the reliability of a source-terminal 3/spl times/10 all-terminal network took only 2.4 seconds on a SPARC 20 workstation. This is much faster than previous factoring-algorithms.     

Lifetime Distribution Identities

Five ways of representing the distribution of a continuous nonnegative random variable T are used extensively in the reliability literature: the probability density function, the reliability (survivor function), the hazard rate, the cumulative hazard function, and the mean residual life function. Properties, identities, and intuitive interpretations of the five representations are discussed. Several examples are given. Although there are other functions, such as normalized mean residual life for studying replacement policies, these five distribution representations have surfaced as vehicles for representing a lifetime distribution. The choice of which distribution representation to use depends on whether ? 1. The representation has a tractable form 2. Intuition is gained concerning the distribution by seeing a plot of the representation.     

基于制造成品率模型的集成电路早期可靠性估计

缺陷是影响集成电路成品率与可靠性的主要因素.本文在区分缺陷与故障两个概念的基础上,将缺陷区分为成品率缺陷(硬故障)、可靠性缺陷(软故障)和良性缺陷.利用关键区域的面积,给出了一个缺陷成为"硬故障"或"软故障"的概率,给出了精度较高的IC成品率预测模型.利用成品率缺陷与可靠性缺陷之间的关系,给出了工艺线生产的产品的失效率与该工艺线制造成品率之间的定量关系.在工艺线稳定的条件下,通过该工艺线的制造成品率可以利用该关系式可以有效的估计出产品的失效率,可以有效地缩短了新产品的研发周期.     

Reliability Analysis of Phased-Mission System With Independent Component Repairs

This paper proposes a hierarchical modeling approach for the reliability analysis of phased-mission systems with repairable components. The components at the lower level are described by continuous time Markov chains which allow complex component failure/repair behaviors to be modeled. At the upper level, there is a combinatorial model whose structure function is represented by a binary decision diagram (BDD). Two BDD ordering strategies, and consequently two evaluation algorithms, are proposed to compute the phased-mission system (PMS) reliability based on Markov models for components, and a BDD representation of system structure function. The performance of the two evaluation algorithms is compared. One algorithm generates a smaller BDD, while the other has shorter execution time. Several examples, and experiments are presented in the paper to illustrate the application, and the advantages of our approach.     

Reversed ROBDD circuits

A new class of logic circuits is proposed. Being derived from reduced ordered binary decision diagrams (ROBDD), these circuits inherit compactness and the ability to represent very large switching functions. The reversed signal propagation results in low dynamic power consumption, complete single stuck-at fault testability and fault security. Simulation results are presented     

Program decision logic optimization using predication and controlspeculation

The mainstream arrival of predication, a means other than branching of selecting instructions for execution, has required compiler architects to reformulate fundamental analyses and transformations. Traditionally, the compiler has generated branches straightforwardly to implement control flow designed by the programmer and has then performed sophisticated "global" optimizations. to move and optimize code around them. In this model, the inherent tie between the control state of the program and the location of the single instruction pointer serialized run-time evaluation of control and limited the extent to which the compiler could optimize the control structure of the program (without extensive code replication). Predication provides a means of control independent of branches and instruction fetch location, freeing both compiler and architecture from these restrictions; effective compilation of predicated code, however requires sophisticated understanding of the program's control structure. This paper explores a representational technique which, through direct code analysis, maps the program's control component into a canonical database, a reduced ordered binary decision diagram (ROBDD), which fully enables the compiler to utilize and manipulate predication. This abstraction is then applied to optimize the program's control component, transforming it into a form more amenable to instruction level parallel (ILP) execution     

A relation model of gate oxide yield and reliability

The relationship between yield and reliability is obviously important for predicting and improving reliability during the early production stage, especially for new technologies. Previous research developed models to relate yield and reliability when reliability is defined as the probability of a device having no reliability defects. This definition of reliability is not a function of mission time and thus is not consistent with reliability estimated from the time-to-first-failure data which is commonly used. In this paper, we present a simple model to tie oxide yield to time-dependent reliability by combining the oxide time to breakdown model with a defect size distribution. We show that existing models become special cases when a single mission time is considered. As the proposed reliability function has a decreasing failure rate, the result is useful for a manufacturer seeking to find an optimal burn-in policy for burn-in temperature, burn-in voltage, and burn-in time.     

Network Approaches to Finding the Reliability of Repairable Systems

Methods of determining the availability and failure frequency of systems of independent repairable units are discussed. The methods are based on representation of the system by a network or reliability block diagram. Conditions for such representation are given and methods of drawing the network are described. Two approaches for determining system reliability given the network and unit characteristics are reviewed and developed. One approach is based on successive reduction of the network and is particularly useful for series-parallel systems. The other approach is based on the determination of either the minimal paths or cuts and subsequent formula manipulations. Both approaches enable quite large systems to be analyzed.     

Managing technology development for safety-critical systems

This paper presents a model that determines the optimal budget allocation strategy for the development of new technologies, for safety-critical systems, over multiple decision periods. The case of the development of a hypersonic passenger airplane is used as an illustration. The model takes into account both the probability of technology development success as a function of the allocated budget and the probability of operational performance of the final system. It assumes that the strategy is to consider (and possibly fund) several approaches to the development of each technology to maximize the probability of development success. The model, thus, decomposes the system's development process into multiple technology development modules (one for each technology needed), each involving a number of alternative projects. There is a tradeoff between development speed and operational reliability when the budget must be allocated among alternative technology projects with different probabilities of development success and operational reliability (e.g., an easily and quickly developed technology may have little robustness). The probabilities of development and operational failures are balanced by a risk analysis approach, which allows the decision maker to optimize the budget allocation among different projects in the development program, at the beginning of each budget period. The model indicates that by considering reliability in the R&D management process, the decision maker can make better decisions, optimizing the balance between development time, cost, and robustness of safety-critical systems.     

Reliability evaluation of wireless sensor networks using an enhanced OBDD algorithm

An enhanced ordered binary decision diagram (EOBDD) algorithm is proposed to evaluate the reliability of wireless sensor networks (WSNs), based on the considerations of the common cause failure (CCF) and a large number of nodes in WSNs. The EOBDD algorithm analyzes the common cause event (CCE) and the network structure when CCE takes place according to the stochastic graph and the CCF model of WSNs. After constructing the ordered binary decision diagram (OBDD) of the original network with node expansion, it uses a set of OBDD variables (SOV) to guide reliability computations along this OBDD. The two steps about OBDD can decrease the cost of OBDD constructions and storage. Furthermore, the efficient OBDD structure and Hash tables can greatly decrease redundant computations of isomorphs. The experiment results show that the EOBDD can be used to evaluate the reliability of WSN efficiently.     

空战机动决策中的影响图方法

首次将影响图分析方法引入到一对一空战机动决策中。在影响图模型中,各种空战态势下的每个备选机动方案都与一个概率值和一个效用值相联系,根据贝叶斯定理可以利用传感器信息降低结果的不确定性,影响图分析为综合效用值提供了概率分布,表示完成各备选动作的成功率,最终的决策根据所选的决策标准而定。最后进行灵敏度分析以决定各因素对决策结果的影响程度。     

Efficient symbolic computation of generalised spectra

An efficient algorithm is presented for the calculation of any generalised spectrum represented as an algebraic decision diagram (ADD) from an ordered binary decision diagram (OBDD) of a Boolean function, and vice versa     

Experience with Bayesian Reliability Measurement of Large Systems

Experience with two methods of Bayesian reliability measurement is described. An aerospace subsystem was evaluated assuming continuous gamma-distributed component failure rates. Priors were developed by conventional reliability prediction methods based on handbook data. The ``strength' of the prior was expressed in terms of variance about a predicted mean. Comparative evaluation was also made by a classical technique during a test program extending over 10 months. The Bayesian method was preferred though problems inherent in the method were apparent. More recently, a complex marine system was evaluated over a one-year period using a Bayesian formulation in which the failure rate is described by a discrete probability distribution with nonuniform cell widths. This technique avoids some of the operational problems of continuous formulations. Experience with Bayesian methods leaves little doubt of their utility as evaluation tools. The philosophical problems, however, remain as intransigent as ever.     

快速解密且私钥定长的密文策略属性基加密方案

在保证密文策略属性基加密(CP-ABE)算法安全性的前提下,尽可能地提升其工作效率一直是密码学领域的研究热点。该文从作为CP-ABE效率核心的访问结构着手,首次提出基于简化有序二叉决策图(ROBDD)的访问结构,给出了相应的策略表示方法、用户可满足性判定;基于简化有序二叉决策图(ROBDD)访问结构设计了在算法时间复杂度、存储空间占用量等方面都具有较好表现的CP-ABE方案;在安全性方面,该方案能够抵抗用户间的合谋攻击和选择明文攻击。对比分析表明,ROBDD访问结构具有更强的表达能力和更高的表达效率;新的CP-ABE方案包含时间复杂度为常数阶的密钥生成算法、解密算法,能够为用户生成定长私钥并实现快速解密。     

A new defect distribution metrology with a consistent discreteexponential formula and its applications

We have proposed a novel discrete exponential distribution function, which describes a defect count distribution on wafers or chips more accurately, especially in near defect-free conditions. The conventional approach based on a gamma probability density function (g-pdf) is known to fail in expressing the defects of defect-free wafers or chips, because it always gives zero as the pdf value. Since the number of defects is countable (discrete distribution should be used) and analyzed in terms of nondefective chip yield, the g-pdf cannot be used because of its inaccuracy in the near defect-free condition. A discrete exponential pdf is introduced corresponding to the defect count distribution. In addition, a convolution formula of the new pdf is derived statistically which can express realistic defect count distribution with multiple defect sources. It is noted that the popular negative binomial yield formula (NBYF) is directly derived with the convoluted discrete exponential distribution, which interprets the cluster factor given in NBYF as the number of different defect sources predicted. It is experimentally proven that defect count distributions are approximated by this new model within an average error of about 0.01 defects per wafer from film deposition process data