Dynamic re-encoding during MDD minimization
Dynamic re-encoding during MDD minimization
复制标题
MDD最小化期间的动态重新编码
DOI：
10.1109/ismvl.2000.848626
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
R. Drechsler
中科院分区：
文献类型：
--
作者：
Frank Schmiedle;Wolfgang Günther;R. Drechsler
多值决策图(MDDS)是二叉决策图(BDDS)的推广。它们通常允许高效地表示具有多值输入变量的函数，类似于二进制情况下的BDDS。因此，它们适用于集成电路综合和验证中的多种应用。根据所使用的变量顺序，以节点数计算的MDD大小从线性到指数不等。在所有这些应用中，最大限度地减少MDDS至关重要。在许多情况下，多值变量由一定数量的二进制变量组成，因此多值输入是通过对二进制变量进行分组而产生的。这些组的选择，即决定合并哪些变量，对MDD大小有巨大影响。最近提出了在开始MDD最小化之前寻找变量分组的技术。本文提出了一种使用重新编码的新方法，即动态变量分组。在最小化MDDS之前，我们不选择一个固定的变量分组，而是允许在最小化过程中改变要一起考虑的二进制变量。这是可能的，因为MDDS是在BDDS之上模拟的。这样，底层的二进制变量在整个最小化过程中都保持可访问。文中详细描述了该方法，并给出了实验结果，证明了该方法的有效性。
Multi-valued decision diagrams (MDDs) are a generalization of binary decision diagrams (BDDs). They often allow efficient representation of functions with multi-valued input variables similar to BDDs in the binary case. Therefore they are suitable for several applications in synthesis and verification of integrated circuits. MDD sizes counted in number of nodes vary from linear to exponential dependent on the variable ordering used. In all these applications, minimization of MDDs is crucial. In many cases, multi-valued variables are composed by a certain number of binary variables, and so the multi-valued inputs arise by grouping binary variables. The selection of these groups, that is, the decision which variables to merge, has enormous impact on MDD sizes. Techniques for finding variable groupings before starting MDD minimization have been proposed recently. In this paper we present a new method that uses re-encoding, i.e. dynamic variable grouping. We don't choose one fixed variable grouping before minimizing MDDs, but allow to change the binary variables to be considered together during the minimization process. This is possible since MDDs are simulated on top of BDDs. By this, the underlying binary variables remain accessible throughout the minimization process. This technique is described in detail and we also show experimental results that demonstrate the efficiency of our approach.