The Statistical Reliability Of The Process Of Integrated Circuits In Nano Analysis And Parallel Optimization Algorithms

The great improvement of semiconductor industry depends on continuous technol-ogy scaling down, which provides integrated circuit with better performance and expo-nentially increasing integration capability. However, on one hand, the pace of scaling down introduces new challenges to IC design. On the other hand, due to the limitation of power density and physics, the shrink of CMOS technology will soon meet the end. Multicore processors become the solution and have dominated the market. To face these two problems, the IC CAD methodology needs to constantly evolve to handle new de-sign problems while leveraging the emerging multicore processor to gain performance improvement.Since the turn of the century, the technology scaling down has approached its phys-ical limit and new critical physical effects emerge. Among them, process variation is one of the major challenges in modern IC design and manufacture. Nowadays, IC tech-nology reaches 45nm node. Complex nano-technology such as sub-wavelength lithog-raphy and chemical-mechanical polishing (CMP) cause severe process variation, which seriously deteriorates the yield. Meanwhile, run-time aging effects, such as electromi-gration, thermal cycling, and negative bias temperature instability (NBTI), have become another fast- growing concern of IC lifetime reliability. NBTI is known to be the dom-inating circuit lifetime aging effect under 45nm nodes and later. Furthermore, process variations and NBTI effect have strong influence on each other.Besides the new design challenge, technology scaling down has brought to the EDA community another challenge. The "free lunch" of gaining speed-up by upgrading to the faster hardware, now faces an end. The frequency increase gets flattened and the mainstream chips are having a multicore revolution. How to design parallel CAD algorithm, to leverage the multicore computation power is now an urgent agenda in the community.This thesis aims at the statistical reliability issue and the challenge of parallel CAD, both of which arise from the continuous scaling down of nano-scale IC technology. The first part of this thesis is devoted to statistical reliability analysis of circuit under process variation. The contribution of this work includes:●A nonlinear scalable statistical gate delay aging model is proposed, which consid-ers both run-time working condition and fabrication-induced process variation.●Using the proposed gate delay model, a statistical timing analysis framework is presented, which is capable of characterizing the performance and reliability degradation under process variation and run-time aging. A fast pruning algorithm is proposed to improve the analysis efficiency.●A criticality and sensitivity analysis method is proposed to quantify the reliability impact of each individual circuit element.This is the first work to consider effects of process variation, run-time environment and circuit topology in circuit level reliability analysis.The second part of this thesis will focus on parallelizing the min-cost flow problem, which lies in the heart of many circuit optimization techniques. The contribution of this part of work includes:●A nondeterministic transactional algorithm design method is proposed for ex-ploring concurrency and a systematic approach to program such an algorithm for multicore platforms. We believe that such an approach is applicable to other al-gorithmic problems in CAD.●The min-cost flow problem is chosen as an example to convey the general idea and multicore parallel min-cost flow algorithm is designed. Its application to speed up the voltage island problem is demonstrated.●Based on the general nondeterministic algorithm framework, three variants of im-plementations are developed and the most efficient one for the current multicore architecture is identified.