Optimal Combinational Multi-Level Logic Synthesis.

Abstract

Within the field of automated logic design, the optimal synthesis of combinational logic has remained one of the most basic design objectives. However, the computational complexity of this optimization problem has limited the practical application of optimal synthesis for large circuits. Since much of the exact synthesis literature predates many advances in both computer hardware as well as reasoning and search techniques, it was our objective to revisit optimal synthesis. Through this investigation we hoped to complete optimal synthesis on more complex functions. In this dissertation, we provide a general formulation of logic synthesis as an expanding search problem and describe BESS, an optimal multi-level branch-and-bound synthesis algorithm for combinational circuits. The formulation of synthesis as an expanding search problem provides insights into the difficulty of optimal synthesis. The generality of the formulation provides the flexibility in the options under which synthesis could be completed. Since BESS was created based on this formulation, it completes optimal synthesis under a variety of options while guaranteeing that an optimal network will be produced. In this dissertation, we provide a comprehensive evaluation of BESS. First we describe an extensive study of the search strategies for BESS, including both empirical and theoretical arguments which explain why these strategies are able to provide a more efficient search. Then through an analysis of the algorithm, we provide proofs of both completeness and convergence as well as an analysis of the search space. Empirically, we discuss the findings yielded by BESS. We give a database of optimal circuits. Optimal implementations of all 2-, 3-, and 4-input functions are given, including for the first time the optimal implementation of the 4-input xor function. We then extend this database of know optimal circuits to include 4,745 5-input functions. We also provide optimal networks and cost formula for n-input functions for a variety of common functions based on an analysis of optimal network structures. Finally, we provide networks for larger function that are with-in a known distance from optimal by modifying the bounding technique in BESS. Networks with as many as 17 inputs and 16 outputs are completed.