Exploiting Symmetrization and D-Reducibility for Approximate Logic Synthesis

Approximate synthesis is a recent trend in logic synthesis where one changes some outputs of a logic specification, within the error tolerance of a given application, to reduce the complexity of the final implementation. We attack the problem by exploiting the allowed flexibility in order to maximize the regularity of the specified Boolean functions. Specifically, we consider two types of regularity: symmetry and D-reducibility, and contribute two algorithms to find, respectively, a symmetric and a D-reducible approximation of a given target function f, within the given error rate threshold if possible. When targeting symmetry, we characterize and compute polynomially the closest symmetric approximation, i.e., the symmetric function obtained by injecting the minimum number of errors in the original incompletely specified Boolean function, with an unbounded number of errors; then, we discuss strategies to achieve partial symmetrization of the original specification while satisfying given error bounds. Finally, we present a polynomial heuristic algorithm to compute a D-reducible approximation of an incompletely specified target function, under a bit error metric. Experimental results on classical and new benchmarks confirm the effectiveness of the proposed approaches.

Automated summary

Approximate synthesis is a recent trend in logic synthesis that aims to reduce the complexity of the final implementation by changing some outputs within the error tolerance. We propose two algorithms to maximize the regularity of specified Boolean functions, targeting symmetry and D-reducibility. Experimental results confirm the effectiveness of our approaches.