Due to aggressive scaling in semiconductor industry, the traditional optical lithography system is facing great challenges printing 32nm and below circuit layouts. Various promising nanolithography techniques have been developed as alternative solutions for patterning sub-32nm feature size. This dissertation studies physical design related optimization problem for these emerging methodologies, mainly focusing on double patterning and electronic beam lithography. Double Patterning Lithography (DPL) decomposes a single layout into two masks, and patterns the chip in two exposure steps. As a benefit, the pitch size is doubled, which enhances the resolution. However, the decomposition process is not a trivial task. Conflict and stitch are its two main manufacturing challenges. First of all, a post-routing layout decomposer has been developed to perform simultaneous conflict and stitch minimization, making use of the integer linear programming and efficient graph reduction techniques. Compared to the previous work which optimizes conflict and stitch separately, the proposed method produces significantly better result. Redundant via insertion, another key yield improvement technique, may increase the complexity in DPL-compliance. It could easily introduce unmanufacturable conflict, while not carefully planned and inserted. Two algo- rithms have been developed to take care of this redundant via DPL-compliance problem in the design side. While design itself is not DPL-friendly, post-routing decomposition may not achieve satisfactory solution quality. An efficient framework of WISDOM has been further proposed to perform wire spreading for better conflict and stitch elimination. The solution quality has been improved in great extent, with a little extra layout perturbations. As another promising solution for sub-22nm, Electronic Beam Lithography (EBL) is a maskless technology which shoots desired patterns directly into a silicon wafer, with charged particle beam. EBL overcomes the diffraction limit of light in current optical lithography system, however, the low throughput becomes its key technical hurdle. The last work of my dissertation formulates and investigates a bin-packing problem for reducing the processing time of EBL. / text

A VLSI chip can today contain hundreds of millions transistors and is expected to contain more than 1 billion transistors in the next decade. In order to handle this rapid growth in integration technology, the design procedure is therefore divided into a sequence of design steps. Circuit layout is the design step in which a physical realization of a circuit is obtained from its functional description. Global routing is one of the key subproblems of the circuit layout which involves finding an approximate path for the wires connecting the elements of the circuit without violating resource constraints. The global routing problem is NP-hard, therefore, heuristics capable of producing high quality routes with little computational effort are required as we move into the Deep Sub-Micron (DSM) regime. In this thesis, different approaches for global routing problem are first reviewed. The advantages and disadvantages of these approaches are also summarized. According to this literature review, several mathematical programming based global routing models are fully investigated. Quality of solution obtained by these models are then compared with traditional Maze routing technique. The experimental results show that the proposed model can optimize several global routing objectives simultaneously and effectively. Also, it is easy to incorporate new objectives into the proposed global routing model. To speedup the computation time of the proposed ILP based global router, several hierarchical methods are combined with the flat ILP based global routing approach. The experimental results indicate that the bottom-up global routing method can reduce the computation time effectively with a slight increase of maximum routing density. In addition to wire area, routability, and vias, performance and low power are also important goals in global routing, especially in deep submicron designs. Previous efforts that focused on power optimization for global routing are hindered by excessively long run times or the routing of a subset of the nets. Accordingly, a power efficient multi-pin global routing technique (PIRT) is proposed in this thesis. This integer linear programming based techniques strives to find a power efficient global routing solution. The results indicate that an average power savings as high as 32\% for the 130-nm technology can be achieved with no impact on the maximum chip frequency.

A VLSI chip can today contain hundreds of millions transistors and is expected to contain more than 1 billion transistors in the next decade. In order to handle this rapid growth in integration technology, the design procedure is therefore divided into a sequence of design steps. Circuit layout is the design step in which a physical realization of a circuit is obtained from its functional description. Global routing is one of the key subproblems of the circuit layout which involves finding an approximate path for the wires connecting the elements of the circuit without violating resource constraints. The global routing problem is NP-hard, therefore, heuristics capable of producing high quality routes with little computational effort are required as we move into the Deep Sub-Micron (DSM) regime. In this thesis, different approaches for global routing problem are first reviewed. The advantages and disadvantages of these approaches are also summarized. According to this literature review, several mathematical programming based global routing models are fully investigated. Quality of solution obtained by these models are then compared with traditional Maze routing technique. The experimental results show that the proposed model can optimize several global routing objectives simultaneously and effectively. Also, it is easy to incorporate new objectives into the proposed global routing model. To speedup the computation time of the proposed ILP based global router, several hierarchical methods are combined with the flat ILP based global routing approach. The experimental results indicate that the bottom-up global routing method can reduce the computation time effectively with a slight increase of maximum routing density. In addition to wire area, routability, and vias, performance and low power are also important goals in global routing, especially in deep submicron designs. Previous efforts that focused on power optimization for global routing are hindered by excessively long run times or the routing of a subset of the nets. Accordingly, a power efficient multi-pin global routing technique (PIRT) is proposed in this thesis. This integer linear programming based techniques strives to find a power efficient global routing solution. The results indicate that an average power savings as high as 32\% for the 130-nm technology can be achieved with no impact on the maximum chip frequency.

The multi-net Global Routing Problem (GRP) in VLSI physical design is a problem of routing a set of nets subject to limited resources and delay constraints. Various state-of-the-art routers are available but their main focus is to optimize the wire length and minimize the over ow. However optimizing wire length do not necessarily meet timing constraints at the sink nodes. Also, in modern nano-meter scale VLSI process the consideration of process variations is a necessity for ensuring reasonable yield at the fab. In this work, we try to nd a fundamental strategy to address the timing-driven Steiner tree construction (i.e., the routing) problem subject to congestion constraints and process variation. For congestion mitigation, a gradient based concurrent approach (over all nets) of Erzin et. al., rather than the traditional (sequential) rip-and-reroute is adopted in or- der to propagate the timing/delay-driven property of the Steiner tree candidates. The existing sequential rip-up and reroute methods meet the over ow constraint locally but cannot propagate the timing constraint which is non-local in nature. We build on this approach to accommodate the variation-aware statistical delay/timing requirements. To further reduce the congestion, the cost function of the tree generation method is updated by adding history based congestion penalty to the base cost (delay). Iterative use of the timing-driven Steiner tree construction method and history based tree construction procedure generate a diverse pool of candidate Steiner trees for each net. The gradient algorithm picks one tree for each net from the pool of trees such that congestion is e ciently controlled. As the technology scales down, process variation makes process dependent param- eters like resistance, capacitance etc non-deterministic. As a result, Statistical Static Timing Analysis or SSTA has replaced the traditional static timing in nano-meter scale VLSI processes. However, this poses a challenge regarding the max/min-plus algebra of Dijkstra like approximation algorithm that builds the Steiner trees. A new approach based on distance between distributions for nding maximum/minimum at the nodes is presented in this thesis. Under this metric, the approximation algorithm for variation aware timing driven congestion constrained routing is shown to be provably tight and one order of magnitude faster than existing approaches (which are not tight) such as the MVERT. The results (mean value) of our variation aware router are quite close to the mean of the several thousand Monte Carlo simulations of the deterministic router, i.e the results converge in mean. Therefore, instead of running so many deterministic Monte Carlo simulations, we can generate an average design with a probability distribution reasonably close to that of the actual behaviour of the design by running the proposed statistical router only once and at a small fraction of the computational e ort involved in physical design in the nano regime VLSI. The above approximation algorithm is extended to local routing, especially non- Manhattan lambda routing which is increasingly being allowed by the recent VLSI tech- nology nodes. Here also, we can meet delay driven constraints better and keep related wire lengths reasonable.