Routing algorithms for field-programmable gate arrays

Field-Programmable Gate Arrays (FPGAs) have been one of the most popular devices for system prototyping, logic emulation, and reconfigurable computing. Their user-programmable prefabricated logic modules and routing structures provide low manufacturing cost and fast time-to-market implementation solutions to the users. However, the routing delay due to their inherent routing structure has been one of the biggest bottlenecks of their speed performance. As the VLSI fabrication feature size is shrunk to deep submicron dimension in modern technology, the portion taken up by routing in both of area and timing grows even more significantly. In this dissertation, we address issues on routing algorithms to optimize area and timing of an FPGA system. We present a new timing-driven routing algorithm for FPGAs. The algorithm finds a routing solution with minimum critical path delay for a given placed netlist using the Lagrangian relaxation technique. Lagrangian multipliers used to relax timing constraints are updated by subgradient method over iterations. Incorporated into the cost function, these multipliers guide the router to construct routing trees for the nets. Experimental results on benchmark circuits show that our approach outperforms the state-of-the-art VPR router. The routing channels of an FPGA consist of wire segments of various types, which provide the tradeoff between performance and routability. To fully exploit the potential of the routing architectures with various wire types, it is beneficial to perform appropriate assignment of wire types to routes for nets. We present a wire-type assignment algorithm that is based on iterative applications of mincost max-flow technique to simultaneously route many nets. At each stage of the network flow computation, we have guaranteed optimal result in terms of routability and total delay cost. Experimental results show that our algorithm can route more nets with smaller total delay. We also present a congestion-driven detailed routing algorithm. Using the min-cost flow approach, our algorithm routes all the nets connected to a common logic module simultaneously. At each stage of the min-cost flow computation, we guarantee optimal routing result for the nets connected to a logic block in terms of routability and total delay cost. To achieve better overall results, we adopt an iterative refinement scheme based on the Lagrangian relaxation technique. We compared the routing results with those from VPR router, and the results show that our router uses less or equal number of routing tracks with smaller critical path delay as well as total routing delay.