Patent ID: 7886252
Filing Date: 2011-02-08
Classification: G06F

Abstract:
1. A same sub-graph detection apparatus for data flow graph, comprising: a conditional branching selection section configured to select one conditional branching from one or a plurality of conditional branchings in a data flow graph represented by a plurality of nodes indicating computations and branches indicating flows of data input/output to the nodes; a node set selection section configured to select a node set included in the selected conditional branching; a node grouping section configured to divide the selected node set into a plurality of groups, each of the plurality of groups being usable as a sub-graph; and a sub-graph comparison section configured to detect 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, wherein the node grouping section is configured such that for each output node that generates an output of a true block or a false block that is executed when a condition of the conditional branching is “true” or “false”, the node grouping section obtains a combination of the nodes for each node included in the true block or the false block, wherein the outputs of the nodes to be obtained have an effect on the output nodes; and divides combinations of the nodes for the output nodes into node groups, which are the same among the combinations of the nodes for the output nodes, and node groups for each output node other than computation nodes.