Min-Max Placement for Large-Scale Timing Optimization

At the 250nm technology node, interconnect delays account for over 40 % of worst delays [12]. Transition to 130nm and below increases this figure, and hence the relative importance of timing-driven place-ment for VLSI. Our work introduces a novel minimization of maxi-mal path delay that improves upon previously known algorithms for timing-driven placement. Our placement algorithms have provable properties and are fast in practice. Empirical validation is based on extending a scalable min-cut placer with proven quality in wirelength-and congestion-driven placement [4]. The CPU overhead of the timing-driven capability is within 50%. We placed industrial circuits and evaluated the resulting layouts with a commercial static timing ana-lyzer