1. Introduction
The STACCATO package implements a structure called the symbolic kernel and an algorithm called smart generalized cofactor to improve upon the performance of previous approaches for computing DSDs from BDDs. STACCATO improves performance while increasing the descriptiveness of the decomposition tree. A brief description of symbolic kernels will be given next and then a description of smart generalized cofactors.
1.1 Symbolic Kernels
The figure below shows how the decomposition tree is represented in STACCATO. Notice that their is another data field added to the internal structure of the node, the symbolic kernel. The symbolic kernel is simply defined as the BDD of the kernel function. For instance, the symbolic kernel of Kf would simply be a BDD with variables representing J, x11, and L. Notice that for undecomposed blocks, i.e. functions with no inherent decompositions like L, the symbolic kernel BDD is actually equal to the BDD of the function L. By adding the symbolic kernels to the decomposition tree, a more detailed description of the DSD is obtained.
1.2 Structure of Symbolic Kernels
To clarify these concepts, consider the figure below that shows a BDD for the function F = (a'b + ac)(d). This function would have the decomposition of F = AND(Prime(a,b,c), d). Therefore the Kf is a function that shows the relationship between the Prime(a,b,c) block and the variable input d. The kernel function is easy to derive here, namely AND2. The BDD on the right side of the figure shows the symbolic kernel for the function F. Notice, that we need to choose a BDD variable to represent each disjoint input. In STACCATO, the bottom BDD variable is chosen, thus c will be used to represent Prime(a,b,c) and the variable d is trivially substituted in for the variable d. We chose a variable from within the support of component functions to reuse BDDs in the package. In the extreme case where a function has no decompositions the symbolic kernel will be exactly equal to the BDD of F. Thus, symbolic kernels do not have memory overhead for undecomposable circuits.
2. Smart Generalized Cofactor
The symbolic kernel can be useful for making cell libraries or providing an alternative encoding for BDDs. But symbolic kernels require computational resources to maintain. Thus, the utility of symbolic kernels could be debatable if the performance for computing DSDs degraded because of symbolic kernel overhead. However, we discovered a symbolic kernel specific optimization, smart generalized cofactor, that can be made in the original DSD algorithm from BDDs. By using smart generalized cofactors, STACCATO provides more information through symbolic kernels and actually achieves speedup in most test instances.
The bottom-up construction algorithm defined previously requires extensive use of an operation called the generalized cofactor. This requires that one take a cofactor with respect to a function instead of just a variable. The figure above provides a visual representation of taking a cofactor of a function, F, with respect to a function A. A series of cofactoring operations need to be made over the big BDD of F to achieve the result. However, with symbolic kernels, the operation can be performed directly on the symbolic kernel. Thus, the operation can be reduced to taking a cofactor with respect to a single variable on the symbolic kernel which is often much smaller than the original function F.
3. Constructing Symbolic Kernels
It is important that the computation required to construct symbolic kernels minimally impacts the complexity of the entire DSD algorithm. As with computing DSDs, symbolic kernels are maintained in two different ways depending on whether the decomposition is constructed as an inherited decomposition or a new decomposition. Inherited and new decompositions are briefly reviewed in the DSD tutorial provided on this webpage and are discussed in more detail in Bertacco '97.
3.1 Symbolic Kernels in Inherited Decompositions
Computing symbolic kernels for inherited decomposition is pretty trivial when the bottom representative variable is used for symbolic kernels. Consider the example for inherited decompositions considered in the DSD tutorial and examine the figure below.
Notice that in this figure, we explicitly show the kernel function for each block by showing a function K with support that consists of the representative variables for that block. For inherited decompositions, it is the case that the symbolic kernel of the resulting inherited decomposition will be equal to the BDD of the symbolic kernel of one of its cofactors. In this example, the symbolic kernel of function F is MAJ(b,e,g) which is identical to the symbolic kernel of Fa=1 which is also MAJ(b,e,g).
3.2 Symbolic Kernels in New Decompositions
Computing symbolic kernels while creating new decompositions is a little more complicated than for inherited decompositions. Most of the details are omitted here but can be found in Plaza '05. In general, the symbolic kernel of a new decomposition is obtained by manipulating the symbolic kernels corresponding to the DSDs of its cofactors in such a way that the resulting symbolic kernel can be produced. This procedure, in general, is much faster than simply taking the resulting new decomposition and substituting a representative variable for each actuals list member by taking generalized cofactors over the original function.
4. Conclusions
STACCATO provides an efficient implementation of a BDD-based DSD computation algorithm. In addition, STACCATO provides a more descriptive decomposition tree representation than previous approaches by introducing a structure called the symbolic kernel. The symbolic kernel could be useful in producing function libraries and in providing a compact alternative to BDDs. Finally, this extra information is achieved with no cost to the performance of STACCATO. Actually, with the use of smart generalized cofactors, the performance of the package is improved. For more information on this, please refer to the paper on STACCATO referenced on the home page.