Logic Synthesis Meets Machine Learning: Trading Exactness for Generalization

Abstract:
Logic synthesis is a fundamental step in hardware design whose goal is to find structural representations of Boolean functions while minimizing delay and area. If the function is completely-specified, the implementation accurately represents the function. If the function is incompletely-specified, the implementation has to be true only on the care set. While most of the algorithms in logic synthesis rely on SAT and Boolean methods to exactly implement the care set, we investigate learning in logic synthesis, attempting to trade exactness for generalization. This work is directly related to machine learning where the care set is the training set and the implementation is expected to generalize on a validation set. We present learning incompletely-specified functions based on the results of a competition conducted at IWLS 2020. The goal of the competition was to implement 100 functions given by a set of care minterms for training, while testing the implementation using a set of validation minterms sampled from the same function. We make this benchmark suite available and offer a detailed comparative analysis of the different approaches to learning.

Click the links to view the paper [IEEE Xplore | arXiv | PDF] and the project page.

To cite the paper, you may use the following BibTex entry.

@inproceedings{Rai:DATE:2021,
    author      = {Shubham Rai and Walter Lau Neto and Yukio Miyasaka and Xinpei Zhang and Mingfei Yu and Qingyang Yi Masahiro Fujita and Guilherme B. Manske and Matheus F. Pontes and Leomar S. da Rosa Junior and Marilton S. de Aguiar and Paulo F. Butzen and Po-Chun Chien and Yu-Shan Huang and Hoa-Ren Wang and Jie-Hong R. Jiang and Jiaqi Gu and Zheng Zhao and Zixuan Jiang and David Z. Pan and Brunno A. de Abreu and Isac de Souza Campos and Augusto Berndt and Cristina Meinhardt and Jonata T. Carvalho and Mateus Grellert and Sergio Bampi and Aditya Lohana and Akash Kumar and Wei Zeng and Azadeh Davoodi and Rasit O. Topaloglu and Yuan Zhou and Jordan Dotzel and Yichi Zhang and Hanyu Wang and Zhiru Zhang and Valerio Tenace and Pierre-Emmanuel Gaillardon and Alan Mishchenko and Satrajit Chatterjee},
    title       = {Logic Synthesis Meets Machine Learning: Trading Exactness for Generalization},
    booktitle   = {Proc. DATE},
    year        = {2021},
    doi         = {10.23919/DATE51398.2021.9473972}
}