Data flow graph processing method

The present invention relates to a data flow graph processing method for processing a data flow graph necessary for setting the operation of a reconfigurable circuit whose function can be changed.

In recent years, the development of a reconfigurable processor using a multifunctional element having a plurality of basic arithmetic functions called an ALU (Arithmetic Logic Unit) has been promoted (see, for example, Patent Document 1). In the reconfigurable processor, the desired arithmetic processing circuit can be realized as a whole by sequentially setting the command data in the ALU circuit.

Command data is created as data that creates a data flow called DFG (Data Flow Graph) from a source program written in a high-level program language such as C language, and maps the DFG to an ALU circuit. The command data is created according to the processing order of the circuits configured on the ALU circuit, and is stored in the continuous storage area of the address.<patcit num="1"><text>Japanese Unexamined Patent Publication No. 2004-220377</text></patcit>

<p> In the conventional reconfigurable processor, command data is sequentially read from the memory and supplied to the ALU circuit to set the function of the ALU circuit. Therefore, if a condition judgment process such as an if statement exists in the source program, command data for executing multiple branching processes is set on the ALU circuit, the operation is executed in advance, and the condition judgment is executed. Later, it is necessary to select the calculation processing result according to the determination result.</p><p> In this case, only one of the arithmetic processing results of the branch is actually used, and the other arithmetic processing result is not used. As a result, the calculation processing time becomes longer than necessary.</p><p> In addition, when a predetermined number of loop operations such as a for statement exist in the source program, the conventional reconfigurable processor needs to store the command data group of the same loop operation for a predetermined number of times at consecutive addresses in the memory. There is.</p><p> For example, if the number of loops is 10, it is necessary to store the same command data group in the memory for 10 times, which increases the amount of command data. Further, when the number of loops is indefinite, it is difficult to generate command data because the number of repetitions is unknown.</p><p> The present invention has been made in view of the above points, and an object of the present invention is to provide a data flow graph processing method capable of efficiently processing a data flow graph necessary for setting the operation of a reconfigurable circuit. ..</p>

<p> In order to solve the above problems, the present invention relates to a method of processing a data flow graph necessary for setting an operation of a reconfigurable circuit whose function can be changed. This data flow graph processing method is a step of dividing a program that describes the desired arithmetic processing into two or more subprograms, and data that expresses the dependency of the operator processing order for each of the two or more subprograms. It includes a step to convert it into a flow graph. The division step divides the program based on the description contents of the program. At this time, the branch processing included in the program may be detected and each of the branch destination processes may be extracted as a subprogram.</p><p> According to the characteristics of the present invention, the number of data flow graphs required for executing the loop statement can be reduced by dividing the program into a plurality of subprograms. Therefore, the amount of set data generated by converting the data flow graph can be reduced, and the memory capacity for storing the set data amount can be reduced. Further, since the amount of set data is reduced, the circuit scale of the reconfigurable circuit can be reduced, and the processing time of the branch statement can be shortened.</p><p> Another aspect of the present invention relates to a method of processing a data flow graph necessary for setting the operation of a reconfigurable circuit whose function can be changed. This data flow graph processing method includes a step of converting a program describing the desired arithmetic processing into two or more data flow graphs according to conditional branching included in the program.</p><p> According to the characteristics of the present invention, by creating a data flow graph for each conditional branch, when the setting data of the data flow graph is mapped to the reconfigurable circuit, the data flow of the branch destination is determined according to the determination result of the condition. You can select the graph each time. Therefore, the processing time can be shortened, the processing performance can be improved, and the power consumption can be reduced.</p><p> Yet another aspect of the present invention is a method of processing a data flow graph necessary for setting the operation of a reconfigurable circuit whose function can be changed, in which a program describing the desired arithmetic processing is substituting two or more. It includes a step of dividing into programs and a step of generating flow data of a data flow graph showing the processing order of the data flow graph representing the dependency of the processing order of operators corresponding to each of two or more subprograms. ..</p><p> According to the features of the present invention, by defining the processing order of the data flow graphs corresponding to the plurality of subprograms, it is possible to efficiently map the setting data corresponding to the data flow graphs to the reconfigurable circuit.</p><p> In the above invention, the reconfigurable circuit may have an arithmetic logic circuit capable of selectively executing a plurality of types of multi-bit operations.</p><p> Another aspect of the present invention is a data flow graph processing method for processing a data flow graph necessary for setting the operation of a reconfigurable circuit whose function can be changed, and the reconfigurable circuit is a process corresponding to the function. Is executed sequentially for each execution step, and the program is converted into the data flow graph expressing the dependency of the processing order of the operators based on the specific description contents in the program that executes the desired arithmetic processing. It is characterized by including a step of dividing the program into two or more subprograms according to the number of execution steps of the reconfigurable circuit corresponding to the converted data flow graph.</p><p> In the above invention, in the division step, if the number of execution steps of the reconfigurable circuit corresponding to the converted data flow graph exceeds the reference number, the program may be divided into two or more subprograms. .. This reference number may be set according to the processing capacity of the reconfigurable circuit.</p><p> In the above invention, the specific description content provides a condition for shifting the arithmetic processing to one of the other plurality of arithmetic processes when the arithmetic processing is branched from one arithmetic processing to a plurality of other arithmetic processes. The description content shown may be included.</p><p> In the above invention, the specific description content may include a description content indicating a condition for repeatedly executing the same arithmetic processing a plurality of times.</p><p> It should be noted that the present invention is naturally applicable not only as a method but also as a device, a circuit, a system, and a computer program.</p>

<p> According to the present invention, it is possible to efficiently process the data flow graph required for setting the operation of the reconfigurable circuit.</p>

FIG. 1 is a configuration diagram of the processing apparatus 10 according to the embodiment. The processing device 10 includes an integrated circuit device 26 having a function of reconfiguring the circuit configuration. The integrated circuit device 26 is configured as one chip, and includes a reconfigurable circuit 12, a setting data holding unit 14, a sequencer device 20, an output data holding unit 30, and a path unit 32. The function of the reconfigurable circuit 12 can be changed by changing the setting. The reconfigurable circuit 12 in this embodiment sequentially executes the processing corresponding to the function for each execution step (stage shown in FIG. 2 to be described later).

