AUTOMATIC DESIGNING SYSTEM, AUTOMATIC DESIGNING METHOD AND AUTOMATIC DESIGNING PROGRAM FOR AUTOMATICALLY DESIGNING ARCHITECTURE FOR SYSTEM COMPONENTS

• US 20100332444A1
• Filed: 06/29/2010
• Published: 12/30/2010
• Est. Priority Date: 06/30/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Miyashita, Hisashi, Nerome, Takashi, Nakamura, Hiroaki, Akatsu, Hiroyuki
• Granted Patent: US 8,396,823 B2
• Time in Patent Office: Days
• US Class Current: 706/54
• CPC Class Codes: G06F 30/15 Vehicle, aircraft or watercraft design
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

An automatic designing system includes: a rule storage unit storing sets of rewrite rules for rewriting variable nodes of a hierarchically structured graph in a design architecture for the system; a search unit sequentially determining variable nodes as application targets for the rewrite rules by searching the graph, including components in the design architecture for the system to be designed, using a search tree; a judgment unit judging whether the rewrite rule is applicable to the determined variable node; and a rule application unit replacing the determined variable node with a partial graph, including at least one of fixed and variable nodes, according to the rewrite rule, in response to a judgment that the rewrite rule is applicable. The search unit performs the searching until an undefined variable node no longer exists in the graph to be designed, and performs backtracking on condition that no variable node is found.

Claims

1. An automatic designing system for automatically designing an architecture for components in a system, the automatic designing system comprising:

a rule storage unit which stores a set of rewrite rules each used for rewriting a variable node of a hierarchically structured graph in a design architecture for the system, a rewritable part of the rewrite rules being taken as a variable node and a non-rewritable part being taken as a fixed node in a previously-designed design architecture for the system;

a search unit (i) which sequentially determines variable nodes to be application targets for the rewrite rules by repeatedly searching the graph including components in the design architecture for the system to be designed using a search tree for the graph until an undefined variable node no longer exists in the graph and (ii) which performs backtracking on condition that no variable node to be the application target is found;

a judgment unit which reads one of the rewrite rules corresponding to the determined variable node from the rule storage unit and judges whether or not the rewrite rule is applicable to the determined variable node; and

a rule application unit which replaces the determined variable node with a partial graph in accordance with the read rewrite rule in response to a judgment result that the read rewrite rule is applicable, the partial graph including at least one of the fixed node and the variable node.

2. The automatic designing system according to claim 1, wherein the search unit is configured to search the graph, including the components to be designed, by using the search tree in a depth-first order and in a left-first order for nodes at the same depth.

3. The automatic designing system according to claim 1, wherein:

each of the rewrite rules stored in the rule storage unit includes rewrite-source identification information for identifying a rewrite-source variable node; and

the judgment unit is configured to read, from the rule storage unit, at least one of the rewrite rules which includes the rewrite-source identification information for identifying the determined variable node.

4. The automatic designing system according to claim 3, wherein:

the rewrite-source identification information included in each of the rewrite rules is configured to use Xpath to indicate the rewrite-source variable node; and

the judgment unit is configured to read, from the rule storage unit, at least one of the rewrite rules which includes the rewrite-source identification information for indicating a node located in the corresponding search tree and corresponding to the determined variable node.

5. The automatic designing system according to claim 1, wherein:

each of the rewrite rules stored in the rule storage unit includes rewrite-source identification information for identifying a rewrite-source variable node;

the rule application unit gives a used mark, including identification information of a variable node to which the rewrite rule is applied, to each rewrite rule once used; and

the judgment unit reads, from the rule storage unit, at least one of the rewrite rules which includes the rewrite-source identification information for identifying the determined variable node, and which is given no used mark including the identification information of the determined variable node.

6. The automatic designing system according to claim 1, wherein:

each of the rewrite rules stored in the rule storage unit further includes partial graph information indicating the partial graph with which the variable node being a rewrite source should be replaced and which includes at least one of the fixed node and the variable node; and

the rule application unit rewrites the determined variable node in accordance with the partial graph information.

