JP3327598B2 - Data processing method and data processing device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data processing method and a data processing apparatus for realizing a compiler used especially for embedded applications.

[0002]

2. Description of the Related Art In recent years, the use of compilers has been remarkable in embedded applications, and the development of applications using high-level languages has become active. However, since the conventional compiler was assumed to be used in a workstation or the like, it was not necessary to have any optimization method for bus access, such as being hidden by a high-speed memory or cache system.

For example, in a system in which a register length is 16 bits, a basic data bus width is 16 bits, a basic memory cycle is 1, and a pipeline has two stages of decoding (DEC) and execution (EX) + one stage of store buffer (OW). 12 is executed. Here, D0, D1, D2, D3 are CPU registers, mov # nn, @ Dn
Is an instruction to store the immediate value nn in the memory at the address indicated by the register Dn, and inc Dn is an instruction to increase the value of the register Dn by 1. The number of execution clocks of all the instructions is 1 for easy understanding. Shall be.

In a conventional system using a high-speed memory such as a workstation, the bus width is 16 bits, the number of memory waits is 0, and the memory can be accessed with one clock. Therefore, the pipeline is as shown in FIG. Thus, the number of execution clocks is T6, and the pipeline is full. However, in a system using a low-speed memory such as an embedded application, for example, a bus width of 16 bits,
In the case of 2-clock memory access, the pipeline is as shown in FIG. 14, and the OW of the third instruction and the OW of the fourth instruction interfere with each other through the bus. The number of clocks becomes T7, indicating that the pipeline is not filled.

[0005]

That is, the above-mentioned conventional data processing method and data processing apparatus have a problem that the performance of the CPU cannot be fully utilized when a low-speed memory or a narrow bus width is used. The present invention has been made in view of the above circumstances, and provides a data processing method and a data processing device that can fully utilize the performance of a CPU when a low-speed memory or a narrow bus width is used. Aim.

[0006]

According to the present invention, a bus access from the bus access parameter storage means is provided by using an instruction string storage means for storing an instruction string and a bus access parameter storage means for holding a bus access parameter. An instruction scheduling step of rearranging the instruction sequence from the instruction sequence storage means so as to reduce a penalty due to bus access based on a parameter is performed.

The present invention provides an instruction sequence storing means for storing an instruction sequence, a bus access parameter storing means for holding a bus access parameter, and the instruction sequence storage based on a bus access parameter from the bus access parameter storing means. Instruction scheduling means for rearranging the instruction sequence from the means so as to reduce a penalty due to bus access.

According to the present invention, a bus access instruction is detected from an instruction string from the instruction string storage means by using an instruction string storage means for storing an instruction string and a bus access parameter storage means for holding a bus access parameter. Calculating the number of execution clocks between bus access instructions from a bus access instruction detecting step for adding information indicating that it is a bus access instruction, and an instruction sequence processed in the bus access instruction detecting step; An inter-instruction distance calculating step of adding inter-instruction distance information to the instruction sequence;
Based on the bus access parameters from the bus access parameter storage means, an instruction that causes a penalty in bus access among the bus access instructions included in the instruction sequence processed in the inter-instruction distance calculation step is detected. A bus access interference instruction detecting step for adding information indicating that the instruction is a generated instruction; and an instruction capable of rearranging the penalty generated instruction is detected from the instruction sequence processed in the bus access interference instruction detecting step. A rearrangeable instruction detecting step for adding information indicating that the instruction is a rearrangeable instruction; and a bus which rearranges the rearrangeable instructions in the instruction sequence processed in the rearrangeable instruction detection step before and after the penalty generating instruction. Instruction sequence for scheduling to avoid access interference It is characterized by executing example and step.