The setting data holding unit 14 holds a plurality of setting data for configuring the desired circuit in the reconfigurable circuit 12, and sequentially supplies the setting data to the reconfigurable circuit 12 at predetermined time intervals. The setting data holding unit 14 may be configured as a command memory that outputs the stored setting data based on the designated address value. In this case, the setting data can be called command data. The sequencer device 20 has a function of selecting setting data to be supplied to the reconfigurable circuit 12 from a plurality of setting data stored in the setting data holding unit 14.

The path unit 32 functions as a feedback path and connects the output of the reconfigurable circuit 12 to the input of the reconfigurable circuit 12. The output data holding unit 30 has a storage area for storing a data signal output from the reconfigurable circuit 12 and / or a data signal input from the outside. The data signal stored in the output data holding unit 30 is transmitted to the input of the reconfigurable circuit 12 through the path unit 32, and is output to the outside of the processing device 10 based on an output instruction from a control unit (not shown).

The reconfigurable circuit 12 is configured to include a plurality of logic circuits whose functions can be changed. Specifically, the reconfigurable circuit 12 has a configuration in which logic circuits capable of selectively executing a plurality of arithmetic functions are arranged in a plurality of stages. The reconfigurable circuit 12 has a connection portion capable of setting a connection relationship between the output of the logic circuit sequence of the previous stage and the input of the logic circuit sequence of the subsequent stage. The plurality of logic circuits may be arranged in a matrix.

The function of each logic circuit and the connection relationship between the logic circuits are set based on the setting data supplied by the setting data holding unit 14. The setting data is supplied to the reconfigurable circuit 12 at predetermined time intervals. Therefore, the reconfigurable circuit 12 executes an arithmetic processing function according to the supplied setting data.

The sequencer device 20 manages the setting data supplied to the reconfigurable circuit 12 by the setting data holding unit 14 based on the calculation result in the reconfigurable circuit 12, specifically, the determination result of the branch condition. The sequencer device 20 outputs the desired setting data from the setting data holding unit 14 based on the control data generated from the program to be executed. The setting data and control data are generated by the following procedure.

The program to be realized by the integrated circuit device 26 is stored in the storage unit 40. The program describes the desired arithmetic processing in the reconfigurable circuit 12, and specifically describes the signal processing circuit or the signal processing algorithm in a high-level language such as C language.

The compilation unit 50 reads out the program stored in the storage unit 40. The compilation unit 50 compiles the read program and generates a plurality of data flow graphs (DFGs) and flow data indicating the processing order of the DFGs. The compilation unit 50 stores the generated DFG and its flow data in the storage unit 40.

DFG expresses the dependency of the processing order of operators (between operations) in a circuit, and shows the flow of operations of input variables and constants in a graph structure. Generally, a DFG is formed so that operations proceed from top to bottom.

A plurality of DFGs are generated by decomposing one program into a plurality of subprograms and converting each of the subprograms. The DFG flow data is generated so as to determine the processing order of DFGs corresponding to a plurality of subprograms, and particularly to determine the processing order of DFGs of the branch source and the branch destination when a conditional branch occurs.

The setting data generation unit 51 converts the DFG into the corresponding setting data and stores it in the setting data holding unit 14. The control data generation unit 54 converts the DFG flow data into the corresponding control data and stores it in the sequencer device 20. The setting data is data for mapping the DFG to the reconfigurable circuit 12, and determines the function of the logic circuit in the reconfigurable circuit 12 and the connection relationship between the logic circuits.

The control data is data expressing the connection relationship of the setting data (DFG) mapped to the reconfigurable circuit 12. For the control data, the DFG to be the branch destination is determined according to the branch control data_SEQ_ which is the determination result of the branch condition during the execution of the operation in the reconfigurable circuit 12.

The sequencer device 20 supplies a read address to the setting data holding unit 14. At this time, the read address of the setting data to be supplied to the reconfigurable circuit 12 is determined next according to the value of the branch control data_SEQ_ or the like supplied from the reconfigurable circuit 12. When the setting data holding unit 14 receives the read address, the setting data holding unit 14 supplies the setting data stored in the read address to the reconfigurable circuit 12.

FIG. 2 shows an example of the configuration of the reconfigurable circuit 12. The reconfigurable circuit 12 is a connection in which a multi-stage arrangement of logic circuits, each of which can selectively execute a plurality of arithmetic functions, and a connection relationship between the output of the logic circuit in the previous stage and the input of the logic circuit in the subsequent stage can be arbitrarily set. It has a part 52.

In the reconfigurable circuit 12, the calculation proceeds from the upper stage to the lower stage due to the multi-stage array structure of the logic circuit. In addition, in this specification, "multi-stage" means a plurality of stages. The circuit configuration of the reconfigurable circuit 12 does not necessarily have to have a multi-stage array, but it does not enable connection between all logic circuits in order to reduce the circuit scale, and some logic circuits are connected to each other. It is preferable to realize the connection of.

The reconfigurable circuit 12 has an ALU (Arithmetic Logic Unit) as a logic circuit. The ALU is an arithmetic logic circuit that can selectively execute a plurality of types of multi-bit operations, and can selectively execute a plurality of types of multi-bit operations such as OR, AND, and bit shift by setting. Each ALU is configured to have a selector for setting a plurality of arithmetic functions. In the illustrated example, the ALU is configured with two input terminals and one output terminal.

The reconfigurable circuit 12 is configured as an X-stage Y-row ALU array in which X ALUs are arranged in the vertical direction and Y ALUs are arranged in the horizontal direction. Here, an ALU array with 3 rows and 6 rows in which 3 ALUs are arranged in the vertical direction and 6 ALUs in the horizontal direction are shown.

