JPH0238965B2 - - Google Patents

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to an instruction prefetch control method in a pipelined computer, and in particular to an efficient method for reflecting instructions to a prefetched instruction sequence when executing a store instruction. Concerning control methods.

[Conventional technology]

In general, high-speed computers perform instruction prefetch control to substantially reduce execution delays caused by memory access during instruction fetching. When performing prefetching of instructions, it is essential to guarantee the temporal ordering of each instruction. If there is a pre-changed instruction in the command sequence, execution of that prefetched instruction must be prohibited.

Computers are equipped with several functions to guarantee such ordering, one of which is a function called STIS (Store in the Instruction Stream).

The STIS function detects when the currently executed instruction is a store to the storage area of an instruction sequence that has already been prefetched. ,
The instruction sequence prefetched by the instruction buffer is temporarily discarded, and subsequent instructions are prefetched again after the store is completed. In other words, re-instruction prefetching (Re-instruction prefetch)
ifetch).

FIG. 2 shows a specific example of such a store, where 21 is a part of the instruction storage area of the memory. Currently, instructions from addresses 0 to 8 have been prefetched by the instruction buffer, and the store instruction "ST6 address" at address 0 has been executed. Therefore, as the contents of address 6 have been updated,
The contents of address 6, which is prefetched by the instruction buffer, are invalid.

FIG. 3 shows the configuration of an example of a conventional method for realizing the above-mentioned STIS function, in which 22 is an execution address generation circuit EAG, 23 is an LBS that functions as an instruction buffer, 24 is an STIS detection circuit, and WAR
is the working address of the store instruction currently being executed, that is, the first store address, and IAR is the first address of the instruction prefetch area.

To explain briefly, the execution address generation circuit
EAG22 performs address modification calculation of the instruction to be prefetched, and calculates the start address IAR of the instruction prefetch area.
occurs. IAR is instruction buffer LBS23
and is supplied to the STIS detection circuit 24.

The STIS detection circuit 24 uses the store address WAR
is compared with the start address IAR of the instruction prefetch area to check whether the WAR will fit into the instruction prefetch area starting with IMR.
A STIS detection signal is output to invalidate the prefetch instruction sequence in that area.

At this time, since it is difficult to accurately calculate the address of the currently executing instruction, the STIS detection range is defined as an interval with a certain width equal to the depth of the instruction buffer.

Figure 4 shows the pipeline control timing of store instructions in the conventional configuration shown in Figure 3, where D, A, T, B, E, and W on the horizontal axis are below the pipeline, respectively. represents the control stage shown.

D: Decode (instruction decode) A: Address (effective address generation) T: Translation (address translation) B: Buffer (buffer search) E: Execution (operation) W: Write (write to register) As shown, T STIS detection is performed at the stage, and the re-preemption flag (Re-
ifetch flag) is set to ON. The execution of Re-ifetch is started after the W stage, that is, after the store instruction is completed.

[Problem that the invention seeks to solve]

In the case of the conventional method explained in FIGS. 3 and 4, as in the example shown in FIG. 5, there is a program A and a program B that is branched from program A.
If there is a work area immediately after the branch instruction BRANCH in program A, if the program is executed from the top of the diagram (lower address) to the bottom, the contents of the work area will be prefetched into the instruction buffer along with the instructions. Something happens. As a result, when the store instruction ST is executed in the program, STIS detection is performed on the store in the work area shown by the arrow in the figure, and the subsequent instructions of the store instruction ST that have been prefetched are invalidated, and the re-preemption (Re- ifetch) is required.

However, in reality, the work area is never executed as an instruction, so the above-mentioned re-preemption is wasteful and causes performance degradation.

Particularly in large computers, the instruction buffer tends to become deeper, so it is expected that the STIS detection range will gradually become wider in the future using conventional methods.
In this situation, if store instructions are executed continuously in a program, performance will drop significantly due to re-ifetching each time. . In addition,
An example in which there is a work area after the branch instruction BRANCH, as in the example shown in FIG. 5, is often seen in actual programs.

[Means for solving problems]

The present invention compares the start address of the instruction currently being executed and the operand address of the store instruction, that is, the store start address of the store instruction, and calculates the difference. By not performing STIGS detection unless the range exceeds 1, the STIS detection range can be limited to a practical range.

