Algorithms for physical mapping of circuits to field-programmable gate arrays

Field Programmable Gate Arrays (FPGAs) are programmable integrated circuits. Applications are typically mapped to FPGAs using a four step process: design entry, technology mapping, physical placement, and routing. Then a configuration file is downloaded to program the FPGA. Recent advances in fabrication technology and device architecture have resulted in tremendous growth in FPGAs, both in terms of density and performance. Currently commercial devices can map up to one million gate equivalent designs (and some newly announced commercial products will map over two million gate equivalent designs). Recent research has demonstrated the ability to clock FPGA circuits at 250 MHz. The advancement of computer aided design (CAD) tools and methods for mapping applications to FPGAs have not kept pace with hardware improvements. Typical mapping methodologies offer one of two alternatives: fast execution time resulting in low quality mappings or slow execution time resulting in high quality mappings. In this dissertation, we present methodologies to help bridge this gap and quickly provide high quality mapping results.; We present a two step algorithm that performs physical placement. Our first step performs two-dimensional placement with a cost function for reducing the mapped application's total wire length. The second step averages the delay through critical application paths. When used to place benchmark circuits, the two-step procedure demonstrates an average execution time speedup of 23× when compared to commercially available CAD tools.; We use our placement algorithms along with clustering techniques to implement a floorplanner for macro based applications. We use clustering to combine macros into pseudo modules or clusters. Then, we use our two-dimensional placement technique to place the clusters. We demonstrate this floorplanner on several macro based applications and compare the results to commercially available CAD tools.; Additionally, the programmable nature of FPGAs make it possible to partially reconfigure part of a mapped FPGA application without the necessity of reconfiguring the entire mapped application. We present a two-part methodology for incremental modification of previously mapped FPGA applications. The first part reconfigures the mapped application's programmable logic. The second part reroutes nets that have been previously routed through the FPGAs interconnection network.