Backpass Trees on a Mixed Route Graph for Accelerated FPGA Routing

One of the main advantages of FPGA design flow compared with ASICs and uncommitted logic arrays is the implementation speed of required functionality on a chip. However, any attempts to improve the final characteristics of designed circuits lead to an increase in the design flow time in most cases. Therefore, creating effective computer-aided design tools for modern FPGA that consider both these aspects is essential. This work proposes an approach to accelerate the routing stage in FPGA design flow by modification of a basic routing algorithm Pathfinder adapted to a mixed route graph. The modification is to create and use backpass tree structures that allow the implementation of a directed path search on a mixed route graph having no information about geometric coordinates of its elements. Benchmark sets used for testing are LGSynth’89, IWLS’2005, and a range of projects from opencores.org. The work of the algorithm was analyzed using four FPGA architectures. According to the analysis of experimental results the modified algorithm has demonstrated an average routing runtime reduction of 1.8 to 3.6 depending on the target FPGA.