Towards Scalable Placement for FPGAs

Hannah Bian,  Andrew Ling,  Jianwen Zhu,  Alexander Choong
University of Toronto


Abstract

Placement based on simulated annealing is in dominant use in the FPGA community due to its superior quality of result (QoR). However, given the progression of FPGA device capacity to the order of 100K LUTs, the long runtime associated with simulated annealing warrants a revisit of other placement paradigms in the context of FPGAs. In this paper, we attempt to make a rigorous comparison of a recent crop of academic ASIC placers and VPR when applied to modern FPGA device features and design sizes. We also report a new detailed placer, MDP, based on a new problem formulation of maximum-bipartite matching. We show that MDP is 3X to 7X faster than the detailed placer in FastPlace, which until now has been the fastest detailed placer publicly available. Furthermore, this speedup occurs while producing comparable or superior QoR. With these results, we speculate promising research directions towards scalable, high quality FPGA placement flows that can change the user experience from an overnight wait-time to a coffee break wait-time -- even on large benchmarks.