Pre-Synthesis Optimization of Arithmetic Circuits

The efficient synthesis of circuits is a well-studied problem. Due to the NP-hardness of the problem, no optimal algorithm has been presented so far. However, the heuristics presented by several researchers in the past, which are also adopted by commercially available tools, are able to generate near-optimal design implementation for most circuits. Apart from very few exceptions, these heuristics exploit the rules of Boolean algebra, involving the logical operations OR and AND, in order to transform the circuit. The approach works well for common logic circuits where OR and AND gates constitute the major portion of the circuitry. On the other hand, on arithmetic circuits including a large proportion of XOR gates in addition to the other two basic types, these heuristics perform poorly. For arithmetic circuits, current logic synthesis tools generate design implementations which are far from optimal. This is the case even for very common arithmetic circuits such as adders and multipliers. Current synthesis tools are unable to convert a Ripple Carry Adder (RCA) into a Carry Look-Ahead Adder (CLA) when synthesized for delay. For this reason, designers still rely on manually explored designs for arithmetic circuits. In this work, we explore the challenges in the efficient synthesis of arithmetic circuits and present a set of efficient algorithms to overcome these challenges. The presented algorithms vary in their computational complexity, and also in the granularity of the circuit details at which they work. We also present a methodology to combine these algorithms so that they can be applied on larger circuits without losing performance. The developed method, to which we refer as pre-synthesis circuit restructuring, starts with an elementary description of the input circuit and generates a quasi-optimal implementation of the circuit. The presented algorithms have been tested on a wide variety of circuits, including both arithmetic and nonarithmetic circuits. In nonarithmetic circuits, the generated design implementations have performance comparable to those generated by state-of-the-art techniques. However, for arithmetic and composite (mixture of arithmetic and nonarithmetic) circuits, our algorithms generate significantly better implementations. Contrary to currently used synthesis tools, our algorithms are able to convert a Ripple Carry Adder into a Carry Look-Ahead Adder without using any information about the functionality of the input circuit. For some circuits, such as multipliers and multi-input comparators, our algorithms are able to generate completely new design implementations, which have not yet been explored manually. Since our algorithm is able to generate a meaningful (i.e., near optimal) architectural implementation of a circuit component without any prior knowledge about its functionality, it eliminates the need of library implementation of arithmetic circuits. Although the algorithms presented here are not specific to arithmetic circuits and can be applied to any circuit, due to higher complexity compared to other logic synthesis heuristics, the use of our method is recommended for arithmetic circuits only. In addition to experimental evidence, the effectiveness of our algorithm on arithmetic circuits is also proved theoretically.