Same Subgraph Detector for Data Flow Graph, High-Order Combiner, Same Subgraph Detecting Method for Data Flow Graph, Same Subgraph Detection Control Program for Data Flow Graph, and Readable Recording Medium

摘要

A same sub-graph detection apparatus for data flow graph is disclosed. An embodiment of the present invention detects a sub-graph at a high speed, in which an area-size reduction effect is large. The same sub-graph detection apparatus for data flow graph according to an embodiment of the present invention includes for a digital circuit behaviour, a conditional branching selection section for selecting one conditional branching from one or a plurality of conditional branchings in a data flow graph; a node set selection section for selecting a node set included in the selected conditional branching; a node grouping section for dividing the selected node set into several groups; and using each of the divided groups as a sub-graph, a sub-graph comparison section for detecting the same sub-graphs by comparing a plurality of sub-graphs obtained as a result of each processing performed on the one or the plurality of conditional branchings by the conditional branching selection section, the node set selection section and the node grouping section. The same sub-graph detection apparatus for data flow graph according to an embodiment of the present invention divides nodes included in each conditional branching in the data flow graph into groups in accordance with a prescribed rule, uses each of the groups as a sub-graph and detects the same sub-graphs by comparing the subgraphs.