Inverter Minimization in Multi-Level Logic Networks

In this paper, we look at the problem of inverter minimization in multi-level logic networks. The network is specified in terms of a set of base functions and the inversion operation. The library is specified as a set of allowed permutations of phase assignments on each base function. Traditional approaches to this problem have been limited to greedy heuristics based on local information. Our approach takes a more global view and maps the problem of inverter minimization into a problem of removing a minimum of vertices from a graph, so as to make the remaining graph 2- colorable. This approach has the flexibility of capturing a variety of design-specific features that are relevant to the problem of inverter minimization. Although, in general the problem is NPcomplete, we have developed several good heuristic and branch and bound search techniques.