Abstract:
With the improvements in fabrication processes, electronic circuit designers have begun to design complex circuits which consist of multibillion transistors. But, as circuit complexity increases, the silicon complexity also increases, leading to process variations having a profound effect on the circuit performance especially in sub micron technologies. Therefore, even if a circuit was designed to achieve a certain design specification, there will be a discrepancy between the simulated and the measured performances. This difference can lead to a decrease in the yield. Circuit designers tend to handle this problem by leaving a safety margin; however, this leads to overdesign and loss of precious chip area. Therefore, there is an undeniable need to have efficient design automation tools for reducing design time without compromising performance. Normally, a typical approach for analyzing a circuit would be running a Monte Carlo simulation with a small sample size and then fitting a standard analytical distribution to the data. Such an approach can be accurate for the main part of the distribution, however it will be heavily inaccurate in the tail of the distribution. Since, the distribution of design specifications with respect to process variation effects tends to have a long tail by nature, a classic Monte Carlo simulation can not be used. In this case, a rare event sampling method can be utilized for increasing number of samples corresponding to tail of the original distribution. Cross entropy minimization based importance sampling (IS) method is chosen as rare event sampling method for the scope of this thesis due to its efficiency, although there are lots of different Monte Carlo based proposals. Also, a hybrid Quasi-Monte Carlo (QMC) method has been utilized in order to both select rare event threshold that is needed for cross entropy based IS algorithm and performance comparison with the proposed algorithm.
