Digital CMOS VLSI circuit routing with manufacturability and yield constraints

Ph.D. University of Hawaii at Manoa 2012.Includes bibliographical references.As the minimum feature size enters nano scale, the IC industry faces great challenges from the yield losses caused by the various imperfections in the manufacturing processes. As the CMOS technology is approaching its fundamental limit, completely relying on the manufacturers to solve the yield problems is not practical. Indeed, the coupling between manufacturing and design at the advanced technology nodes has become so strong that, to achieve a decent yield, the designers must be aware of the impact of the design style on the manufacturing of the circuits. In this dissertation, the possibilities of optimizing manufacturability and yield in the stage of routing are investigated. The dissertation mainly focuses on problem formulations and algorithms rather than modeling. Since there are so many potential problems involved in the topic, the dissertation is not intended to be complete. Rather, several interesting formulations and algorithms for the optimization of manufacturability and yield are proposed. In chapter 1, some basic concepts about routing and design for manufacturability and yield are introduced. Then, the research objective is presented is chapter 2. In chapter 3, a track routing algorithm for the co-optimization of timing and yield is proposed. In the work it is shown that, for a given segment ordering, the optimization problem can be formulated as a mixed linear geometric programming problem, which can be transformed into a general non-linear convex programming problem. Therefore, theoretically, the co-optimization problem can be solved in polynomial time. However, since the practical running time of the optimal solver for the general convex programming problem is too long, a heuristic is proposed to return a decent solution within much shorter running time. In chapter 4, two techniques are proposed to enhance the double-patterning-friendly detailed routing algorithm. One of the two techniques takes advantage of the idea of delayed decision to make the coloring choices more reasonable. The other technique tries to get rid of the within-path coloring conflicts by recording more information during path searching . In chapter 5, a jumper insertion algorithm that targets practical antenna rules and is aware of timing constraints is proposed. The problem is first formulated as an integer programming problem. Then, the technique of Lagrangian relaxation is employed to relax the difficult constraints and convert the original problem into two sub-problems that can be solved efficiently with combinatorial algorithms. In chapter 6, an algorithm is proposed that combines the wire sizing and layer reassignment techniques together to improve the yield of the circuits. It is shown that, even with its NPcompleteness, the problem can be solved optimally by using the technique of tree decomposition. To make the running time practical, a heuristic is proposed to construct the largest subgraphs with bounded treewidth. To take advantage of multi-core CPUs, the dynamic programming algorithm is implemented with multiple threads. Finally, it is pointed out that the proposed algorithms can also be used to solve some problems in multiple patterning technologies. In the last chapter, the dissertation is concluded and some possible future research directions are presented