Certified by...............

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 thesis, an new integrated floorplanning and routing system for FPGAs, called Frontier, is detailed. This system has been 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 island-style 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 thesis, it is shown that for the depth-first case, the sparse nature of plana