IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2019 · 57 citations · 32 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureHardware Description LanguagesDesign SynthesisDigital Logic DesignLogic SynthesisAcyclic Directed Graph RepresentationsConstraintsLogic OptimizationOpen QuestionsParallel CircuitsTechnology Mapping To Logic BlocksTopology Management
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 led 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: 1) quantifying differences between CNF encoding schemes and their impacts on runtime; 2) demonstrating impact of symmetry breaking constraints; 3) showing how directed acyclic graph topology information can be used to decrease runtime; and 4) showing how topology information can be used to leverage parallelism.
32
The Art of Computer Programming
G.E. Whitesides · Nuclear Science and Engineering · 1970 · 6.1K citations
Synthesis and optimization of digital circuits
Choice Reviews Online · 1994 · 2.4K citations
Engineering, Computer Engineering, Electrical Engineering +17
Practical graph isomorphism, II
Brendan D. McKay, Adolfo Piperno · Journal of Symbolic Computation · 2013 · 1.6K citations
Minimization of Boolean Functions*
E.J. McCluskey · Bell System Technical Journal · 1956 · 1.2K citations
The Problem of Simplifying Truth Functions
W. V. Quine · American Mathematical Monthly · 1952 · 801 citations