CS-270 Course Project:

On Detailed Routing for a Hierarchical Scalable Reconfigurable Array With Constrained Switching Capability

Eylon Caspi . . . Randy Huang . . . Christoforos Kozyrakis

Abstract

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.

Report

Gzipped PostScript version

People

Eylon Caspi
Randy Huang
Christoforos Kozyrakis
Christos Papadimitriou -- course professor
André DeHon -- project guidance

The Course

This report describes a course project for Christos Papadimitriou's graduate course, "Combinatorial Algorithms and Data Structures" at U.C.Berkeley's Computer Science department, spring 1998 semester.

Last updated: 4/29/98
Comments to: eylon@cs.berkeley.edu