Physical placement driven by sequential timing analysis

Traditional timing-driven placement considers only combinational delays and does not take into account the potential of subsequent sequential optimization steps. As a result, the potential of re-balancing path delays through post-placement applications of clock skew scheduling and in-place retiming cannot be fully realized. In this paper we describe a new placement algorithm that is based on a tight integration of sequential timing analysis in the inner loop of an analytic solver. Instead of minimizing the maximum path delay, our approach minimizes the maximum mean delay on any circuit loop, thus enabling the full optimization potential of clock skew scheduling and in-place retiming. We present two versions of the new algorithm: one approximates sequential criticality and weights wires accordingly (Cong and Lim, 2000), the other extends this with the inclusion of explicit wire-length constraints for loops that limit the final clock period. Our algorithms are implemented using a hybrid, GORDlAN-style sequence of analytical placement steps interleaved with cell partitioning (Kleinhans et al., 1988). Our experiments on a set of large industrial designs demonstrate that the presented placement algorithm can minimize the contribution of interconnection delays to the clock period on average by 23.5% compared to a solution based on combinational delays.