2
$\begingroup$

A straightforward implementation of Binary Decision Diagrams (BDDs) typically requires 12 bytes per node, with an additional 4 bytes commonly used for auxiliary data. Each node is encoded as a 4-tuple with values (hi, lo, value, aux).

Is this memory usage optimal? While researching BDDs, I found numerous papers discussing the theoretical sizes of BDDs (in terms of the total number of nodes) for given circuits. However, there is a lack of information on the specific number of bits needed to encode a single node in a BDD.

Considering that BDDs are a specific type of Directed Acyclic Graph (DAG), this question extends to DAGs in general. What is the optimal bit encoding for nodes in DAGs, and how does this compare to the typical BDD implementation? Are there any known techniques or references that address the encoding efficiency of nodes in DAG structures?

Can anyone provide insights or references on the optimal bit encoding for BDD nodes and DAG nodes in general?

$\endgroup$
6
  • $\begingroup$ What is your reference for the 24 bytes? Also what does "value" stands for? Is it the variable label? 24 bytes may be smaller if the total number of nodes is small as you would not need 8 bytes to encode one pointer. You could be even more succinct by using just the right number of bytes, eg using variable length quantities. $\endgroup$
    – holf
    Commented Jun 24 at 20:02
  • 1
    $\begingroup$ Donald Knuth's BDD14 program uses 32 bytes per node (24 without the ref counter) Microsoft's Decsion Diagrams also uses 24 bytes. Sylvan, a multi core bdd package uses 16 bytes for each node. Value is the variable's label, also called the variable index. $\endgroup$ Commented Jun 25 at 8:27
  • $\begingroup$ I fail to see how this has anything to do with theoretical computer science. Clearly, the size of encoding of nodes in BDD depends on the size of the data that you want to store in the BDD, and for what purpose. There is nothing in the concept itself that would force you to use any particular node size. $\endgroup$ Commented Jun 28 at 8:13
  • $\begingroup$ By itself, a BDD with $n$ nodes is a directed acyclic graph where each nonleaf node is labelled with a yes/no query of some kind, and it has two outgoing edges labelled with the two possible answers, whereas each leaf node is labelled with an output value of some kind. Thus, it suffices to have for each node $2\log_2n$ bits + whatever is needed to represent the queries and/or output values. But you mention reference counters and what not, suggesting you want an implementation with additional frills. This is not a matter of theoretical computer science, but of your implementation. $\endgroup$ Commented Jun 28 at 8:50
  • $\begingroup$ I think this question is a better fit for cs.stackexchange. (How) Should I formally suggest a migration? $\endgroup$ Commented Jul 5 at 19:04

1 Answer 1

3
$\begingroup$

The minimum size of a BDD node. A BDD node must contain enough storage for pointers to the low + high nodes, and optionally the variable index. Let's treat these in turn.

  • The low and high pointers. The two pointers must each have length $\log_2(m^\ast)$ if a node can point to $m^\ast$ different other nodes. Here I mean that a node halfway down the diagram cannot point "up", so in principle this pointer only needs to distinguish between the nodes below it. Unfortunately, there is no good way to take advantage of this by achieving an $m^\ast$ which is much smaller than the total number of nodes $m$ in your diagram. To see this, I remark that a completely populated BDD has $2^k$ nodes at layer $k$ (counting from the root), and will have $m^\ast\geq \frac 12m-o(m)$. So unfortunately you cannot save any bits in these pointers by taking advantage of this fact.
  • The variable index. If only $n$ variables appear in the problems you wish to solve using BDDs, then only $\left\lceil \log_2(n+1) \right\rceil$ bits are required for the variable index. For example, the MQT library uses a 7-bit index, instead of 32 bits, because its intended use case is problems with up to 128 variables. Indeed, in some BDD versions, each node is connected only to nodes on the next layer, so a variable index is redundant.