The configuration of the present invention is to use the store start address (TOAR) of the previously executed store instruction and the start address (TIAR) of the currently executed instruction in a computer that executes and controls instructions using a pipeline system and prefetches instructions. ) and the difference (TOAR−
It is equipped with an adder that calculates the output (TOAR-TIAR) of the adder and a counter that holds the output (TOAR-TIAR) of the adder. The first case where TIAR) is negative and its absolute value is smaller than the length of the store operand of the above store instruction, and the first case where the output (TOAR−TIAR) of the above adder is positive and its value is the buffer storing the prefetched instruction. In the second case where the instruction length is subtracted from the contents of the above counter for each instruction when it is smaller than the value related to the depth (STIK), and the value of the subtraction result becomes negative, the current prefetch is performed. The feature is that the instruction sequence is invalidated and re-preemption is performed.

〔Example〕

The details of the present invention will be explained below with reference to Examples.

FIG. 1 is a configuration diagram of a pipeline that is an embodiment of the present invention. In the figure, 1, 2, 3 are registers IAR-0, IAR-1, which store the start address of the instruction prefetch area instruction buffer, respectively.
Indicates IAR-2, 4 is an NSI counter that counts in half-word units the number of half words from the start address IAR of the currently executing instruction, 5 is the value of this NSI counter added to IAR, NSI adders 6 and 7 generate instruction execution addresses, and registers AIAR and 7 hold the instruction execution address of the addition result of NSI adder 5 in the A stage and T stage.
It is TIAR. 8 is a displacement register DR, 9 is a base register BR, 10 is an index register Operand address registers TOAR, OEAR
It is. 14 is an STIS adder that takes the difference between the contents of TIAR7 and TOAR12, and 15 is an STIS detection circuit. In addition, D, A, T, B, E, W at the top of the figure
shows the correspondence with the control stage of the pipeline explained in FIG. The operation when executing a store instruction will be described below.

At the D stage, registers IAR-0 to
The start address of the instruction prefetch area (instruction buffer) held in a specified one of IAR-2,
The offset amount from the start address of the instruction prefetch area to the address of the currently executing instruction, which is the contents of the counter NSIC, is added by the NSI adder, and the resulting execution instruction address (start address) is stored in AIAR. be done.

For example, if the instruction prefetch area is 8 bytes long, the start address held in IAR is 1040,
If the value of the counter NSIC is 4 (bytes), the instruction execution address is 1040+4=1044, and this value is stored in AIAR.

The execution instruction address of AIAR is transferred to TIAR in the next A stage. On the other hand, the operand execution address generation circuit OEAG generates the operand execution address (first address) based on the contents of DR, BR, and XR specified by the store instruction in RX format.
In other words, store addresses are generated and stored in TOAR and OEAR, respectively.

In the next T stage, the STIS adder 14
The STIS detection circuit 15 calculates the difference between the instruction execution address of TIAR and the operand execution address of TOAR, and compares the difference with the TST length (length to store) or STIK (a constant that is a guideline for the depth of the instruction buffer). However, if STIS detection is performed, the re-preemption flag is set. There are two types of STIS detection:

Type: TIAR-TOAR<TST length Type: TOAR-TIAR<STIK As shown in Figure 6a, the instruction execution address (TIAR) is larger (farther) than the operand execution address (TOAR), but This is a case where the length of the operand (TST length) stored starting from the operand execution address (TOAR) extends beyond the instruction execution address (TIAR), and the instruction currently being executed or its successor is prefetched. Because the instructions have changed,
As STIS state, re-ifetch is performed immediately after the store instruction ends.

The type is one in which the operand execution address (TOAR) is larger (farther) than the instruction execution address (TIAR), but the difference is determined in relation to the depth of the instruction buffer, as shown in Figure 6b. If the range is smaller than STIK, and the instruction being executed or the subsequent instruction that has been prefetched may have been changed, the end of the instruction is changed to the operand execution address (store address) each time the instruction is executed. Check whether it takes or not.
Only when this happens is the STIS status established.

