Approximate Logic Synthesis Using Boolean Matrix Factorization

Approximate computing is an emerging computing paradigm offering benefits in hardware metrics, such as design area and power consumption, by relaxing the requirement for full accuracy. In circuit design, a major challenge is to synthesize approximate circuits automatically from input exact circuits requiring minimal expert input. In this work we present a method for approximate logic synthesis based on Boolean matrix factorization, where an arbitrary input circuit can be approximated in a controlled fashion. Our methodology enables automatic computation of the dominant elements, bases, of the truth table of the circuit, and later combining the bases to approximate the original truth table. Such compression can reduce the complexity of the hardware implementation significantly, while introducing variable degrees of error. Furthermore, in our approach, the factorization algorithm can be fine tuned as required by the application, to effectively improve control over degree of approximation. In this work, we provide a unified approach enabling the factorization algorithm to utilize semi-ring algebra, field algebra, and a combination of both for truth table factorization. In addition, we provide an automatic circuit partitioning approach and a design space exploration heuristic to navigate the search space. We implement our methodology using a full stack of open-source tools, and thoroughly evaluate our methodology on a number of representative circuits showcasing the benefits of our proposed methodology for approximate logic synthesis. Finally, we compare our methodology against an existing library of approximate designs and demonstrate state-of-the-art performance.