Using lower bounds during dynamic BDD minimization
Using lower bounds during dynamic BDD minimization
复制标题
在动态 BDD 最小化期间使用下界
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Wolfgang Günther
中科院分区：
文献类型：
--
作者：
R. Drechsler;Wolfgang Günther
有序二元决策图（BDD）是一种用于表示和操作布尔函数的数据结构，常用于VLSI CAD中。变量排序的选择在很大程度上影响BDD的大小;它的大小可以从线性到指数变化。最成功的寻找好的排序的方法是基于动态变量重新排序，即，相邻变量的交换。这个基本操作已经被用于各种变体中，如筛选和窗口排列。在本文中，我们表明，在最小化过程中计算的下限可以大大加快计算速度。首先，从理论的角度研究了下界。然后，这些技术被纳入动态最小化算法。通过计算好的下界，可以修剪搜索空间的大部分，从而导致非常快的计算。实验结果表明，我们的方法的效率。
Ordered Binary Decision Diagrams (BDDs) are a data structure for representation and manipulation of Boolean functions often applied in VLSI CAD. The choice of the variable ordering largely influences the size of the BDD; its size may vary from linear to exponential. The most successful methods for finding good orderings are based on dynamic variable reordering, i.e., exchanging of neighboring variables. This basic operation has been used in various variants, like sifting and window permutation. In this paper we show that lower bounds computed during the minimization process can speed up the computation significantly. First, lower bounds are studied from a theoretical point of view. Then these techniques are incorporated in dynamic minimization algorithms. By the computation of good lower bounds large parts of the search space can be pruned resulting in very fast computations. Experimental results are given to demonstrate the efficiency of our approach.