Efficient algorithms for fundamental statistical timing analysis problems in delay test applications of VLSI circuits

Abstract

Tremendous advances in semiconductor process technology are creating new challenges for the delay test of today’s digital VLSI circuits. The complexity of state-of-the-art manufacturing processes does not only lead to greater process variability, it also makes today's integrated circuits more prone to defects such as resistive shorts and opens. As a consequence, some of the manufactured circuits do not meet the timing requirements set by the design specification. These circuits must be identified by delay testing and sorted out to ensure the quality of shipped products. Due to the increasing process variability, key transistor and interconnect parameters must be modelled as random variables. These random variables capture the uncertainty caused by process variability, but also the impact of modelling errors and variations in the operating conditions of the circuits, such as the temperature or the supply voltage. The important consequence for delay testing is that a particular delay test detects a delay fault of fixed size in only a subset of all manufactured circuits, which inevitably leads to the shipment of defective products. Despite the fact that this problem is well understood, today's delay test generation methods are unable to consider the distortion of the delay test results, caused by process variability. To analyse and predict the effectiveness of delay tests in a population of circuits which are functionally identical but have varying timing properties, statistical timing analysis is necessary. Although the large runtime of statistical timing analysis is a well known problem, little progress has been made in the development of efficient statistical timing analysis algorithms for the variability-aware delay test generation and delay fault simulation. This dissertation proposes novel and efficient statistical timing analysis algorithms for the variability-aware delay test generation and delay fault simulation in presence of large delay variations. For the detection of path delay faults, a novel probabilistic sensitization analysis is presented which analyses the impact of process variations on the sensitization of the target paths. Furthermore, an efficient method for approximating the probability of detecting small delay faults is presented. Beyond that, efficient statistical SUM and MAX-operations are proposed, which provide the fundamental basis of block-based statistical timing analysis. The experiment results demonstrate the high efficiency of the proposed algorithms.