Abstract
We describe a routing method for the design of a class of RAM-based field programmable gate arrays (FPGA). We model the interconnect resources as a graph. A routing solution is represented as a set of disjoint trees, each connecting all terminals of a net, on the graph. An expansion router is used for connecting a net. Initially, nets are connected independently of one another. Conflicts among nets over the usage of interconnect resources are resolved iteratively by a rip-up and rerouter, which is guided by a simulated evolution-based optimization technique. The proposed approach has been implemented in a program called TRACER-fpga. As compared with CGE [2] and SEGA [3], TRACER-fpga in general requires fewer routing tracks at the expense of longer wiring delay. It is suitable for low-speed applications such as hardware emulation. © 1995 IEEE