Browse Theses

Placement is an important step in the physical design of VLSI chips. The exponential growth of on-chip complexity has dramatically increased the demand for scalable optimization algorithms for large-scale physical design. Modern designs, due to the constraints involved, have posed tremendous challenges to placement algorithms. In this Ph.D. dissertation, we focus on several aspects of constraint-driven placement algorithms.

First, we study extensively the optimality and scalability of wirelength-driven and timing-driven placement algorithms. For the first time, our study reveals the gap between results produced by state-of-the-art placement algorithms and the true optima. Experiment results show the wirelength produced by existing tools is 24% to 111% longer than the optima on average. The circuit delay produced by existing timing-driven placement tools is 4% to 18% longer than the optima on average.

Second, we propose a rout ability-driven multilevel placement workflow. We enhance the routability during global placement by re-placing cells to avoid congested regions. A congestion-driven white space allocation is applied after the global placement stage to provide appropriate routing resources to congested regions. Experiment results show that we achieve placements with the best routability among the publicly available placement tools, with all IBM-Dragon v2 easy and hard circuits successfully routed with 5% to 13% shorter wirelength.

Third, we propose a combination of the constraint-graph-based method and linear programming for mixed-size legalization. Using the legalization as a building block, we propose a three step mixed-size detailed placement algorithm, XDP. Experiments show that XDP can produce comparable or better results using placements generated by different global placement tools. Furthermore, XDP is 10X faster than its competitor on examples with more than 2M movable objects. The legalization algorithm has also been applied in each refinement level of global placement. Macros are selectively legalized and fixed. Experiments show that this scheme can help to reduce the final wirelength by 6% and runtime by 25% on average. Experiments also show that with this legalization algorithm, a 12% reduction in wirelength can be obtained compared to all macros pre-fixed.

Fourth, we propose the first analytical placement algorithm for heterogeneous placement, mPL-H. Based on the multilevel generalized force-directed formulation, the algorithm creates multiple layers, each corresponding to one type of placeable resource on the chip. Forbidden regions are pre-occupied by blockages. Filler cells are introduced to enhance the quality and stability of the algorithm. When compared to a leading edge commercial placer for FPGA, mPL-H produces 3% shorter half-perimeter wirelength and 2% shorter routed wirelength on average. mPL-H also shows better scalability when the circuits become sufficiently large. With more than 4K movable objects, mPL-H is 2x faster.