Skip to main content
Presentation
Efficient Algorithms for Subcircuit Enumeration and Classification for the Module Identification Problem
Proceedings of the International Conference on Computer Design
  • Jennifer L. White
  • Moon-Jung Chung
  • Anthony S. Wojcik
  • Travis E. Doom, Wright State University - Main Campus
Document Type
Conference Proceeding
Publication Date
9-1-2001
Catalog Record
Catalog Record
Disciplines
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
Citation Information
Jennifer L. White, Moon-Jung Chung, Anthony S. Wojcik and Travis E. Doom. "Efficient Algorithms for Subcircuit Enumeration and Classification for the Module Identification Problem" Proceedings of the International Conference on Computer Design (2001) p. 519 - 522 ISSN: 0769512003
Available at: http://works.bepress.com/travis_doom/38/