| Along the history of Very Large Scale Integration (VLSI), we have successfully scaled down the size of transistors, scaled up the speed of integrated circuits (IC) and the number of transistors in a chip - these are just a few examples of our achievement in VLSI scaling. It is projected to enter the nanometer (10-9m) scale era in the nearest future. At the same time, the scaling has imposed new challenges to physical synthesis. Among all the challenges, this thesis focuses on the following problems: (1) Increasingly domination of interconnect delay leads to a need in interconnect-centric design flows; (2) Different design stages (e.g. floorplanning, placement and global routing) have unmatched timing estimation, which brings difficulty in timing closure; (3) More and more VLSI circuits are designed in architectural styles, which require a new set of algorithms.;The paper consists of two parts, each of which focuses on several specific problems in VLSI physical synthesis when facing the new challenges. (1) Place and route aware buffer Steiner tree construction. Efficient techniques are presented for the problem of buffered interconnect tree construction under blockage and routing congestion constraint. This part also contains timing estimation and buffer planning for global routing and other early stages such as floorplanning. A novel path based buffer insertion scheme is also included, which can overcome the weakness of the net based approaches. (2) Circuit clustering techniques with the application in Field-Programmable Gate Array (FPGA) technology mapping. The problem of timing driven n-way circuit partitioning with application to FPGA technology mapping is studied and a hierarchical clustering approach is presented for the latest multi-level FPGA architectures. Moreover, a more general delay model is included in order to accurately characterize the delay behavior of the clusters and circuit elements. |
