Title

Efficient Algorithms for Subcircuit Enumeration and Classification for the Module Identification Problem

Document Type

Conference Proceeding

Publication Date

9-2001

Abstract

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.

Comments

Presented at the International Conference on Computer Design, Austin, TX, September 23-26, 2001.

DOI

10.1109/ICCD.2001.955082

Catalog Record

Share

COinS