Novel SRAM-based FPGA architectures and supporting CAD tools

Reconfigurable computing has emerged as a new computing paradigm to bridge the general purpose and application specific computing paradigms. It is more flexible than application specific computing and much faster than general purpose computing, as shown in several application domains including data encryption and cryptography. There are many other areas that benefit from reconfigurable computing due to its performance and flexibility. Field-programmable gate arrays (FPGAs) are the building blocks of reconfigurable systems.; Our research is focused on reducing the area, power, configuration bits, and test time of FPGAs. We propose lowering FPGA area by allowing the static random access memory (SRAM) tables to be shared by more than one function, therefore reducing the total number of SRAM tables required in the FPGA. This reduction in the number of SRAM tables will also lower the power required by the FPGA. With the fewer number of configuration bits, configuration time, and therefore test time, will be reduced. Our goal is to achieve this without increasing delay or routing. Our approach allows SRAM tables to be shared by NPN equivalent functions, where NPN means functions that can be negated at the primary inputs, permuted at the inputs and negated at the primary outputs. This was motivated by a study of the benchmarks that revealed that the synthesis tools are biased. Most circuits only contained a significant number of functions from a very small number of the NPN equivalence classes. We were able to exploit this fact in coming up with FPGA architectures that allowed SRAM tables to be shared without increasing power, delay, or routing.; We modified FPGA CAD flow to take NPN equivalence into account. We first created equivalence tables so that determining if two functions are NPN equivalent becomes a trivial operation. Next, we modified packing tools to only allow NPN equivalent functions to be mapped to shared SRAM tables. Once packing, placement, and routing were completed, we modified the routing tools to implement our critical path improvement algorithms.; Experimental results showed that larger clustered logic blocks (CLBs) containing a mixture of normal SRAM tables and SRAM tables shared by two NPN equivalent functions produced the best results. Several architectures, such as CLBs with 16 lookup tables (LUTs) and 34 inputs, were found to successfully share SRAM tables without increasing channel width, delay, or routing parameters. With the addition of our critical path delay reduction algorithm, we were able to obtain successful architectures where all except one pair of SRAM tables were shared. This architecture resulted in a 44% reduction in the number of SRAM tables, a 4.4% reduction in overall FPGA area, and a 2% reduction in total power consumption, all without increasing routing, wirelength, or delay.