|
Frontier: A Fast FPGA Floorplanning and Routing System for
Reconfigurable Computing.
Abstract
With recent advances in silicon device technology,
a new branch of computer architecture, reconfigurable
computing, has emerged. While this computing domain holds the promise
of exceptional fine-grained parallel performance, the amount of time
required to compile a program to a reconfigurable computing
platform can be prohibitive for many applications.
A large portion of this compile time is typically spent performing
device layout for field-programmable gate arrays (FPGAs),
the core hardware components of most reconfigurable computing systems.
In this talk, I discuss an integrated
floorplanning and routing system, called Frontier, designed to
optimize FPGA layout time at the cost of modest increases in device
logic and routing resources. Experimental results are presented which
demonstrate an order of magnitude speedup over traditional layout approaches
for an array-based FPGA architecture.
A key part of the Frontier system is a depth-first router that significantly
reduces the search space required for FPGA routing and leads to
decreased run time when compared to a traditional, breadth-first maze
router. In the talk, I show that for the depth-first case, the sparse
nature of planar switchboxes, found in array-based architectures,
necessitates an additional localized
search near net inputs, called domain negotiation, to aid in directing
the route of each design net onto a set of routing resources most
likely to lead to a successful route.
This router is tightly coupled with a macro-based floorplanner
based on hierarchical, slicing approaches. The floorplanner takes
advantage of a set of pre-placed and pre-routed macrocells that are
commonly found in a broad range of computing
applications. The depth-first router is used to rapidly identify
congested areas in the floorplan and drive a feedback-driven floorplan
relaxation phase.
|