Probabilistic Error Propagation through Approximated Boolean Networks

Abstract

Most approximate logic synthesis techniques successively apply local approximate transformations to Boolean circuits. Naturally, an efficient, robust, and scalable error estimation technique is due. This paper addresses this problem by propagating error probabilities within a network of circuits, each circuit being described by an approximated Boolean function. We specifically tackle error rate, that is, the likelihood of a logic network evaluating to an erroneous output. Our simulation-free error rate estimation technique is fully accurate when there are no mutual dependencies among signals in the Boolean network-also known as fanout-reconvergence-and shows a neglectable inaccuracy lying within 1% with respect to exhaustively simulated values for benchmark designs including signal correlations. Moreover, our methodology is capable of computing the error rate in the order of milliseconds for every tested benchmark, allowing the proposed error analysis to be applied during design space exploration. For comparison, we finally applied our methodology to a state-of-the-art approximate logic synthesis framework showing its superiority in terms of quality and runtime.