The reconfigurable circuit 12 includes a connection 52 and an ALU row 53. The ALU row 53 is provided in a plurality of stages, and the connection portion 52 is provided between the ALU rows 53 in the front and rear stages to set the connection relationship between the output of the ALU in the front stage and the input of the ALU in the rear stage.

In the example shown in FIG. 2, the connecting portion 52b constituting the second stage is provided between the ALU row 53a of the first stage and the ALU row 53b of the second stage. A connection portion 52c constituting the third stage is provided between the ALU row 53b of the second stage and the ALU row 53c of the third stage. The connecting portion 52a constituting the first stage is provided above the ALU row 53a of the first stage.

Input variables and constants are input to ALU11, ALU12, ..., ALU16 in the first stage, and the set predetermined operations are performed. The output of the calculation result is input to ALU21, ALU22, ..., ALU26 of the second stage according to the connection set in the connection unit 52b of the second stage.

In the connection portion 52b of the second stage, an arbitrary connection relationship or a combination of predetermined connection relationships can be selected between the output of the ALU column 53a of the first stage and the input of the ALU column 53b of the second stage. The connection connection is configured so that the established connection relationship can be realized, and the desired connection becomes effective depending on the setting.

The output of the ALU column 53a is input to the ALU21, ALU22, ..., ALU26 in the second stage, and the set predetermined calculation is performed. The output of the calculation result is input to ALU31, ALU32, ..., ALU36 of the third stage according to the connection set in the connection connection of the connection portion 52c of the third stage.

The output data from the ALU column 53c of the third stage, which is the final stage, is output to the output data holding unit 30. The output data holding unit 30 inputs output data to the connecting unit 52a via the route unit 32. The connection unit 52a sets the connection for connection and supplies data to ALU11, ALU12, ..., ALU16 in the first stage. When the final result of the arithmetic processing is generated, the output data holding unit 30 outputs the data to the outside of the processing device 10.

FIG. 3 shows the configuration of the compilation unit 50. The compilation unit 50 includes a program analysis unit 100, a sequence processing unit 102, a division unit 104, a DFG generation unit 106, and a flow data generation unit 108.

The data flow graph processing function in the embodiment is realized by a CPU, a memory, a DFG processing program loaded in the memory, and the like in the processing device 10, and here, a functional block realized by their cooperation is drawn. The DFG processing program may be built in the processing device 10 or may be supplied from the outside in the form of being stored in the recording medium. Therefore, it will be understood by those skilled in the art that these functional blocks can be realized in various forms by hardware only, software only, or a combination thereof.

FIG. 4 shows a flowchart of the DFG processing method in this embodiment. First, the program analysis unit 100 reads the program stored in the storage unit 40 (S10) and executes the analysis of the program (S12).

The program analysis unit 100 is a preprocessing unit for efficiently executing the subsequent processing, and executes expansion of functions included in the program. The sequence processing unit 102 adds a sequence processing specification and a branch condition operation to the program based on the program description content (S14).

In this embodiment, the sequence processing is a preprocessing for dividing the program into a plurality of subprograms, detects the branch processing in the program, and executes the sequence processing designation. The division unit 104 divides the program into a plurality of subprograms based on the sequence processing designation added by the sequence processing unit 102 (S16). At this time, the division unit 104 extracts each of the processing at the branch destination as a subprogram.

The DFG generation unit 106 generates a DFG suitable for the circuit configuration of the reconfigurable circuit 12 for each subprogram (S18) and stores it in the storage unit 40. The flow data generation unit 108 generates DFG flow data based on the program and subprogram to which the sequence processing specification and the branch condition are added (S22).

The setting data generation unit 51 generates the setting data for the reconfigurable circuit 12 from the generated DFG (S20), and the control data generation unit 54 sets the control data for setting in the sequencer device 20 from the flow data of the DFG. Is generated (S24).

FIG. 5 shows an example of the source program. In this program, when func0 is executed, func1 is called. Figure 6 shows the form in which func1 is expanded into func0 and combined into one program. The program analysis unit 100 executes the expansion process of this function. By expanding the function, it is possible to efficiently execute the sequence processing specification to be executed later and the program division processing. The sequence processing unit 102 adds a specification of sequence processing and an operation of a branch condition to the program analyzed by the program analysis unit 100.

FIG. 7 is a flowchart showing the operation of the sequence processing unit 102. First, the sequence processing unit 102 sets m to the number of lines in the program (S100). The sequence processing unit 102 refers to the program shown in FIG. 6, and sets m = 10 because the number of lines of the program is 10. The sequence processing unit 102 sets i = 1 (S102). The sequence processing unit 102 analyzes the i-th line of the program (S104) to check whether it is a part that executes the sequence processing (S106).

Sequence processing is a pre-processing for dividing a program, and if the arithmetic processing cannot be executed simply by converting it to DFG like a loop operation with an indefinite number of loops, or if the sequence processing is executed, the circuit scale and processing It is executed when the performance such as speed is improved, and whether or not to execute is determined by the function in the program or the processing content.

In this embodiment, the sequence processing is executed when the number of operations in the statement is 2 or more in the branch statement (if statement, etc.) and the number of loops is indefinite or 10 or more in the loop statement (for statement, etc.). In this way, by determining the execution of sequence processing based on whether or not the processing amount of the branch destination exceeds a predetermined amount, it is possible to efficiently create the setting data to be supplied to the reconfigurable circuit 12. Become.

In the program of FIG. 6, since the description content of the first line of the program is "int i;" and the description content is not a branch statement or a loop statement, the sequence processing unit 102 does not execute the sequence processing (N in S106). .. At this time, the sequence processing unit 102 determines whether or not i is equal to m (S114). Here, since i = 1 and m = 10 (N in S114), the sequence processing unit 102 adds 1 to i (S116) to set i = 2.

The step returns to S104, and since the description content of the second line of the program is "x + = 1;", the sequence processing unit 102 similarly determines that the sequence processing is not executed (N in S106). The sequence processing unit 102 adds 1 to i (S116) to set i = 3. The description on the third line of the program is "if (* y&gt; 0) {".

