Near-Optimum Circuits for Binary Addition and Multi-Output And Functions

Abstract

In this thesis we present theoretical and practical work on the optimization of Boolean functions in chip design. On a chip, complex Boolean functions are built from basic building blocks computing for example an AND. For every function there are various possible implementations differing in depth or size. The goal of this thesis is to find a good implementation for special classes of such functions.<br /> The first main chapter is dedicated to the task of adding two binary encoded numbers. This problem can be reduced to the computation of the carry bits, each of which corresponds to a path consisting of alternating AND and OR gates. We derive an algorithm to restructure AND-OR paths, achieving the best depth known so far. The basis for this algorithm are recursive splits similar to those proposed in earlier work. We refine their analysis to derive an improved depth bound of log₂ <em>n</em> + log₂ log₂ <em>n</em> for AND-OR paths with <em>n</em> inputs and refine our bound asymptotically even further. We show that our circuits can be built with a linear number of gates upper bounded by 2.7<em>n</em> by using small multi-output AND functions. Moreover, we show how to use these AND-OR paths to build only slightly deeper adder circuits, i.e., all carry bits, still maintaining linear size. This yields the fastest linear size adders known so far. This chapter is joint work with Ulrich Brenner.<br /> Next, we study the problem of constructing multi-output AND functions with minimum size. Let <em>k</em> be the maximum number of inputs that are combined in a single AND function. We show that the problem is already APX-hard for <em>k</em> = 3. We derive approximation algorithms achieving an approximation guarantee of 1.212 and 1.731 for <em>k</em> = 3 and <em>k</em> = 4, respectively. In both cases we provide a combinatorial algorithm and a randomized LP rounding algorithm. Moreover, we give a 2/3 <em>k</em> algorithm for general <em>k</em>.<br /> Last, we consider the problem of multi-output AND or XOR function optimization on practical instances. We decompose the whole chip into gates with two inputs and apply De Morgan rules to make it consist of ANDs, XORs and inverters only. We then collect single-output AND and single-output XOR functions implemented on the chip and combine them to a larger instance whenever they share at least two inputs. Afterward, we introduce an integer linear program similar to the rounded LP introduced in our theoretical work and solve it using an ILP solver to decrease the number of gates in the instances. This algorithm is then followed by a technology mapping and some other restructuring routines. We present tests on the EPFL logic benchmark instances as well as on industry chips provided by our industry partner IBM and show experimental results and different statistics. Even though there is some distortion by technology mapping, the results show that our core algorithm is useful and can reduce the number of gates significantly.