Computer Graphics & A Minimization Technique for BDD based on Microcanonical Optimization


The KIPS Transactions:PartA, Vol. 8, No. 1, pp. 48-55, Mar. 2001
10.3745/KIPSTA.2001.8.1.48,   PDF Download:

Abstract

Using BDD, we can represent Boolean functions uniquely and compactly. Hence, BDD have become widely used for CAD applications, such as logic synthesis, formal verification, and etc. The size of the BDD representation for a function is very sensitive to the choice of orderings on the input variables. Therefore, it is very important to find a good variable ordering which minimize the size of the BDD. Since finding an optimal ordering is NP-complete, several heuristic algorithms have been proposed to find good variable orderings. In this paper, we propose a variable ordering algorithm based on the μO (microcanonical optimization). μO consists of two distinct procedures that are alternately applied Initialization and Sampling. The initialization phase is to executes a fast local search, the sampling phase leaves the local optimum obtained in the previous initialization while remaining close to that area of search space. The proposed algorithm has been experimented on well known benchmark circuits and shows superior performance compared to a algorithm based on simulated annealing.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
M. N. Lee and S. Y. Cho, "Computer Graphics & A Minimization Technique for BDD based on Microcanonical Optimization," The KIPS Transactions:PartA, vol. 8, no. 1, pp. 48-55, 2001. DOI: 10.3745/KIPSTA.2001.8.1.48.

[ACM Style]
Min Na Lee and Sang Young Cho. 2001. Computer Graphics & A Minimization Technique for BDD based on Microcanonical Optimization. The KIPS Transactions:PartA, 8, 1, (2001), 48-55. DOI: 10.3745/KIPSTA.2001.8.1.48.