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 finding approximate representations of Boolean functions obtained by reducing the number of variables.
An example is shown in the figure. The left part shows the truth table of three 4-variable Boolean functions: f, g and h. Let us focus on the implementation of function f. A possible implementation in disjunctive normal form (DNF) is shown on the same figure (the Boolean equation has 8 literals).
Let us now consider approximations of f using a fewer number of variables. Function g only uses three variables and is the best approximation of f with this number of variables (notice that the only discrepancy is in the point abcd=0111). The question is: why is {a,b,d} the best subset of {a,b,c,d} to represent the function? How about using {a,b,c} or {b,c,d} instead?
As we drop more variables, the approximation is less accurate. For example, h is another approximation using only 2 variables, a and b. However, f and h differ in 3 points now: 0111, 1001 and 1011.
The conjecture is that good approximations of Boolean functions contribute to find good decompositions, as shown in the circuit of the figure. By using function g (red box), a simple implementation of f can be found (blue box).
The main question we want to answer is the following: given an n-variable Boolean function, what is the subset of k variables that can be used to find the best approximation of the function? For example, imagine a 20-variable function and an approximation using only 6 variables.
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 techniques of dimensionality reduction to approximate Boolean functions.
Good algorithmic skills. No previous knowledge about logic synthesis is required. Jordi Cortadella will provide a quick tutorial to learn the basics of logic synthesis and Boolean decomposition. During the tutorial, the student will learn about Boolean algebra, Binary Decision Diagrams, Boole's expansion theorem and Shannon cofactors and Boolean differences. The project will require an implementation of the techniques in Python and C++, possibly using pyeda and yosys.
If the results of the project are promising, a publication in a prestigious journal or conference in the area of Electronic Design Automation is envisioned (see conferences and journals).