Title :
Multi-level approximate logic synthesis under general error constraints
Author :
Jin Miao ; Gerstlauer, Andreas ; Orshansky, Michael
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Texas at Austin, Austin, TX, USA
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 :
Boolean functions; adders; logic design; logic gates; multivalued logic circuits; optimisation; Boolean relations; EXDC-based network optimizations; adder designs; arithmetic blocks; error frequency constraints; error-magnitude constrained problem; external don´t cares; gate count; logic function; minimum cost circuits; multilevel approximate logic synthesis; multiplier designs; optimized exact Boolean network; Algorithm design and analysis; Approximation algorithms; Boolean functions; Hamming distance; Logic gates; Optimization; Upper bound;
Conference_Titel :
Computer-Aided Design (ICCAD), 2014 IEEE/ACM International Conference on
Conference_Location :
San Jose, CA
DOI :
10.1109/ICCAD.2014.7001398