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

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

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

1 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
頁(從 - 到)337-355
頁數19
期刊Journal of Heuristics
10
發行號3
DOIs
出版狀態已發佈 - 2004 五月 1

ASJC Scopus subject areas

  • 軟體
  • 資訊系統
  • 電腦網路與通信
  • 控制和優化
  • 管理科學與經營研究
  • 人工智慧

指紋

深入研究「Towards the exact minimization of BDDs - An elitism-based distributed evolutionary algorithm」主題。共同形成了獨特的指紋。

引用此