Improving the efficiency of circuit-to-BDD conversion by gate and input ordering
Improving the efficiency of circuit-to-BDD conversion by gate and input ordering
复制标题
通过门和输入排序提高电路到 BDD 转换的效率
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
K. Sakallah
中科院分区：
文献类型：
--
作者：
F. Aloul;I. Markov;K. Sakallah
布尔函数是数字逻辑综合和验证的基础，布尔函数的紧致表示具有重要的现实意义。常用的表示法，如CNF、DNF、电路和ROBDDS[4]，提供了不同的优势，并且对于不同的任务是首选的。这些表示之间的转换是常见的，特别是当一个用于表示输入而另一个用于加快相关算法的速度时。我们的工作解决了表示给定布尔电路的输出的ROBDDS的构造。它被用于合成和验证。早期作品(藤田、藤泽和川藤，1988)。Malik等人，1988年。)提出了用图遍历法对电路输入和门进行排序。我们利用20世纪90年代末在递归二等分和多级最小分割划分方面取得的进展，基于电路划分和布局进行排序。我们的实验结果表明，基于电路划分和布局的排序方法比直接的DFS和BFS以及相关的启发式算法更成功。
Boolean functions are fundamental to synthesis and verification of digital logic, and compact representations of Boolean functions have great practical significance. Popular representations, such as CNF, DNF, circuits and ROBDDs [4], offer different advantages and are preferred for different tasks. Conversion between those representations is common, especially when one is used to represent the input and another speeds up relevant algorithms. Our work addresses the construction of ROBDDs that represent outputs of a given Boolean circuit. It is used in synthesis and verification. Earlier works (Fujita, Fujisawa, and Kawato, 1988. Malik et al., 1988.) proposed ordering circuit inputs and gates by graph traversals. We contribute orderings based on circuit partitioning and placement, leveraging the progress in recursive bisection and multi-level min-cut partitioning achieved in late 1990s. Our empirical results show that the proposed orderings based on circuit partitioning and placement are more successful than straightforward DFS and BFS, as well as related heuristics.