Area optimizations in FPGA architecture and CAD

Field programmable gate arrays (FPGAs) are an increasingly popular implementation medium for digital circuits. An FPGA is a prefabricated piece of silicon that can be configured by the user to implement any digital circuit. This ability enables them to offer two key advantages over other implementation technologies: low cost and fast time-to-market. However, the flexibility they offer comes at a steep price. Circuits implemented in FPGAs are three times slower and ten times larger than an equivalent circuit implemented using standard cells or mask programmed gate arrays.; This dissertation presents area optimizations in FPGA architecture and CAD. The primary focus is on a new area efficient adaptive FPGA (AFPGA) architecture. An AFPGA is obtained from an FPGA by replacing a fraction of the configuration SRAM with adaptive SRAM whose functionality changes in response to changes in a control signal. Adaptive programmable structures (logic elements, multiplexers, and routing switches) are produced wherever adaptive SRAM is used, and the resulting structures can be shared by two subcircuits that are not required to "exist" simultaneously. To support the new architecture, a new CAD flow is proposed and a set of CAD tools are developed. A step called adaptation is introduced after technology mapping, but before packing, and helps identify subcircuits that can share a set of adaptive resources. Adaptation is shown to reduce circuit size by 28%. The packing problem for AFPGAs is shown to be quite different from FPGAs, and a new packing algorithm is developed. Finally, a tool that estimates the effects of clustering, placement, and routing on an AFPGA circuit is developed, and is used in conjunction with an area model to determine the area benefits of AFPGAs. Using the tool, AFPGAs are shown to reduce area by 8--14% compared to a similar FPGA architecture for cluster sizes with between 4 and 10 BLEs per cluster.; A secondary focus is on the area efficiency of the technology mapping step in a traditional FPGA CAD flow. An iterative technology mapping algorithm is presented, and is shown to produce depth optimal solutions that are 12--18% smaller than those produced by two leading academic technology mappers. Furthermore, the algorithm is shown to produce solutions that are 8--14% smaller than those produced by optimal duplication free mapping.