Towards the Exact Minimization of BDDs—An Elitism-Based Distributed Evolutionary Algorithm |
| |
| Authors: | Chen Shan-Tai Lin Shun-Shii Huang Li-Te Wei Chun-Jen |
| |
| Institution: | (1) Department of Information and Computer Education, National Taiwan Normal University, Taipei, Taiwan, R.O.C;(2) Graduate Institute of Computer Science and Information Engineering, National Taiwan Normal University, No. 88, Sec. 4, Ting-Chow Rd., Taipei, Taiwan, R.O.C.;(3) Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan, R.O.C |
| |
| 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: | DEBEA EBEA Binary Decision Diagram evolutionary algorithm heuristic algorithm paralleled algorithm |
| 本文献已被 SpringerLink 等数据库收录！ |
|
