Abstract
We study the layout optimization problem of integrated circuit design. First, we propose a performance-driven cell placement method based on a modified force-directed approach. After that, we utilize a 3-step preprocessing approach for whole chip detail routing. Finally, we develop a k-layer constrained via minimization algorithm. Placement and routing are two important steps in physical design of very large scale integrated circuits. They significantly affect layout area, routability and performance. Standard-cell-based layout style is very popular for semi-custom design because it enables the success of both synthesis methodology and automatic placement and route (APR) flow. In the past, many approaches have been proposed to optimize the layout quality via placement or routing process. In the very deep submicron era, large chip complexity, multiple metal layer, and wire delay dominance together call for re-investigation of these current solutions. Therefore, we implement a layout optimization system to achieve the timing-driven objective for very deep submicron design. We integrate our system into an industry design flow to evaluate the efficiency and effectiveness of our approaches. In the first part, we design a modified force-directed algorithm to perform timing-driven placement. A pseudo net is added to link the source and sink flip-flops of every critical path to enforce their closeness. Given a user-specified I/O pad locations at the chip boundary and starting with all core cells in the chip center, we iteratively move a cell to its force-balanced location assuming all other cells are fixed. The process stops when no cell can be moved farther than a threshold distance. Next, cell rows are adjusted one at a time starting from the top and bottom. After forming theses two rows (top/bottom), all movable core cells' force-balanced locations are updated. The row-formation-and-update process continues until all rows are adjusted and, hence, a legal placement is obtained. We also study the effect on both layout quality and CPU time consumption due to the amount of pseudo net added. We found that the introduction of pseudo net indeed significantly improves the layout quality. The next part is a preprocessor for a router. We propose a 3-step approach for net planning. In the first step, we construct a performance-driven Steiner tree for each net ignoring the existence of other nets. In the second step, we optimally assign significant wire segments of all trees to tracks of a two-dimensional, two-layer grid. Finally, in the third step, we complete the remaining local short connection between net terminals and those assigned wire segments and resolve any violations or congestion. We have incorporated this approach into an industrial VDSM design flow. Finally, we employ a new layer assignment approach for the k-layer constrained via minimization (k-CVM) to improve the layout quality further. We transform the k-CVM problem into a constrained k-way graph partitioning one. Practical issues such as pin-out constraint, over-the-cell constraint, and overlapping between wire segments of the same net, have all been taken into consideration. We also address the crosstalk issue. We propose a simulated-annealing based algorithm for this problem. A set of large routing results generated by a commercial four-layer router has been used to test the effectiveness of the program. This work is the first to demonstrate the feasibility of via minimization for practical-sized multi-layer layout.