7. The automatic designing system according to claim 1, wherein:

each of the rewrite rules stored in the rule storage unit includes an application condition indicating a condition for applying the rewrite rule; and

the judgment unit judges that the read rewrite rule is applicable on condition that the application condition is satisfied.

8. The automatic designing system according to claim 7, wherein:

the application condition included in each of the rewrite rules includes judgment target identification information for identifying a variable node to be judged as to whether the applied condition is satisfied and a partial graph condition indicating a certain partial graph including at least one of the fixed node and the variable node;

the judgment unit identifies the variable node in the graph for the components to be designed with reference to the judgment target identification information; and

the judgment unit judges that the read rewrite rule is applicable on condition that (i) the partial graph with which the identified variable node is replaced and (ii) the certain partial graph indicated by the partial graph condition match each other.

9. The automatic designing system according to claim 1, wherein the search tree has, as its nodes, all variable nodes included in the graph for the components to be designed, and has a tree structure corresponding to the hierarchical structure of the graph for the components to be designed.

10. The automatic designing system according to claim 1, wherein the rule application unit updates the search tree in response to the replacement of the determined variable node.

11. A computer-implemented automatic designing method for automatically designing an architecture for components in a system by means of computation by a computer capable of accessing a storage unit which stores a set of rewrite rules each used for rewriting a variable node of a hierarchically structured graph in a design architecture for the system, the rewrite rules being written while a rewritable part is taken as a variable node and a non-rewritable part is taken as a fixed node in a previously-designed design architecture for the system, the automatic designing method comprising the steps of:

(a) storing, in a work area, a graph for components in the design architecture for the system to be designed;

(b) searching the graph, including the components to be designed, by means of computation by the computer using a search tree corresponding to the graph, thereby determining that a variable node is an application target for any of the rewrite rules and then storing, as a current search position, a position of a node in the search tree corresponding to the determined variable node;

(c) reading one of the rewrite rules from the storage unit, and judging, by means of computation by the computer, whether or not the read rewrite rule is applicable to the determined variable node;

(d) in response to a judgment result that the read rewrite rule is applicable, replacing the determined variable node with a partial graph, which includes at least one of the fixed node and the variable node, in accordance with the read rewrite rule by means of computation by the computer, and storing, in the work area, the resultant graph for the components to be designed;

(e) repeating the steps (b) through (d) while updating the current search position until an undefined variable node no longer exists in the graph for the components to be designed; and

(f) backtracking if no variable node is determined to be the application target in the searching step, thereby moving the current search position back to the previous one;

wherein each of the foregoing steps is performed by a data processing machine.

12. A storage medium tangibly storing an automatic design computer program for automatically designing an architecture for components in a system, the automatic designing program, when it is executed by a computer capable of accessing a storage unit which stores a set of rewrite rules each used for rewriting a variable node of a hierarchically structured graph in a design architecture for the system, the rewrite rules being written while a rewritable part is taken as a variable node and a non-rewritable part is taken as a fixed node in a previously-designed design architecture for the system, which program causes the computer to execute the steps of:

(a) storing, in a work area, a graph for components in the design architecture for the system to be designed;

(b) searching the graph including the components to be designed, by means of computation by the computer using a search tree corresponding to the graph, thereby determining a variable node to be an application target for any of the rewrite rules, and then storing, as a current search position, a position of a node in the search tree corresponding to the determined variable node;

(c) reading a corresponding one of the rewrite rules from the storage unit, and judging, by means of computation by the computer, whether or not the read rewrite rule is applicable to the determined variable node;

(d) in response to a judgment result that the read rewrite rule is applicable, replacing the determined variable node with a partial graph, which includes at least one of the fixed node and the variable node, in accordance with the read rewrite rule by means of computation by the computer, and storing, in the work area, the resultant graph for the components to be designed;

(e) repeating the steps (b) through (d) while updating the current search position, until an undefined variable node no longer exists in the graph for the components to be designed; and

(f) backtracking if no variable node is determined to be the application target in the searching step, thereby moving the current search position back to the previous one.