Minimization of average path length in BDDs by variable reordering
Loading...
Authors
Mishchenko, Alan
Sasao, Tsutomu
Nagayama, Shinobu
Butler, Jon T.
Subjects
Advisors
Date of Issue
2003-05
Date
May 28-30, 2003
Publisher
Language
Abstract
Minimizing the Average Path Length (APL) in a BDD reduces the time needed to evaluate Boolean functions represented by BDDs. This paper describes an efficient heuristic APL minimization procedure based on BDD variable reordering. The reordering algorithm is similar to classical variable sifting with the cost function equal to the APL rather than the number of BDD nodes. The main contribution of our paper is a fast way of updating the APL during the swap of two adjacent variables. Experimental results show that the proposed algorithm effectively minimizing the APL of large MCNC benchmark functions, achieving reductions of up to 47%. For some benchmarks, minimizing APL also reduces the BDD node count.
Type
Article
Description
12th International Workshop on Logic and Synthesis, Laguna Beach, California, USA, May 28-30, 2003, pp.207-213.
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.
Series/Report No
Department
Department of Electrical and Computer Engineering
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
S. Nagayama, A. Mishchenko, T. Sasao, and J. T. Butler, "Minimization of average path length in BDDs by variable reordering," 12th International Workshop on Logic and Synthesis, Laguna Beach, California, USA, May 28-30, 2003, pp.207-213.