A Timing-Aware Probabilistic Model for Single-Event-Upset Analysis

With device size shrinking and fast rising frequency ranges, the effect of cosmic radiations and alpha particles known as single-event upset (SEU) and single-event transients (SET), is a growing concern in logic circuits. Accurate understanding and estimation of SEU sensitivities of individual nodes is necessary to achieve better soft error hardening techniques at logic level design abstraction. We propose a probabilistic framework to the study the effect of inputs, circuits structure, and gate delays on SEU sensitivities of nodes in logic circuits as a single joint probability distribution function (pdf). To model the effect of timing, we consider signals at their possible arrival times as the random variables of interest. The underlying joint probability distribution function, consists of two components: ideal random variables without the effect of SEU and the random variables affected by the SEU. We use a Bayesian network to represent the joint pdf which is a minimal compact directional graph for efficient probabilistic modeling of uncertainty. The attractive feature of this model is that not only does it use the conditional independence to arrive at a sparse structure, but it also utilizes the same for smart probabilistic inference. We show that results with exact (exponential complexity) and approximate nonsimulative stimulus-free inference (linear in number of nodes and samples) on benchmark circuits yield accurate estimates in reasonably small computation time     

Switching activity estimation of VLSI circuits using Bayesian networks

Switching activity estimation is an important aspect of power estimation at circuit level. Switching activity in a node is temporally correlated with its previous value and is spatially correlated with other nodes in the circuit. It is important to capture the effects of such correlations while estimating the switching activity of a circuit. In this paper, we propose a new switching probability model for combinational circuits that uses a logic-induced directed-acyclic graph (LIDAG) and prove that such a graph corresponds to a Bayesian network (BN), which is guaranteed to map all the dependencies inherent in the circuit. BNs can be used to effectively model complex conditional dependencies over a set of random variables. The BN inference schemes serve as a computational mechanism that transforms the LIDAG into a junction tree of cliques to allow for probability propagation by local message passing. The proposed approach is accurate and fast. Switching activity estimation of ISCAS and MCNC circuits with random and biased input streams yield high accuracy (average mean error=0.002) and low computational time (average elapsed time including CPU, memory access and I/O time for the benchmark circuits=3.93 s).     

Maximum error modeling for fault-tolerant computation using maximum a posteriori (MAP) hypothesis

The application of current generation computing machines in safety-centric applications like implantable biomedical chips and automobile safety has immensely increased the need for reviewing the worst-case error behavior of computing devices for fault-tolerant computation. In this work, we propose an exact probabilistic error model that can compute the maximum error over all possible input space in a circuit-specific manner and can handle various types of structural dependencies in the circuit. We also provide the worst-case input vector, which has the highest probability to generate an erroneous output, for any given logic circuit. We also present a study of circuit-specific error bounds for fault-tolerant computation in heterogeneous circuits using the maximum error computed for each circuit. We model the error estimation problem as a maximum a posteriori (MAP) estimate [28] and [29], over the joint error probability function of the entire circuit, calculated efficiently through an intelligent search of the entire input space using probabilistic traversal of a binary Join tree using Shenoy-Shafer algorithm [20] and [21]. We demonstrate this model using MCNC and ISCAS benchmark circuits and validate it using an equivalent HSpice model. Both results yield the same worst-case input vectors and the highest percentage difference of our error model over HSpice is just 1.23%. We observe that the maximum error probabilities are significantly larger than the average error probabilities, and provides a much tighter error bounds for fault-tolerant computation. We also find that the error estimates depend on the specific circuit structure and the maximum error probabilities are sensitive to the individual gate failure probabilities.     

Covariance approximation of nonlinear regression

A nonlinear regression model on the basis of the covariance approximation of a multidimensional probability distribution is constructed. The model is represented by an expansion in the basis functions in the form of partial derivatives of the logarithm of the joint factor probability distribution. The weight coefficients of the expansion are the covariances of the resulting and explanatory variables. On particular examples, the efficiency of the Bayesian approximation of the proposed regression model in which the factor distribution is described by a finite mixture of ellipsoidally symmetric densities is demonstrated.     

