A Mini-Review of Methods for Forecasting Post Routing Congestion from Placement in FPGA Physical Design

Placement and routing are two time-consuming steps in the FPGA physical design flow and can take hours or even days. The placement steps map the logic elements of the netlist onto the computational resources of the FPGA, and the routing step is responsible for finding paths to connect the logic blocks through the FPGA routing fabric. The routing resources have a fixed capacity; using them beyond their capacity results in congestion. Congestion can cause routing failures and make it difficult to achieve timing closure and the placement algorithms should produce solutions that do not generate congestion in routing. Researchers have employed many approaches, from elementary ways (e.g., counting the number of pins) to accurate artificial intelligence-driven methods. This article categorizes congestion estimation methods developed over the last 25 years, providing an overview and survey of methods belonging to each category. To aid in understanding, simple experiments are included to illustrate each method's application. Finally, the article concludes by outlining potential future research directions in the field.