Towards the exact minimization of BDDs - An elitism-based distributed evolutionary algorithm

Shan Tai Chen, Shun Shii Lin, Li Te Huang, Chun Jen Wei

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Binary Decision Diagrams (BDDs) are the state-of-the-art data structure for representation and manipulation of Boolean functions. In general, exact BDD minimization is NP-complete. For BDD-based technology, a small improvement in the number of nodes often simplifies the follow-up problem tremendously. This paper proposes an elitism-based evolutionary algorithm (EBEA) for BDD minimization. It can efficiently find the optimal orderings of variables for all LGSynth91 benchmark circuits with a known minimum size. Moreover, we develop a distributed model of EBEA, DEBEA, which obtains the best-ever variable orders for almost all benchmarks in the LGSynth91. Experimental results show that DEBEA is able to achieve super-linear performance compared to EBEA for some hard benchmarks.

Original languageEnglish
Pages (from-to)337-355
Number of pages19
JournalJournal of Heuristics
Volume10
Issue number3
DOIs
Publication statusPublished - 2004 May 1

Keywords

  • Binary Decision Diagram
  • DEBEA
  • EBEA
  • Evolutionary algorithm
  • Heuristic algorithm
  • Paralleled algorithm

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications
  • Control and Optimization
  • Management Science and Operations Research
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Towards the exact minimization of BDDs - An elitism-based distributed evolutionary algorithm'. Together they form a unique fingerprint.

  • Cite this