A Fast FPGA Routing Algorithm Based on Repeated Search Avoidance

This paper presents a fast FPGA routing algorithm that reduces repeated search in order to improve the speed of FPGA routing.The algorithm divides into routability-driven algorithm and timing-driven algorithm.By transforming the routed path of each net into routed paths of connections, routability-driven algorithm judges whether the path of every connection contains congested nodes or not.If the path of one connection contains congested nodes,it will be ripped-up and rerouted; otherwise,the path will be reserved.Criticality determinant strategy is employed to trade-off running speed and timing performance in timing-driven algorithm.Experimental results demonstrated that,the proposed routability-driven algorithm and timing-driven algorithm decrease 95.19% and 28.98% of runtime respectively,and critical path delay of timing-driven algorithm can be reduced by 4.80% on average,compared with VPR.