SEGMENTED ROUTING FOR SPEED-PERFORMANCE AND ROUTABILITY IN FIELD-PROGRAMMABLE GATE ARRAYS

This paper addresses several issues involved for routing in Field-Prog rammable Gate Arrays (FPGAs) that have both horizontal and vertical ro uting channels, with wire segments of various lengths. Routing is stud ied by using CAD routing tools to map a set of benchmark circuits into FPGAs, and measuring the effects that various parameters of the CAD t ools have on the implementation of the circuits. A two-stage routing s trategy of global followed by detailed routing is used, and the effect s of both of these CAD stages are discussed, with emphasis on detailed routing, We present a new detailed routing algorithm designed specifi cally for the types of routing structures found in the most recent gen eration of FPGAs, and show that the new algorithm achieves significant ly better results than previously published FPGA routers with respect to the speed-performance of implemented circuits. The experiments pres ented in this paper address both of the key metrics for FPGA routing t ools, namely the effective utilization of available interconnect resou rces in an FPGA, and the speed-performance of implemented circuits. Th e major contributions of this research include the following: 1) we il lustrate the effect of a global router on both area-utilization and sp eed-performance of implemented circuits, 2) experiments quantify the i mpact of the detailed router cost functions on area-utilization and sp eed-performance, 3) we show the effect on circuit implementation of di viding multi-point nets in a circuit being routed into point-to-point connections, and 4) the paper illustrates that CAD routing tools shoul d account for both routability and speed-performance at the same time, not just focus on one goal.