JP5253286B2 - Common data flow extraction system and common data flow extraction method - Google Patents

Description

  The present invention relates to a common data flow extraction system and a common data flow extraction method for extracting and outputting a common data flow description from data flow descriptions of a plurality of applications.

  In platform circuits and dynamic reconfiguration circuits that realize multiple types of applications while switching the circuit configuration on a single circuit, using a data path that is too versatile may not provide sufficient performance, or the circuit scale may be enormous There is a problem of becoming too much. Therefore, this problem is solved by using a data path circuit that narrows the functions to be realized to some extent and optimizes performance and circuit scale.

  Conventionally, as a common data flow detection used in such a circuit, for example, there is one described in Patent Document 1. This detection device selects one conditional branch from one or more conditional branches in the data flow graph for digital circuit operation, divides the node set included in the conditional branch into several groups, and A plurality of subgraphs are obtained by performing the processing of subgraphs for one or a plurality of conditional branches. The plurality of subgraphs are compared to detect the same subgraph. Furthermore, the nodes included in each conditional branch in the data flow graph are divided into groups according to a certain rule to make them subgraphs, and the same subgraph is detected by comparing the subgraphs.

JP 2006-139427 A

  However, since the system for detecting a common data flow as described above is a system for detecting the same processing function called a subgraph from the data flow of a single program, a plurality of types of application programs may be input. There is a problem in that it is impossible to extract function processing that exists in common among a plurality of applications.

  The present invention has been made to solve the above problems, and a common data flow extraction system and a common data flow extraction method capable of automatically determining the function of a data path circuit to be prepared in consideration of a plurality of applications. The purpose is to obtain.

  The common data flow extraction system according to the present invention analyzes and compares data flow descriptions of a plurality of applications, extracts data flow descriptions that exist in common among the data flow descriptions of the plurality of applications, and exists in common. A common data flow extracting means for outputting a data flow description is provided.

  Since the common data flow extraction system of the present invention extracts and outputs the data flow description that exists in common among the data flow descriptions of a plurality of applications, the function of the data path circuit to be prepared in consideration of the plurality of applications Can be automatically determined, and the efficiency of the platform circuit and dynamic reconfigurable circuit design can be improved.

It is a block diagram which shows the common data flow extraction system by Embodiment 1 of this invention. It is explanatory drawing which shows the example of a circuit using the common dataflow example in the common dataflow extraction system by Embodiment 1 of this invention, and a common dataflow extraction result. It is a block diagram which shows the common data flow extraction system by Embodiment 2 of this invention. It is a block diagram of the common data flow extraction means of the common data flow extraction system by Embodiment 3 of this invention. It is a flowchart (the 1) which shows the common data flow extraction method by Embodiment 3 of this invention. It is a flowchart (the 2) which shows the common data flow extraction method by Embodiment 3 of this invention. It is a flowchart (the 3) which shows the common data flow extraction method by Embodiment 3 of this invention. It is a flowchart (the 4) which shows the common data flow extraction method by Embodiment 3 of this invention. It is a flowchart (the 5) which shows the common data flow extraction method by Embodiment 3 of this invention. It is explanatory drawing of the data flow expansion | deployment example of the application a in the common data flow extraction system by Embodiment 3 of this invention. It is explanatory drawing of the data flow expansion example of the application b in the common data flow extraction system by Embodiment 3 of this invention. It is explanatory drawing of the common data flow extraction example in the common data flow extraction system by Embodiment 3 of this invention.

Embodiment 1 FIG.
FIG. 1 is a configuration diagram of a common data flow extraction system according to Embodiment 1 of the present invention.
The illustrated common data flow extraction system includes common data flow extraction means 1. The common data flow extraction unit 1 analyzes the input data flow description 2a of the application a and the data flow description 2b of the application b, compares them, and shares a common data flow part between the application a and the application b. It is a means for outputting as data flow 3. The language for describing the data flow is not limited as long as it is a language that can express the data flow. In addition, although an example in which the data flows of two applications are input is shown here, three or more may be used.

