Recent dramatic improvements in integrated circuit fabrication technology have led to Field-Programmable Gate Arrays (FPGAs) capable of implementing entire digital systems, as opposed to the smaller logic circuits that have traditionally been targeted to FPGAs. Unlike the smaller circuits, these large systems often contain memory. Architectural support for the efficient implementation of memory in next-generation FPGAs is therefore crucial.

This dissertation examines the architecture of FPGAs with memory, as well as algorithms that map circuits into these devices. Three aspects are considered:​ the analysis of circuits that contain memory, as well as the automated random generation of such circuits, the architecture and algorithms for stand-alone configurable memory devices, and architectures and algorithms for the embedding of memory arrays in an FPGA.

We first present statistics gathered from 171 circuits with memory. These statistics include the number of memories in each circuit and the width and depth of these memories. We identify common interconnect patterns between memory and logic. These statistics are then used to develop a circuit generator that stochastically generates realistic circuits with memory that can be used as benchmark circuits in architectural studies.

Next, we consider the architecture of a stand-alone configurable memory that is flexible enough to implement memory configurations with different numbers of memories, memory widths and depths. Instrumental in this work is the algorithms that map memory configurations to the device. These algorithms are used in an experimental framework to investigate the effect of various architectural parameters on the flexibility, chip area, and access time of the configurable memory.

Finally, the architecture of an FPGA containing both embedded memory arrays and logic elements is considered, along with new automatic placement and routing algorithms that map circuits to the FPGA. We show that only 4 switches per memory block pin are required in the interconnection between the memory arrays and logic elements, and even lower in FPGAs with four or fewer memory arrays. In addition, we show that by providing direct connections between memory arrays, the FPGA density can be improved slightly, and the average memory access time can be improved by as much as 25%.