A Fast Routability-Driven Router for Hierarchical FPGA

By using historical information of congestions to evaluate the routability and reroutability in congestion area and the influence of rip-up,the algorithm proposes another mechanism to resolve resource competition problem.Tabu nodes,rip-up nets and reroute paths are selected under the framework of tabu search,and relative strategies are applied to implement the mechanism,which simultaneously enhance the speed and the effectiveness of ripping up.The algorithm consists of two stages:initial routing process,rip-up and reroute process,during which it proposes an effective but simple scheme of routing.Experimental results show the effectiveness of our algorithm on reduction of rip-up nets and a notable enhancement on running speed,compared with PathFinder.