FIG. 2 shows an example of a common data flow extracted by the common data flow extraction system of the first embodiment (shown in (a) in the figure) and an example of a circuit configuration configured using this common data flow extraction result ( (Shown in (b)).
In FIG. 2A, as a result of inputting the data flow description 2a of the application a and the data flow description 2b of the application b to the common data flow extracting means 1, the data flow description 2a of the application a and the data flow description 2b of the application b are obtained. It is assumed that a common data flow (A) 3 is extracted as a data flow common to the. Thus, in FIG. 2B, only one block is provided as the common block (A) 6 in the common data flow (A), and the remaining data flow (B) not extracted as the common data flow in FIG. , (C) and (D) are not shared in FIG. 2 (b), and there are configuration examples provided as block (B) 7, block (C) 8 and block (D) 9, respectively. Conceivable. The common block (A) 6 and the other blocks (B) to (D) are connected to each other by the connecting means 10.

  As described above, according to the common data flow extraction system of the first embodiment, the data flow descriptions of a plurality of applications are analyzed and compared, and the data flow descriptions that exist in common among the data flow descriptions of the plurality of applications. Since the common data flow extraction means 1 for extracting the common data flow description and outputting the common data flow description is provided, it is possible to automatically determine the function of the data path circuit to be prepared in consideration of a plurality of applications. It becomes possible to improve the efficiency of architecture studies of circuits that operate multiple applications on the same circuit, such as reconfigurable circuits and platform circuits.

Embodiment 2. FIG.
FIG. 3 is a block diagram showing a common data flow extraction system according to Embodiment 2 of the present invention.
In the figure, the operation description 4a of the application a and the operation description 4b of the application b are operation descriptions described by a C program, an RTL description, or the like. The data flow expansion means 5a and 5b are means for analyzing a plurality of application operation descriptions and expanding them into data flow descriptions. The configuration after the common data flow extraction means 1 is the same as that of the first embodiment.

The operation description 4a of the application a and the operation description 4b of the application b are input to the data flow expansion means 5a and 5b, respectively. The data flow expansion means 5a and 5b are respectively the data flow description 2a of the application a and the application b. The data flow description 2b is expanded.
The common data flow extraction unit 1 analyzes the data flow description 2a of the application a and the data flow description 2b of the application b which are expanded by the data flow expansion units 5a and 5b, and compares the data flow description 2a. A common data flow part is output as a common data flow 3. The common data flow 3 to be output may be a C program or RTL description similar to the operation description input to the common data flow extraction system, or a data flow description. In addition, although an example in which operation descriptions of two applications are input is shown here, three or more may be used.

In the common data flow extraction system, the operation description of the input application may be C language, and the output of the common data flow extraction system may be the RTL description.
In addition, if the common data flow extracted by the common data flow extraction system is output as a file format that defines basic operations in a software compiler, a dynamic reconfiguration circuit that implements the common data flow as a common data path circuit It is also possible to improve the efficiency of software compiler generation for platform circuits.

  As described above, according to the common data flow extraction system of the second embodiment, the common data flow is provided with data flow expansion means for analyzing a plurality of application operation descriptions in C language or RTL language and expanding them into data flow descriptions. Since the extracting means analyzes the data flow descriptions of a plurality of applications developed by the data flow developing means, the common data flow is extracted even for a plurality of application operation descriptions in C language or RTL language. be able to.

Embodiment 3 FIG.
In the common data flow extraction system of the third embodiment, the common data flow extraction means 1 in the first or second embodiment is configured using a data flow comparison unit and a common data flow extraction unit.
FIG. 4 is a configuration diagram of common data flow extraction means in the common data flow extraction system of the third embodiment.
In the figure, the common data flow extraction means includes a first input unit 101a, a second input unit 101b, a data flow comparison unit 102, a common data flow extraction unit 103, a target depth step number storage unit 104, and a matching step number storage unit 105. ing. In addition, the data flow comparison unit 102 includes a reference data flow depth step number storage unit 102a and a non-reference data flow depth step number storage unit 102b. Here, the common data flow extraction unit 1 is realized using a computer, and the data flow comparison unit 102 and the common data flow extraction unit 103 include software corresponding to each function, a CPU and a memory for executing the software, and the like. It consists of hardware. Alternatively, the data flow comparison unit 102 and the common data flow extraction unit 103 may be configured with dedicated hardware.

  The first input unit 101a and the second input unit 101b are used to input a data flow to be compared, such as the data flow description 2a of the application a and the data flow description 2b of the application b illustrated in FIGS. Part. Here, two input units are used for the data flow descriptions of two applications, but three or more input units may be used for three or more data flow descriptions. The data flow comparison unit 102 has a function of comparing calculation types for each number of calculation stages starting from the final point of data flow descriptions of a plurality of applications. The reference data flow depth step storage unit 102a holds the value of the depth step number of the data flow serving as the reference data flow, and the non-reference data flow depth step storage unit 102b is the depth of the data flow serving as the non-reference data flow. This is a storage unit that holds the value of the number of steps. The common data flow extraction unit 103 has a function of extracting the data flow description portion of the target number of steps as a common data flow when the data flow comparison unit 102 obtains the same number of matching steps as the target number of steps. Yes. The target depth step number storage unit 104 is a storage unit that holds a value of the target step number that is set from the outside or is preset as an initial value. The coincidence stage number storage unit 105 is a storage unit that holds values of the number of stages that coincide as a result of comparison in the data flow comparison unit 102.

Next, the operation of the common data flow extraction system of Embodiment 3 will be described.
FIGS. 5-1 to 5-5 are flowcharts illustrating a common data flow extraction method by the common data flow extraction system according to the third embodiment.
<Step ST1> The target depth step number of the common data flow is set. The value of the target depth step number is stored in the target depth step storage unit 104.
<Step ST2> The data flow comparison unit 102 measures the number of depth stages of a plurality of extraction target data flows input from the first and second input units 101a and 101b.
<Step ST3> Among the plurality of extracted data flow depth steps obtained in step ST2, the data flow having the minimum depth step is used as a reference data flow, and the value of the depth step number is stored as the reference data flow depth step number. It is held by the unit 102a. Further, the other data flow is set as a non-reference data flow, and the value of the depth step number is held in the non-reference data flow depth step number storage unit 102b.
<Steps ST4a, ST4b> The data flow comparison unit 102 compares the target depth step number set in step ST1 with the reference data flow depth step number obtained in step ST3, and if the target depth step number is larger, The target depth step value is changed to the reference data flow depth step value. That is, the value of the target depth step number storage unit 104 is changed with the value of the depth step number of the reference data flow depth step number storage unit 102a. On the other hand, if the number of depth steps of the reference data flow is equal to or greater than the target depth step, no change is made.

<Steps ST5a and ST5b> If the target depth step number is larger than 0, the starting point of the reference data flow is set to the lowest point of the data flow, that is, the final operator of the data flow. This is equivalent to setting the starting stage number of the reference data flow to 0. On the other hand, if the target depth step number is 0, it is determined that the common data flow has not been extracted, and the process ends.
<Steps ST6a, ST6b> If “the number of steps in the reference data flow−the number of steps in the target depth” is equal to or greater than the “starting step number of the reference data flow”, the starting point of the non-reference data flow is set to the lowest point, Set the starting stage number of the non-reference data flow to 0. On the other hand, if “the depth step of the reference data flow−the target depth step” is smaller than the “starting step number of the reference data flow”, it is determined that the common data flow of the current “target depth step” has not been extracted. The process proceeds to ST18.

The data flow comparison unit 102 executes the following steps ST7 to ST10 as preprocessing before starting the comparison.
<Steps ST7a, ST7b> If “the number of non-reference data flow depth steps−the number of target depth steps” is equal to or greater than the “starting step number of the non-reference data flow”, the number of matching steps in the matching step number storage unit 105 is reset to zero. . On the other hand, if “the depth step number of the non-reference data flow−the target depth step number” is smaller than the “starting step number of the non-reference data flow”, the common data flow is not extracted at the starting point of the current reference data flow. The process proceeds to step ST17.
<Step ST8> The number of comparison stages is reset to zero.
<Step ST9> The starting stage of the reference data flow is set to the comparison stage of the reference data flow.
<Step ST10> The starting stage of the non-reference data flow is set to the comparison stage of the non-reference data flow.
<Steps ST11a and ST11b> The data flow comparison unit 102 compares the operation types of the comparison stage of the reference data flow and the comparison stage of the non-reference data flow, and determines whether the operation types match.
<Steps ST12a and ST12b> As a result of the comparison in step ST11, if the operation types match, the number of matching stages in the matching stage number storage unit 105 is counted up. As a result, when the coincidence step number and the target depth step number become equal, the common data flow extraction unit 103 outputs the common data flow as extracted, and ends the processing. If the number of matching steps does not reach the target depth step, the data flow comparison unit 102 continues the process from step ST13. On the other hand, if the operation types do not match, the process proceeds to step ST16.

<Step ST13> The comparison stage of the reference data flow is traced back by one stage.
<Step ST14> The comparison stage of the non-reference data flow is traced back by one stage.
<Steps ST15a and ST15b> The number of comparison stages is incremented by one. When the comparison step number reaches the target depth step number, processing from step ST16 is performed. On the other hand, if the comparison step number does not reach the target depth step number, the processes of steps ST11 to ST15 are repeated.
<Step ST16> Since the common data flow could not be extracted in the comparison up to step ST15, the starting point of the non-reference data flow is traced back by one step. That is, the starting stage number of the non-reference data flow is incremented by 1, and steps ST7 to ST16 are repeated.
<Step ST17> It is assumed that the common data flow is not extracted in the comparison up to the above step ST16, that is, the comparison of the reference data flow is performed one step after the start of the non-reference data flow without changing the reference data flow. Go back one step in the flow. That is, the starting point number of the reference data flow is incremented by one.
<Step ST18> Comparison up to the above step ST17, that is, assuming that the common data flow is not extracted with the currently set target depth step number, the target depth step number is counted down by 1, and the processing of step ST5 to step ST17 is performed again. repeat.

Next, a specific example of common data flow extraction will be described.
FIG. 6A shows the C program description of application a. The data flow shown in FIG. 6B is obtained by developing the data flow by the data flow development means 5a (see FIG. 3 in the second embodiment). On the other hand, FIG. 7A shows a C program description of the application b. Similarly, the data flow expanded by the data flow expansion means 5b is the data flow of FIG. 7B. FIG. 8 shows an example in which common data flow extraction is performed on the data flow of application a and the data flow of application b by the method of the third embodiment.

<Step ST1> The target depth step number of the common data flow is set to five steps.
<Step ST2> The depth steps of the data flows of the application a and the application b, which are extraction target data flows, are measured. The number of depth steps for application a is nine, and the number of depth steps for application b is four.
<Step ST3> Since the number of depth steps of the application b is the smallest among the number of depth steps of the plurality of extracted data flows obtained in step ST2, the data flow of the application b is set as a reference data flow.
<Steps ST4a and ST4b> The target depth step number 5 is compared with the target depth step number 4 because the target depth step number is larger. The value of the number of steps is changed to four depth steps of the reference data flow.

<Steps ST5a, ST5b> Since the target depth step number is 4 and larger than “0”, the starting point of the reference data flow is set to the lowest point of the data flow.
<Steps ST6a and ST6b> Since “the number of reference data flow depth steps [4 steps] −the target depth step number [4 steps]” is equal to or greater than “the reference data flow starting step number [0]”, the non-reference data flow Is set to the lowest point, that is, the starting stage number of the non-reference data flow is set to “0”.
<Steps ST7a, ST7b> Since the number of depth steps [9 steps] -target depth step [4 steps] of the non-reference data flow is equal to or greater than the “starting step number [0] of the non-reference data flow”, the number of matching steps Is reset to 0.
<Step ST8> The number of comparison stages is reset to zero.
<Step ST9> The starting stage [0] of the reference data flow is set as the comparison stage of the reference data flow.
<Step ST10> The starting stage [0] of the non-reference data flow is set as the comparison stage of the non-reference data flow.
<Steps ST11a and ST11b> Operation types of the comparison stage [0] of the reference data flow (application b data flow) and the comparison stage [0] of the non-reference data flow (application a data flow), that is, “-(subtraction) ) ”And“ + (addition) ”. At this time, if the subtraction and the addition are considered to have the same operation type, the comparison matches.
<Steps ST12a and ST12b> Since the operation types match, the number of matching stages is counted up to “1 stage”. At this stage, since the number of matching stages “1 stage” has not reached the target depth stage number “4 stages”, the processing from step ST13 is continued.

