Multi-level approximate logic synthesis under general error constraints
Authors:
- 1 November 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10923152,p. 504-510
Abstract
We address the problem of multi-level approximate logic synthesis. Our strategy assumes existence of an optimized exact Boolean network, which is critical in practice since arithmetic blocks are rarely synthesized from 2-level representation automatically. The goal is to produce minimum cost circuits whose logic function deviates in a controlled manner from the exact function with deviations quantified by the magnitude and frequency of errors. We rely on network simplifications allowed by external don't cares (EXDCs). We formulate the error-magnitude constrained problem by using Boolean relations to capture the allowed error behavior in a more general manner compared to incompletely specified functions. Our key contribution is in finding sets of external don't cares that maximally approach the Boolean relation. The algorithm starts with an EXDC set that is overly relaxed and iteratively, and in a greedy fashion, identifies a feasible EXDC set by solving a series of conventional EXDC-based network optimizations. The algorithm then ensures compliance to error frequency constraints by recovering the correct outputs on the sought number of error-producing inputs while aiming to minimize the network cost increase. We applied the algorithm to several well-known adder and multiplier designs of varying bit-width. Even for small error magnitudes, the algorithm produces networks with gate count reduced by 30-50%, when the error frequency constraint is loose. This is up to 20% fewer gates than a naive EXDC-based approach.Keywords
This publication has 17 references indexed in Scilit:
- Quality programmable vector processors for approximate computing2013
- Approximate logic synthesis under general error magnitude and frequency constraints2013
- On reconfiguration-oriented approximate adder design and its application2013
- An energy efficient approximate adder with carry skip for error resilient neuromorphic VLSI systems2013
- Exploring the energy efficiency of Multispeculative Adders2013
- SALSA2012
- Dynamic effort scaling2011
- Energy parsimonious circuit design through probabilistic pruning2011
- ABC: An Academic Industrial-Strength Verification Tool2010
- Heuristic minimization of multiple-valued relationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993