Timing Driven Analytical Placement for FPGA

Abstract

Conventional Simulated Annealing (SA) based placement methods for FPGAs give best results in terms of wirelength and critical path delay. The runtime for these SA based methods is directly proportional to the total number of cells to be placed. In case of modern multi-million gate FPGAs, SA based methods for placement dominate the total runtime in the FPGA CAD flow. In this thesis, we propose a new fast and efficient timing driven analytical placement engine targeted at global placement for FPGAs followed by low temperature SA for detailed placement. Our global placement engine uses quadratic programming approach to minimize the wirelength and dynamic net weights based on timing criticality between the blocks to minimize the critical path delay. The placement engine proceeds by iteratively partitioning the placement area and making the Configurable Logic Blocks (CLBs) move near each partition's Center of Gravity (CG). After each iteration, to calculate the timing criticality between each CLB, they are snapped to physical grid locations. The placement engine uses this timing feedback to update the net weights and calculate new coordinates for the CLBs in the next iteration. We employ a spiral legalization method in the end to obtain a legalized placement which then undergoes low temperature Simulated Annealing in VPR to give comparable or better critical path delay and 8.7% bad overall wirelength after placement. Experimental results of 20 largest MCNC benchmark circuits show that our global placement engine outperforms the state-of-the-art academic placer VPR 7.0 in terms of runtime by 30% on an average, making it scalable and provides an overall similar QoR in terms of critical path delay.