Average path length of binary decision diagrams
Average path length of binary decision diagrams
复制标题
DOI：
10.1109/tc.2005.137
复制
发表时间：
2005-09
影响因子：
3.7
通讯作者：
J. T. Butler;Tsutomu Sasao;M. Matsuura
中科院分区：
文献类型：
--
作者：
J. T. Butler;Tsutomu Sasao;M. Matsuura
二进制决策图（BDD）中的传统问题是最小化节点数量，因为这减少了存储BDD所需的内存。最近出现了一个新的问题：最小化平均路径长度（APL）。APL是通过应用一系列变量值来计算函数所需时间的度量。将bdd应用于仿真和设计验证具有特殊的意义。本文的一个主要结果是，基准函数的api通常比随机函数小得多。也就是说，对于所有函数的集合，我们表明平均APL接近最大路径长度，而基准函数显示非常小的APL。然而，令人惊讶的是，典型函数并没有达到绝对最大的APL。我们证明了奇偶函数在这种区别上是唯一的。我们展示了BDD的APL可以随着不同的排序而发生很大的变化。我们推导了各种函数的api，包括与、或、阈值、阿喀琉斯之踵和某些算术函数。我们证明了单级联函数唯一地实现了绝对最小的APL。
The traditional problem in binary decision diagrams (BDDs) has been to minimize the number of nodes since this reduces the memory needed to store the BDD. Recently, a new problem has emerged: minimizing the average path length (APL). APL is a measure of the time needed to evaluate the function by applying a sequence of variable values. It is of special significance when BDDs are used in simulation and design verification. A main result of this paper is that the APL for benchmark functions is typically much smaller than for random functions. That is, for the set of all functions, we show that the average APL is close to the maximum path length, whereas benchmark functions show a remarkably small APL. Surprisingly, however, typical functions do not achieve the absolute maximum APL. We show that the parity functions are unique in having that distinction. We show that the APL of a BDD can vary considerably with variable ordering. We derive the APL for various functions, including the AND, OR, threshold, Achilles' heel, and certain arithmetic functions. We show that the unate cascade functions uniquely achieve the absolute minimum APL.