On Detailed Routing for a Hierarchical Scalable Reconfigurable Array
With Constrained Switching Capability
. . .
. . .
In modern FPGA CAD flow, netlist routing on a particular routing
architecture is solved in two steps, global routing based on wire
bandwidth constraints of the architecture, and subsequent detailed
routing based on the finer switching constraints of the architecture.
Reducing or constraining switching resources is desirable for reducing
an FPGA's circuit area and power consumption, though it typically
makes detailed routing more difficult. Detailed routing is provably
NP-complete in popular 2-D mesh architectures with constrained
switching flexibility, as in the Xilinx 4000 series FPGAs.
Wu et al. have presented a tree-based
routing architecture with constrained switching flexibility which has
a polynomial algorithm and guarantees for detailed routing but which
has non-scalable bandwidth. In this paper
we study approaches to detailed routing for a scalable fat-tree
routing architecture with restricted switching topology, in which
routing bandwidth scales according to Rent's Rule. We discuss several
formulations and frameworks for solving the detailed routing problem,
using such techniques as graph coloring, multicomodity flow, integer
linear programming, and satisfiability.
This report describes a course project for
"Combinatorial Algorithms and Data Structures"
Computer Science department,
spring 1998 semester.
Last updated: 4/29/98