FIG. 7 shows the embodiment shown in FIG.
FIG. 3 is a detailed configuration diagram of the STIS detection circuit. In the figure,
14 is an STIS adder that calculates the difference between the operand execution address and the instruction execution address (TOAR - TIAR);
15 is an STIS detection circuit, 25 is an adder for type detection, 26 is an adder for type detection, 27 is a positive detector, 28 is an OR circuit, 29 is a (TOAR-
Counter STIC for sequentially subtracting the length of the executed instruction TILC from TIAR), 30 is a latch STIC VALID, 31 that displays the validity/invalidity of STIC.
is an instruction length TILC adder of the TILC subtracter, 32 is a selector, 33 is a comparator, and 34 is a negative detector.

First, when executing a store instruction, the STIS adder 14
Add TOAR+(-TIAR). here
If TOAR−TIAR<0, adder 25
When TST-(TIAR-TOAR) is calculated and the positive detector 27 detects TST length-(TIAR-TOAR)>0, the above-mentioned type of condition is satisfied, so STIS is detected via the OR circuit 28. Output a signal.

On the other hand, if TOAR−TIAR>0, adder 2
In step 6, calculate (TOAR−TIAR)−STIK. If the above-mentioned type of condition (TOAR-TIAR)-STIK<0 is satisfied, the STIS condition is further checked using the counter STIC, ILC adder, negative detector, etc. That is, each time an instruction is executed, its length
Subtract TILC from (TOAR−TIAR),
When the value becomes negative, that is, the end of the instruction being executed overlaps with the part after TOAR of the store address, and the instruction being executed or the instruction being executed and the subsequent instruction are It determines that it has been rewritten and outputs a STIS detection signal.
This condition, for example, defines the length of a store instruction and each subsequent instruction executed as TILC ₀ , TILC ₁ ,...
TILC _r , and assuming that the subsequent instruction is not a store instruction, STIS is detected for the first time at the r-th instruction such that (TOAR - TIAR) - (TILC ₀ + TILC ₁ + ... + TILC _r ) < 0, and r
- Since STIS detection is not performed until the first instruction, re-preemption can be avoided.

Therefore, TOAR−TIAR is set in the counter STIC when a store instruction is executed, and every time a subsequent instruction is executed thereafter, the instruction length TILC is subtracted from the contents of the counter STIC by the ILC adder, and the subtraction result is returned to the counter STIC. A cyclic subtraction operation is performed to store the . The selector 32 is used to switch between setting (TOAR-TIAR) to the counter STIC described above and subtracting the execution instruction length thereafter. The comparator 33 compares the (TOAR−TIAR) value and the counter when a store instruction appears for the second time or later.
Compare with the current value of STIC, (TOAR−TIAR)<
If it is STIC, the selector 32 is controlled to set the (TOAR-TIAR) value of this new store instruction to STIC. This is type STIS
STIS when there are two or more store instructions detected.
This is because detection needs to be performed for the store address where STIS occurs earliest. The negative detector 34 outputs a STIS detection signal from the OR circuit 28 when the subtraction result from the ILC adder 31 becomes negative.

FIG. 8 shows the control flow when a type store instruction is detected. In addition, (TOAR−
TIAR)=A.

When STIC VALID = 0 when executing a store instruction, it is the first time it has become a type, so
STIC←A, STIC VALID← to find A of the current instruction
Set to 1.

On the other hand, when STIC VALID = 1, valid data has already been set in STIC by the preceding store instruction, so check whether STIC or A of the current instruction is smaller, and if STIC - TILC < A
Perform subtraction of STIC←(STIC−TILC), and STIC
-If it is TILCA, update STIC with this A.
That is, always adopt a smaller STIS detection range.

FIG. 9 shows a control flow when executing another normal instruction (non-store instruction) following the store instruction of the type detected in FIG.

First, if STIC VALID = 1, subtract the length of the currently executed instruction TILC from STIC and use the result value as
Assign to STIC. If this value is less than "0", the store address of the store instruction that last set TOAR-TIAR in STIC will be included in the currently executing instruction, so instruction execution will be stopped. , pre-fetch the instruction that was being executed again and re-execute the instruction. On the other hand, STIC VALID=
If 0, STIS detection by type is not performed.

