SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism

Exact synthesis is a versatile logic synthesis technique with applications to logic optimization, technology mapping, synthesis for emerging technologies, and cryptography. In recent years, advances in SAT solving have lead to a heightened research effort into SAT-based exact synthesis. Advantages of exact synthesis include the use of various constraints (e.g. synthesis of emerging technology circuits). However, although progress has been made, its runtime remains unpredictable. This paper identifies two key points as hurdles to further progress. First, there are open questions regarding the design and implementation of exact synthesis systems, due to the many degrees of freedom. For example, there are different CNF encodings, different symmetry breaks to choose from, and different encodings may be suitable for different domains. Second, SAT-based exact synthesis is difficult to parallelize. Indeed, this is a common drawback of logic synthesis algorithms. This paper proposes four ways to close some open questions and to reduce runtime: (i) quantifying differences between CNF encoding schemes and their impacts on runtime, (ii) demonstrating impact of symmetry breaking constraints, (iii) showing how DAG topology information can be used to decrease runtime, (iv) showing how topology information can be used to leverage parallelism.