Abstract

This talk will review the development of logic synthesis from manipulating small Boolean functions using truth tables, through the discovery of efficient heuristic methods for sum-of-product minimization and algebraic factoring applicable to medium-sized circuits, to the present-day automated design flow, which can process digital designs with millions of logic gates. The talk will discuss the main computation engines and packages used in logic synthesis, such as circuit representation in the form of And-Inverter-Graphs, recent improvements to the traditional minimization and factoring methods, priority-cut-based technology mapping into standard-cells and lookup-tables, and don't-care-based optimization using Boolean satisfiability. We will also discuss the importance of formal verification for validating the results produced by the synthesis tools, and the deep synergy between algorithms and data-structures used in synthesis and verification. In the course of this talk, the presenter will share his 14-year experience of being part of an academic research group with close connections to companies in Silicon Valley, both design houses and CAD tool vendors.

Speaker's Biography

Alan Mishchenko graduated from Moscow Institute of Physics and Technology, Moscow, Russia, in 1993, and received his Ph.D. degree from Glushkov Institute of Cybernetics, Kiev, Ukraine, in 1997. In 2002, Alan started at University of California at Berkeley as an Assistant Researcher and, in 2013, he was promoted to a Full Researcher. Alan shared the D.O. Pederson TCAD Best Paper Award in 2008 and the SRC Technical Excellence Award in 2011 for work on ABC. His research interests are in developing computationally efficient methods for logic synthesis and verification.