Timing-driven routing for FPGAs based on Lagrangian relaxation

摘要: As interconnection delay plays an important role in determining circuit performance FPGAs, timing-driven FPGA routing has received much attention recently. In this paper, we present a new algorithm for FPGAs. The finds with minimum critical path given placed using the Lagrangian relaxation technique. multipliers used to relax timing constraints are updated by subgradient method over iterations. Incorporated into cost function, these guide router construct tree each net. During routing, exclusivity on resources also taken care of route circuits successfully. Experimental results benchmark show that our approach outperforms state-of-the-art VPR router.