An Efficient Routability-Driven Analytic Placer for Ultrascale FPGA Architectures

Field Programmable Gate Arrays (FPGAs) continue to find increasingly wide use in commercial products as a good trade-off between CPU and ASIC, due to their flexibility and versatility. The increasing complexity and scale of modern FPGAs impose great challenges on the FPGA Computer-Aided Design (CAD) flow. However, within the FPGA CAD flow, placement remains one of the most important, time-consuming steps. In this thesis, we developed two novel routability-driven analytic placement tools for Xilinx UltraScale architectures, GPlace-pack and GPlace-flat. The former (GPlace-pack) placed third in the ISPD 2016 Routability-driven Placement Contest for FPGAs. The later (GPlace-flat) is a flat analytic placer which incorporates several unique features including a novel window-based procedure for satisfying legality constraints in lieu of packing, an accurate congestion estimation method based on modifications to the pathfinder global router, and a novel detailed placement algorithm that optimizes both wirelength and external pin count. Experimental results show that compared to the top three winners at the recent ISPD'16 FPGA placement contest, GPlace-flat is able to achieve (on average) a 7.53%, 15.15%, and 33.50% reduction in routed wirelength, respectively, while requiring less overall runtime. Despite the superiority results that are achieved by GPlace-flat compared to the state-of-the-art placers, there is no one best flow for all benchmarks. Therefore, we present a general machine-learning framework, that seeks to address the disconnect between different stages of the FPGA CAD flow that adversely affect the quality of results of the implemented designs.