Frontier: A Fast FPGA Floorplanning and Routing System for Reconfigurable Computing.
AbstractWith 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.