An Analytic and Clustering Based Approach for Timing-Driven Placement of Very Large Integrated Circuits

摘要

A novel approach for timing-driven placement of very large integrated circuits is presented. Our strategy is to apply clustering technique to a quadratic placement procedure. By clustering, the number of components for placement is reduced considerably. We design a high efficiency clustering algorithm, named CARGO, which has global optimality and runs very fast. We use a path-based timing-driven quadratic placement algorithm to complete the placement of the condensed circuit. Because quadratic based placement algorithm can mathematically find global optima in very short time, our new approach might be more promising for solving the problem thoroughly. We have tested our algorithm on a set of MCNC circuits and obtained satisfactory results.