Light Search Algorithm for FPGA Routing Path

In order to address the long runtime issue of FPGA routing, a light search algorithm for FPGA routing path is presented. By predicting optimal nodes, the proposed algorithm computes and analyzes only the optimal nodes when searching for the shortest route, which improves the search efficiency. When the light search fails to find the sink, a new light search process is then started from the global optimal node, so as to improve the global search ability. In the search of global best nodes, only the suboptimal nodes that are promising to be on the lowest cost path are further analyzed which reduces the useless work. The proposed algorithm and VPR 8.0 are compared in terms of run-time and quality of results by using the VTR standard benchmark. Experimental results show that compared to the routing path searching algorithm in VPR 8.0, the proposed algorithm reduces the number of explored nodes by 41.8%, leading to a 31.3% runtime reduction. Meanwhile, the quality of results is basically unaffected.