Subcircuits discovery in transistor level CMOS circuits using Graph Mining

In recent years, there has been an increased interest in the development of data mining algorithms that work on graphs. Such graphs occur naturally in a number of different areas, such as network attack detection, semantic web, behavioral modeling, re-designing of VLSI, analysis of social networks and classification of chemical compounds. The problem of Graph Mining is to discover typical patterns of graph data. Common feature of such patterns are frequent subgraphs. Graph Mining is one of the arms of data mining in which voluminous complex data are represented in the form of graphs and mining is done to infer knowledge from them. Frequent subgraph mining (FSM) is a sub section of graph mining domain which is extensively used for graph classification, building indices and graph clustering purposes. Identification of frequently occurring graphs / subgraphs in a database or in one large graph is a method that can be used for motif detection, social network monitoring, fraud detection, etc. Electrical circuits consist of elements that are connected to each other by "wires", and the natural formal model of the description of the scheme is a colored undirected bipartite graph. One part consists of the elements' terminals and ports of the circuit, and the other - the connections (nets) between the terminals, i.e., networks (nets) are the "wires". The transformation of the hierarchical circuit of an electronic device into a circuit consisting solely of primitive elements is naturally called a compilation. The reverse process, in the result of which a hierarchical circuit is built up from a flat circuit, is decompilation. To build a hierarchical structural description, you need to select in the circuit as a separate component a set of interconnected transistors, i.e. find subcircuits in the original circuit. After replacing the subcircuits with elements, the description of the circuit becomes two-level. Modern digital circuits contain up to a billion primitive elements at the transistor level. Assuming that subcircuits are frequent subgraphs, you can try to build a decompiler using the Graph Mining methods. The task FSM has become a popular area of research in the last decade, and so far, the bibliography of this task has hundreds of publications. The complexity of FSM is enormous because of the need to solve many times the problem of subgraph isomorphism. The naive search algorithm for FSM consists of two operations. The first operation searches for all candidate subgraphs for a given graph G, and the second ones calculates the frequency of occurrence of each candidate subgraph. Due to the extremely large computational complexity of the second operation, the well-known practical FSM algorithms are limited to the search for small subgraphs (less than 10 vertices) - graflets. Our study of the known Graph Mining methods shows that, despite the attractiveness of the approach (independence from the style of primitive elements of circuits), the known methods of Graph Mining do not allow to build decompiler of transistor circuits.

Keywords

Authors

References