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.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.