Congestion and timing optimization for standard-cell placement

Standard-cell placement problem is a critical step in VLSI physical design process, and it becomes more and more difficult as VLSI system complexity continues to increase. In this dissertation, we present our Ph.D. research work on the following topics: (1) We build an efficient placement framework and implement a strong placement tool. We studied wirelength minimization problem for large industrial designs. Different cost functions including net cut, wirelength were studied in the hierarchical placement flow. We propose an top-down placement flow which combines multi-level partitioning and cluster based simulated annealing. (2) We propose two congestion estimation approaches for early placement stages. First, we theoretically analyze the peak congestion value of the design and experimentally validate the estimation approach. Second, we estimate regional congestion in the early top-down placement. This is done by combining the wirelength distribution model and inter-region wire estimation. (3) We present a novel method to reduce routing congestion during placement stage. The proposed approach is used as a post-processing step in placement. Congestion reduction is based on local improvement on the existing layout. However, the approach has a global view of the congestion over the entire design. It uses integer linear programming (ILP) to formulate the conflicts between multiple congested regions, and performs local improvement according to the solution of ILP. (4) We propose a white space allocation approach that dynamically assigns white space according to the congestion distribution of the placement. In the top-down placement flow, white space is assigned to congested regions using a smooth allocating function. A post allocation optimization step is taken to further improve placement quality. (5) We present a new methodology for delay budgeting based timing-driven placement. A novel slack assignment approach is described as well as its application on delay budgeting with design hierarchy information. The proposed timing-driven placement flow is evaluated using an industrial place and route flow. Experimental results show that considering design hierarchy is a promising way to handle timing optimization problem.