The execution condition of the sequence processing of the if statement is that there are two or more operations as described above. If you refer to the operations in the if statement here, they are "x = x &gt;&gt; 2;" and "* y- = x + 3;", and since the number of operations is two or more, the sequence processing unit 102 performs sequence processing. Determine to execute (Y in S106).

Next, the sequence processing unit 102 executes the syntactic analysis of the program, and selects the range of the sequence processing and the branching condition (S108). In this case, the range of sequence processing is "if () {...}" and the branch condition is "* y&gt; 0". Next, the sequence processing unit 102 adds an arithmetic instruction for determining the branch condition to the program (S110).

FIG. 8 shows a program in which a determination operation instruction is added before the if statement of the program shown in FIG. In this example, the determination operation instruction is "_SEQ_ = * y&gt; 0;". The branch condition is "* y&gt; 0". Therefore, the sequence processing unit 102 describes the if statement as "if (_SEQ_)" in order to indicate that it is a part that executes the sequence processing (S112).

"If (_SEQ_)" is a "sequence processing specification" indicating that it is a part for executing sequence processing. Here, "_SEQ_" is a variable corresponding to the output signal from the reconfigurable circuit 12 required for branch selection.

When the arithmetic processing in the reconfigurable circuit 12 is executed, _SEQ_ is supplied from the reconfigurable circuit 12 to the sequencer device 20 as branch control data. When the sequencer device 20 receives the branch control data_SEQ_, it generates a read address for the setting data of the DFG to be executed next based on the control data to be held, and supplies the read address to the setting data holding unit 14.

After S112, the sequence processing unit 102 determines whether i is equal to m (S114). At this time, since the sequence processing unit 102 has i = 3 and m = 10 (N in S114), 1 is added to i (S116) to set i = 4.

The sequence processing unit 102 does not execute the sequence processing because the description content of the fourth line of the program is "x = x &gt;&gt; 2;" (N in S106). The sequence processing unit 102 adds 1 to i and sets i = 5 (S116). After that, the flow is executed in the same way. When i = 8, the description on the 8th line of the program is "for (i = 0; i &lt;100; i ++) {". The condition for sequence processing of the for statement is that the number of loops is indefinite or 10 or more as described above. Here, referring to the number of loops in the for statement, the number of loops is 100. Therefore, the sequence processing unit 102 determines that the sequence processing is executed (Y in S106).

The sequence processing unit 102 executes parsing of the program and selects the range of sequence processing and branching conditions (S108). In this case, the range of sequence processing is "for () {...}" and the branching condition is "i &lt;100". Next, an arithmetic instruction for determining the branch condition is added to the program (S110). Since the branch condition is i &lt;100, the sequence processing unit 102 adds the determination operation instruction _SEQ_ = i &lt;100; to the end of the for statement, as shown in FIG. Also, add "i = 0;" for initializing i before the for statement.

Then, the sequence processing unit 102 describes the for statement as "do {...} while (_SEQ_);" in order to indicate that it is a part that executes the sequence processing (S112). "Do {...} while (_SEQ_);" is a "sequence processing specification" indicating that it is a part for executing sequence processing. In this case, the number of loops is fixed at 100, but if the number of loops is indefinite, for example, the branch condition is "i &lt;* y", the judgment operation command " Add "_SEQ_ = i &lt;* y;".

Subsequently, the sequence processing unit 102 determines whether or not i is equal to m (S114). Since the sequence processing unit 102 has i = 8 and m = 10 (N in S114), 1 is added to i (S116) to set i = 9. After that, the flow is executed in the same manner, and the sequence processing unit 102 ends the sequence processing in the sequence processing unit 102 because i = m when i = 10 (Y in S114). By the above sequence processing, the program with the sequence designation shown in FIG. 8 is generated. The division unit 104 divides the program into subprograms based on the sequence processing designation.

FIG. 9 is a flowchart showing the operation of the division unit 104. First, the division unit 104 sets m to the total number of program parts specified for sequence processing (S200). In the program with sequence designation shown in FIG. 8, there are two sequence processing parts, "if (_SEQ_) {...}" and "do {...} while (_SEQ_)". Therefore, the division unit 104 sets m = 2.

Next, the division unit 104 determines whether or not m is 0 (S202). If m = 0 (Y in S202), the division unit 104 sets all the programs as one subprogram (S212) and ends the division process. Here, since the division portion 104 has m = 2 (N in S202), i = 1 is set (S204).

Subsequently, the division unit 104 divides the i-th sequence processing designation program portion as one subprogram (S206). With reference to FIG. 8, since the first sequence processing part is if (_SEQ_) {...}, the division part 104 uses that part as one subprogram.

FIG. 10 shows a plurality of subprograms finally generated by dividing the program shown in FIG. 8, and if (_SEQ_) {...} is a subprogram shown in func02 of FIG. It is cut out.

The "if (_SEQ_)" in the program corresponds to the judgment of whether to execute func02, and this judgment is based on the value of _SEQ_ output from the reconfigurable circuit 12 shown in FIG. It is executed by the sequencer device 20. Therefore, the operations to be converted to DFG are "x = x &gt;&gt; 2;" and "* y- = x + 3;", and "if (_SEQ_)" does not need to be converted to DFG, so it is added to the subprogram. Absent.

Subsequently, the dividing unit 104 determines whether or not i is equal to m (S208). Since the division portion 104 has i = 1 and m = 2 (N in S208), 1 is added to i (S210) to set i = 2.

The step returns to S206, and the second sequence processing part is "do {...} while (_SEQ_);", so the division unit 104 similarly sets that part as one subprogram. Do {...} while (_SEQ_); is cut out as a subprogram shown in func04 in FIG.

Subsequently, the dividing unit 104 determines whether or not i is equal to m (S208). Since the division portion 104 has i = 2 and m = 2 (Y in S208), it moves to S214. With the processing up to this point, subprogramming of the program part specified for sequence processing is completed.

