A fast routability-driven router for Hierarchical FPGAs based on Tabu search

In this paper, we propose a fast routability-driven routing algorithm for hierarchical FPGAs (HFPGAs), using several strategies to steer the automated process of rip up and reroute in order to speed up the process and reach the same effectiveness of Pathfinder´s negotiation mechanism. Net is expelled from congestion zone to resourceful zone. The algorithm is divided into two procedures. First, it generates an initial solution by routing nets in a descent order, then applies TS strategy to guide the generation of new solution during the iterations of rip-up and reroute. The process terminates when obtaining a feasible solution without congestion or when iteration time is out. Experimental results show the effectiveness of our algorithm both in quality and speed compared with Pathfinder.