Maximizing NPN equivalent functions in a LUT-level circuit for SRAM-based FPGAs

In this thesis, we investigate a novel FPGA (Field Programmable Gate Array) synthesis algorithm. The new algorithm aims at maximizing the number of NPN (Input Negation, Input Permutation and Output Negation) equivalent functions in a LUT (Lookup Table) level circuit. The goal is to efficiently utilize newly proposed FPGA architectures that enable SRAM (Static Random Access Memory) sharing among NPN-equivalent functions. Our algorithm utilizes a fast NPN-equivalence checker tool and incorporates it into an FPGA synthesis tool, called the ABC (A System for Sequential Synthesis and Verification) tool. The NPN-equivalence checker tool formulates two logic functions as hyper-graphs and calls a hyper-graph isomorphism checker tool, called Nauty graph isomorphism tool, to check the equivalency of two hyper-graphs. The user provides a set of functions as input to the extension of ABC tool that we developed and forces the ABC tool to generate LUT functions that are NPN-equivalent to the user inputted functions. The user specified functions are identified as follows. First, the circuit is synthesized with the original, unmodified ABC tool. The resulting circuit is analyzed and the most frequently occurring NPN equivalence classes are identified. Later, a representative function from each of these classes is selected as the input to the second synthesis process. After that, we synthesize the circuit one more time with the modified ABC tool to force the LUTs to be equivalent to the identified functions. The modified ABC tool does its best to generate LUTs that are NPN-equivalent to the user specified functions. The performance of the proposed algorithm is evaluated by performing the synthesis on a set of benchmark circuits, namely MCNC (Microelectronics Center of North Carolina) synthesis benchmarks. In our experiments, we have investigated five and six input functions, since these input function sizes were applicable in practice.