Next, the division unit 104 executes subprogramming of the remaining program portion. First, the division unit 104 determines whether or not there is a program before the program specified for the first sequence processing (S214). Since there is a program before the first sequence processing designation program "if (_SEQ_) {...}" (Y in S214), the division unit 104 makes that program one subprogram (S216). As a result, the subprogram shown in func01 in FIG. 10 is generated.

Subsequently, the dividing unit 104 determines whether or not m is equal to 1 (S218). If the program does not exist before the program specified for the first sequence processing (N in S214), the division unit 104 directly executes the determination in S218. In this example, the division 104 has m = 2 (N in S218), so j = 1 is set (S220).

Subsequently, the division unit 104 executes a determination as to whether or not there is a program between the jth sequence processing designation program and the (j + 1) th sequence processing designation program (S222). Here, there is a program between the first sequence processing specification program "if (_SEQ_) {...}" and the second sequence processing specification program "do {...} while (_SEQ_);". Therefore (Y of S222), the division unit 104 makes the program one subprogram (S224). As a result, the subprogram shown in func03 in FIG. 10 is generated.

Subsequently, the dividing unit 104 determines whether or not j is equal to m-1 (S226), and in this example, j = 1, m = 2, and j = m-1 (S226). Y), the division unit 104 executes a determination as to whether or not there is a program after the program specified for the m-th sequence processing (S230). Here, since there is no program after the second sequence processing designation program "do {...} while (_SEQ_);" (N of S230), the division unit 104 ends this flow.

In S218, when m is equal to 1 (Y in S218), the dividing unit 104 shifts to S230 and executes a determination as to whether or not there is a program after the program specified for the first sequence processing. .. If a program exists (Y in S230), the division unit 104 divides the part after the program specified for the m-th sequence processing into one subprogram (S232).

Also, in S226, if j is not equal to (m-1) (N in S226), the dividing unit 104 adds 1 to j (S228) and returns to S222, during the program specified for sequence processing. Executes the determination of whether or not there is a program.

By the above division processing, the subprogram shown in FIG. 10 is generated. The DFG generation unit 106 converts the subprograms shown in FIG. 10 into DFGs, respectively. FIG. 11 shows the DFG generated by the DFG generation unit 106. The setting data generation unit 51 generates setting data to be supplied to the reconfigurable circuit 12 based on these DFGs.

Next, the flow data generation unit 108 generates DFG flow data based on the program with the sequence designation shown in FIG. 8 and the subprogram shown in FIG.

FIG. 12 is a flowchart showing the operation of the flow data generation unit 108. First, the flow data generation unit 108 examines which part of the program with the sequence designation in FIG. 8 corresponds to all the subprograms in FIG. 10 (S300). As a result, the flow data generation unit 108 investigates the connection relationship of the subprograms, that is, the connection relationship of the DFG. At this time, the flow data generation unit 108 replaces the operations in the program of FIG. 8 with func01 to func04 of FIG. FIG. 13 shows a flow program in which the operations in the program are replaced from func01 to func04.

Subsequently, the flow data generation unit 108 is arranged in order from the subprograms upstream of the flow program based on the survey results in S300 (S302). As a result, the execution order between DFGs is determined, and the DFGs are arranged according to the execution order.

FIG. 14 shows DFG flow data. In the flow program of FIG. 13, the most upstream subprogram is func01. Therefore, as shown in FIG. 14, the flow data generation unit 108 arranges func01 at the top of the DFG flow data. Then, since the subprogram that appears next is func02, the flow data generation unit 108 arranges func02 in the second stage as shown in FIG. Similarly, the flow data generation unit 108 arranges func03 in the third stage and func04 in the fourth stage.

Next, the flow data generation unit 108 sets m to the total number of subprograms (S304). Since the total number of subprograms shown in FIG. 10 is 4, the flow data generation unit 108 sets m = 4. Further, the flow data generation unit 108 sets i = 1 (S306). Then, the flow data generation unit 108 examines the i-th subprogram to find out how many subprograms may be transferred from the survey result (S308).

Here, i = 1, and referring to the flow program in FIG. 13, the subprogram executed after the first subprogram func01 is func02 or func03. Therefore, the total number of subprograms that may be migrated from func01 is two, and the flow data generator 108 sets n = 2 (S310). Further, the flow data generation unit 108 sets j = 1 (S312).

Next, the flow data generation unit 108 adds information to the DFG flow data indicating that processing proceeds from the i-th subprogram to the j-th migration destination subprogram (S314). Here, as shown in FIG. 14, the flow data generation unit 108 is connected from the first subprogram func01 to the first migration destination subprogram func02.

Subsequently, the flow data generation unit 108 determines whether or not n is greater than 1 (S316). Since n = 2 here (Y in S316), the flow data generator 108 adds information indicating the migration condition to the DFG flow data (S318). Referring to FIG. 13, since the transition to func02 occurs when _SEQ_ = 1, the flow data generation unit 108 adds "_SEQ_ = 1" as a transition condition from func01 to func02.

The flow data generation unit 108 determines whether j is equal to n (S320). Here, since the flow data generation unit 108 has j = 1 and n = 2 (N in S320), 1 is added to j (S322) to set j = 2.

Returning to S314, the flow data generation unit 108 executes a connection for indicating that the processing proceeds from the first subprogram func01 to the second migration destination subprogram func03 in the same manner as described above. The flow data generation unit 108 adds information _SEQ_ = 0 indicating the transition condition. The flow data generation unit 108 determines whether j is equal to n (S320). Since the flow data generation unit 108 has j = 2 and n = 2 (Y in S320), it determines whether i is equal to m (S324). At this time, since the flow data generation unit 108 has i = 1 and m = 4, 1 is added to (N) i of S324 (S326) to set i = 2.

