Study Of New Hybrid Routing Algorithms For FPGA

Field Programmable Gate Array (FPGA) is digital integrated circuits containing reconfigurable logic blocks and routing resources. The programmable reconfiguration, as well as the great saving in processing cost and time, leads to wide applications for FPGA in communications, industry control, automotive electronics, data processing and consumer electronics, due to its flexibility, low rist and short research and development period. However, the corresponding computer aided design (CAD) tools have to be upgraded and optimized with the increasing number of reconfigurable blocks in FPGA. As the design becomes more and more complicated, it usually takes much longer time (eg., a couple of hours) for CAD tools to map a design to the FPGA device and meet the requirements of various parameters. Since the routing stage often consumes nearly 30% of the whole CAD flow time, it is of great importance to explore a high efficiency routing algorithm to reduce the whole FPGA flow time and satisfy all constraints.Currently, most FPGA routing algorithms are mainly based on the geometry searching and Boolean Satisfiability (SAT). Both types of algorithms have their own advantages and drawbacks. The geometry searching routing algorithms, all evolving from the basic Maze algorithm, can be optimzed to raise the routing speed, but they only route one wire each time, making it difficult to determine the routability. The algorithms are thus normally terminated by an up time limit setting. Meanwhile, all the other similar algorithms developed from the Maze algorithm have the disadvantage of high routing sequence dependence. SAT-based algorithms, however, can route all the wires at one time, making the routabilty theoretically provable. The problem is that these algorithms usually require a large number of variables and constraint clauses, making the scalability relatively poor.Recently, a routing algorithm based on Pseudo-Boolean Satisfiability (PB-SAT) becomes a hot topic. Similar to common SAT-based algorithms, the PB-SAT algorithm can route all the wires at the same time, and the routability becomes determinable. The good thing is that the PB-SAT routing algorithm can present the constraints in routing problem by simple clauses, reducing the numbers of variables and clauses significantly. Therefore, the memory requirement is greatly reduced and the scalability is obvisouly improved. On the other side, the PB-SAT routing algorithm still has lower routing speed than the traditional geometry searching algorithms. Thus a new hybrid routing algorithm (P-PB-SAT), combing the advantages of the PB-SAT algorithm and geometry searching ones, has been proposed. The major work and conclusions of this thesis are summarized as below.? Features of FPGA were firstly introduced and compared to Application Specific Integrated Circuits (ASICs). Common programming technologies, architectures and properties of FPGA were then analyzed. Finally, the Xilinx's island-based FPGA architecture was determined as the routing object for this work.? Three geometry searching routing algorithms, Lee Maze algorithm, A* algorithm and Pathfinder (a negotiation-based performance driven algorithm), were firstly introduced in detail. Two Boolean SAT routing algorithms, the track-based detailed SAT routing algorithm (T-SDR) and the route-based detailed SAT routing algorithm (R-SDR), were then analyzed. The experimental results show that both the routing time and the stability of R-SDR are a little weaker than those of Pathfinder (117.9% and 0.901 times, respectively). However, R-SDR can evaluate the routablity accurately in unroutable circuit bench cases, while Pathfinder can not.? The latest PB-SAT based routing algorithm was also studied and compared to SAT-based ones from the viewpoint of constraint presentations. The experimental results indicate that the routing time and the stability of PB-SAT algorithm fall between R-SDR and Pathfinder. The total routing time of PB-SAT algorithm is about 89.5% of R-SDR and 105.5% of Pathfinder, while the stability of PB-SAT algorithm is about 1.042 times of R-SDR and 0.939 times of Pathfinder; the total time of PB-SAT algorithm for evaluating unroutablity is about 91.9% of R-SDR.? Finally, a new hybrid routing algorithm (P-PB-SAT) was proposed by combing the PB-SAT algorithm and Pathfinder. The experimental results show that both the routing time and the stability of this new algorithm are superior to Pathfinder, R-SDR and PB-SAT. The total routing time of P-PB-SAT is only 55.3%, 47.4% and 52.5% of Pathfinder, R-SDR and PB-SAT, respectively, and the stability of P-PB-SAT is about 1.65, 1.83 and 1.76 times of the later three algorithms, respectively. Besides, the time of P-PB-SAT for evaluating unroutablity is about 88.2% of PB-SAT and 81.0% of R-SDR. All these results prove the high efficiency of this new hybrid routing algorithm.