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

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

Fingerprint

Binary decision diagrams
Decision Diagrams
Distributed Algorithms
Parallel algorithms
Evolutionary algorithms
Evolutionary Algorithms
Binary
Benchmark
Boolean functions
Boolean Functions
Data structures
Manipulation
Data Structures
Simplify
NP-complete problem
Diagrams
Networks (circuits)
Experimental Results
Vertex of a graph

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

Cite this

Towards the exact minimization of BDDs - An elitism-based distributed evolutionary algorithm. / Chen, Shan Tai; Lin, Shun Shii; Huang, Li Te; Wei, Chun Jen.

In: Journal of Heuristics, Vol. 10, No. 3, 01.05.2004, p. 337-355.

Research output: Contribution to journalArticle

Chen, Shan Tai ; Lin, Shun Shii ; Huang, Li Te ; Wei, Chun Jen. / Towards the exact minimization of BDDs - An elitism-based distributed evolutionary algorithm. In: Journal of Heuristics. 2004 ; Vol. 10, No. 3. pp. 337-355.
@article{c25eb2e978ad466c9967ba7c19635792,
title = "Towards the exact minimization of BDDs - An elitism-based distributed evolutionary algorithm",
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.",
keywords = "Binary Decision Diagram, DEBEA, EBEA, Evolutionary algorithm, Heuristic algorithm, Paralleled algorithm",
author = "Chen, {Shan Tai} and Lin, {Shun Shii} and Huang, {Li Te} and Wei, {Chun Jen}",
year = "2004",
month = "5",
day = "1",
doi = "10.1023/B:HEUR.0000026899.63797.f9",
language = "English",
volume = "10",
pages = "337--355",
journal = "Journal of Heuristics",
issn = "1381-1231",
publisher = "Springer Netherlands",
number = "3",

}

TY - JOUR

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

AU - Chen, Shan Tai

AU - Lin, Shun Shii

AU - Huang, Li Te

AU - Wei, Chun Jen

PY - 2004/5/1

Y1 - 2004/5/1

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

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

KW - Binary Decision Diagram

KW - DEBEA

KW - EBEA

KW - Evolutionary algorithm

KW - Heuristic algorithm

KW - Paralleled algorithm

UR - http://www.scopus.com/inward/record.url?scp=3543069406&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3543069406&partnerID=8YFLogxK

U2 - 10.1023/B:HEUR.0000026899.63797.f9

DO - 10.1023/B:HEUR.0000026899.63797.f9

M3 - Article

AN - SCOPUS:3543069406

VL - 10

SP - 337

EP - 355

JO - Journal of Heuristics

JF - Journal of Heuristics

SN - 1381-1231

IS - 3

ER -