Efficient don't care computation for hierarchical designs

In this paper, we describe a BDD-based hierarchical don't care computation algorithm. In contrast to traditional don't care computation techniques, our method retains the hierarchy in the design netlist during the don't care computation. Although this may reduce some of the flexibility inherent in the optimization process, it allows our technique to handle large designs. Our method computes don't cares at input and output interfaces of different modules in the hierarchy by an image computation process. In case an exact image cannot be computed, our method computes the largest approximate image. Once the don't cares at the input and output interfaces are computed, the hierarchical instances are optimized separately using a traditional optimization flow. Experimental results demonstrate that our technique can achieve a 36% reduction in literal count for large hierarchical designs, with reasonable runtimes. Our method can complete for several examples in which flattened optimization fails.