On Biased and Non-Uniform Global Routing Architectures and CAD Tools for FPGAs

Abstract

This report addresses the question of how, in terms of quantity and positioning, routing tracks should be distributed across a Field-Programmable Gate Array (FPGA). Since all routing resources in an FPGA are prefabricated, it is essential that FPGA architects distribute these resources in a manner that can be most efficiently used by the largest class of circuits. The first question we address is whether horizontal and vertical channels should contain the same number of tracks (capacity), or if there is a density advantage to a directional bias. This question is motivated by the fact that commercial FPGAs with both biased and unbiased routing exist, yet no attempt has been made to determine which alternative is superior. Second, should the channels across an FPGA have uniform capacity, or should the capacities vary from channel to channel? This question is motivated both by the widespread belief among FPGA architects that wider channels in the center of an FPGA should help routability, and by the fact that the most recent devices from two FPGA vendors have included non-uniform routing structures.

To evaluate FPGAs with directionally-biased and non-uniform routing architectures, we have developed placement and routing algorithms and tools that exploit these features directly. We employ an experimental methodology in which many benchmark circuits are placed and routed on FPGAs with widely varying global routing architectures.

The key (and surprising) result is that the most area-efficient global routing structure is one with completely uniform channel capacities, across the entire chip and in both horizontal and vertical directions. The reason is that most circuits have routing demands which are reasonably evenly spread across an FPGA, and so they map best to a uniform routing architecture. The only (slight) exception we found to this "uniform is better" rule occurred when the I/O pad locations were fixed in poor positions. In this case, a 25% wider I/O channel was a net benefit.

Although the uniform architecture is the most area-efficient, we also find that highly non-uniform and directionally-biased architectures are not terribly inefficient, provided that appropriate choices are made for the pin positions on the logic blocks or for the aspect ratio of the chip logic array. We also found that by choosing the directional bias of the routing appropriately, one can increase the IO-to-logic ratio by making chips rectangular with little impact on the core area.

While these issues have been widely discussed, to our knowledge this is the first comprehensive study on the subject of the global routing architecture of FPGAs.

Back to my home page.