Backpass Trees for Modifying PathFinder-based Routing Algorithm for FPGA

In the field-programmable gate array and programmable system-on-a-chip design flow routing is a highly time-consuming stage that provides the last opportunity to make any design optimizations. Therefore, reducing its runtime with no significant losses in a quality of result occurs to be an extremely important problem to solve. This paper proposes a modification of a PathFinder-based algorithm to implement a directed search technique which contributes FPGA routing acceleration. The main idea is to direct the searching process by routing graph connectivity consideration in a form of backpass trees. The modification is relevant for the situation when there are no geometric coordinates known for FPGA/PSoC routing resources. The modified algorithm was tested on IWLS’2005 and some commercial benchmark sets. The obtained experimental results demonstrate an average runtime reduction by 10% while the average critical path delay and wirelength slightly increase (1.8% and 0.3% respectively) caused by usage of the introduced backpass trees structures.