Multilevel routing for a higher degree of circuit integration

Routing is a well-researched problem in VLSI physical design. However, the advances in circuit design and manufacturing technologies have resulted in a higher degree of circuit integration, in the form of the shrinking technology size, increased chip size and total number of cells, and the vertical direction integration, i.e., the 3-D ICs. Such highly integrated designs bring new challenges to the routing tool. Routers are required to handle extremely large problems, as well as special constraints such as temperature, yield and manufacturability, etc. This thesis addresses two routing problems for highly integrated circuits: (1) the high complexity of full-chip routing, and (2) thermal-aware routing with thermal through-the-silicon via planning for 3-D ICs.;To handle the growing problem size, we propose MARS, a novel multilevel full-chip routing system. The multilevel framework with recursive coarsening and refinement allows for scaling of our gridless detailed router to very large designs. The downward pass of recursive coarsening builds the representations of routing regions at different levels while the upward pass of iterative refinement generates a gradually improved solution. We introduce a number of efficient techniques in the multilevel routing scheme, including resource reservation, multilevel graph-based Steiner tree generation, and history-based iterative refinement. Compared to a recently published three-level routing flow, MARS 1.0 helps improve the completion rate by over 10%, and speeds up the runtime by 11.7x. MARS 2.0 incorporates several new techniques, such as the segment packing-based routing resource model, flexible Steiner tree generation with pin propagation, and block map data structure for routing graphs. Compared to MARS 1.0, MARS 2.0 can improve the completion rate by 4.5% and the runtime by about 2x. In addition to high scalability, the multilevel optimization scheme also provides a powerful planning capability.;3-D IC has a great potential for improving circuit performance and degree of integration. It is also an attractive platform for system-on-chip or system-in-package solutions. A critical issue in 3-D circuit design is heat dissipation. In this thesis we propose an efficient 3-D multilevel routing approach that includes a novel through-the-silicon via (TS-via) planning algorithm. The proposed approach features an adaptive lumped resistive thermal model and a two-step multilevel TS-via planning scheme. Experimental results show that with multilevel TS-via planning, the thermal-aware approach can reduce the maximum temperature to the required temperature with a reasonable wirelength increase. Compared to a post-processing approach for thermal TS-via insertion, to achieve the same required temperature, our approach uses 80% fewer TS-vias. To our knowledge, this proposed approach is the first thermal-aware 3-D routing algorithm.;We also propose a much enhanced thermal through-the-silicon via (TTS-via) planning algorithm. We formulate the TTS-via minimization problem with temperature constraints as a constrained nonlinear programming problem (NLP) based on the thermal resistive model and develop an efficient heuristic algorithm (named m-ADVP), which solves a sequence of simplified via planning subproblems in alternating direction in a multilevel framework. The vertical via distribution is formulated as a convex programming problem, and the horizontal via planning is based on two efficient techniques: path counting and heat propagation. Experimental results show that the m-ADVP algorithm is more than 200x faster than the direct solution to the NPL formulation for via planning with very similar solution quality (within 1% of TS-vias count). Compared to our published work on the multilevel TS-via planning algorithm based on temperature profiling [CZ05a], the new algorithm can reduce the total TS-via number by over 68% for the same required temperature with similar runtime, thus improving the final completion rate by 3.2%.