<Step ST13> The comparison stage of the reference data flow is traced back by one stage. That is, the comparison stage of the application b is “1”.
<Step ST14> The comparison stage of the non-reference data flow is traced back by one stage. That is, the comparison stage of application 1 is “1”.
<Steps ST15a and ST15b> The number of comparison stages is incremented by 1, and the number of comparison stages is set to “1 stage”. Since the comparison stage number “1 stage” has not reached the target depth stage number “4 stages”, the processes of step ST11 to step ST15 (loop 4) are repeated.
<Steps ST11a-2, ST11b-2> Operation types of the comparison stage [1] of the reference data flow and the comparison stage [1] of the non-reference data flow, that is, “no operation”, “+ (addition)”, “+ (Addition) "and" + (addition) "are compared. At this time, since the comparison of one of the calculation types does not match, the process proceeds to step ST16.

<Step ST16> Since the common data flow could not be extracted in the comparison up to step ST15, the starting point of the non-reference data flow is traced back by one step, the starting step number of the non-reference data flow is updated to “1”, and step ST7 -Repeat the process of step ST15 (loop 3).
<Steps ST7a-2, ST7b-2> “Non-reference data flow depth step number [9 steps] −Target depth step number [4 steps]” is not less than “Non-reference data flow start step number [1]” Therefore, the number of matching stages is reset to zero.
<Step ST8-2> The number of comparison stages is reset to zero.
<Step ST9-2> The starting stage [0] of the reference data flow is set as the comparison stage of the reference data flow.
<Step ST10-2> The starting stage [1] of the non-reference data flow is set as the comparison stage of the non-reference data flow.
<Steps ST11a-3 and ST11b-3> Operation types of the comparison stage [0] of the reference data flow (application b) and the comparison stage [1] of the non-reference data flow (application a), that is, “+ (addition)” And “+ (addition)” are compared, and the comparisons match.
<Steps ST12a-2, ST12b-2> Since the operation types match, the number of matching stages is counted up to “1 stage”. At this stage, since the number of matching stages “1 stage” has not reached the target depth stage number “4 stages”, the process from step ST13-2 is continued.

