Abstract
This dissertation studies four problems of advanced layout design in two different aspects. For engineering change order (ECO), we focus on redundant-via-aware ECO routing and mask-cost-aware ECO routing; for triple patterning lithography (TPL), we first investigate cell-based row-structure TPL layout decomposition and then TPL-aware detailed placement refinement. For the purpose of fixing functional and/or timing problems effectively and efficiently after place-and-route or even tape-out, designers can utilize pre-injected spare cells to change the original design and apply ECO routing to connect modified nets incrementally. However, redundant via insertion (RVI) has become an inevitable means adopted in the routing or post-routing stage to enhance chip reliability and yield as feature size shrinks down to nanometer scale. The remaining routing resources could become so limited after RVI, thus causing difficulties in ECO routing which regards existing layout objects as routing blockages. We propose an ECO routing approach that considers redundant via replacement, removal, and insertion. We also address another ECO routing problem, especially for post-silicon ECO implementation; this problem considers four types of circuit modifications: net addition, net deletion, pin connection, and pin disconnection. As minimum feature size continues to scale down, the cost of photomasks becomes a critical issue for post-silicon ECO. We present an ECO routing approach that considers the reuse of old routes to save the mask re-spin cost. In the past few years, much attention has been devoted to layout design with the advanced lithography technology, TPL. Several relevant problems in TPL, such as layout decomposition and TPL-aware placement have been explored. The TPL layout decomposition problem is to divide the polygons on a layer into three different masks, in which the distance between two polygons assigned on the same mask should not be less than the minimum coloring distance in TPL, or a coloring conflict is caused. For any cell-based row-structure layout on Metal 1 (M1) layer, we design a graph-based approach to solve the TPL layout decomposition problem by finding a decomposition solution with the minimal total cost in terms of conflicts and stitches. We also develop several graph simplification methods to speed up our approach. To enhance the decomposition quality, we finally study TPL in the detailed placement stage. We present a row-based detailed placement refinement approach which aims at finding a legal placement with a conflict-free TPL layout decomposition and meanwhile minimizing the number of stitches and the wirelength.