Returning to S308 and referring to the flow program in FIG. 13, the second subprogram func02 migrates only to the subprogram func03. The total number of subprograms to be migrated from func02 is one (S310), and the flow data generation unit 108 sets n = 1. Further, the flow data generation unit 108 sets j = 1 (S312). Then, the flow data generation unit 108 is connected from func02 to func03 (S314).

The flow data generation unit 108 determines whether n is greater than 1 (S316). Here, the flow data generation unit 108 has n = 1 (N in S316), and it is not necessary to add information indicating the transition condition. The flow data generation unit 108 determines whether j is equal to n (S320). At this time, since the flow data generation unit 108 has j = 1 and n = 1 (Y in S320), it subsequently determines whether or not i is equal to m (S324). Since the flow data generation unit 108 has i = 2 and m = 4 (N in S324), 1 is added to i (S326) to set i = 3.

Returning to S308, the third subprogram func03 is also connected from func03 to func04. Then, the flow data generation unit 108 adds 1 to i to set i = 4. For the fourth subprogram func04, referring to the flow program in FIG. 13, the subprogram executed after the fourth subprogram func04 is func04 or &lt;end of processing&gt;.

Therefore, the total number of subprograms to be migrated from func04 is two, and n = 2 (S310). When the flow data generation unit 108 adds the connection and transition conditions, the DFG flow data shown in FIG. 14 is finally generated. Then, since i becomes equal to m (Y in S324), all the processing of the flow data generation unit 108 is completed.

The DFG flow data in FIG. 14 is a conceptual diagram, and in reality, DFG flow data in which the information in FIG. 14 is converted into numerical data is generated. The control data generation unit 54 generates control data used for selecting setting data in the sequencer device 20 based on the DFG flow data of FIG. The control data is supplied to and stored in the sequencer device 20.

In the embodiment, the process of extracting the program between the two sequence processing specified programs as a subprogram has been described, but the compile unit 50 supports even if the sequence processing specified program further includes the sequence processing specification. it can.

For example, when there is a sequence processing specified for statement in the sequence processing specified for statement, the sequence processing unit 102 generates a program with the sequence specification as shown in FIG. Then, the division unit 104 treats the three programs &lt;A&gt;, &lt;B&gt;, and &lt;C&gt; as a program for which sequence processing is specified, and divides the program. FIG. 16 shows a plurality of subprograms generated by the division unit. FIG. 17 shows the DFG flow data generated by the flow data generation unit 108.

Further, when the DFG generation unit 106 generates a DFG from a subprogram so as to be suitable for the circuit configuration of the reconfigurable circuit 12, it is also possible to generate a plurality of DFGs from one subprogram. For example, the DFG generation unit 106 may generate a plurality of DFGs from the subprogram shown in FIG. 16 for one subprogram as shown in FIG.

Even in this case, the relationship between the flows of funcA, funcB, and funcC is the same as that shown in FIG. At this time, the "funcA" part in FIG. 17 is replaced with three DFGs belonging to funcA arranged in the order of execution. The same applies to funcB and funcC. Therefore, in such a case, the flow data generation unit 108 can deal with this by adding the replacement process after generating the DFG flow data for funcA, funcB, and funcC.

Assuming that the execution order of DFG belonging to funcA is DFGA-1, DFGA-2, and DFGA-3, and that funcB and funcC are also the same, the DFG flow data is as shown in FIG. Execution of DFG in funcA, funcB, and funcC is determined regardless of _SEQ_, and when a branch occurs between func, the next func is determined according to _SEQ_.

In this embodiment, the program analysis unit 100 expands func1 in FIG. 5 into func0 and makes it into one function as shown in FIG. If func0 and func1 are DFG processed independently, "x + = 1;" and "_SEQ_ = * y&gt; 0;" will be subprogrammed separately, so if it is a single subprogram like func01 Instead, the number of subprograms will increase.

If the number of subprograms increases, the DFG that is finally generated increases, which may lead to a decrease in processing performance and an increase in the circuit scale. Therefore, in order to reduce the number of divisions as much as possible and reduce the number of subprograms, the program analysis unit 100 executes a process of combining a plurality of functions into one function.

The present invention has been described above based on examples. Examples are examples, and it will be understood by those skilled in the art that various modifications are possible for each of these components and combinations of each processing process, and that such modifications are also within the scope of the present invention.

FIG. 20 shows an example of the source program. In this source program, comments such as "/ * _ SEQ_ * /" are added to the C description. This comment is inserted by the programmer as a sequence processing specification comment for specifying the sequence processing when the program is created.

In C language, the character string enclosed by two slashes "/ ... /" is treated as a comment, and a normal compiler ignores the command part at compile time. In this modification, the sequence processing unit 102 determines whether or not there is a comment part that is not described as the intended arithmetic processing, and if a sequence processing specified comment is added, the comment part is sequenced. Recognize as processing designation.

This allows the user to freely specify the sequence processing. Also, by specifying the sequence processing as a comment, the operation in the C description is not affected.

FIG. 21 shows an example of a program with a sequence designation. When a function has a sequence processing specification described by a programmer as in "func1 / * _ SEQ _ * / ();" in FIG. 20, the division unit 104 recognizes the function part as a sequence processing specification and makes a comment. The range defined by the part is extracted as a subprogram.

When one function is called in multiple places, in the past, all DFGs are expanded and the same operation content is created in multiple places, but by specifying sequence processing for the function, only one DFG of the function is created. , Since the DFG will be called multiple times, the number of DFGs finally generated can be reduced.

When sequence processing is specified for a function, it is necessary to pass the argument data of func1 because the argument value (variable) is different each time the function DFG is called. Here, the upper two lines and the lower one line of "func1 / * _ SEQ_ * / ();" of the program with sequence designation shown in FIG. 21 correspond to it. If the data to be passed is an array, pass the address of the array, and if it is a variable, pass the variable (numerical value). The additional processing of this data transfer operation instruction may be executed in S110 of FIG.

