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.

Exploiting Symmetrization and D-reducibility for Approximate Logic Synthesis

Anna Bernasconi
Primo
;
2022-01-01

Abstract

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.
2022
Bernasconi, Anna; Ciriani, Valentina; Villa, Tiziano
File in questo prodotto:
File Dimensione Formato  
ApproxSymm.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 882.61 kB
Formato Adobe PDF
882.61 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1067761
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact