JPH0195331A - System for processing pipe line - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] (Summary) The present invention relates to a pipeline processing system having a high-speed branch mechanism, and aims to speed up pipeline processing by reducing empty cycles due to successful branch instructions. An associative memory circuit that registers the address of a branch instruction and compares the address of the branch instruction with the address of the currently executed instruction, and registers the branch destination instruction of the branch instruction when the branch instruction is successful, and registers the address of the currently executed instruction. An instruction storage circuit that sends out the branch destination instruction of a branch instruction when the address of the branch instruction is hit, and when the branch instruction is successful, the branch destination address of the branch instruction + the number of bytes of the branch destination instruction registered in the instruction storage circuit. The address of the currently executed instruction has the address of the branch instruction, and when the address of the currently executed instruction hits the address of the registered branch instruction, the instruction storage circuit stores the instruction for pipeline processing. The queue stage is configured such that an address storage circuit is connected to a briefetch counter for pipeline processing.

[Industrial application field]

The present invention relates to a pipeline processing system having a fast branching mechanism.

[Conventional technology]

As we pursue high speed in microprocessors,
Pipeline processing, which is used in large computers, is required. Pipeline processing is processing in which one instruction is divided into multiple processing units so that the instructions appear to be executed in parallel. FIG. 13 shows an example of a three-stage pipeline. That is, in FIG. 13, the -instruction is divided into processing units of instruction fetch IF, instruction decode ID, and execution EX, and three instructions are apparently executed in parallel.

[Problem that the invention seeks to solve]

However, in the pipeline processing described above, a problem occurs when executing a branch instruction (loop instruction). If the program forms a loop, for example: X0RA (sets A to zero) LD B, lO (counter initialization) LD
11.1 (Initial setting of pointer) LOOPI
AOD A, II (A←A+H) INCH(A
←H+ 1) DJNZ LOOPI (B"8 1), DINZ LOOPI is a branch instruction, ADD
A.

H is the branch destination instruction. That is, Fig. 14A, Fig. 14
As shown in Figure B, the branch instruction execution cycle (EX)
Sometimes it enters into decoding (ID) of the instruction at the next address of a branch instruction that has already been fetched. At this time, when branching fails (when loop control is not performed), normal pipeline processing is performed as shown in FIG. 12A.
When the branch is successful (when loop control is performed), the 12th
As shown in Figure B, the branch destination instruction fetch (IF
), a pipeline processing upper cycle occurs. In this way, since it is necessary to fetch the branch destination instruction a number of times equal to the number of loops minus 1, (number of loops minus 1) empty cycles occur in the pipeline process, resulting in a delay in execution time. There was a problem with the size.

Therefore, an object of the present invention is to speed up pipeline processing by reducing empty cycles due to successful branch instructions.

[Means for solving problems]

A means for solving the above problems is shown in FIG. 1A. That is, an associative memory circuit 1, an instruction memory circuit 2, and an address memory circuit 3 are provided, and when the branch instruction is successful, that is, when the branch instruction is executed (WR="l"), the address of the branch instruction is stored in the associative memory. In the circuit 1, the branch destination instruction is registered in the instruction storage circuit 2, and the address of the branch destination address+the number of bytes of the instruction stored in the instruction storage circuit 2 is registered in the address storage circuit 3. Further, the associative memory circuit l compares the address of the registered branch instruction and the address of the currently executed instruction, and as a result, when the address of the currently executed instruction hits (-matches) the address of the registered branch instruction, A hit signal is generated. As a result, the instruction storage circuit 2 sends the branch destination instruction of the branch instruction to the instruction queue stage 4 for pipeline processing, and the address storage circuit 3 stores the branch destination address of the branch instruction + instruction storage circuit 2. The address of the number of bytes of the instruction is sent to the brief fetch stage 5 for pipeline processing. In other words, the briftetch stage 5 normally outputs an instruction corresponding to the briftetch address, and outputs the instruction of the address stored in the corresponding WAY only when the associative memory circuit 1 is hit. In addition, LRυ (Least Recently
Used) is a management system that retrieves the newest one at the time of last use, and is a WAY generation circuit that indicates the oldest one that has not been used recently among several AYs. .

The operation of FIG. 1A when a valid bit is added to the associative memory circuit 2 in FIG. 1A is shown in FIG. 1B.

[For production]

The operation will be explained with reference to FIGS. 2A, 2B, 3A, and 3B.

Figures 2A and 2B show the case of a mishit, that is,
A case is shown in which a branch instruction is not registered in the associative memory circuit 1 and the branch instruction has been decoded. In this case, when a branch instruction is decoded (ID), an instruction is fetched (ID) equal to the address of the branch instruction + the number of bytes of the instruction stored in the instruction storage circuit 2, and when the branch instruction is executed (EX) The address of the branch instruction+the number of bytes of the instruction stored in the instruction storage circuit 2 is decoded (ID). At this time, if the branch instruction is successful due to execution (EX) of the branch instruction (loop control is performed), the branch destination instruction will be executed, but in this case, as shown in Figure 2A, , the execution of the instructions corresponding to 7 addresses of the branch instructions + the number of bytes of the instructions stored in the instruction storage circuit 2 is stopped, and it is necessary to fetch and decode the branch destination instruction again. Therefore, an empty cycle occurs as shown in FIG. 2A. In the present invention, at the time of such a miss hint and when a branch instruction is successful, the address of the branch instruction, the branch destination instruction, the branch destination address + the number of bytes of the instruction stored in the instruction storage circuit 2 are respectively It is stored (registered) in the instruction storage circuit 2 and address storage circuit 3. On the other hand, if the branch instruction fails due to execution (EX) of the branch instruction (when loop control is not performed), the execution of the instruction (EX) equal to the address of the branch instruction + the number of bytes of the instruction stored in the instruction storage circuit 2 X) is performed, and therefore, in this case, normal pipeline processing is performed as in the case of FIG.

3A and 3B show a hit case, that is, a case where a branch instruction is registered in the associative memory circuit 1 and the branch instruction is decoded. In this case, a hit signal is generated when the branch instruction is decoded (TD), and as a result, when the branch instruction is executed (EX), the branch destination instruction sent from the instruction storage circuit 2 is decoded (I
At the same time as step D) is performed, an instruction fetch (IF) of the branch destination address sent from the address storage circuit 3 + the number of bytes of the instruction stored in the instruction storage circuit 2 is performed. At this time, if the branch instruction is successful due to the execution of the branch instruction (EX), as shown in FIG. 3A, the branch destination instruction is executed (EX) and the branch destination address + instruction storage circuit is Decoding (ID) of instructions of the number of bytes of instructions stored in 2 is performed. On the other hand, execution of a branch instruction (EX)
If the branch instruction fails, the execution of the branch destination instruction is stopped, and it is necessary to fetch and decode the address of the branch/branch instruction + the number of bytes of the instruction stored in the instruction storage circuit 2 again. . Therefore, an empty cycle occurs as shown in FIG. 3B.

The present invention focuses on the fact that if a branch instruction succeeds once, there is a high probability that the next branch instruction will branch in the same direction.

In other words, before entering the branch instruction loop, pipeline processing is performed in the state shown in Figure 2B, and if the first branch instruction is successful, pipeline processing is performed in the state shown in Figure 2A. Then, pipeline processing is performed in the state shown in Figure 3A, and when exiting the branch instruction loop (i.e.,
When a branch of a branch instruction fails), pipeline processing is performed in the state shown in FIG. 3B6.Therefore, the number of times an empty cycle occurs is two.

〔Example〕

The details of FIG. 1A will be explained below.

FIG. 4 is a detailed circuit diagram of the associative memory circuit 1 shown in FIG. 1A. In FIG. 4, write buffer WB4. WBi,
1. WB+*z, ``'' is a branch instruction (7) 7)' and 7.WDi.

WD, , WD, and 2. ..., and the synchronous circuits CSz, C3+, +, C3t,z,
. . . is the address of the currently executed instruction from the program counter (PC, not shown) PC4, Pct-+, PCB+
It latches z,..., and the associative memory element CA
M,, CAM, ya,,CAMi. 2. . . . is the write buffer B,, WB Ying, 1. Output D ++ D i : D i + l + D ++ I; D
i+l Di*2+ "' and synchronous circuit C3H, C54,
+, C54-z.

...'s output C8, i r Ci+1+τi, 1;
With C4+2+. It is used to compare with 1...
When all bits match, a hint signal HIT is generated.

The write operation in FIG. 4 will be explained with reference to the timing diagram in FIG. 5. In the write buffer WB, To
Therefore, φ1=″0″, so transistor ′dister′r+,
'rz is turned on, so D,,D.

are both at a high level. That is, D,,D, are precharged. If the branch instruction is successful at the time of a miss hint, a control circuit (not shown) outputs signals -R, W at T1.
AY is set to "1", therefore, transistors Ts and T
O, Ts, and Tb are turned on, and as a result, the write data WD+ (1 bit of the branch instruction address) is transferred to the content addressable memory element CAM! latched to.

Next, the hint determination operation shown in FIG. 4 will be explained with reference to FIG. 6. First, in the synchronous circuit CSi, T1
At , φO=“θ”, transistors T□ and T1□ are turned on, and therefore C,,C.

becomes low level (equivalent to precharge). Next, To
When φO becomes “l”, the transistors T, , T, 6
is turned on, and therefore, depending on the address bit PC of the program counter PC, the transistor T+ff+T1 is turned on.
4 is turned on and the other is turned off, and as a result, i,
C4 has a level corresponding to address bit PC8. That is, logically, =PCt.

Cmu=pci.

In addition, in the associative memory element CAM, φ0 at TI
= ``O'', so the transistor T1. is turned on and the hit signal line 1 (IT is precharged, and at TO,
where i and ci are transistors T* and T+. is supplied to For example, PC4(=C!)="1".

If WD = “1”, transistor T? , T
+o is turned on, and transistors TI and TI are turned off, so that the hit signal line HIT is not discharged and remains at a high level. Also, PC five (=
If C5) = “0” and WD = “l”, the transistor T? , TI is turned on, and therefore the hit signal line old T
is discharged and becomes low level. In other words, W
Di, WDi, I+S'lDi+t,... and PC4,
Pct++.

Only when all of pc, .

7 is a detailed circuit diagram of the instruction storage circuit 2 shown in FIG.
The figure is a detailed circuit diagram of the address storage circuit 3 shown in FIG. That is, the instruction storage circuit 2 and the address storage circuit 3
has a similar configuration, and write buffers JJBJ, +
, WBj4g, ... (pull, pull,...

WB,...) and launch circuit RAMj, RA
Mj++.

RAMj, z, ... (RAMt,, R static i + * +,
RAMk+z,...).

Also, the write buffer WB, (WBt,) has the same configuration as the write buffer WB in FIG. 4. The input section of the latch circuit RAJ (RAMb) also has the same configuration as the input section of the content addressable memory element CAM in FIG. Therefore, the write operation of instruction memory circuit 2 and address memory circuit 3 is the same as the write operation of content addressable memory circuit 1.

The read operation of the circuit shown in FIG. 7 will be explained using the timing diagram shown in FIG. 9. That is, if the hint signal T, which performs the read operation based on the hit signal HIT which is the output of the content addressable memory circuit 1, is at a high level, the transistor TUB
is turned on, and if the latch data is at a high level, the transistor T is also turned on, and therefore, A is discharged and becomes a low level. Conversely, if the latch data is at a low level, the transistor T27 is turned off, so that A is not discharged and remains at a high level. In other words, when the hit signal T is at high level,
The latched branch destination instruction is output. Also in FIG. 8, when the hit signal T is at a high level, the address equal to the branch destination address+the number of bytes of the instruction stored in the instruction storage circuit 2 is output.

FIG. 11 is a detailed circuit diagram of the WR signal generating circuit (LRU), which includes a NOR circuit 1101, a latch circuit 1102, and an AND circuit 1103. Since the number of hit signals is equal to the number of WAYs, by taking the NOR logic of all the hint signals, it can be determined that all -AYs were miss-hits. However, the human signal is T
Since the signal is output only between OB and 11, a launch circuit 1102 is required to hold the signal for one cycle period.

As shown in FIG. 12, the operation of FIG. 11 is such that the high-node signal is asserted only at Tl when the branch instruction is successful and misses.

Note that various changes can be made to the number of ways, word length, timing, etc. in the content addressable memory circuit 1, instruction memory circuit 2, and address memory circuit 3 described above. For example, FIG. 10 shows an example in which the associative memory circuit 1 is configured with 4 WAYs and 32 bit words. For example, PCO~
When all 32 CAM values of PC□ and -AYI match, the hit signal HIT1 becomes high level, but if even one difference occurs, the hit signal old T1 becomes low level. That is, comparison is performed in word units (32 bits).

〔Effect of the invention〕

As explained above, according to the present invention, the number of empty cycles associated with a successful branch can be reduced, and especially when the number of loops in a program is large, the number of empty cycles can be significantly reduced.
Therefore, the speed of pipeline processing can be increased.

[Brief explanation of the drawing]

FIG. 1A is a diagram showing the principle configuration of the present invention, and FIG. 1B is a diagram showing the basic configuration of the present invention.
Flowcharts showing the operations in Figures 2A, 2B,
3A and 3B are timing diagrams explaining the present invention in detail, FIG. 4 is a detailed circuit diagram of the associative memory circuit of FIG. 1A, and FIGS. 5 and 6 illustrate the circuit operation of FIG. 4. 7 is a detailed circuit diagram of the instruction storage circuit shown in FIG. 1A, FIG. 8 is a detailed circuit diagram of the address storage circuit shown in FIG. 1A, and FIG. 9 is a detailed circuit diagram of the instruction storage circuit shown in FIG. 1A. 10 is a circuit diagram showing a modification of FIG. 4, FIG. 11 is a detailed circuit diagram of the WR signal generation circuit in FIG. 1, and FIG. 12 is the circuit in FIG. 11. 13 is a timing diagram showing normal pipeline processing, and FIGS. 14A and 14B are timing diagrams showing conventional pipeline processing. 1...Associative memory circuit, 2...Instruction memory circuit, 3
...Address storage circuit, 4.Briefetch stage, 5.Instruction queue stage. Operation in Figure 1A (Miss) in Figure 18, branch success (Figure 2A) miss, branch failure in Figure 28 (Hit), branch instruction successful in Figure 3A (Hit), branch instruction failure in Figure 38 (write operation in Figure 4) Figure 4 Hit determination operation Figure 6 Branch destination instruction Details of instruction storage circuit Figure 7 Branch destination address +1 Details of address storage circuit Figure 8 Read operation of Figure 7 (Figure 8) Figure 9 Figure 11 Figure 12. Normal pipeline operation Figure 13. Branch instruction ←IF I [and - once branch instruction fails Figure 144 Branch instruction succeeds Figure 148

Claims (1)

[Claims] 1. Registering the address of the branch instruction when the branch instruction is successful;
an associative memory circuit (1) that compares the address of the branch instruction with the address of the currently executed instruction; registers the branch destination instruction of the branch instruction when the branch instruction is successful; and stores the address of the currently executed instruction in the registered branch; An instruction storage circuit (which sends out the branch destination instruction of the branch instruction when the address of the instruction is hit)
2) When a branch instruction is successful, the address of the branch destination address of the branch instruction + the number of bytes of the branch instruction registered in the instruction storage circuit is registered, and the address of the currently executed instruction hits the address of the branch instruction. an address storage circuit (3) that sends an address equal to the branch destination address of the branch instruction + the number of bytes of the branch destination instruction registered in the instruction storage circuit, when the address of the currently executed instruction is the registered address. The pipeline processing system is configured to connect the instruction storage circuit to an instruction queue stage for pipeline processing and connect the address storage circuit to a prefetch stage for pipeline processing when the address of a branch instruction that has been issued is hit.