Minimum node size is not the only objective. Achieving the minimum possible size per node is a good objective. Nevertheless, it is a design choice which is traded off against several other competing objectives that you have when implementing BDD software. The most important other objective is speed: speed is a bottleneck just as often as memory. For example:

  • for this reason, many implementations have a visited bit on each node, which speeds up operations such as counting the number of nodes in a node's subtree, and counting the number of satisfying assignments (the MQT implementation has this, but Microsoft's does not).
  • Many implementations have a flippped bit on each node (or each edge), indicating whether the node represents the function $f$ or $\neg f$ (Microsoft's implementation has this).

More broadly, it is admissible to use a different architecture with larger nodes, if that results in a more succinct diagram. For example,

  • SDDs have nodes that are unbounded in size, but can be exponentially smaller than BDDs in some cases, even when taking into account the size of these large nodes.
  • LIMDDs [6] store $\Theta(n)$ bits per edge and can be exponentially more succinct and exponentially faster than other DDs.
  • the DSDBDD [4,5] will build a BDD for a function $f$, and then will do an extra check to see if $f$ can be written as $f(x,y)=g(x)\wedge h(y)$; if so, then it builds BDDs only for $g$ and $h$ and discards the (much larger) BDD representing the function $f$. This requires more memory per node, but can lead to exponentially smaller and faster diagrams.

These tricks fit into a more general patterns where it is admissible to pay a polynomial cost to solve an exponential problem. In these cases there is a "return on investment". One practical reason why these tricks pay off is that the speed of the operations are heavily influenced by whether the operations cache fits into memory. Indeed, the operations cache can in theory grow to $\mathcal O(m^2)$ size, if you have $m$ nodes in your BDD, so in principle it can be the memory bottleneck. Since $m^2$ items typically doesn't fit in memory (since the $m$ nodes of the DD almost don't fit into memory), you may have to repeatedly recompute intermediate results, which can take exponential time. By designing a more succinct diagram, you then need a much smaller operations cache, which leads (all other things equal) to a much faster implementation.

When I did my PhD, I got good results by aiming to design new DDs which take advantage of the structure of common Boolean functions (instead of aiming to minimize size per node).

Advice for a software implementation. Although you did not specifically ask for advice, in your question I read an implicit intention to build a BDD package, so I take the liberty to give some.

  • It may be profitable to stick some extra helper bits onto a node, such as flipped and visited.
  • design your implementation to be easy to change so that you can easily implement new / additional types of nodes when you have new ideas, and so that you can implement BDD, CBDD, ZDD, etc. without having to write a new implementation from scratch. Microsoft's implementation is actually quite good in this regard. In fact, consider forking their implementation and making your own BDD node a class like their BDD and CBDD nodes.
  • Find new ways to decompose Boolean functions

Why research focuses on the number of nodes. Let me briefly address why, as you point out, most publications on this topic talk about the number of nodes, not about the byte size of these nodes. They are often trying to find asymptotic bounds on the sizes of DDs, in order to better understand the strengths and weaknesses of different types of DDs (e.g., BDD vs. ZDD vs. SDD). In these situations, considering the size of the node is too granular for the intended purpose, because (i) the size of the node is a multiplicative constant factor, which is absorbed into the $\mathcal O(size)$ notation, since $\mathcal O(size)=\mathcal O((\#nodes)\cdot (size\ per\ node))=\mathcal O(\#nodes)$; and (ii) the margin of error in the size of DD nodes is much smaller than the difference between the sizes of different DDs. For example, in [1], Randall Bryant shows that BDDs have size $\mathcal \Omega(2^{n/8})$ for a specific function; whereas in [2], Simone Bova shows that SDDs have size only $\mathcal O(n^3)$. No matter how efficient your encoding, such a BDD will not fit on disk, but the SDD might fit in memory even with a shoddy implementation.

Having said that, some research is of course done at the granularity of counting bits, e.g., [3] compares several decision diagrams and other methods on the number of bytes needed per state stored, both analytically and empirically.

References

[1] Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691.

[2] Bova, Simone. "SDDs are exponentially more succinct than OBDDs." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 30. No. 1. 2016.

[3] Laarman, Alfons. "Optimal compression of combinatorial state spaces." Innovations in Systems and Software Engineering 15 (2019): 235-251.

[4] Bertacco, Valeria, and Maurizio Damiani. "Boolean function representation based on disjoint-support decompositions." Proceedings International Conference on Computer Design. VLSI in Computers and Processors. IEEE, 1996.

[5] Vinkhuijzen, Lieuwe, and Alfons Laarman. "The Power of Disjoint Support Decompositions in Decision Diagrams." NASA Formal Methods Symposium. Cham: Springer International Publishing, 2022.

[6] Vinkhuijzen, Lieuwe, et al. "LIMDD: A decision diagram for simulation of quantum computing including stabilizer states." Quantum 7 (2023): 1108.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.