<Step ST13-2> The comparison stage of the reference data flow is traced back by one stage. That is, the comparison stage of the application b is “1”.
<Step ST14-2> The comparison stage of the non-reference data flow is traced back by one stage. That is, the comparison stage of application 1 is “2”.
<Steps ST15a-2 and ST15b-2> The number of comparison stages is incremented by 1, and the number of comparison stages is set to “1 stage”. Since the comparison stage number “1 stage” has not reached the target depth stage number “4 stages”, the processing of step ST11 to step ST15 (loop 4) is repeated.
<Steps ST11a-4 and ST11b-4> The operation types of the comparison stage [1] of the application b and the comparison stage [2] of the application a, that is, “+ (addition)”, “+ (addition)”, “+ ( Addition) ”and“ + (addition) ”are compared, and the comparisons match.
<Steps ST12a-3, ST12b-3> Since the operation types match, the number of matching stages is counted up to “2 stages”. At this stage, the number of coincidence steps “2 steps” has not reached the target depth step number “4 steps”, and hence the processing from step ST13-3 is continued.

<Step ST13-3> The comparison stage of the reference data flow is traced back by one stage. That is, the comparison stage of application b is “2”.
<Step ST14-3> The comparison stage of the non-reference data flow is traced back by one stage. That is, the comparison stage of application 1 is “3”.
<Steps ST15a-3, ST15b-3> The number of comparison stages is incremented by 1, and the number of comparison stages is set to “2 stages”. Since the comparison step number “2 steps” has not reached the target depth step number “4 steps”, the processing of step ST11 to step ST15 (loop 4) is repeated.
<Steps ST11a-5 and ST11b-5> Operation types of the comparison stage [2] of the application b and the comparison stage [3] of the application a, that is, “+ (addition)”, “+ (addition)”, “+ ( “Addition” ”and“ + (addition) ”,“ + (addition) ”and“ + (addition) ”,“ + (addition) ”and“ + (addition) ”are compared, and the comparisons match.
<Steps ST12a-4, ST12b-4> Since the operation types match, the number of matching stages is counted up to “3 stages”. At this stage, the number of coincidence steps “3 steps” has not reached the target depth step number “4 steps”, so the processing from step ST13-4 is continued.

<Step ST13-4> The comparison stage of the reference data flow is traced back by one stage. That is, the comparison stage of the application b is “3”.
<Step ST14-4> The comparison stage of the non-reference data flow is traced back by one stage. That is, the comparison stage of application 1 is “4”.
<Step ST15-4> The number of comparison stages is incremented by 1, and the number of comparison stages is set to “3 stages”. Since the comparison stage number “3” does not reach the target depth stage “4”, the processes of step ST11 to step ST15 (loop 4) are repeated.
<Steps ST11a-6 and ST11b-6> The operation types of the comparison stage [3] of the application b and the comparison stage [4] of the application a, that is, “× (multiplication)” and “x (multiplication)”, “× ( "Multiplication)" and "X (Multiplication)", "X (Multiplication)" and "X (Multiplication)", "X (Multiplication)" and "X (Multiplication)", "X (Multiplication)" and "X (Multiplication)" ) "," X (multiplication) "and" x (multiplication) "," x (multiplication) "and" x (multiplication) "," x (multiplication) "and" x (multiplication) " Match.
<Steps ST12a-5, ST12b-5> Since the types of calculation match, the number of matching stages is counted up to “4 stages”. Since the coincidence step number “4 steps” has reached the target depth step number “4 steps”, it is assumed that the common data flow has been extracted, and the processing is terminated.
As described above, a data flow common to a plurality of applications can be extracted.

  As described above, according to the common data flow extraction system of the third embodiment, as a common data flow extraction unit, a data flow that compares operation types for each number of operation stages starting from the final point of data flow descriptions of a plurality of applications. The comparison unit 102 and the common data flow extraction unit 103 that extracts the data flow description portion of the target number of steps as a common data flow when the matching number of steps corresponding to the predetermined number of target steps is obtained by the data flow comparison unit 102 Since it is provided, it is possible to easily and reliably extract a data flow that exists in common among a plurality of applications.

  Further, according to the common data flow extraction method of the third embodiment, the target depth level of the common data flow to be extracted is set, and the depths of the data flow descriptions of the plurality of applications that are the common data flow extraction target are set. Measure and use the data flow of the application with the smallest depth among the data flows of multiple applications as the reference data flow. If the depth of the reference data flow is smaller than the target depth step number, use the target depth step number as the reference data flow. After initializing the step of changing to the flow depth value and the number of matching stages, the final point of the data flow of multiple applications is used as the starting point, and whether or not the operation type matches or does not match is determined by going back each data flow step by step. If there is a match, count up the number of matching steps and continue to go back one step in the data flow If there is a discrepancy, reset the number of matching steps to 0, shift the starting point of the data flow that is not the reference data flow up one step, and start a new determination, and the number of matching steps reaches the target depth step Is the step of extracting the matching data flow part as a common data flow, and when the determination is completed up to the uppermost stage of the data flow that is not the reference data flow before the matching stage number reaches the target depth stage number, the matching stage number is set to 0. If the determination is completed up to the top level of the reference data flow before the number of matching steps reaches the target depth step A step of resetting the number of steps to 0, reducing the number of target depth steps by one, and determining again from the final point of each data flow as a starting point. The data flow that exists in common can be easily and reliably extracted between publication.

  DESCRIPTION OF SYMBOLS 1 Common data flow extraction means, 2a Data flow description of application a, 2b Data flow description of application b, 3 Common data flow, 4a Operation description of application a, 4b Operation description of application b, 5a, 5b Data flow expansion means, 101a First input unit, 101b Second input unit, 102 Data flow comparison unit, 102a Reference data flow depth level storage unit, 102b Non-reference data flow depth level storage unit, 103 Common data flow extraction unit, 104 Target depth Step number storage unit, 105 Matching step number storage unit.

Claims (4)

  Common data flow extraction that analyzes and compares data flow descriptions of multiple applications, extracts data flow descriptions that exist in common among the data flow descriptions of these multiple applications, and outputs the data flow descriptions that exist in common A common data flow extraction system characterized by comprising means.   Analyzing a plurality of application operation descriptions in C language or RTL language and providing data flow expansion means for expanding the data into a data flow description, and a common data flow extraction means includes data of the plurality of applications expanded by the data flow expansion means 2. The common data flow extraction system according to claim 1, wherein the flow description is analyzed. The common data flow extraction means is
A data flow comparison unit that compares operation types for each number of operation steps starting from the final point of the data flow description of multiple applications;
The data flow comparison unit includes a common data flow extraction unit that extracts a data flow description portion of the target number of steps as a common data flow when the number of matching steps corresponding to a predetermined target number of steps is obtained. The common data flow extraction system according to claim 1 or 2. A common data flow extraction method for extracting a common data flow description executed by the common data flow extraction system according to claim 1, comprising:
Set the target depth level of the common data flow to be extracted, measure the depths of the data flow descriptions of the multiple applications that are the common data flow extraction target, A data flow of a small application is set as a reference data flow, and when the depth of the reference data flow is smaller than the target depth step number, the target depth step number is changed to a depth value of the reference data flow step; ,
After initializing the number of matching stages, starting from the final point of the data flow of the plurality of applications, it is determined whether the operation type matches or does not match while going back through each data flow step by step. If there is a match, the number of matching stages is counted up. And continuing the determination by going back one step of the data flow, and resetting the number of matching steps to 0 in the case of inconsistency, shifting the starting point of the data flow that is not the reference data flow one step upward, and starting a new determination; ,
When the number of matching steps reaches the target depth step number, extracting the matched data flow portion as a common data flow; and
If the determination is completed up to the highest level of the data flow that is not the reference data flow before the number of matching steps reaches the target depth step number, the number of matching steps is reset to 0 and the starting point of the reference data flow is increased by one step. A step of starting a new determination after shifting to
When the determination is completed up to the uppermost stage of the reference data flow before the coincidence step number reaches the target depth step number, the coincidence step number is reset to 0, the target depth step number is reduced by 1, and each data flow is again performed. And a step of making a determination starting from the last point of the common data flow extraction method.

Images