Design automation for physical synthesis of VLSI circuits and FPGAs

We address the problem of delay optimization for VLSI circuits and FPGAs at the physical design stage. A new net-based statistical timing-driven partitioning algorithm demonstrates that circuit delay can be improved while the run-time remains virtually the same and the cutsize deterioration is insignificant. Because path-based timing-driven partitioning has the advantage that global information about the structure of the circuit is captured, we also propose multi-objective partitioning for cutsize and circuit delay minimization. We change the partitioning process itself by introducing a new objective function that incorporates a truly path-based delay component for the most critical paths. To avoid semi-critical paths from becoming critical, the traditional slack-based delay component is also accounted for. The proposed timing-driven partitioning algorithm is built on top of the hMetis algorithm, which is very efficient. Simulations results show that important delay improvements can be obtained. Integration of our partitioning algorithms into a leading-edge placement tool demonstrates the ability of the proposed edge-weighting and path-based approaches for partitioning to lead to a better circuit performance. We propose and develop means for changing a standard timing-driven partitioning-based placement algorithm in order to design more predictable (predictability is to be achieved in the face of design uncertainties) and robust (high robustness means that performance of the design is less influenced by noise factors and remains within acceptable limits) circuits without sacrificing much of performance. A new timing-driven partitioning-based placement and detailed routing tool for 3D FPGA integration is developed and it is shown that 3D integration results in significant delay and wire length reduction for FPGA designs.