Probabilistic Analysis for Modeling and Simulating Digital Circuits.

Abstract

Due to the rapid progress of their manufacturing technologies, integrated circuit (ICs) can now contain billions of transistors and operate at gigahertz frequencies. This great complexity has forced engineers to rely on electronic design automation (EDA) software tools to design, verify and test new ICs. Traditional EDA tools are deterministic in nature and try to explicitly address all a circuit’s operating modes by examining very large input signal sets and computing their output responses. However, beyond some point, such methods must be replaced by random sampling of the inputs, an approach that is inherently probabilistic. Manufacturing process variations and soft errors caused by environmental disturbances also call for statistical approaches to gauge their impact. Hence, there is an increasing need for probabilistic characterizations of IC behavior that can be easily incorporated into EDA tools, and can be used in situations where traditional deterministic approaches are ineffective. The goal of this dissertation is to develop ways to significantly improve the quality of the probabilistic analysis techniques required for EDA. The accuracy and scalability of these techniques is greatly affected by several factors, including the probability models employed and the handling of correlations among signals. To address such issues, we develop novel and efficient ways to sample logic circuit behavior, model the impact of soft errors, and estimate circuit reliability. First, we present a methodology for sampling input signals that improves accuracy and run-time by prioritizing the sample variables and compressing the sample space. Then, we introduce a trigonometry-based technique for efficiently analyzing soft errors by mapping signal probabilities into angles. Finally, a reliability estimation method is described that uses probabilistic transfer matrices to calculate signal and error probability distributions in sequential circuits. Unlike previous techniques, its memory usage grows slowly even when simulating very large circuits over many clock cycles. Extensive simulation studies are presented in support of all the foregoing results. The contributions of this dissertation identify features of probabilistic, error-inducing phenomena that can lead to significant improvements in circuit quality. They also reduce the computational overhead for probabilistic calculations which are essential for many EDA tasks.