An FPGA timing routing algorithm based on pathfinder and rip-up and retry approach

In order to improve timing performance of FPGA implementations, this paper presents an FPGA timing-driven routing algorithm that mixes PathFinder algorithm and the rip-up and retry approach. After execution of PathFinder algorithm, the proposed algorithm rips up the routed paths of nets influencing the critical path delay, and then incrementally reroutes these nets. During the rip-up and retry stage, the algorithm optimizes the path of critical connection and decreases critical path delay, by setting different criticalities for critical connection and non-critical connections. Experimental results demonstrated that the proposed method decreases 12.97% of critical path delay, while, compared with the VPR, the run time only increases by 4.87% on average.