Candidate
Jude Arun Selvan Jesuthasan
Title
Incremental Timing Driven Placement with Displacement Constraint
Supervisor
Andrew Kennings
Abstract
Incremental Timing Driven Placement with Displacement ConstraintIn the modern deep-submicron Very Large Integrated Circuit (VLSI) design flow interconnect delays are becoming major limiting factor for timing closure. Traditional placement algorithms such as routability-driven placement (improves routability) and wirelength-driven placement (reduces total wirelength) are no longer sufficient to close timing. To this end, timing-driven placement plays a crucial role in reducing the interconnect delay through timing critical paths (paths with timing violations/negative slacks) of the design and thereby achieving specific performance/clock frequency.
In the placement flow, timing information about the design can be incorporated during global placement and/or incremental/detailed placement. Although, over the years, there has been significant advances in the quality of the global placement, there is a growing need for high performance incremental timing-driven placement due to the lack of accurate interconnect information during global placement. Moreover, incremental timing-driven placement is essential to recover timing while preserving the other optimization objectives such as total wirelength, routing congestion, and so forth which are optimized at the early stages of the design flow.
This thesis proposes a simple, yet efficient, incremental timing-driven placement algorithm that seeks to find optimized locations for standard cells so that the total negative slack of the design can be maximized. Our algorithm consists two stages: (1) Global Move which positions standard cells inside a critical bounding box to eliminate timing violations on timing critical nets; and (2) Local Move which provides further timing improvement by finely adjusting the current locations of the standard cells within a local region.
We evaluate our algorithm using ICCAD-2014 timing-driven placement contest benchmarks. The results show that, on average, our technique eliminates 94% and 30% of the late and early total negative slacks, respectively, and, 82% and 27% of the late and early worst negative slacks, respectively, under short and long displacement constraints. The 1st place team of the contest improves late and early total negative slacks by 90% and 39%, respectively, and improves late and early worst negative slack by 76% and 32%, respectively. Taking into account both timing violation improvement and the placement quality (i.e., other objectives), on average, we outperform the 1st place team by 3% in terms of the ICCAD-2014 contest quality score and our technique is 4.6× faster in terms of runtime.