Discretized Network Flow Techniques for Timing and Wire-Length Driven Incremental Placement With White-Space Satisfaction

We present a novel incremental placement methodology called FlowPlace for significantly reducing critical path delays of placed standard-cell circuits without appreciable increase in wire length (WL). FlowPlace includes: 1) a timing-driven (TD) analytical global placer TAN that uses accurate pre-route delay functions and minimizes a combination of linear and quadratic objective functions; 2) a discretized network-flow-based detailed placer DFP that has new and effective techniques for performing TD/WL-driven incremental placement while satisfying row-width (white space) constraints; 3) new and accurate unrouted net delay models that are suitable for an analytical placer; and 4) an effective probability-based WL-cost function in detailed placement for reducing WL deterioration while performing TD-incremental placement. We ran FlowPlace on three sets of benchmarks with up to 210 K cells. Starting from WL-optimized placements done by Dragon 2.23, and using purely timing-driven incremental placement, we are able to obtain up to 33.4% and an average of 17.3% improvement in circuit delays at an average of 9.0% WL increase. When incorporating both timing and WL costs in the objective functions of global and detailed placement, the average WL increase reduces to 5.8%, a 35% relative reduction, while the average delay improvement is 15.7%, which is only relatively 9% worse. The run time of our incremental placement method is only about 10% of the run time of Dragon 2.23. Furthermore, starting from an already timing-optimized placement done by TD-Dragon, we still obtain up to 10% and an average of 6.5% delay improvement with a 6.1% WL deterioration; the run time is about 6% of TD-Dragon´s.