Timing-driven placement for regular architectures

We present a new iterative algorithm for timing-driven placement applicable to regular architectures such as field-programmable gate arrays (FPGAs). Our algorithm has two phases in each iteration: a compression phase and a relaxation phase. We employ a novel compression strategy based on the longest path tree of a cone for improving the timing performance of a given placement. Compression might cause a feasible placement to become infeasible. The concept of a slack neighborhood graph is introduced, and is used in the relaxation phase to transform an infeasible placement into a feasible one using a mincost maxflow formulation. The slack neighborhood graph approach used in the relaxation phase guarantees a bounded increase in delay during the relaxation phase. Our analytical results regarding the bounds on delay increase during relaxation are validated by the rapid convergence of our algorithm on benchmark circuits, We obtain placements that have 13% less critical path delay (on the average) than those generated by the Xilinx automatic place and route tool (apr) on technology-mapped MCNC benchmark circuits. The running time of our algorithm is significantly less than that of apr. Slack neighborhood graphs are of independent interest because they can also be used for timing-driven reconfiguration for yield enhancement and for handling incremental design changes efficiently