Probabilistic transfer matrices in symbolic reliability analysis of logic circuits
Probabilistic transfer matrices in symbolic reliability analysis of logic circuits
复制标题
DOI：
10.1145/1297666.1297674
复制
发表时间：
2008-01
期刊：
影响因子：
--
通讯作者：
Smita Krishnaswamy;George F. Viamontes;I. Markov;J. Hayes
中科院分区：
文献类型：
--
作者：
Smita Krishnaswamy;George F. Viamontes;I. Markov;J. Hayes
我们提出了概率转移矩阵（PTM）的框架来捕捉逻辑电路中的不确定性行为。PTM提供了对正常和故障行为的简明描述，并且非常适合于可靠性和错误敏感性计算。基于连通性的一些简单的组合规则可以用于从较小的门PTM递归地构建较大的PTM（表示整个逻辑电路）。使用矩阵乘法组合用于串联的门的PTM，并且使用张量积运算组合用于并联的门的PTM。PTM可以准确地计算联合输出概率的存在下，再收敛扇出和不可分割的联合输入分布。为了提高计算效率，我们将PTM编码为代数决策图（ADD）。我们还开发了新定义的矩阵运算，如消除_变量和消除_冗余_变量，这有助于电路PTM的数值计算的等效ADD算法。我们使用PTM来评估电路的可靠性，并推导出多项式近似电路的错误概率的门错误概率。PTM还可以分析逻辑和电气掩蔽对错误缓解的影响。我们发现，忽略逻辑掩蔽可以高估错误的数量级。我们将电掩蔽计算误差衰减概率，分析模型的基础上，到一个扩展的PTM框架的可靠性计算。我们进一步定义了一个敏感性措施，以确定门的错误没有很好地掩盖。我们表明，硬化几个门可以显着提高电路的可靠性。
We propose the probabilistic transfer matrix (PTM) framework to capture nondeterministic behavior in logic circuits. PTMs provide a concise description of both normal and faulty behavior, and are well-suited to reliability and error susceptibility calculations. A few simple composition rules based on connectivity can be used to recursively build larger PTMs (representing entire logic circuits) from smaller gate PTMs. PTMs for gates in series are combined using matrix multiplication, and PTMs for gates in parallel are combined using the tensor product operation. PTMs can accurately calculate joint output probabilities in the presence of reconvergent fanout and inseparable joint input distributions. To improve computational efficiency, we encode PTMs as algebraic decision diagrams (ADDs). We also develop equivalent ADD algorithms for newly defined matrix operations such as eliminate_variables and eliminate_redundant_variables, which aid in the numerical computation of circuit PTMs. We use PTMs to evaluate circuit reliability and derive polynomial approximations for circuit error probabilities in terms of gate error probabilities. PTMs can also analyze the effects of logic and electrical masking on error mitigation. We show that ignoring logic masking can overestimate errors by an order of magnitude. We incorporate electrical masking by computing error attenuation probabilities, based on analytical models, into an extended PTM framework for reliability computation. We further define a susceptibility measure to identify gates whose errors are not well masked. We show that hardening a few gates can significantly improve circuit reliability.