According to the present invention, an instruction sequence storing means for storing an instruction sequence, a bus access parameter storing means for holding a bus access parameter, and a bus access instruction are detected from the instruction sequence from the instruction sequence storing means. A bus access instruction detecting means for adding information indicating that the instruction is a bus access instruction; and an instruction clock from the bus access instruction detecting means. The number of execution clocks between the bus access instructions is calculated. An inter-instruction distance calculating unit for adding information to the instruction sequence; and a bus access instruction included in the instruction sequence from the inter-instruction distance calculating unit, based on a bus access parameter from the bus access parameter storing unit. Bus access that detects an instruction that generates a penalty and adds information that it is a penalty-generating instruction Arbitration instruction detection means, and an instruction capable of rearranging the penalty-occurring instruction is detected from the instruction string from the bus access interference instruction detection means, and rearrangement for adding information indicating that the instruction is a rearrangeable instruction. Possible instruction detecting means, and an instruction sequence rearranging means for rearranging the rearrangeable instructions in the instruction sequence from the rearrangeable instruction detecting means before and after the penalty generating instruction and scheduling so as not to cause bus access interference, It is characterized by having.

The present invention is characterized in that the number of memory waits and the bus width are used as bus access parameters. The present invention provides, as a bus access parameter,
It is characterized in that the number of memory weights and the bus width are used.

[0011]

In the present invention, in the instruction scheduling step, the instruction sequence from the instruction sequence storage means is rearranged based on the bus access parameters from the bus access parameter storage means so as to reduce the penalty due to the bus access. In the invention according to claim 2, the instruction sequence storing means stores the instruction sequence. The bus access parameter storage means holds a bus access parameter. The instruction scheduling unit rearranges the instruction sequence from the instruction sequence storage unit based on the bus access parameter from the bus access parameter storage unit so that a penalty due to the bus access is reduced.

In the present invention, in the bus access instruction detecting step, the bus access instruction is detected from the instruction sequence from the instruction sequence storage means, information indicating that the instruction is a bus access instruction is added, and the distance between instructions is calculated. Then, the number of execution clocks between bus access instructions is calculated from the instruction sequence processed in the bus access instruction detection step, and the inter-instruction distance information as the calculation result is added to the instruction sequence. Detecting, among the bus access instructions included in the instruction sequence processed in the instruction distance calculation step, an instruction that causes a penalty in bus access based on the bus access parameter from the bus access parameter storage means, Attach information indicating that the instruction is a bus access at the reorderable instruction detection step. An instruction that can be rearranged for the penalty-occurring instruction is detected from the instruction sequence processed in the negotiation instruction detection step, information indicating that the instruction is a rearrangeable instruction is added, and the instruction In the instruction sequence processed in the replaceable instruction detection step, the rearrangeable instructions are rearranged before and after the penalty generating instruction, and scheduling is performed so that bus access interference does not occur.

[0013] In the present invention, the instruction sequence storing means stores the instruction sequence. The bus access parameter storage means holds a bus access parameter. The bus access instruction detecting means detects a bus access instruction from the instruction sequence from the instruction sequence storage means, and adds information indicating that the instruction is a bus access instruction. The inter-instruction distance calculation means calculates the number of execution clocks between bus access instructions from the instruction sequence from the bus access instruction detection means, and adds the inter-instruction distance information as the calculation result to the instruction sequence. The bus access interference instruction detecting means detects, based on the bus access parameter from the bus access parameter storing means, an instruction which causes a penalty in the bus access among the bus access instructions included in the instruction sequence from the instruction distance calculating means. , Information indicating that it is a penalty generation instruction. The reorderable instruction detecting means detects an instruction that can be rearranged with respect to the penalty generating instruction from the instruction sequence from the bus access interference instruction detecting means, and adds information indicating that the instruction is a reorderable instruction. The instruction sequence rearranging unit rearranges the rearrangeable instructions in the instruction sequence from the rearrangeable instruction detecting unit before and after the penalty generating instruction, and performs scheduling so that bus access interference does not occur.

In the present invention, the number of memory waits and the bus width are used as bus access parameters. In the present invention, the bus access parameters are the number of memory waits and the bus width.

