Progressive decomposition: a heuristic to structure arithmetic circuits

Despite the impressive progress of logic synthesis in the past decade, finding the best architecture for a given circuit still remains an open problem and largely unsolved. In most of the arithmetic circuits the outcome of the synthesis tools depends on the input description of the circuit. In other words, logic synthesis optimisations hardly change the architecture of the given circuit. However, once the input description belongs to the right architecture, logic synthesis does an excellent job in optimising the circuit locally. This is the reason why designers still rely on well studied architectures. The main difficulty in finding the suitable architecture for an arithmetic circuit is the high fan-in dependencies between inputs and outputs (i.e., each output bit depends on a large portion of input bits). Hence, imposing hierarchy and structure is the key to find the best architecture. Although factorisation is one potential solution for this problem, the computational complexity of Boolean factorisation and poor performance of algebraic factorisation make this solution impractical in most cases of interest. In this paper we present a novel approach which progressively decomposes the input circuits into building blocks and constructs hierarchy among these blocks. We show that our approach optimises the critical path delay by 15--30% at the cost of marginal or no area penalty. In some cases, it even improves the area. Qualitatively we observed that our approach found the best known architecture for some circuits without any a priori knowledge about the functionality of the circuit.