Entropy methods for joint distributions in decision analysis

A fundamental step in decision analysis is the elicitation of the decision maker's information about the uncertainties of the decision situation in the form of a joint probability distribution. This paper presents a method based on the maximum entropy principle to obtain a joint probability distribution using lower order joint probability assessments. The approach reduces the number of assessments significantly and also reduces the number of conditioning variables in these assessments. We discuss the order of the approximation provided by the maximum entropy distribution with each lower order assessment using a Monte Carlo simulation and discuss the implications of using the maximum entropy distribution in Bayesian inference. We present an application to a practical decision situation faced by a semiconductor testing company in the Silicon Valley.     

Analysis of probability and energy of nanometre CMOS circuits in presence of noise

Motivated by the necessity to consider probabilistic approaches to future designs, probability and switching energy characteristics of probabilistic CMOS (PCMOS) circuits are analysed. Using 90 and 65 nm processes, detailed analytical models for the probability of correctness (p) of these circuits are developed and verified through circuit simulations.     

An efficient solution technique for discrete-time queues fed by heterogeneous traffic

During the past couple of years, a lot of effort has been put into solving all kinds of Markov modulated discrete-time queueing models, which occur, almost in a natural way, in the performance analysis of slotted systems, such as asynchronous transfer mode (ATM) multiplexers and switching elements. However, in most cases, the practical application of such solutions is limited, because of the large state space that is usually involved. In this paper we try to take a first step towards obtaining approximate solutions for a discrete-time multiserver queueing model with a general heterogeneous Markove modulated cell arrival process, which allows accurate predictions concerning the behaviour of the buffer occupancy in such a model and still remains tractable, both from an analytical and a computational point of view. We first introduce a solution technique which leads to a closed-form expression for the joint probability generating function of the buffer occupancy and the state of the arrival process, from which an expression for V(z), the probability generating function of the buffer occupancy is easily derived. On the basis of this result we propose an approximation for the boundary probabilities, which reduces all calculations to an absolute minimum. In addition, we show how accurate data for the distribution of the buffer occupancy can be obtained, by using multiple poles of V(z) in the geometric-tail approximation of the distribution. ©1997 by John Wiley & Sons, Ltd.     

非线性高斯系统边缘分布多目标贝叶斯滤波器

为解决存在数据关联不确定、检测不确定和杂波情况下的多目标跟踪问题,提出了一种新的多目标贝叶斯滤波器.代替维持多目标状态的联合后验密度,所提出的贝叶斯滤波器联合传递各个目标状态的边缘分布和它们的存在概率.为了处理目标运动和传感器测量模型中的非线性,利用无迹变换技术提出了一种非线性高斯条件下边缘分布贝叶斯滤波器的近似实现算法.仿真实验结果表明,与PHD(Probability Hypothesis Density)滤波器相比,所提出的滤波器具有更好的多目标跟踪能力.     

Statistical timing analysis of combinational logic circuits

Efficient methods for computing an exact probability distribution of the delay of a combinational circuit, given probability distributions for the gate and wire delays, are developed. The derived distribution can give the probability that a combinational circuit will achieve a certain performance, across the possible range. This information can then be used to predict the expected performance of the entire circuit. The techniques presented target fast analysis as well as reduced memory requirements. The notion of a correct approximation, based on convex inequality, which never overestimates the percentage of circuits that will achieve any given performance is defined. It is shown that given the assumption that all the topologically longest paths are responsible for the delay, the computation technique provides a correct probabilistic measure in the sense given above. Methods are given to identify and to ignore false paths in the probabilistic analysis, so as to obtain correct and less pessimistic answers to the performance prediction question. Some practical results are given for a number of benchmark combinational circuits     

Turbo equalization for GMSK signaling over multipath channels basedon the Gibbs sampler

