Architecture and CAD for speed and area optimization of FPGAs

grantor: University of TorontoIn the thirteen years since their introduction, Field-Programmable Gate Arrays (FPGAs) have become one of the most popular implementation media for digital circuits. Their programmability has been the key to the success of FPGAs, but this programmability also makes them ten times larger and three times slower than Masked Programmed Gate Arrays (MPGAs). This thesis investigates three aspects of FPGA architecture in order to find ways to reduce these speed and area penalties. Our investigation method is experimental--we technology map, place and route circuits in each architecture of interest and measure the resulting speed and density of the circuit. To enable this architectural exploration, we create new, flexible Computer-Aided Design (CAD) tools to perform logic block packing, placement and routing into a wide variety of FPGA architectures. These CAD tools incorporate new algorithms that result in better result quality than previous approaches, and their 'flexibility' enables rapid exploration of radically different FPGA architectures in a way that was not previously possible. The three FPGA architectural issues we investigate are global routing architecture, cluster-based logic blocks, and detailed routing architecture. In the global routing architecture investigation, we determine how FPGA architects can best allocate wiring tracks to the various channels within an FPGA. We show that an island-style FPGA should make all channels the same width, while a row-based FPGA should make the horizontal channels twice as wide as the vertical channels. We also find that an island-style FPGA has 5% better area-efficiency than a row-based FPGA. In our investigation of cluster-based logic blocks, we show that any logic block composed of a cluster of one to ten look-up tables has reasonable area-efficiency. The absolute best area-efficiencies are obtained by logic blocks with 1 or with 4 look-up tables per logic block. As well, we found that the number of look-up tables in a logic block must be considered when choosing other FPGA parameters, such as the flexibility of the logic block--routing interface. Finally, we examine different detailed routing architectures--that is, how long the various wires in an FPGA should be, and how they should be interconnected. We found that it is important for FPGA routing to contain both tri-state buffers and pass transistor switches. While most commercial FPGAs use many very long and very short wires, we found that routing architectures composed of medium length lines are superior. We found that such routing architectures are 11-18% faster and require only 0-6% more area than a routing architecture modelled after that of a top-selling commercial FPGA, despite being considerably simpler.Ph.D