A fast recursive detailed routing algorithm for hierarchical FPGAs

Traditional sequence based routing algorithms for FPGAs usually route only one net at a time, so as to simplify the routing problems. However, with the number of logic blocks in the FPGAs becomes larger and larger, the time need to route each net can increase significantly. A new recursive detailed routing algorithm is proposed to address this problem. As decided by its recursive nature, this algorithm can only be applied for hierarchical FPGAs, which of the architectural features with its connection patterns is also presented in detail in this paper. The overall algorithm begins its routing from the topmost cluster and continues to route for each cluster from top down recursively, where the routing clusters map to the architectural cluster exactly. At each cluster level, a new heuristic is proposed to solve the specific routing problem. The scale of the problem is so small that the heuristic can be considered deterministic and quickly to solve. The proposed algorithm also takes advantages of the architectural features such as the connection patterns of switch box. As a result, the proposed algorithm is very fast in runtime due to all these facts. The experimental results show that detailed routing for a very large circuit can be done very quickly in just a few seconds.