[0015]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 is a configuration diagram of a data processing device according to an embodiment of the present invention. The data processing device includes an instruction sequence storage device 1, a bus access parameter storage device 2, and an instruction scheduling device 3, and has an instruction scheduling device. The scheduling device 3 includes a bus access instruction detecting device 4, an instruction distance calculating device 5, a bus access interference instruction detecting device 6,
And an instruction reordering device 7 and an instruction reordering device 8. The instruction sequence storage device 1 stores an instruction sequence. The bus access parameter storage device 2 stores bus access parameters. The instruction scheduling device 3 rearranges the instruction sequence from the instruction sequence storage device 1 based on the bus access parameters from the bus access parameter storage device 2 so that the penalty due to the bus access is reduced. Bus access instruction detecting device 4
Receives a command sequence from the command sequence storage device 1, detects a bus access command from the command sequence, and outputs a command sequence to which information indicating that the command is a bus access command is added. The instruction-to-instruction distance calculating device 5 calculates the number of execution clocks between bus access instructions by receiving an instruction sequence from the bus access instruction detecting device 4, and adds an instruction-to-instruction distance information which is the calculation result. Is output. The bus access interference command detecting device 6 includes a command distance calculating device 5
, A bus access parameter from the bus access parameter storage device 2 is referred to, and among the bus access commands included in the command sequence, an instruction which causes a penalty in bus access is detected. An instruction sequence to which information indicating that the instruction is a penalty generating instruction is output. The reorderable instruction detecting device 7 detects an instruction that can be rearranged with respect to the penalty generating instruction when the instruction sequence is input from the bus access interference instruction detecting device 6, and the instruction is the reorderable instruction. An instruction sequence to which information indicating the effect is added is output. The instruction rearranging device 8 rearranges the rearrangeable instructions before and after the penalty generating instruction so that the instruction sequence is input from the rearrangeable instruction detecting device 7 so as not to cause interference in bus access.
Outputs a sequence of instructions scheduled to suppress penalties.

Next, the operation of the data processing device will be described.
This will be described with reference to the flowchart of FIG. Now
The operating CPU has a register length of 16 bits, a basic data bus width of 16 bits, a basic memory cycle of 1, and a pipeline having two stages of decoding (DEC) and execution (EX) +
In a one-stage (OW) store buffer system, D0, D
1, D2, D3 are CPU registers, mov # nn, @ Dn are immediate n
The instruction for storing n in the memory at the address indicated by the register Dn, the inc Dn is an instruction for increasing the value of the register Dn by one. It is assumed that an instruction sequence as shown in FIG. 3 is stored in the column storage device 1, and a bus access parameter as shown in FIG. 4 is stored in the bus access parameter storage device 2. First, the bus access instruction detecting device 4
However, when an instruction sequence is input from the instruction sequence storage device 1, a bus access instruction is detected from the instruction sequence, and an instruction sequence as shown in FIG. 5 to which information indicating that it is a bus access instruction is added is output. (Step S1). In this example,
Bus access is performed by instructions 1, 3, and 4, which are indicated by stars. When there is no bus access instruction, an instruction sequence without information indicating that the instruction is a bus access instruction is output.

Next, the instruction distance calculating device 5 calculates the number of execution clocks between bus access instructions by inputting an instruction sequence as shown in FIG. 5 from the bus access instruction detecting device 4, and calculates the number of execution clocks between the bus access instructions. An instruction sequence as shown in FIG. 6 to which certain instruction distance information is added is output (step S2). In this example, the distance between instructions is 2 between instructions 1 to 3, and 1 between instructions 3 and 4. If there is no bus access instruction, an instruction sequence having no inter-instruction distance information is output.

Next, the bus access interference instruction detecting device 6
When a command sequence as shown in FIG. 6 is input from the command-to-instruction distance calculation device 5, a bus access parameter from the bus access parameter storage device 2 as shown in FIG.
Among the bus access instructions included in the instruction sequence, an instruction causing a penalty in the bus access is detected, and an instruction sequence as shown in FIG. 7 to which information indicating that the instruction is a penalty generating instruction is added (step S3). That is, from the bus access parameters, since the memory cycle is the number of memory waits + the basic memory cycle = 2 cycles and the bus width = the basic data bus width, it is understood that the bus cycle is completed in one memory cycle, and the distance between bus access instructions. If no more than two cycles occur, a penalty will occur in bus access, so in this example, a penalty occurs between three and four instructions, which are indicated by double circles. In addition,
If there is no instruction that causes a penalty, an instruction sequence without penalty-occurring instruction information is output.

Next, the reorderable instruction detecting device 7 detects an instruction that can be rearranged with respect to the penalty generating instruction by inputting an instruction sequence as shown in FIG. 7 from the bus access interference instruction detecting device 6. Then, an instruction sequence as shown in FIG. 8 to which information indicating that the instruction is a rearrangeable instruction is added (step S4). For example, an operation of detecting instructions that can be rearranged by checking each instruction including a mutual relationship by focusing on a register is realized by software. In the case of this example, rearrangement of six instructions is possible to alleviate the interference between three and four instructions, which is indicated by triangles. When there is no penalty generating instruction and when there is no rearrangeable instruction, an instruction sequence having no rearrangeable instruction information is output.

Next, the instruction rearranging device 8 receives the instruction sequence as shown in FIG. 8 from the rearrangeable instruction detecting device 7, so that among the rearrangeable instructions included in the instruction sequence,
Instructions that contribute to penalty mitigation are selected, instructions are rearranged, and a scheduled instruction sequence as shown in FIG. 9 in which the occurrence of penalties is suppressed is output (step S).
5). When there is no rearrangeable instruction or when there is no rearrangement target instruction that contributes to the reduction of penalty, the instruction sequence is output as it is without rearranging.

As described above, based on the instruction sequence storage device 1 for storing the instruction sequence, the bus access parameter storage device 2 for holding the bus access parameters, and the bus access parameters from the bus access parameter storage device 2,
The instruction scheduling device 3 for rearranging the instruction sequence from the instruction sequence storage device 1 so as to reduce the penalty due to the bus access is provided. Therefore, when a low-speed memory or a narrow bus width is used, the performance of the CPU is sufficiently improved. It can be used for That is, when the instruction sequence shown in FIG. 3 is directly executed, the pipeline becomes as shown in FIG. 10, whereas when the instruction sequence shown in FIG. 9 is executed, the pipeline becomes as shown in FIG. 11, and the bus penalty is reduced. It turns out that it can be avoided.

In the above embodiment, as the CPU to operate, the pipeline is composed of decode (DEC) and execution (EX).
, A register length of 16 bits, a basic data bus width of 16 bits, a basic memory cycle of 1, and an execution clock number of all instructions of 1 are used. Is not limited in this way.

In the above embodiment, the scheduling is performed only for the instruction having the OW as the effect related to the store buffer. However, the present invention is not limited to the OW, and the present invention can be used for the instruction fetch and the operand fetch. It is. Further, in the above embodiment, the assembler instruction is employed as a scheduling target, but an instruction other than the assembler such as an intermediate language may be employed.

In the above embodiment, the bus width and the number of memory waits are fixed in the entire system. However, by setting bus access parameters such as the bus width and the number of memory waits for each area, the static memory, the dynamic memory, and the like can be obtained. It can be easily extended so that access such as I / O can be optimized. Further, in the above embodiment, the bus width and the number of memory waits are used as the bus access parameters, but other parameters may be used.

[0025]

As described above, according to the present invention, the instruction sequence is rearranged according to the distance between the bus access instructions on the basis of the bus access parameters, so that a low-speed memory or a narrow bus width is used. In a system in which bus access cannot be ignored, penalties due to bus access can be reduced. Further, since bus access parameters can be specified at the time of compiling, optimal instruction scheduling can be realized for each system having various bus access parameters.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a data processing device according to an embodiment of the present invention.

FIG. 2 is a flowchart illustrating an operation of the data processing device according to one embodiment of the present invention.

FIG. 3 is an explanatory diagram of an input instruction sequence.

FIG. 4 is an explanatory diagram of a bus access parameter.

FIG. 5 is an explanatory diagram of an instruction sequence to which bus access instruction information is added.

FIG. 6 is an explanatory diagram of an instruction sequence to which inter-instruction distance information is added.

FIG. 7 is an explanatory diagram of an instruction sequence to which penalty generation instruction information is added.

FIG. 8 is an explanatory diagram of an instruction sequence to which rearrangeable instruction information is added.

FIG. 9 is an explanatory diagram of a scheduled instruction sequence.

FIG. 10 is an explanatory diagram of a pipeline when an input instruction sequence is executed.

FIG. 11 is an explanatory diagram of a pipeline when a scheduled instruction sequence is executed.

FIG. 12 is an explanatory diagram of an input instruction sequence in a conventional technique.

FIG. 13 is an explanatory diagram of a pipeline when an input instruction sequence in the related art is executed by a system using a high-speed memory and a wide bus width.

FIG. 14 is an explanatory diagram of a pipeline when an input instruction sequence in the related art is executed by a system using a low-speed memory or a narrow bus width.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Instruction string storage device 2 Bus access parameter storage device 3 Instruction scheduling device 4 Bus access instruction detection device 5 Inter-instruction distance calculation device 6 Bus access interference instruction detection device 7 Sortable instruction detection device 8 Instruction rearrangement device

Claims (6)

(57) [Claims] 1. A and the instruction sequence storage means for storing an instruction sequence, by using the bus access parameter storage means for storing the bus access parameters, detects a bus access instructions from the instruction sequence to store, from the detected bus access instruction Between bus access instructions
The number of execution clocks is calculated as inter-instruction distance information, and the bus access parameters held and the calculated instruction
Penalty for bus access based on distance information
Detecting a penalty generating instructions that raw, parallel with respect to the penalty generating instructions from the instruction sequence that contains
Reorderable instructions are detected, and the reorderable instruction
Instructions before and after the penalty occurrence instruction.
Instruction scheduling step to prevent
A data processing method for executing the data processing. 2. An instruction sequence storing means for storing an instruction sequence, and a bus access parameter for holding a bus access parameter.
Data storage means and a bus access instruction is detected from the stored instruction sequence .
The number of execution clocks is calculated as inter-instruction distance information, and the bus access parameters held and the calculated instruction
Penalty for bus access based on distance information
Detecting a penalty generating instructions that raw, parallel with respect to the penalty generating instructions from the instruction sequence that contains
Reorderable instructions are detected, and the reorderable instruction
Instructions before and after the penalty occurrence instruction.
Instruction scheduling to avoid interference
A data processing device comprising scheduling means . 3. A bus access instruction is detected from an instruction string from said instruction string storage means using an instruction string storage means for storing an instruction string and a bus access parameter storage means for holding a bus access parameter. A bus access instruction detecting step of adding information indicating that the command is a bus access instruction; and calculating the number of execution clocks between the bus access instructions from the instruction sequence processed in the bus access instruction detecting step. An inter-instruction distance calculating step of adding inter-instruction distance information to the instruction sequence; and a bus access instruction included in the instruction sequence processed in the inter-instruction distance calculating step based on the bus access parameter from the bus access parameter storage means. Of instructions that cause a penalty on bus access A bus access interference instruction detecting step of adding information indicating that the instruction is a command; and detecting an instruction that can be rearranged for the penalty generating instruction from the instruction sequence processed in the bus access interference instruction detecting step. A rearrangeable instruction detecting step of adding information indicating that the instruction is a permutable instruction; and a bus access by rearranging the rearrangeable instruction in the instruction sequence processed in the rearrangeable instruction detecting step before and after the penalty generating instruction. An instruction sequence rearranging step of performing scheduling so that interference does not occur. 4. An instruction sequence storing unit for storing an instruction sequence, a bus access parameter storing unit for storing a bus access parameter, a bus access instruction is detected from an instruction sequence from the instruction sequence storing unit, and the bus access instruction is detected. A bus access instruction detecting means for adding information indicating that the instruction is an instruction; and calculating the number of execution clocks between the bus access instructions from an instruction sequence from the bus access instruction detecting means. An inter-instruction distance calculation unit to be added to the instruction sequence; and a penalty for bus access among bus access instructions included in the instruction sequence from the inter-instruction distance calculation unit, based on a bus access parameter from the bus access parameter storage unit. A bus access interference instruction that detects the instruction that occurs and adds information that it is a penalty-occurring instruction Detecting means for detecting a sortable instruction for the penalty generating instruction from the instruction sequence from the bus access interference instruction detecting means and adding information indicating that the instruction is a sortable instruction; Detecting means; and an instruction sequence rearranging means for rearranging the re-arrangeable instructions in the instruction sequence from the re-arrangeable instruction detecting means before and after the penalty generating instruction and scheduling so as not to cause bus access interference. A data processing device, characterized in that: 5. The data processing method according to claim 1, wherein a memory weight number and a bus width are used as bus access parameters. 6. The data processing device according to claim 2, wherein a number of memory waits and a bus width are used as bus access parameters.