Segmented Routing for Speed-Performance and Routability in Field-Programmable Gate Arrays
Abstract
This paper addresses several issues involved for routing in
Field-Programmable Gate Arrays
(FPGAs) that have both horizontal and vertical routing channels, with
wire segments of various
lengths. Routing is studied by using CAD routing tools to map a set of
benchmark circuits into
FPGAs, and measuring the effects that various parameters of the CAD
tools have on the implementation
of the circuits. A two-stage routing strategy of global followed by
detailed routing is
used, and the effects of both of these CAD stages are discussed, with
emphasis on detailed routing.
We present a new detailed routing algorithm designed specifically for
the types of routing
structures found in the most recent generation of FPGAs, and show that
the new algorithm
achieves significantly better results than previously published FPGA
routers with respect to the
speed-performance of implemented circuits.
The experiments presented in this paper address both of the key
metrics for FPGA routing
tools, namely the effective utilization of available interconnect
resources in an FPGA, and the
speed-performance of implemented circuits. The major contributions of
this research include the
following: 1) we illustrate the effect of a global router on both
area-utilization and speed-performance
of implemented circuits, 2) experiments quantify the impact of the
detailed router cost
functions on area-utilization and speed-performance, 3) we show the
effect on circuit implementation
of dividing multi-point nets in a circuit being routed into
point-to-point connections, and 4)
the paper illustrates that CAD routing tools should account for both
routability and speed-performance
at the same time, not just focus on one goal.
Reference
Stephen D. Brown, Guy Lemieux, and Muhammad Khellah, "Segmented Routing for Speed-Performance and Routability in Field-Programmable Gate Arrays," Journal of VLSI Design, Vol. 4, No. 4, 1996, pp. 275-291.
(Download Full Paper)