Graph transformations to improve LUT mapping in FPGAs

A Field-Programmable Gate Array (FPGA) is a general re-configurable device for implementing logic circuits. This technology is extensively used for prototyping circuits due to its cost and speed. The underlying implementation consists of Lookup Tables (k-LUT), logic functions that can implement any function up to k variables. And-Inverter graphs (AIG) are multi-level networks composed of two input ANDs and inverters and are the standard format for describing Boolean functions in practical applications of logic synthesis. In this thesis, we present an orthogonal technique that, interleaved with already known high-effort area mapping, outperforms previous best work on technology mapping. This technique, named AIGROT, explores several ways to exploit the commutativity and associativity of the AND operation, thereby reducing the number of LUTs needed to represent the Boolean functions. Experimental results show a substantial circuit minimization on several large public benchmarks without practically increasing the runtime or memory requirements. The proposed scheme is a blend of alternating techniques throughout the logic synthesis flow that provides tangible results at least as good as previous ones. In particular, using our technique, we are able to improve the best known area of four circuits from the EPFL benchmark library, which is considered the most comprehensive and diverse set of benchmarks, where all recently developed logic synthesis algorithms are tested