Several New And Efficient Hybrid Routing Algorithms For FPGA

Digital circuits can be realized almost instantly using Field-Programmable Gate Arrays (FPGAs). However, it usually takes a couple of hours for CAD tools to generate FPGA programming bit-streams during compiling the large-scale circuits. Some designers even have to use more resources on a given FPGA or sacrifice the circuit speed in order to increase the compilation speed. Since a significant portion of the compilation time is spent on the routing stage, an efficient routing algorithm may reduce the routing time remarkably.A variety of routing algorithms have been developed and applied, among them the Boolean Satisfiability (SAT)-based routing algorithm and the geometric search routing algorithm are two most popular methods. However, they have different disadvantages. The SAT-based routing algorithm has problems in scalability, while the geometric search routing algorithm, though having the extensive rip-up-rerouting capability, has difficulty in achieving convergent routing solutions when the practical problem possesses tight routing constraints. Thus, in this thesis, we make efforts to explore a new and efficient algorithm to solve the above-stated problems. Detailed research work and results are listed below.Firstly, progress on the FPGA architectures is thoroughly reviewed. An FPGA routing architectural model, which is a symmetrical array (island-style) FPGA architecture based on SRAM, is determined to be the investigating object. The model needs only three appropriate parameters to represent the target routing architecture. The benchmarks from twenty large-scale circuits of Microelectronics Center of North Carolina (MCNC) are selected so that all the routing algorithms can work on the same platform. Thirty placements for each circuit are generated using VPR399 before running any routing algorithms. Thus all the routing algorithms can be run directly on these pre-placed circuits.Secondly, four geometric search routing algorithms are studied in detail, including a basic maze-running routing algorithm (Lee), a negotiation-based performance-driven routing algorithm (PathFinder), a fast timing-driven routing algorithm (VPR430) and a negotiated A* routing algorithm for FPGAs (Frontier). The four routing algorithms are evaluated based on their performance on the same large benchmark circuits. Comparison results suggest that PathFinder spends much less CPU time and has a significant reduction in the standard deviation of the CPU time than Lee. On the other hand, comparing to Pathfinder, VPR430 and Frontier can save CPU time by 59.7% and 86.9%, and improve the stability by 41.0% and 81.3%, respectively. So, from the viewpoint of routing speed and stability, the order of excellence of the four algorithms can be ranked in the following sequence, Frontier, VPR430, PathFinder, Lee.Thirdly, we investigate a general SAT-based routing concept and introduce this concept into the detailed routing method for FPGA. Two typical SAT-based detailed routing formulas, the track-based formula (T-SDR) and the route-based formula (R-SDR) were analyzed and compared. The distinguishable advantages of T-SDR are: 1) simultaneous net embedding, 2) routability decision (or estimation) and 3) flexible formulation ability. However, the running time for some large benchmark circuits is often too long due to the enormous flexibility captured in the routing solution space. In contrast to T-SDR, R-SDR is able to represent "exclusivity" routing constraints in efficient expressions requiring only 2-literal CNF clauses, so yields more compact SAT instances, and is, thus, more efficient. Experiment results show that the CPU time spent by T-SDR and the corresponding standard deviation are 31.4 and 36.8 times of those by R-SDR, respectively, indicating that R-SDR is more stable and efficient than T-SDR.We also performed experiment comparisons between R-SDR and the conventional geometric routing algorithms, PathFinder, VPR430 and Frontier. Results show that the CPU time and its standard deviation by R-SDR is 1.2 and 1.1 times of those by PathFinder, respectively. So, from the viewpoint of routing speed and stability, R-SDR is inferior to the geometric search routing algorithm. The primary reason is that R-SDR is a detailed routing algorithm, which is usually constrained more by the single global routing configuration provided by the global router regardless of quality.Then, we proposed three hybrid approaches that integrated Boolean-based FPGA routing (R-SDR) with the state-of-the-art routine FPGA routing algorithms (PathFinder, VPR430 and Frontier), abbreviated as P-R-SDR, V-R-SDR and F-R-SDR, respectively. By doing this, we are not only able to overcome the major shortcoming of the Boolean-baste FPGA routing algorithm (i.e., the scalability problem), but also able to compensate the typical defects of conventional routing algorithms, i.e., the net-ordering dependence and the disability of proving unroutability. Experiment results show that, comparing to those pure geometric routing algorithms (PathFinder, VPR430 and Frontier), the new hybrid algorithms, P-R-SDR, V-R-SDR and F-R-SDR can reduce CPU time by 32.0%, 28.9%, 25.0%, and increase the stability by 24.1%, 25.0%, 29.1%, respectively. Further comparisons among the hybrid methods suggest that the order of excellence of F-R-SDR, V-R-SDR and P-R-SDR is similar to that of Frontier, VPR430 and PathFinder.Finally, we presented a formula suitable for subset-satisfiable Boolean SAT (sub-SAT) to solve the problem that SAT-based approaches cannot support partial solutions. By doing this, a"strict"SAT problem with N constraints can be transformed into a new"relaxed"one which is satisfiable only when no more than k variables (k<