skip to main content
10.1145/2908961.2908987acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
poster

Approximate BDD Optimization with Prioritized ε-Preferred Evolutionary Algorithm

Published: 20 July 2016 Publication History

Abstract

Approximate computing has gained high attention in various applications that can benefit from a reduction in costs by lowering the accuracy. In this paper we present an optimization approach for functional approximation of Binary Decision Diagrams (BDDs) which are known for their widespread applications in electronic design automation and formal verification. We propose a three-objective ε-preferred evolutionary algorithm with the first objective set to the BDD size which is given higher priority to the two other objectives set to errors caused by approximation. This is highly demanded by the application to ensure that the minimum size for the approximated BDD is accessible when the error metrics meet certain threshold values. While BDD size minimization is guaranteed by incorporating priority, the use of ε in the proposed approach ensures to guide the search towards desired error values in parallel. Experiments confirm the efficiency of the proposed approach by a size improvement of 64.24% at a fair cost of 3.86% inaccuracy on average.

References

[1]
F. Brglez, D. Bryan, and K. Kozminski. Combinational profiles of sequential benchmark circuits. In ISCAS, pages 1929--1934, 1989.
[2]
R. E. Bryant. Binary decision diagrams and beyond: enabling technologies for formal verification. In ICCAD, pages 236--243, 1995.
[3]
N. Drechsler, A. Sülflow, and R. Drechsler. Incorporating user preferences in many-objective optimization using relation ε-preferred. Natural Computing, 14(3):469--483, 2015.
[4]
M. Soeken, D. Große, A. Chandrasekharan, and R. Drechsler. BDD minimization for approximate computing. In ASP-DAC, pages 474--479, 2016.
[5]
F. Somenzi. CUDD: CU Decision Diagram package release 2.5.0. University of Colorado at Boulder, 2012.

Cited By

View all
  • (2021)An Adaptive Metric for Node Substitution-Based BDD Minimization2021 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS51556.2021.9401583(1-5)Online publication date: May-2021
  • (2019)BDD Optimization and Approximation: A Multi-criteria ApproachIn-Memory Computing10.1007/978-3-030-18026-3_3(21-47)Online publication date: 23-May-2019
  • (2017)An adaptive prioritized ε-preferred evolutionary algorithm for approximate BDD optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071281(1232-1239)Online publication date: 1-Jul-2017

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion
July 2016
1510 pages
ISBN:9781450343237
DOI:10.1145/2908961
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Check for updates

Author Tags

  1. ε-preferred evolutionary algorithm
  2. bdd approximation

Qualifiers

  • Poster

Funding Sources

  • Deutsche Forschungsgemeinschaft (DFG) within a Reinhart Koselleck-project
  • University of Bremen's graduate school SyDe

Conference

GECCO '16
Sponsor:
GECCO '16: Genetic and Evolutionary Computation Conference
July 20 - 24, 2016
Colorado, Denver, USA

Acceptance Rates

GECCO '16 Companion Paper Acceptance Rate 137 of 381 submissions, 36%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2021)An Adaptive Metric for Node Substitution-Based BDD Minimization2021 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS51556.2021.9401583(1-5)Online publication date: May-2021
  • (2019)BDD Optimization and Approximation: A Multi-criteria ApproachIn-Memory Computing10.1007/978-3-030-18026-3_3(21-47)Online publication date: 23-May-2019
  • (2017)An adaptive prioritized ε-preferred evolutionary algorithm for approximate BDD optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071281(1232-1239)Online publication date: 1-Jul-2017

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media