Fundamental algorithms for physical design planning of VLSI

Rapid advances in semiconductor technologies have led to a dramatic increase in the complexity of VLSI circuits. With fabrication technology entering deep submicron era, devices are scaled down, more functionalities are integrated into one chip, and chips run at higher clock frequencies. Handling the extremely large designs with ever-increasing clock rates, while reducing design turnaround time and ensuring timing convergence, is exhausting the capabilities of traditional design tools. Thus careful up-front design planning, analyzing physical implementation effects before the actual place-and-route, is essential in designing today’s multi-million and future’s billion gate ICs. We study several fundamental problems of VLSI physical design planning in this dissertation. In floorplanning, we develop a floorplanner FAST-SP based on sequence pair floorplan representation. A new approach is proposed to evaluate a sequence pair based on computing longest common subsequence in a pair of weighted sequences in

    time. Our evaluation algorithm is significantly faster than

the previous

graph-based algorithm. For all MCNC benchmark problems, we obtain the best results ever reported in the literature with significantly less runtime. Placement constraints are important in floorplanning. We consider fixedframe floorplanning and extend FAST-SP to handle placement constraints such as pre-placed constraint, range constraint, boundary constraint, abutment constraint, alignment constraint, rectilinear shape constraint, and performance constraint. We propose a uniform method to deal with all these constraints. Buffer planning is a key component in design planning. We present a new approach to buffer planning based on network flow computation. Our algorithm optimally solves the problem of inserting maximum number of buffers into the free space between the circuit blocks with minimum total cost in polynomial time. Buffered routing tree construction is essential in wire planning. We consider the problem of constructing routing trees with simultaneous buffer insertion and wire sizing in the presence of routing and buffer obstacles. A new graph-based approach is proposed to solve the problem. Both theoretical and experimental results show that the graph-based algorithm outperforms the previous DP-based algorithm by a large margin. Routing resource allocation or distribution is a key issue in wire planning. We need to minimize the use of routing resource while satisfying the delay constraints. Thus we study the problem and extend the graph-based algorithm to solve it. We also develop a hierarchical approach to buffered routing tree construction to tradeoff runtime and routing quality.