We consider the problem of Bayesian data restoration for Gaussian minimum shift keying (GMSK) signals over unknown multipath channels. As an alternative to the linear approximation method employed in the conventional finite impulse response (FIR) model, we develop a nonlinear signal model for this system. A Bayesian equalizer based on the Gibbs sampler, a Markov chain Monte Carlo (MCMC) procedure, is developed for estimating the a posteriori symbol probability in the GMSK system without explicit channel estimation. The basic idea of this technique is to generate ergodic random samples from the joint posterior distribution of all unknowns, and then to average the appropriate samples to obtain the estimates of the unknown quantities. Being soft-input soft-output in nature, the proposed Bayesian equalization technique is well suited for iterative processing in a coded system, which allows the Bayesian equalizer to successively refine its processing based on the information from the decoding stage, and vice versa     

Power estimation methods for sequential logic circuits

Recently developed methods for power estimation have primarily focused on combinational logic. We present a framework for the efficient and accurate estimation of average power dissipation in sequential circuits. Switching activity is the primary cause of power dissipation in CMOS circuits. Accurate switching activity estimation for sequential circuits is considerably more difficult than that for combinational circuits, because the probability of the circuit being in each of its possible states has to be calculated. The Chapman-Kolmogorov equations can be used to compute the exact state probabilities in steady state. However, this method requires the solution of a linear system of equations of size 2^N where N is the number of flip-flops in the machine. We describe a comprehensive framework for exact and approximate switching activity estimation in a sequential circuit. The basic computation step is the solution of a nonlinear system of equations which is derived directly from a logic realization of the sequential machine. Increasing the number of variables or the number of equations in the system results in increased accuracy. For a wide variety of examples, we show that the approximation scheme is within 1-3% of the exact method, but is orders of magnitude faster for large circuits. Previous sequential switching activity estimation methods can have significantly greater inaccuracies     

A numerical integration-based yield estimation method for integrated circuits

A novel integration-based yield estimation method is developed for yield optimization of integrated circuits.This method tries to integrate the joint probability density function on the acceptability region directly. To achieve this goal,the simulated performance data of unknown distribution should be converted to follow a multivariate normal distribution by using Box-Cox transformation(BCT).In order to reduce the estimation variances of the model parameters of the density function,orthogonal array-based modified Latin hypercube sampling (OA-MLHS) is presented to generate samples in the disturbance space during simulations.The principle of variance reduction of model parameters estimation through OA-MLHS together with BCT is also discussed.Two yield estimation examples,a fourth-order OTA-C filter and a three-dimensional(3D) quadratic function are used for comparison of our method with Monte Carlo based methods including Latin hypercube sampling and importance sampling under several combinations of sample sizes and yield values.Extensive simulations show that our method is superior to other methods with respect to accuracy and efficiency under all of the given cases.Therefore,our method is more suitable for parametric yield optimization.     

结合版图结构信息的基本门电路故障概率估计

在门级电路可靠性估计方法中,基本门的故障概率P一般采用经验值或人为设定.本文结合基本门的版图结构信息,综合考虑了设计尺寸及缺陷特性等因素,分析了不同缺陷模型下的粒径分布数据,给出了缺陷模型粒径概率密度分布函数的参数c的计算算法,并推导出了P的计算模型.理论分析与在ISCAS85及74系列电路上的实验结果表明,缺陷的分段线性插值模型能较准确地描述电路可靠性模型的低层真实缺陷.对ISCAS85基准电路采用本文方法所得到的电路可靠度与采用美国军用标准MIL-HDBK-217方法所得到的计算结果进行了比较,验证了本文所建P模型的合理性.     

Asymptotic distributions for the performance analysis of hypothesistesting of isolated-point-penalization point processes

The performance of the likelihood ratio test is considered for a many-point interaction point process featuring a reduced number of isolated points. Limit theorems are proved that establish the Poissonian asymptotic distribution of the log-likelihood function for point processes with the isolated-point-penalization joint probability density function. The asymptotic distribution is used to approximate the detection probability associated with the likelihood ratio test. The approximation is compared to empirical results generated using Markov-chain Monte Carlo simulation. The reported results provide an efficient alternative method to simulation in assessing the performance of hypothesis testing for the point-process model considered     

