This dissertation examines the architecture of FPGAs with memory, as well as
algorithms that map circuits to these devices. Three aspects are considered:
circuit analysis and generation, stand-alone configurable memory devices,
and embedded memory arrays in an FPGA.
A detailed circuit analysis is presented that examines the use of memory in
large digital circuits. We present statistics including the number of
memories in each circuit and the width and depth of these memories. We also
discuss how memories are used in circuits, and 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.
The architecture of a stand-alone configurable memory that is flexible
enough to implement memory configurations with different numbers of memories
and different memory widths and depths is then presented, along with algorithms
that map memory configurations to the device. These algorithms are used to
investigate the effects 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 surprisingly little flexibility is required in the interconnection between the memory arrays and logic elements, especially 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 somewhat, and the average memory access time can be reduced significantly.