Don't cares in multi-level network optimization
Hamid Savoj · 1992
An important factor in the optimization of a multi-level circuit, modeled as a Boolean network, is to compute the flexibility for implementing each node of the network and to exploit this flexibility to get a better functional implementation at that node. A general form for describing input-output behavior of a Boolean network is a Boolean relation. This relation or a subset of it, is then used to compute the flexibility for implementing each node in the network. The nodes in the network can be either single or multiple output. In the case of a network composed of single-output nodes, this flexibility is captured by don't cares. Techniques for computing both maximum and compatible don't care sets for each node are presented. In the case of multi-output nodes, don't cares are not sufficient to express input-output behavior of the node. Thus, we present techniques to compute maximal and compatible flexibility at multi-output nodes using Boolean relations. The current model for representing a Boolean circuit uses single output nodes. We present efficient techniques for single-output node simplification that use don't cares in terms of the fanins of node being simplified. The don't care set in terms of fanins of a node is called the local don't care set for that node; it usually has a small size and can be used to remove all the redundancies within that node. Practical issues for computing local don't cares and simplifying nodes are discussed in detail and experimental results are presented that show the effectiveness of the approach. New scripts are designed for technology independent optimization of Boolean circuits which use these new techniques. Finally, a new Boolean matching algorithm is presented that can match two functions with given don't care sets. To prove the effectiveness of the approach, this algorithm is used within a technology mapper where matches are sought between subfunctions in the network and sets of gates in the library. The symmetries of the gates in the library are used to speed up the matching process.