Analytical Placement for FPGAs

Placing a technology-mapped netlist of logic blocks onto a 2D array of pre-fabricated con gurable logic blocks (CLB) on a eld programmable gate array (FPGA) chip is a classical problem. However, the increasing design complexity of modern circuits has reshaped this problem and made traditional FPGA placement techniques not appropriate anymore. Traditional simulated-annealing-based FPGA placers, placers which can achieve very high-quality placements, have been dominating for decades. Nevertheless, for modern high-complexity designs, they are not scalable while maintaining high quality. Recently, industry has migrated to another technology called analytical placement which is expected to better handle the scalability issue in high-complexity designs. Therefore, developing and applying analytical methods have become inevitable trends for FPGA placement. In this thesis, we propose a multilevel timing-and-wirelength-driven analytical placement algorithm for FPGAs. Our proposed algorithm consists of (1) multilevel timing-and-wirelength-driven analytical global placement with block alignment consideration, (2) partitioning-based legalization, (3) wirelength-driven block matching-based detailed placement, and (4) timing-driven simulated-annealing-based detailed placement. Our proposed ap- proach is not only faster than the well-known, state-of-the-art academic simulated-annealing-based FPGA placer VPR but also better than VPR in terms of critical path delay and total routed wirelength. More speci cally, our proposed method can achieve 6.91 X speedup on average with 7% smaller critical path delay and 1% shorter routed wirelength compared to VPR.