Efficient Algorithms for Subcircuit Enumeration and Classification for the Module Identification Problem
The problem of extracting RTL modules from a gate level netlist has many interesting applications in digital design (V.K. Madiseti, 1999; P. Schaumont et al., 1999; K. Singh and P. Subrahmunyam, 1995), because it provides a conceptual description of the circuit. We approach this transformation by solving two subproblems: the identification of potential modules (candidate subcircuits) and testing them for functional equivalence to known high-level modules (subcircuit identification).
We present a technique for unique and comprehensive enumeration of subgraphs of an arbitrary graph, as well as a method of recognizing subgraph isomorphisms. Combined, these results provide a solution to the problem of candidate subcircuit enumeration. These techniques provide both theoretical and practical contributions within design automation and graph theory.
White, J. L.,
Wojcik, A. S.,
& Doom, T. E.
(2001). Efficient Algorithms for Subcircuit Enumeration and Classification for the Module Identification Problem. Proceedings of the International Conference on Computer Design, 519-522.