So e ara eters ecting Routabilit o G s

-

-

ntroduction

Field-Programmable gate arrays (FPGAs) are becoming popular for implementing Application Speci c Integrated Circuits (ASICs). FPGAs support very rapid prototyping with design realization times in the order of few hours. Devices can be configured into any desired functionality using software tools. These tools, also called CAD tools, can greatly affect the performance and realization of designs using FPGA technology. A circuit realization can be viewed as a two step process, namely:

1. Mapping of circuit to a set of pre-fabricated logic cells (technology mapping

2. Assignment of logic cells to physical locations on FPGAs (placement and configuration of routing architecture to interconnect cells (routing

The problem of technology mapping has been addressed in [4, 6, 10] and more. The problem of routing for FPGAs has been addressed in [2, 8]. The problem of placement has not been addressed for FPGAs. Our study addresses the issues related with routing in an FPGA architecture called logic cell arrays (LCAs). The architecture is very popular and has been pioneered by Xilinx [12]. Our results directly impact the design decisions for FPGA architecture and CAD tools. Based on experimental evidence, we also recommend a set of properties that should be fine tuned inorder to achieve enhanced routability. The routability of a net is the probability of the net being routed in the shortest possible distance.

In this paper, we study the effect of various properties of the routing architecture and CAD tools on the overall routability for an FPGA. In particular, we study the effect of