Algorithmic and Theoretical Problems Related to the Physical Design of Three Dimensional Field Programmable Gate Arrays

Field Programmable Gate Arrays (FPGAs) have become an increasingly useful and important architecture in hardware design. As a flexible alternative to custom integrated chips, FPGA-implemented designs can be produced quickly and cheaply. However, this flexibility comes at a significant performance penalty. To help address this issue, we propose a family of three-dimensional FPGA architectures, with increased speed and smaller size as compared to existing 2D FPGAs. We implemented the first suite of tools for creating circuit designs for the new proposed architecture, and used these tools to demonstrate the efficacy of 3D FPGAs (e.g., 3D FPGA circuit mappings seem superior to those mapped to 2D ones). We explored several issues arising in the design of both 2D and 3D- FPGAs, and implemented two useful tools: (1) Spiffy, which performs placement and global routing simultaneously for 2D and 3D FPGAs, and (2) Gambit, which is the first tool to perform placement, global routing and detailed routing simultaneously, and which demonstrates the usefulness of conflict graphs. These tools yield superior solutions within reasonable runtimes, and employ a "template smoothing" technique which significantly improves the results at a modest runtime cost. Our results indicate that 3D FPGAs are a viable future architecture.