贝叶斯框架下基于区域的相关反馈算法

融合基于区域的图像表达方式和相关反馈技术能够有效地提高图像检索的性能。由于现有的方法没有充分考虑相同语义类内区域特征的分布情况,进而无法对该类的语义信息进行有效的描述,为此该文提出了贝叶斯框架下基于区域的相关反馈模型。在每轮相关反馈中,通过在线学习区域的贝叶斯分类器,同时根据最近邻最小错误估计原则确定分类器的可信度,可以可靠地建立图像相似性度量的概率模型。此外,在应用非参数密度估计技术来构造语义类的特征分布时,针对区域分割的不精确性,该文还考虑了区域特征空间的总体分布因素,进而对区域的后验分布进行更可靠地估计。最后的实验说明了该文方法的有效性。     

Predictive Distribution of the Dirichlet Mixture Model by Local Variational Inference

In Bayesian analysis of a statistical model, the predictive distribution is obtained by marginalizing over the parameters with their posterior distributions. Compared to the frequently used point estimate plug-in method, the predictive distribution leads to a more reliable result in calculating the predictive likelihood of the new upcoming data, especially when the amount of training data is small. The Bayesian estimation of a Dirichlet mixture model (DMM) is, in general, not analytically tractable. In our previous work, we have proposed a global variational inference-based method for approximately calculating the posterior distributions of the parameters in the DMM analytically. In this paper, we extend our previous study for the DMM and propose an algorithm to calculate the predictive distribution of the DMM with the local variational inference (LVI) method. The true predictive distribution of the DMM is analytically intractable. By considering the concave property of the multivariate inverse beta function, we introduce an upper-bound to the true predictive distribution. As the global minimum of this upper-bound exists, the problem is reduced to seek an approximation to the true predictive distribution. The approximated predictive distribution obtained by minimizing the upper-bound is analytically tractable, facilitating the computation of the predictive likelihood. With synthesized data and real data evaluations, the good performance of the proposed LVI based method is demonstrated by comparing with some conventionally used methods.     

概率图模型的表示理论综述

概率图模型结合概率论与图论的知识,利用图结构表示变量的联合概率分布,近年已成为不确定性推理的研究热点.随着概率图模型在实际领域中的应用日益增加,不同的任务和应用环境对概率图模型的表示理论提出了不同的新要求.本文总结出近年来提出的多种概率图模型的表示理论.最后指出概率图模型的进一步研究方向.     

On Bayesian image reconstruction from projections: uniform and nonuniform a priori source information

A method that incorporates a priori uniform or nonuniform source distribution probabilistic information and data fluctuations of a Poisson nature is presented. The source distributions are modeled in terms of a priori source probability density functions. Maximum a posteriori probability solutions, as determined by a system of equations, are given. Interactive Bayesian imaging algorithms for the solutions are derived using an expectation maximization technique. Comparisons of the a priori uniform and nonuniform Bayesian algorithms to the maximum-likelihood algorithm are carried out using computer-generated noise-free and Poisson randomized projections. Improvement in image reconstruction from projections with the Bayesian algorithm is demonstrated. Superior results are obtained using the a priori nonuniform source distribution.     

PCA联合子空间理论的规范化与扩展

对于高维数据的分类,主成分分析(PCA)联合子空间可为各类数据建立更为细致的概率模型,从而提高贝叶斯分类的准确性。本文首先对PCA联合子空间理论进行了规范化,提出了两个基本假设,并从理论上证明了残差子空间参数“代表特征根”的启发式取值正是其极大似然估计。本文进一步对样本残差的概率模型进行了扩展,提出了扩展型逐类联合子空间算法。最后,本文通过在真实数据上实验结果证明了扩展型逐类联合子空间算法的优越性。