Layout optimization algorithms vor VLSI design and manufacturing

As the feature size of the transistor shrinks into nanometer scale, it becomes a grand challenge for semiconductor manufacturers to achieve good manufacturability of integrated circuits cost-effectively. In this dissertation, we aim at layout optimization algorithms from both manufacturing and design perspectives to address problems in this grand challenge. Our work covers three topics in this research area: a redundant via enhanced maze routing algorithm for yield improvement, a shuttle mask floorplanner, and optimization of post-CMP topography variation. Existing methods for redundant via insertion are all post-layout optimizations that insert redundant vias after detailed routing. In the first part of this dissertation, we propose the first routing algorithm that conducts redundant via insertion during detailed routing. Our routing problem is formulated as a maze routing with redundant via constraints and transformed into a multiple constraint shortest path problem, and then solved by Lagrangian relaxation technique. Experimental results show that our algorithm can find routing solutions with remarkably higher rate of redundant via insertion than conventional maze routing. Shuttle mask is an economical method to share the soaring mask cost by placing different chips on the same mask. Shuttle mask floorplanning is a key step to pack these chips according to certain objectives and constraints related to mask manufacturing and cost. In the second part of this dissertation, we develop a simulated annealing based floorplanner that can optimize these objectives and meet the constraints simultaneously. Chemical-mechanical polishing (CMP) is a crucial manufacturing step to planarize wafer surface. Minimum post-CMP topography variation is preferred to control the defocus in lithography process. In the third of this dissertation, we present several studies on optimization of the variation. First, we enhance the shuttle mask floorplanner to minimize the post-CMP topography variation. Then we study the following singleblock positioning problem: given a shuttle mask floorplan, how to determine a movable block's optimal position with respect to post-CMP topography variation. We propose a fast incremental algorithm achieving 6x to 9x speedup. Finally, we formulate a novel CMP dummy fill problem that targets at minimizing the height variance, which is key to reduce the image distortion by defocus. Experimental results show that with the new formulation, we can significantly reduce the height variance without sacrificing the height spread much.Computer Science