Scalable and Generic Logic Synthesis

(since 02/2020, PhD research)
Advisor: Professor Giovanni De Micheli, EPFL

Circuit simulation is often used in Boolean methods as an efficient approximator of the Boolean functions embedded in logic networks. In the simulation-guided logic synthesis and verification paradigm, efforts are made in pre-generating a set of high-quality, expressive simulation patterns, which can be reused many times, to guide more efficient and powerful logic optimization. On one hand, using partial simulation, global Boolean information can be taken into account with low cost to improve optimization quality. On the other hand, using expressive simulation patterns, expensive SAT-solver calls are reduced and efficiency is enhanced. [1,2]

Classic cut-based Boolean rewriting algorithms usually rely on a database of minimal circuit implementations. They are difficult to be extended to larger than 4-cuts due to the exponential growth of the number of cuts and of the database. Thus, we propose "window rewriting", which (1) builds one good-quality window around each node instead of computing many cuts; and (2) heuristically resynthesize the window on the fly instead of looking up in a database. [4]

Logic resynthesis is the problem of finding a dependency function to re-express a given target function in terms of some (given) divisor functions. The AIG resynthesis algorithm detailed in [4] is used in both simulation-guided resubstitution [2] and window rewriting [4]. As its counterpart for MIG optimization, a top-down decomposition-based method to resynthesize MIGs is proposed in [3]. [8] summarizes the resynthesis problem with various heuristics: AIG/XAG, MIG, and MuxIG resynthesis algorithms.

Related publications

  1. Siang-Yun Lee, Heinz Riener, Alan Mishchenko, Robert K. Brayton, and Giovanni De Micheli. "Simulation-Guided Boolean Resubstitution," 2020 International Workshop on Logic and Synthesis (IWLS). (arXiv, video)
  2. Siang-Yun Lee, Heinz Riener, Alan Mishchenko, Robert K. Brayton, and Giovanni De Micheli. "A Simulation-Guided Paradigm for Logic Synthesis and Verification," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD). (IEEEXplore)
  3. Siang-Yun Lee, Heinz Riener, and Giovanni De Micheli. "Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition," 2021 International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS). (IEEEXplore)
  4. Heinz Riener, Siang-Yun Lee, Alan Mishchenko, and Giovanni De Micheli. "Boolean Rewriting Strikes Back: Reconvergence-Driven Windowing Meets Resynthesis," 2021 International Workshop on Logic and Synthesis (IWLS). (video)
  5. Heinz Riener, Siang-Yun Lee, Alan Mishchenko, and Giovanni De Micheli. "Boolean Rewriting Strikes Back: Reconvergence-Driven Windowing Meets Resynthesis," 2022 Asia and South Pacific Design Automation Conference (ASP-DAC). (IEEEXplore, pitch video, full presentation)
  6. Siang-Yun Lee, Heinz Riener, and Giovanni De Micheli. "An Automated Testing and Debugging Toolkit for Gate-Level Logic Synthesis Applications," 2022 International Workshop on Logic and Synthesis (IWLS). (arXiv, video)
  7. Hanyu Wang, Siang-Yun Lee, and Giovanni De Micheli. "A Cost-generic Resubstitution Algorithm with Customizable Cost Functions," 2022 International Workshop on Logic and Synthesis (IWLS). (video)
  8. Siang-Yun Lee and Giovanni De Micheli. "Heuristic Logic Resynthesis Algorithms at the Core of Peephole Optimization," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD). (IEEEXplore)
  9. Siang-Yun Lee, Heinz Riener, and Giovanni De Micheli. "Customizable On-the-fly Design Space Exploration for Logic Optimization of Emerging Technologies," 2023 International Workshop on Logic and Synthesis (IWLS).

Open-source implementation

Back