FPGA routing is a well studied problem. Basic point-to-point routing of nets on FPGA fabrics can be done optimally using well known shortest path algorithms like Dijkstra's and A-star. Practical rip-up and reroute algorithms like PathFinder have been very influential in various academic and industrial routers. The relaxed version of the routing problem, that ignores congestion, has a polynomial time-complexity. This allows us to easily determine the best-case timing performance of a placed design and the degradation introduced by the router due to congestion alleviation on the datapath. Is it possible for an industrial router to actually improve upon the best case timing performance? Modern FPGAs like the Xilinx Ultrascale+ family, have introduced major changes to the clocking architecture to help improve clock skews and also to support a large number of user clocks. The new clocking architectures also allow the router to perform low-cost time-borrow optimization and efficient high fanout net routing, to alleviate fabric congestion and simplify timing-closure. We describe various methods by which industrial FPGA routers take advantage of the clocking features to improve timing performance of placed circuit designs beyond the traditional best-case scenarios.

Interconnect planning is becoming an important design issue for large field programmable gate array (FPGA)-based designs. One of the most important issues for planning interconnection is the ability to reliably predict the routing requirements of a given design. In this paper, a new methodology, called fast generic routability estimation for placed FPGA circuits (fGREP), for fast and reliable estimation of routing requirements for placed circuits on island-style FPGAs, is introduced. This method is based on newly derived detailed router characterizations that are introduced in this paper. It is observed that the router has a limited number of available routing elements to use and the number is proportional to the distance from a net's terminal. This is defined as the routing flexibility and an estimate for interconnect requirements is derived from it. This method is able to predict the distribution of interconnect requirements, with very fine granularity, across the entire device. The interconnect-distribution information is used to estimate congestion and total wirelength. Multiterminal nets are efficiently handled, without the need for net decomposition. This method is generic enough to enable its usage with any standard FPGA place-and-route design flow and for any island-style FPGA architecture. The method is also applicable to application-specific integrated circuit (ASIC) design flows. Experimental results on a large set of standard benchmark examples show that the estimates obtained here closely match with the detailed routing results of the state-of-the-art router PathFinder , as implemented in the well-known FPGA physical design suite VPR.

Interconnect management is a critical design issue for large field-programmable gate arrays (FPGA) based designs. One of the most important issues for planning interconnection is the ability to reliably and efficiently predict the interconnect requirements of a given design on a given FPGA architecture. Many interconnect estimation methods have been reported so far and the estimation problem is also under active research. From a CAD tool deployment point of view, comparing these estimation methods is very difficult because of the different reporting methods used by the authors. We make an argument for and propose a new uniform reporting metric, based on comparing the estimates with the results of an actual detailed router on both local and global levels. We then compare some of the well known and promising interconnect estimation methods using our new metric on a large number of benchmark circuits.

Interconnect planning is fast becoming an important design issue for large FPGA based designs. The fundamental requirement for interconnect planning is the ability to estimate the routing requirements of a given design. Many estimation methods for uniform island-style FPGA architectures have been reported. However, no estimation method targets the problem of estimating the interconnect requirements for timing driven physical design. Most estimation methods assume minimum cost routing, which underestimates the interconnect resource requirements when timing is of main concern. Timing driven physical design typically involves minimum delay routing which demands extra interconnects as compared to minimum-cost routing. We propose a new method to estimate the interconnect requirements of placed FPGA circuits, under timing driven domains. We compare our estimates with the detailed routing results produced by standard routing tools in the VPR [V. Betz et al., (1997)] design suite.

Interconnect management is a critical design issue for large FPGA based designs. One of the most important issues for planning interconnection is the ability to accurately and efficiently predict the routability of a given design on a given FPGA architecture. The recently proposed routability estimation procedure, fGREP [6], produced estimates within 3 to 4% of an actual detailed router. Other known routability estimation methods include RISA [5], Lois's [7] method and Rent's rule based methods [1] [11] [9]. Comparing these methods has been difficult because of the different reporting methods used by the authors. We propose a uniform reporting metric based on comparing the estimates produced with the results of an actual detailed router on both local and global levels. We compare all the above methods using our reporting metric on a large number of benchmark circuits and show that the enhanced fGREP method produces tight estimates that outperform most other techniques.