Research On Efficient FPGA Routing Algorithm

Field programmable gate arrays(FPGAs)are semi-custom circuits in integrated circuit field.FPGAs have many advantages such as design flexibility,low cost,abundant logic resources and so on,and hence have been widely used in designing digital system.FPGA Electronic Design Automation(EDA)softwares compile the circuits designed using hardware description language(HDL)to bitstream.The bitstream can be used to configure the programable physical devices within the FPGAs,such as switches,to accomplish the functions of circuits on the FPGAs.However,with the increasing scale of FPGAs and circuits,the FPGA EDA softwares consume more CPU time to compile the circuits,which reduces the competitiveness of FPGAs and thus restricts the development of FPGAs.Accordingly,a lot of researchers have focused on improving the efficiency of FPGA EDA softwares.The FPGA EDA flow mainly consists of circuit designing,behavior synthesis/logic synthesis,technology mapping,packing,placement and routing.Routing is one of the most time-consuming steps in the FPGA EDA flow and directly affects the performance of the final circuits.However,there are some shortcomings in the existing routing algorithms:(1)the algorithms are time intensive,which lengthens the compile-debug cycle and reduces the efficiency of circuit development;(2)the routed circuits perform poorly.To overcome the above problems,this paper focus on efficient FPGA routing.The main work is summarized as follows:First of all,we propose a novel runtime optimization FPGA routing algorithm using efficient rerouting strategy.This FPGA routing algorithm iteratively routes circuits nets until a feasible routing result is obtained.During the routing process,the paths satisfying the set conditions are referred to as low-quality paths.Both congested paths and low-quality paths are called illegal paths.In each iteration,with the improved re-routing strategy only illegal paths are ripped-up and re-routed,which reduces the number of paths to be re-routed.When routing a sink,the proposed algorithm invokes an improved maze router to search for the target sink on the routing resource graph;in the initialization phase of the maze routing,the improved maze router adds only relatively close part of the current routing tree to the maze routing wavefront,which avoids the long initialization time when the current routing tree is very large.Experimental results show that the proposed routing algorithm reduces routing runtime by 68.5% compared with VPR timing-driven router,and the critical path delay and total wirelength by 2.5% and 1.4% respectively.Secondly,we propose a parallel FPGA routing algorithm based on hybrid net partitioning approach and parallel strategy.The parallel routing algorithm consists of two phases: nets partition and parallel routing.During the nets partition,in order to solve the problem of partitioning large nets,the nets are partitioned into two groups of sets: conflict sets and overlapping sets.The nets in different overlapping sets do not overlap each other while the nets in the same conflict sets do not overlap each other.In each routing iteration,we apply different parallel routing strategies for the two groups of sets so as to reduce the interfere between threads and thus increase the routing parallelization.When routing the nets in conflict sets,on the whole the routing iteration routes conflict sets one by one.For each conflict set,the illegal paths of the nets are evenly distributed among the threads,so that the threads route almost the same number of sinks.When routing the nets in overlapping sets,a different parallel routing strategy is applied by which each thread is assigned with an overlapping set and re-routes the illegal paths of the nets.Experimental results show that the proposed parallel routing algorithm achieves a 24.3× speedup using 16 threads when compared with VPR timing-driven router,while keeping the quality of results unchanged.Finally,we develop the supporting tools of the runtime optimization FPGA routing algorithm and parallel FPGA routing algorithm.The supporting tool of the runtime optimization FPGA routing algorithm is implemented in VPR framework.During the routing process,each iteration preserves the routing results of nets by using routing trees.In this way,the following routing iteration can reroute the illegal paths on the routing trees according to the new rerouting strategy.Experimental results show that the FPGA routing tool significantly reduces routing runtime while maintaining the quality of results.In addition,we develop a supporting tool of the proposed parallel routing algorithm by using Open MP parallel programming technology.The parallel FPGA routing tool includes hybrid net partitioning and parallel routing.During the hybrid net partitioning process,the main thread invokes a recursive partitioning function to partition the FPGA into several regions.Nets in the same region form an overlapping set,and the nets cross several regions are further partitioned into a number of conflict-free sets.During the parallel routing process,the threads adopt two different parallel routing strategies to route the conflict-free and overlapping sets respectively.After the threads route all of the nets,the main thread performs timing analysis of the circuit and checks the routing result.Experimental results show that the parallel FPGA routing tool accelerates FPGA routing,and its routing performance is better than the state of art FPGA routing tools.