FIG. 22 is a flowchart showing another example of the operation of the sequence processing unit 102. First, the sequence processing unit 102 sets m as the number of lines in the program (S400). Specifically, the sequence processing unit 102 refers to the program shown in FIG. 23, and sets m = 14 because the total number of lines in the program is 14. Then, the sequence processing unit 102 sets i = 1 (S402).

Subsequently, the sequence processing unit 102 analyzes the i-th line of the program (S404). The sequence processing unit 102 determines whether or not the program i-th line has a specific description content (S406). Further, the sequence processing unit 102 proceeds to the processing of S408 when this determination is YES, and proceeds to the processing of S420 when this determination is NO.

This specific description content indicates a condition for migrating an arithmetic process to one of a plurality of other arithmetic processes when one arithmetic process is branched into a plurality of other arithmetic processes (a description content indicating a condition for transferring the arithmetic process to one of the other plurality of arithmetic processes. Here, a branch statement such as an if statement), a description content indicating a condition for repeatedly executing the same arithmetic processing multiple times (here, a loop statement such as a for statement), and the like are included.

In S406, the description content of the first line of the program is "int i;", which is not a specific description content (branch statement or loop statement), so the sequence processing unit 102 moves to the processing of S420. The sequence processing unit 102 determines whether or not i is equal to m (S420). Here, since i = 1 and m = 14 (N in S420), the sequence processing unit 102 adds 1 to i (S422) to set i = 2.

Returning to the processing of S404 above, the sequence processing unit 102 determines that the description content is not a specific description content (branch statement or loop statement) because the description content of the second line of the program is "x + = 1;". (N of S406). The sequence processing unit 102 adds 1 to i to set i = 3 (S420).

Returning to the processing of S404 above, the sequence processing unit 102 analyzes the description content because the description content of the third line of the program is "if (* y&gt; 0) {" (branch statement) indicating a specific description content. Is executed, and the range of sequence processing and the selection of branching conditions are executed (S408). In this case, the range of sequence processing is "if () {...}", "else {...}", and the branch condition is "y&gt; 0".

This sequence processing is a preprocessing for dividing the program, and is executed when the performance such as the circuit scale and the processing speed of the reconfigurable circuit 12 is improved by dividing the program.

Subsequently, the sequence processing unit 102 creates a DFG corresponding to the subprogram in a specific description content (S410). Here, the sequence processing unit 102 creates DFG1 corresponding to "x = x &gt;&gt; 2;", "y- = 3;", and "* z + = 4" in the specific description content if statement (Fig. 24). See DFG1 shown in. In addition, the sequence processing unit 102 creates a DFG2 corresponding to "x = 5;" in a specific description content else statement (see DFG2 shown in FIG. 24).

The sequence processing unit 102 determines whether or not to execute the sequence processing according to the number of execution steps of the reconfigurable circuit 12 corresponding to the created DFG1 (or DFG2). In the present embodiment, the execution step is a process executed for each stage shown in FIG. However, the execution step may be a process executed every two or more steps.

In the present embodiment, in the sequence processing unit 102, the number of execution steps (stages shown in FIG. 2) of the reconfigurable circuit 12 corresponding to the created DFG1 (or DFG2) exceeds the first reference number (here, 3). If so, the sequence processing is executed, and if the number of execution steps of the reconfigurable circuit 12 corresponding to the created DFG1 (or DFG2) does not exceed the first reference number, the sequence processing is not executed.

For example, in DFG1 shown in FIG. 24, the operation corresponding to x = x &gt;&gt; 2; corresponds to ALU11 in the first stage of the reconfigurable circuit 12. In DFG1, the operation corresponding to "y- = 3;" corresponds to ALU12 in the first stage of the reconfigurable circuit 12. Furthermore, in DFG1, the operation corresponding to "* z + = 4" corresponds to ALU13 in the first stage of the reconfigurable circuit 12.

Therefore, the DFG1 corresponds to each ALU in the first stage of the reconfigurable circuit 12, and corresponds to only one execution step (one-stage processing). In addition, DFG2 also supports only one execution step as described above. Therefore, the sequence processing unit 102 performs sequence processing because the number of execution steps of the reconfigurable circuit 12 corresponding to each of the created DFG1 or DFG2 is 1, and does not exceed the first reference number (3 in this case). Is determined not to be executed.

Subsequently, the sequence processing unit 102 determines whether or not i is equal to m (S420). Here, since the sequence processing unit 102 has i = 3 and m = 14 (N in S420), 1 is added to i (S422) to set i = 4. The description content on the 4th line of the program is "x = x &gt;&gt; 2;", which is not a specific description content (N in S406), so 1 is added to i to make i = 5 (S422). After that, the flow is executed in the same way.

Returning to the processing of S404 above, the sequence processing unit 102 is "for (i = 0; i &lt;100; i ++) {" in which the description content of the 12th line of the program indicates a specific description content in i = 12 (S406). Y). The sequence processing unit 102 executes parsing of the program and selects the range of sequence processing and branching conditions (S408). In this case, the range of sequence processing is "for () {...}" and the branching condition is "i &lt;100".

Subsequently, the sequence processing unit 102 creates a DFG3 corresponding to the description content included in the for statement (see S410, DFG3 shown in FIG. 25). In DFG3, iterative processing is executed 100 times.

In addition, the calculation in the first processing of DFG3 corresponds to ALU11 in the first stage of the reconfigurable circuit 12, and the calculation in the second processing corresponds to ALU21 in the second stage of the reconfigurable circuit 12. To do.

Therefore, since 100 times of iterative processing of DFG3 is sequentially executed in each stage of the reconfigurable circuit 12, the number of stages (including the stage used repeatedly) of the reconfigurable circuit 12 corresponding to DFG3 is 100. The number of execution steps is 100. Therefore, the sequence processing unit 102 determines that the sequence processing is executed because the number of execution steps of the reconfigurable circuit 12 corresponding to the created DFG3 is 100, which exceeds the second reference number (10 in this case). (Y of S414).