Also, for instructions that change the address of the instruction being executed due to BRANCH, LPSW, and interrupts,
Reset STIC VALID to “0”. As a result, wasteful STIS detection and preemption as described in the example of FIG. 5 are suppressed.

FIG. 10 is a program example for explaining the effectiveness of the circuit according to the embodiment of the present invention shown in FIG. 7, and FIG. 11 shows the pipeline during execution.
This shows STIS detection operation. Elements 14, 29, 30, and 31 in FIG.
STIS adder, counter STIC, latch in figure
Represents STIC VALID, ILC adder. The numbers in FIGS. 10 and 11 also show the correspondence between sequential instructions in the program and pipeline operations. For simplicity, the instruction length is
All TILCs are 2 bytes.

The store instruction ST18 is the first store instruction, and the STIS adder 14 has TOAR−TIAR=18−0
Calculate =18. This will detect the type and set STIC VALID to ON as well as
Set “18” to STIC29.

In the store instruction ST22, the output of the STIS adder is TOAR−TIAR=22−2=20, and STIC=
18 is smaller, so the output STIC of IC adder 31
Substitute -TILC=18-2=16 into STIS29.

In normal (non-store) instruction A, the addition result of ILC adder 31 STIC-TILC=16-2=14 is
Assign to STIC29.

In the store instruction ST16, the STIS adder 14
Outputs TOAR−TIAR=16−6=10, which is
Since STIC is smaller than 14, select this value "10" and substitute it into STIS29.

In the normal instructions B and C of and, respectively,
The ILC adder subtracts the instruction length by 2 from STIC,
STIC=6.

In the instruction BRANCH, STC VALID is reset to "0" and the type-based STIS detection operation is temporarily terminated.

〔Effect of the invention〕

As described above, according to the present invention, re-prefetching is started after checking whether the execution instruction actually applies to the store address, which eliminates wasted control operations and significantly reduces computer processing costs compared to conventional methods. Performance can be improved.

[Brief explanation of drawings]

FIG. 1 is a block diagram of one embodiment of the present invention, FIG. 2 is an explanatory diagram of a store instruction that requires re-prefetching, FIG. 3 is a block diagram showing an example of a circuit that implements the conventional STIS function, and FIG. Figure 4 is a pipeline control timing diagram showing the operation of the conventional example circuit shown in Figure 3, Figure 5 is an explanatory diagram of a program that causes unnecessary re-preemption due to STIS detection, and Figure 6 is the same as shown in Figure 1. FIG. 7 is an explanatory diagram of types and types of STIS detection in the embodiment shown in FIG.
Detailed configuration diagram of STIS detection circuit, Figures 8 and 9
The figures are a control flow diagram showing the operation of the STIS detection circuit shown in Fig. 7, Fig. 10 is an explanatory diagram of a program example for explaining the operation of the embodiment, and Fig. 11 is a control flow diagram showing the operation of the STIS detection circuit shown in Fig. 7.
The figure shows the execution of the program shown in Figure 10.
FIG. 3 is an explanatory diagram showing STIS detection operation. In the figure, 5 is an NSI adder that generates an instruction execution address, 7 is a register TIAR, 11 is an operand execution address generation circuit OEAG, and 12 is a register
TOAR, 14 is an STIS adder, 15 is an STIS detection circuit, TILC is the length of an execution instruction, and TST length is the length of an operand to be stored.

Claims (1)

[Claims] 1. In a computer that executes and controls instructions using a pipeline system and also prefetches instructions, the store start address (TOAR) of the previously executed store instruction and the start address (TOAR) of the currently executed instruction TIAR) and an adder that calculates the difference (TOAR−TIAR) and the output of the adder (TOAR−TIAR).
When a series of instructions in a program are sequentially executed, the output of the adder (TOAR - TIAR) is negative and its absolute value is the length of the store operand of the store instruction. In the first case, when the output of the adder (TOAR−TIAR) is positive and its value is smaller than the value (STIK) related to the depth of the buffer storing the prefetched instruction, the An instruction characterized by subtracting the instruction length from the contents of the counter, and in a second case where the value of the subtraction result becomes negative, invalidating the currently prefetched instruction sequence and causing the prefetch to be performed again. Preemptive control method.