Timing-Driven Placement Optimization Facilitated by Timing-Compatibility Flip-Flop Clustering

Abstract

Timing-driven placement optimization is applied incrementally in various parts of the flow, together with other timing optimization techniques, to achieve timing closure. In this work, we present a generalized approach for Lagrange-Relaxation-based timing optimization that is used to iteratively relocate gates, flip-flops, and local clock buffers, with the goal being to reduce timing violations. Cells are allowed to move within an appropriately positioned search window, the location of which is decided by force-like timing vectors covering both late and early timing violations. The magnitude of these timing vectors is determined by the value of the corresponding Lagrange Multipliers. The introduced placement optimization is applied in conjunction with a newly proposed flip-flop clustering algorithm that (re)assigns flip-flops to local clock buffers, to separate flip-flops with incompatible timing profiles and to facilitate the subsequent timing-optimization steps. The proposed approach is tested on the ICCAD-2015 benchmarks, providing the best overall results when compared to state-of-the-art timing-driven placement techniques.