Force-directed performance-driven placement algorithm for FPGAs

We propose a net-based force-directed performance-driven placement algorithm for hierarchical FPGAs. The input netlist is first transformed into a net dependency graph. Then we partition this graph into clusters and a net-cluster level floorplan is derived by simulated annealing. Force-directed net placement is performed to generate a coarse net-level placement. Next, a force-directed logic cell placement is computed iteratively. Finally, we assign I/O pins using a modified Munkres´ algorithm. The main contribution of our work is that we apply force-directed method in hierarchical FPGAs to improve delay as compared to Xilinx tools. We improve the post-layout delay and average connection delay by an average of 10.2% and 19.3% respectively over a set of MCNC combinational benchmark. We also improve the maximum clock frequency by an average of 20.7% over a set of MCNC sequential circuits.