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

Exploiting Symmetrization and D-reducibility for Approximate Logic Synthesis / A. Bernasconi, V. Ciriani, T. Villa. - In: IEEE TRANSACTIONS ON COMPUTERS. - ISSN 0018-9340. - 71:1(2022 Jan 01), pp. 121-133. [10.1109/TC.2020.3043476]

Exploiting Symmetrization and D-reducibility for Approximate Logic Synthesis

V. Ciriani
Secondo
;
2022

Abstract

Approximate synthesis is a recent trend in logic synthesis where one changes some outputs of a logic specification, withinthe error tolerance of a given application, to reduce the complexity of the final implementation. We attack the problem by exploiting theallowed flexibility in order to maximize the regularity of the specified Boolean functions. Specifically, we consider two types of regularity:symmetryandD-reducibility, and contribute two algorithms to find, respectively, a symmetric and a D-reducible approximation of agiven target functionf, within the given error rate threshold if possible. When targeting symmetry, we characterize and computepolynomially the closest symmetric approximation, i.e., the symmetric function obtained by injecting the minimum number of errors inthe original incompletely specified Boolean function, with an unbounded number of errors; then, we discuss strategies to achievepartial symmetrization of the original specification while satisfying given error bounds. Finally, we present a polynomial heuristicalgorithm to compute a D-reducible approximation of an incompletely specified target function, under a bit error metric. Experimentalresults on classical and new benchmarks confirm the effectiveness of the proposed approaches.
Logic synthesis; Approximate synthesis;, Regular Boolean functions;
Settore INF/01 - Informatica
1-gen-2022
Article (author)
File in questo prodotto:
File Dimensione Formato  
12.2020BCV.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 891.18 kB
Formato Adobe PDF
891.18 kB Adobe PDF Visualizza/Apri
Exploiting_Symmetrization_and_D-Reducibility_for_Approximate_Logic_Synthesis.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 390.41 kB
Formato Adobe PDF
390.41 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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/2434/797786
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact