JPH0451328A - Composite type instruction scheduling processing system - Google Patents

Abstract

PURPOSE:To generate an optimal composite type instruction train whose execution time is short as a whole by determining the priority of an operation, based on an analyzed data dependent relation, and generating a composite type instruction arranging each operation in the composite type instruction in accordance with its priority. CONSTITUTION:In the case the dependent relation of definition/reference of data is present on each operation, a data dependence analysis processing part 12 analyzes it and generates a data dependent graph 15. By referring to this data dependent graph 15, which station must be executed first is known, and by considering an instruction originatable time, the inversion of the definition/ reference relation is prevented, and also, by considering an instruction finishable time, the finish time of the whole can be quickened. A composite type instruction generation processing part 14 arranges each operation in a composite type instruction, while deciding whether the combination of operations is correct or not, base on the result of a priority determination processing part 13.

Description

[Detailed Description of the Invention] [Summary] The present invention relates to a compound instruction scheduling processing method that has good execution performance and determines the combination and arrangement position of operations in compound instructions in which multiple operations are stored in an instruction that is a unit of simultaneous transmission. The purpose is to enable efficient creation of complex type instructions.

A data dependency analysis processing unit that analyzes data dependencies for linearly arranged operations, a priority determination processing unit that determines the priority of operations based on the analyzed data dependency, and the determined priority. Accordingly, the present invention is configured to include a composite type instruction creation processing unit that arranges each operation into a composite type instruction.

[Industrial application field]

The present invention relates to a complex instruction scheduling processing method that determines the combination and location of operations in a complex instruction in which a plurality of operations are stored in an instruction that is a unit of simultaneous transmission.

[Conventional technology]

FIG. 10 shows an example of a complex type instruction which does not provide a detailed explanation of the present invention.

2. Description of the Related Art Computers have been proposed that are equipped with a plurality of arithmetic units and that simultaneously issue compound instructions that are a combination of several instructions and execute them in parallel, thereby increasing the speed of instruction execution. FIG. 10 is an example of the compound type instruction,
Three instructions each having a length of 32 bits can be stored in a composite type instruction having a length of 96 pins. below,
Each instruction stored in a compound instruction is called an "operation."

Execution performance will vary depending on how this operation is arranged in the sequence of complex instructions, but until now, no efficient method has been established for instruction scheduling processing for arranging operations. Ta.

[Problem to be solved by the invention]

When scheduling instructions for a complex instruction architecture, the following points need to be considered.

(1) Each operation has a different execution time. That is, the number of machine clocks required for execution is different.

(2) There are restrictions on the combination of operations and where the operations are placed in a complex instruction.

Taking these points into consideration, it is desirable to create complex instructions that can be executed in the shortest possible time, and to realize desired processing with as few complex instructions as possible.

An object of the present invention is to solve the above-mentioned problems and to make it possible to efficiently create complex instructions with good execution performance.

[Failure to solve the problem]

FIG. 1 is a diagram explaining the principle of the present invention.

In FIG. 1, 10 is a data processing device equipped with a CPU, memory, etc., 11 is an operation sequence storage unit that stores the sequence of individual operations, 12 is a data dependency analysis processing unit that creates a data dependency graph, and 13 is a data 14 is a priority determination processing unit that analyzes the dependency graph and rearranges the graph according to the priority; 14 is a composite instruction creation processing unit that determines the placement position of operations and creates composite instructions; 15 is data handled in each operation. definition/
A data dependency graph showing reference relationships, and 16 represent a composite type instruction storage section that stores the created composite type instructions.

The operation sequence storage unit 11 stores a linear sequence of operations consisting of a sequence of instructions corresponding to an assembler language output by, for example, an existing compiler.

The present invention stores ffl in this operation string storage unit 11.
This technology provides a technique for creating an optimal sequence of complex instructions from a sequence of operations.

The data dependency analysis processing unit 12 processes each operation 11.
+2. . . , the data dependence relationships between them, that is, the definition/reference relationships, are analyzed and a data dependence graph 15 is created.

The priority determination processing unit 13 determines the priority of the operation based on the data dependency graph 15 based on several criteria such as the time when the command can be completed and the time when the command can be issued.
Operations in the data dependency graph 15 are rearranged.

Composite instruction creation processing section 14, priority order determination processing section 13
Each operation is arranged in a composite type instruction according to the priority order of operations determined by the composite type instruction storage unit 16.
Store in.

[Effect]

Operation 12 refers to the data defined by operation i1, operation i5 refers to the data defined by operations i3 and i4, etc. There is a data definition/reference dependency between each operation. If there is a relationship, the data dependency analysis processing unit 12 analyzes this and creates a data dependency graph 15 as shown in FIG. Note that the data dependency graph 15 is realized by control tables indicating each operation and pointers between these control tables.

By referring to this data dependency graph 15, it can be determined which operation should be executed first. Furthermore, by considering the executable time for each operation, it is possible to determine a criterion for execution in the shortest time.

In particular, by considering the command issuing time as this criterion, it is possible to prevent the definition/reference relationship from being reversed. By considering the possible instruction completion time, the overall completion time can be shortened.

The composite instruction creation processing unit 14 is a priority order determination processing unit 13
Based on the results, we are determining whether or not the combination of operations is correct.

Each operation is placed in a compound type instruction.

In the example shown in FIG. 1, the first compound instruction r1 includes operations il, i3. i4 is placed and operation 12゜i5. i7 is placed, and a compound type instruction is created like this.

〔Example〕

FIG. 2 is an example of a compound instruction computer that executes compound instructions created according to the present invention, FIG. 3 is an application example of the present invention, and FIG. 4 is an example of a sequence of operations for explaining the present invention in detail. , FIG. 5 is an example of a data dependency graph according to an embodiment of the present invention, FIG. 6 is a data structure of a node in a data dependency graph used in an embodiment of the present invention, and FIG. 7 is a dictionary used in an embodiment of the present invention. FIG. 8 shows an example of priority criteria according to an embodiment of the present invention, and FIG. 9 shows a processing flow of an embodiment of the present invention.

The present invention is to create a sequence of compound instructions to be executed by, for example, a compound instruction computer 20 shown in FIG. This compound instruction computer 20 has two integer operation units) 22.
23, a floating point addition unit 24, and a floating point multiplication unit I/25.

Each of these arithmetic units can operate in parallel.

A complex type instruction is fetched from main memory (not shown),
They are sequentially set in the composite instruction register 21. In this example, a maximum of three operations can be included in one compound type instruction.

3 operations are issued simultaneously to the corresponding integer arithmetic unit 1-22.23. Floating point addition unit 24
．． It is designed to operate a floating point multiplication unit I□25.

Since each unit can only perform one operation, the operations that can be combined in a compound instruction are as follows. here.

I: Integer type operations (I, ○ include D/5TORB types) F: Floating point type operations B: Branch type operations.

■　B → 1 piece and I → 2 pieces.

■ B → 1 piece, I-) 1 piece, and F-+1 piece.

■　B → 1 piece and F → 2 pieces.

■　■→2 pieces and F→1 piece.

■　■→1 piece and F→2 pieces.

FIG. 3 shows an example of the configuration of a compiler 3° that outputs complex instructions to be executed by one or more complex instruction computers 2˚.

The processing phases (a) to (f) in the compiler 30 are as follows.

It is similar to a conventional normal compiler. That is, the following processing is performed.

(a) Input a source program and perform syntax analysis.

(b) Perform semantic analysis based on the syntactic analysis results.

(C) Perform data allocation.

(d) Perform optimization such as changing processing logic and data types.

(C) Allocate registers.

(f) Generate code at the assembler language level.

The present invention relates to the following processing phases:
Instruction scheduling is performed by regarding the output of the code generation phase (f) as a sequence of operations listed in the order of execution. As a result, a compound type instruction is created.

Hereinafter, two aspects of the present invention will be described in detail according to specific examples.

For example, suppose that a compound instruction to be executed by the compound computer 20 shown in FIG. 2 is created from the sequence of operations (1) to (2) as shown in FIG.

The operations shown in FIG. 4 each have the following functions.

Note that fprl to fpr5 indicate floating point registers, and S b(i), a(i), etc. indicate variables.

(1) flood x, r1 Load the value of floating point variable χ into register r1.

(2) fstore rl, x Stores the floating point value in register r1 into one variable X.

(3) fmult rl,, r2. r3 Multiply the floating point number in register r1 and register r2, and store the result in register r3.

(4) fadd rl, r2. r3 register r1
and the floating point number in register r2, and store the result in register r3.

In the instruction scheduling according to the present invention, a sequence of operations as shown in FIG. 4 is input.

Perform the following processing.

(i) Creating a data dependence graph Each input operation is set as a node, and from there it is chained to nodes that define the operands of that operation and nodes whose execution order cannot be changed (the instruction cannot be executed by overtaking that instruction). and a reverse chain.

FIG. 5 is an example of a data dependency graph created from the sequence of operations shown in FIG. The arrow shown in FIG. 5 is a definition chain, and the inverse of this arrow is a reference chain. For example, the operation ■ refers to fprL fpr2, and the operations that define fprl, fpr2 are ■ and ■, so a definition chain from ■ to ■ and ■ is created.

Information on this node is managed by a data structure as shown in FIG. 6, for example. Here, each element has the following contents.

Instruction sequence: Refers to input operations.

Node number Number of operations in two-person order.

Definition Chain: Chain to the operations that this operation utilizes (i.e.

executed before this operation Operations that must be performed (linkage to tion).

Reference Chain - Chain to operations that are using the result of this operation.

FINISll: Standard value for sorting nodes.

DISPATCII: Second reference value for sorting nodes.

To define/reference operands, register the operands that appear in each operating engine in a "dictionary" with a data structure as shown in Figure 7, and refer to, update, and register this dictionary each time an operand appears. You can find out by going.

In the tree embodiment, in order to speed up the search, this dictionary is managed in a binary tree structure, in which the operands are arranged in alphabetical order, with the front one being the left child and the rear one being the right child. Manage with pointers. If there are no child operands, the elements of DICTIONARY are empty pointers.

The type of operand indicates the type of floating point register number, general purpose register number 5, variable name or constant name.

(11) Analysis of data dependence graph Once the data dependence graph is completed, based on the graph, a priority order criterion for selecting instructions is calculated.

As mentioned above, the data dependency graph can be said to show the definition/reference relationship of each node (peration).

There is a v-u relationship between the two nodes u and v (the definition chain of node V points to node U), which means that the execution of ■ must wait until the execution of U is completed. It means that. This means that if the execution of U takes tτ (τ is machine cycles), then the execution of V will be executed after τ even after the start of U.

In this way, between the nodes connected by the definition chain,
There is a "right of priority." The schedule must take this priority into account. Also, when there are several executable operations, it is better to give priority to operations that take a long time to complete.
You can schedule efficiently. Therefore, the following two criteria are used: FINISII, which indicates the time when the command can be completed, and DISFATCll, which indicates the time when the command can be issued.

■ FINISII FI 11 I S without indicating the time when the instruction can be completed
It's called I+.

Calculate using the following formula. The larger the FINISII value, the
We need to send it out quickly.

(vlv->ul→: definition chain where EX[EC(x) is the number of machine cycles required to execute the operation of one node X.

(2) DISPATCll DISPATCII (V) indicates the shortest machine cycle time during which operation V is sent to its arithmetic unit l-.

If the arithmetic unit on which each operation is executed is in a normal state with no cache misses or TLB hit misses, the execution time of the operation is determined by the hardware.

Therefore, DISF'ATCII(v) can be calculated and is calculated by the following formula. DISFATCll
The smaller the value, the sooner it must be transmitted.

(vlv->ul→: Definition chain Figure 8 (a) shows the FIN r S of each node calculated using one or more formulas for the data dependence graph shown in Figure 5.
The H value (FT) is shown in Figure 8 (b) and c.

It shows the DISFATCll value (DI). Note that in this example, the execution time of the operation is assumed as follows.

Load/fstore execution time → 1τfmult
Execution time of →4τ Execution time of fadd →3τ (■) FINISII and DISPA obtained by analysis of node rearrangement graph
The two nodes are rearranged based on TCll. The criteria for sorting in this embodiment is as follows, starting from the highest priority.

■ Early order of FINIS II ■ If FINIS II+ are equal, DIS
In descending order of FATCll values ■ If FINISII and DISI'ATCI+ are equal.

Input order (iv) In the order of the nodes rearranged according to the creation priority of the compound type instruction, the following (a
) to (C) to create a composite type instruction.

(a) First, search for a complex type instruction in which operation V should be stored. What is your starting point when searching?

■ Base point for complex type instructions.

■ The position of the instruction where the node U that defines V is stored.

■It uses the same calculation unit as V.

(2) The instruction furthest from the base point of the compound type instruction among the instructions in which the operation U issued before is stored.

In other words, it is the command that is sent out the latest.

(b) Follow the compound type instruction (2) from the starting point and check whether one node V can be stored in combination in the instruction I. If it can be stored, incorporate ■ into the complex type instruction I. If it cannot be stored, do the same for the next instruction after the compound type instruction ii) The condition is that the combination of the three operations is allowed by the hardware. Condition ii) can be easily changed by creating a table for combinations of operations.

(C) During process (b), when instruction I is filled with three operations, a new compound type instruction is created and ■ is incorporated into it.

When the above processes (a) to (C) are completed, the sequence of complex instructions traced sequentially from the base point becomes the desired complex instruction sequence.

FIG. 9 shows an overview of the processing according to the above-described embodiments of the present invention in the form of a processing flow, and is as follows.

(i) Create a data dependency graph with each operation as a node.

(11) Analyze the data dependence graph and calculate the FINISII value and DISPATCH value for each node, which are used as priority standards.

(iii) Rearrange the 9 nodes based on the FINISII value and the old 5PATCII value.

(iv) According to the rearranged order of the nodes, search for a compound type instruction in which each operation should be stored, change the storage conditions, and then incorporate it into the compound type instruction.

In the above processes, (i) to (iii) are processes that take into account shortening the instruction execution time as much as possible, and (iv) is a process that takes into consideration shortening the length of one instruction.

As an example, instruction scheduling for creating a compound type instruction to be executed on a compound computer 20 as shown in FIG. be. Further, the number of simultaneous transmissions does not necessarily have to be three, and the same implementation can be performed even if the number of simultaneous transmissions is different.

〔Effect of the invention〕

As explained above, according to the present invention, it is possible to create an optimal complex instruction sequence with a short overall execution time. By efficiently packing operations into compound instructions, it is possible to reduce the number of compound instructions.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram of the principle of the present invention. FIG. 2 is an example of a compound instruction computer that executes compound instructions created according to the present invention. FIG. 3 is an example of application of the present invention. FIG. 4 is an example of a sequence of operations for explaining the present invention in detail. FIG. 5 is an example of a data dependency graph according to an embodiment of the present invention. FIG. 6 is a node of a data dependency graph used in an embodiment of the present invention. data structure. FIG. 7 shows a data structure of a dictionary used in an embodiment of the present invention. FIG. 8 shows an example of priority criteria according to an embodiment of the present invention. FIG. 9 shows a processing flow of an embodiment of the present invention. FIG. 10 shows an example of a complex type instruction for explaining the present invention in detail. In the figure, 10 represents a data processing device, 11 represents an operation sequence storage unit, 12 represents a data dependency analysis processing unit 13 represents a priority order determination processing unit, 14 represents a composite type instruction creation processing unit, and 15 represents a data dependency graph.

Claims (1)

[Claims] 1. In a complex instruction scheduling processing method that determines the combination and arrangement position of operations in a complex instruction in which a plurality of operations are stored in an instruction that is a unit of simultaneous transmission, a data dependency analysis processing unit (12) that analyzes data dependencies for the determined operations; a priority determination processing unit (13) that determines the priorities of operations based on the analyzed data dependencies; and the determined priorities. A compound instruction scheduling processing method, comprising: a compound instruction creation processing unit (14) that arranges each operation into a compound instruction according to the order. 2. The composite instruction scheduling processing method according to claim 1, wherein the priority of the operations is evaluated based on the time at which execution can be completed for each operation and the time at which each operation can be transmitted earliest. .