Next, the sequence processing unit 102 adds a determination operation instruction for determining a branch condition to the program (S416). Since the branch condition is i &lt;100, as shown in FIG. 26, the sequence processing unit 102 adds the determination operation instruction _SEQ_ = i &lt;100; to the end of the for statement. Also, add "i = 0;" for initializing i before the for statement.

Then, the sequence processing unit 102 describes the for statement as "do {...} while (_SEQ_);" in order to indicate that it is a part that executes the sequence processing (S418). "Do {...} while (_SEQ_);" is a "sequence processing specification" indicating that it is a part for executing sequence processing.

Subsequently, the sequence processing unit 102 determines whether or not i is equal to m (S420). Since the sequence processing unit 102 has i = 12 and m = 14 (N in S420), 1 is added to i (S422) to set i = 13. The sequence processing unit 102 executes the flow in the same manner thereafter, determines that i = m when i = 14 (Y in S420), and ends the sequence processing in the sequence processing unit 102.

By the above sequence processing, the program with the sequence designation shown in FIG. 26 is generated. The division unit 104 divides the program into subprograms based on the sequence processing designation.

FIG. 26 shows a program in which a determination operation instruction is added to the for statement of the program shown in FIG. 23. In this example, "_SEQ_ = i &lt;100;" is a determination operation instruction, and "do {...} while (_SEQ_);" is a sequence processing specification. Similar to the process shown in FIG. 9 described above, the division unit 104 refers to the sequence process specification do {...} while (_SEQ_); shown in FIG. 26, and the subprogram to which the sequence process specification is not added is added. It is divided into (func01) and other subprograms (func02) (see Fig. 27).

After that, the DFG generation unit 106 generates a DFG corresponding to the subprogram (func01) and a DFG corresponding to the subprogram (func02) (see FIG. 28). The setting data generation unit 51 generates setting data to be supplied to the reconfigurable circuit 12 based on the generated DFG. Further, the flow data generation unit 108 generates DFG flow data based on the program with the sequence designation shown in FIG. 29 and the subprogram shown in FIG. 27 in the same manner as the process shown in FIG. 12 described above (see FIG. 30). .. Since the detailed processing in the setting data generation unit 51 and the flow data generation unit 108 is as described above, it is omitted here.

In FIGS. 22 to 30 above, a DFG corresponding to a specific description content (branch statement or loop statement) is generated, and a plurality of programs are programmed according to the number of execution steps of the reconfigurable circuit 12 corresponding to the DFG. It is divided into subprograms.

Therefore, the processing in FIGS. 22 to 30 can prevent the number of DFGs from being increased more than necessary as compared with the processing in FIGS. 7 to 14, and the amount of storage of the setting data corresponding to the DFG is small. Furthermore, the circuit scale can be reduced.

Further, since the processes in FIGS. 22 to 30 do not increase the number of DFGs more than necessary, the processes in the reconfigurable circuit 12 can be efficiently executed. Therefore, the processing in FIGS. 22 to 30 does not cause unnecessary processing to be executed in the reconfigurable circuit 12, so that power consumption can be suppressed to a low level.

The examples disclosed this time should be considered to be exemplary in all respects and not restrictive. The scope of the present invention is shown by the scope of claims rather than the above description, and it is intended to include all modifications within the meaning and scope equivalent to the scope of claims.

<figref num="1">It is a block diagram of the processing apparatus which concerns on Example.</figref><figref num="2">It is a figure which shows an example of the structure of the reconfigurable circuit.</figref><figref num="3">It is a figure which shows the structure of a compilation part.</figref><figref num="4">It is a flowchart of the DFG processing method in this Example.</figref><figref num="5">It is a figure which shows an example of a source program.</figref><figref num="6">It is a figure which shows the form which expanded the function and put together in one program.</figref><figref num="7">It is a flowchart which shows the operation of a sequence processing part.</figref><figref num="8">It is a figure which shows the program which added the judgment operation instruction before the if statement of the program shown in FIG.</figref><figref num="9">It is a flowchart which shows the operation of the division part.</figref><figref num="10">It is a figure which shows the plurality of subprograms finally generated by dividing the program shown in FIG.</figref><figref num="11">It is a figure which shows the DFG generated by the DFG generation part.</figref><figref num="12">It is a flowchart which shows the operation of the flow data generation part.</figref><figref num="13">It is a figure which shows the program for flow.</figref><figref num="14">It is a figure which shows the DFG flow data.</figref><figref num="15">It is a figure which shows the program with a sequence designation.</figref><figref num="16">It is a figure which shows a plurality of subprograms generated by a division part.</figref><figref num="17">This is the DFG flow data generated by the flow data generator.</figref><figref num="18">It is a figure which shows a plurality of DFGs generated for one subprogram.</figref><figref num="19">It is a figure which shows the DFG flow data.</figref><figref num="20">It is a figure which shows an example of a source program.</figref><figref num="21">It is a figure which shows the example of the program with a sequence designation.</figref><figref num="22">It is a flowchart which shows the operation of a sequence processing part.</figref><figref num="23">It is a figure which shows an example of a source program.</figref><figref num="24">It is a figure which shows the DFG corresponding to a subprogram.</figref><figref num="25">It is a figure which shows the DFG corresponding to a subprogram.</figref><figref num="26">It is a figure which shows the program to which the determination operation instruction is added.</figref><figref num="27">It is a figure which shows a plurality of divided subprograms.</figref><figref num="28">It is a figure which shows the DFG generated by the DFG generation part.</figref><figref num="29">It is a figure which shows the program for flow.</figref><figref num="30">It is a figure which shows the DFG flow data.</figref>

Code description

10 ... processing device, 12 ... reconfigurable circuit, 14 ... setting data holding unit, 20 ... sequencer device, 26 ... integrated circuit device, 30 ... output data holding unit, 32 ... Path section, 40 ... Storage section, 50 ... Compile section, 51 ... Setting data generation section, 54 ... Control data generation section, 100 ... Program analysis section, 102 ... Sequence processing unit, 104 ... division unit, 106 ... DFG generation unit, 108 ... flow data generation unit.