Logic
synthesis is the process of generating the implementation of a
Boolean function using logic gates. A typical goal is to find a
minimum-size implementation of the behavior of the Boolean function. When
complex functions are to be implemented, the initial specification needs
to be decomposed into smaller functions that can be mapped into the basic
primitives available in the technology, e.g., logic gates or lookup tables
with few inputs.
Decomposition is a process that has to explore a large design space. A Boolean function can be decomposed in different ways and the selection of a good decomposition is essential to reduce the complexity of the final implementation. Therefore, having good estimators during decomposition contributes to take good decisions.
This project is about creating good estimators of the complexity of Boolean functions.
An example is shown in the Figure. The left part shows the truth table of a 4-variable Boolean function. A more visual representation is shown by the Karnaugh map in which the prime implicants can be easily derive to obtain a sum of products (SOP) with 7 literals. The SOP can be represented as a matrix with as many columns as variables (4) and as many rows as products (3). Each cell denotes the presence of the variable in the term (0: negative, 1: positive, *: not present).
However, SOP is not the best representation to generate efficient implementations of Boolean functions. The same figure shows a factored form (represented as a tree) in which the nodes are conjunctions (∧) and disjunctions (∨). This representation only uses 5 literals.
The SOP representation is a Boolean matrix (a B&W picture?). Would it be possible treat the matrix as a picture and create a Convolutional Neural Network (CNN) that can estimate the complexity of a function when represented with simple logic gates?
A CNN (see figure below) can be trained with supervised learning using the implementation of a huge amount of functions for which efficient implementations are known. This training may help constructing a model that can be fed with the matrix representation of an SOP and estimate the complexity of its implementation (in literals of a factored form or number of lookup-tables).
In the PhD thesis by Lucas Machado, various methods for logic decomposition for FPGA mapping were explored (see Lucas' PhD thesis). This work would be a follow up of Lucas' thesis with the goal of providing quick estimations of the quality of Boolean decompositions using deep learning models.
