JPS6295636A - Pre-fetch control processor - Google Patents

Abstract

PURPOSE:To decrease the quantity of information transferred between a main storage part and a processor by providing a storing part for the pre-fetch information on the destination branched by a branch instruction at each stage of a pre-fetching process in order to reproduce the branch instruction executed previously at a high speed and also performing the transfer of data between a storing part serving as an internal memory part and a register. CONSTITUTION:A storing part which stores the information on the branch processing is provided together with an associative memory part 19 which registers a storage for branch processing information with the address of a registered branch instruction used as a key ann then delivers it when the registered branch instruction is delivered, and an executing part 13 which judges a registered or non-registered branch instruction and controls it. If the branch instruction is registered in the first branch processing mode, it is transferred to the storing part from a temporary storing part. Then the branch instruction is transferred to the temporary storing part from the storing part thereafter by the output information on the part 19.

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial Field of Application] The present invention relates to a preemption control processing device that can efficiently perform prefetching when branch processing is performed in a computer that can perform prefetching processing.

[Prior art and its problems]

A prefetch type computer is one in which other instructions or data required during processing of an instruction are fetched from a storage device into a processing device in advance of the operation, thereby making it possible to improve processing efficiency. The prefetch procedure can generally be divided into a plurality of stages along the lapse of time until instruction execution, such as an instruction string buffering stage, an instruction decoding stage, and the like. In such prefetch processing, it is important to be able to predict the instruction or data to be executed in order to improve efficiency. Examples of prior art related to prefetch processing include C and V.

“Pipeline Architecture” by Ramamoorthy
CM Computing Surveys Volume 9-1,
March 1977 (C, V, Ramamoorthy”
Pipel+ne Architecture A
CM Computing surveys, Vol.
9, No. 1, March 1977)
It is described on pages 1 to 102.

However, for branch processing that includes an unconditional branch or a conditional branch, it is not possible to perform prefetch processing while anticipating sequential prefetching in the order of addresses. This is because prefetching cannot be performed unless the branch destination is known.

As a result, after the branch destination is determined, the instructions at the branch destination are prefetched sequentially from the first stage of prefetching, and as a result, the performance of branch processing is equivalent to or lower than when no prefetching is performed. I had a problem with that.

Here, the problem of prefetching that occurs between prefetching and a branch instruction will be explained with reference to FIG. 2(a). In FIG. 2(a), the horizontal axis represents time, and shows a state in which processing progresses sequentially toward the right. In FIG. 2(a), instruction processing is divided into a first stage in which an instruction sequence is stored in an instruction buffer, a second stage in which an instruction is decoded, and a third stage in which an instruction is executed. Explain the process of preemption. First, the first instruction (I1) is read into the instruction buffer. Next, the instruction (11) is decoded (Dl) and the second instruction (I2) is read into the instruction buffer. Then, at the same time as the instruction (I1) is executed (El), the instruction (I1) is executed (El).
I2) decoding (D2), third branch instruction (Ia
) is read to the instruction buffer. Branch instruction (I8)
becomes a read target, the next instruction will not be read at the time of decoding (D,) of the branch instruction (IB).

When the branch instruction (r,) is executed (EB), the next instruction to be executed (A) is determined. Therefore, after the instruction (L) is determined, reading of the instruction (I, ) to the instruction buffer and decoding (D, ) of the instruction (IX) continue. Therefore, from execution (E, ) of the branch instruction (I8) to the next branch destination instruction (I
The time T during which no execution processing is performed until the execution (EK) of K).

occurs, and there is a problem in that it is not possible to improve processing efficiency through prefetching.

[Purpose of the invention]

The purpose of the present invention is to solve the above problems,
A prefetch control processing device that can achieve high-speed prefetching even when branch processing is involved, and that can increase processing capacity by reducing the amount of information transferred between the main storage unit and the processing unit, and that can efficiently use the added storage storage unit. Our goal is to provide the following.

[Structure of the invention]

The present invention provides a computer configured to divide the process up to the execution of an instruction into a plurality of stages, provide a necessary temporary storage section for each of the plurality of stages, and perform prefetch processing. A storage storage section that is attached to each of the temporary storage sections and stores and saves the information related to the branch processing stored in the temporary storage section, etc., and the branch processing in each storage storage section is performed using at least the address of the registered branch instruction as an input key. an associative memory unit that registers the storage location of information related to processing and outputs the storage location when the registered branch instruction occurs again; and an execution unit that determines whether it is a registered branch instruction and, if it is a registered branch instruction, controls registration of the storage location in the associative storage unit and storage of information related to branch processing in each of the storage storage units; If the branch instruction is a registered branch instruction at the time of the first branch processing, information related to the necessary branch processing is transferred from each of the temporary storage units to the corresponding storage storage unit and stored, and thereafter At the time of the branch processing, information related to the branch processing is transferred from the storage storage section to the temporary storage section based on the output information of the associative storage section.

[Effect]

In the present invention, storage memory of sufficient word length to store (save) the stored contents corresponding to each of the instruction buffers and temporary storage units of registers provided in each stage for prefetching processing is provided.1. The storage storage section stores the contents of the temporary storage section of each stage in which the branch destination is prefetched when a required branch instruction is executed for the first time. At this time, the address of the branch instruction and, in the case of a conditional branch, information that can uniquely determine the branch destination, such as satisfaction or dissatisfaction of the condition, are stored (registered) in the associative memory, and
At the same time, the storage location of the prefetch information stored in each storage storage section is stored (registered). Then, when the branch instruction becomes the execution target again, information that can uniquely determine the branch destination, such as the address of the instruction, is used as a search key to search for the associative entry 1. ! The storage location of the prefetch information is outputted from the storage section, and the prefetch information related to the branch processing stored in the storage storage section is read out and stored in the corresponding temporary storage section. As a result,
The internal state of the branch destination can be realized more quickly than when reading the branch destination instruction from the main memory where the program is stored and sequentially executing each stage of the prefetch.

The above processing is not performed for all branch instructions. According to the present invention, branch instructions are divided into registered branch instructions that require the above processing and unregistered branch instructions that do not require the above processing. Some of the processes described in the program include
There are cases where the above-mentioned registration and storage are not necessary. for example,
For instructions that branch to exception processing that is executed infrequently, or instructions that branch to overflow processing of an operation, and instructions that branch in a program that is executed infrequently, there is a possibility that the branch instruction will branch again. is extremely low. In such a branch instruction, the registration in the associative memory and the storage of the prefetch information in the storage memory are unlikely to be used in the future, so there is little effect on speeding up the prefetch. A non-registration branch instruction that makes registration and storage unnecessary in such a case is provided together with a registration branch instruction that performs registration and storage. The difference between these instructions controls the registration in the associative memory unit and the storage of prefetch information in the storage memory at the time of branching.

〔Example〕

The present invention will be explained in detail below using the drawings.

FIG. 1 is a block diagram showing the configuration of a computer equipped with a preemption control processing device according to an embodiment of the present invention.

In FIG. 1, numeral 1 is a main storage section in which machine language instruction sequences and data are stored, and numeral 2 is an instruction buffer that stores machine language instructions read from the storage section 1. This instruction buffer 2 constitutes the first stage. Machine language instructions read out sequentially are stored in the instruction buffer 2, and the instruction code and operand syllable of each machine language instruction are decoded by the instruction decoder 3, and each piece of information is sent to the next prefetching stage. A buffer address disk 4 holds an address for reading out the next instruction following the machine language instruction stored in the instruction buffer 2 from the storage unit 1. This buffer address register 4 also belongs to the first stage of prefetching.

The above instruction buffer 2 and buffer address register 4
are respectively provided with an instruction buffer storage section 5 and a buffer address storage section 6. The instruction buffer storage storage unit 5 is a storage unit for storing a branch destination instruction sequence prefetched into the instruction buffer 2 under certain conditions to be described later, and is capable of holding a plurality of instruction sequences. Further, the buffer address storage storage section 6 is a storage section that stores the contents of the buffer address register 4 at the time when data of an instruction string is transferred from the instruction buffer 2 to the instruction buffer storage storage section 5, and stores a plurality of buffer address information. can be retained.

Next, the second stage of preemption will be explained. It is assumed that this data processing device has first and second operands as machine language instructions. 7 is an instruction code register that holds the instruction code information output from the instruction decoder 3; 8 is the first operand register that holds the first operand information that is output from the instruction decoder 3; 9 is the first operand register that is output from the instruction decoder 3; This is a second operand register that holds two-operand information. These registers are the second
Configure the stage. The instruction code register 7, first operand register 8, and second operand register 9 each have storage records 1. @ part 10.11.12 is attached.

Instruction code storage record 1. When a branch instruction is executed, the contents of the instruction code register 7 are transferred to the α section 10 and stored therein. The contents of the first operand register 8 are transferred to the first operand storage storage unit 11 at the same timing,
Save this.

The contents of the second operand register 9 are transferred to the second operand storage storage section 12 at the same timing and are stored therein. Each of these storage units 10, 11, and 12 can store multiple words.

13 is an execution unit that performs data manipulation, calculation, etc. specified for each instruction, and an instruction decoder 14 that decodes registered branch instructions, unregistered branch instructions, and other machine language instructions.
, a control unit 15 that controls registration and non-registration in an associative memory unit, which will be described later, based on the decoding results of the instruction decoder 14 using a microprogram. The execution unit 13 belongs to the third stage, which is the final stage of processing. The contents of the instruction code register 7, first operand register 8, and second operand register 9 are provided to the execution unit 13 and processed. 1
Reference numeral 6 indicates an execution instruction address register that holds the address of an instruction to be executed by one execution unit 13, and 17 indicates the storage storage unit 5.
, 6, 10, 11, and 12. The contents of the execution instruction address register 16 are transferred at the same timing as when data is stored in 12, and is an execution instruction address storage unit that stores the contents.

Reference numeral 18 denotes a storage address counter, which indicates the address in each storage storage section when these storage storage sections store prefetched information for each of the storage storage sections 5, 6, 10, 11, 12, and 17. , increments for each storage process,
The address value is retained for the information to be saved next. Further, the contents of the saved memory address counter 18 are also given to the associative memory section 19. The associative storage unit 19 includes storage storage units 5, 6, and 10.1 that store prefetch information when prefetching a branch destination instruction sequence when a branch instruction is executed for the first time.
1.12.17 address (memory location), and when executing the same branch instruction thereafter, the contents of the execution instruction address register 16 indicating the location of the branch instruction and the condition result in the case of a conditional branch instruction. Or condition information 20
is used as a search input key, and outputs the address of each storage storage unit that stores the prefetch information. A branch instruction address register 21 is used to hold the address of a branch instruction during execution of the branch instruction, and outputs a key value to be registered in the associative memory unit 19.

Next, an example of prefetching processing of a branch instruction in the computer having the above configuration shown in FIG. 1 will be described.

Now, set the machine language instruction string to be executed as follows.

Address Machine language instruction sequence Processing content Lo
rGo TOLn Branch to address Lh. Register branch instruction, SOB RO, R1 (RO-R1)
L to store in 1 register, ADD RO, R1 (RO+R1) to R
Lh to store in 1 register, + LOAD C, R2C de 9 to store in R2 register Ly1+2.

Note that the "rGOTOL, J instruction belongs to registered branch instructions.

The instruction currently being executed in the above instruction sequence. Suppose that it is rrGo To LhJ at the address. Therefore, at this time, the execution instruction address register 16 is filled. The address is stored, and the instruction code register 7 is rrG.
o The operation code portion of the TO'L, , J instruction is stored, and the first operand is stored in the first operand register 8. Also, instruction buffer 2 has [
rGOT○Lh" as the command following the L11 address rs
UBRO and RIJ instructions are stored, and the buffer address register 4 stores an address L22 so that the instructions following rsUBRO and RIJ can be read.

Registered branch instruction r stored in instruction code register 7
The instruction decoder 14 of the execution unit 13 analyzes rGOTo L, .J, and based on the analysis result, the control unit 15 starts controlling the registered branch instructions rrGo To L, . Address stored in the execution instruction address register 16. Associative memory unit 19 is given the address. Each storage storage unit corresponding to 5゜6, 10.11.12
．． The presence or absence of the address in 17 is checked. Assume that there is no corresponding address at this point.

In the above case, the execution unit 13 performs the following process as branch processing for the rrGOTo L, , J instructions. First, the content 3 "Lo" of the execution instruction address register 16 is stored in the branch instruction address register 21. Next, Lh is stored in the execution instruction address register 16 and the buffer address register 4 as the address of the branch destination instruction. Based on this address information, the contents of the instruction sequence sequentially read from the storage section 1 starting from the wrinkle address are stored in the instruction buffer 2. Therefore, first of all, rADD, RO, RIJ of Ln address
is stored in the instruction buffer 2. This instruction is interpreted by the instruction decoder 3, which causes the instruction code rAD
The DJ writes the first operand “R” to the instruction code register 7.
O' is stored in the first operand register 8, and the second operand 'R1' is stored in the second operand register 9. At this time, the instruction buffer 2 continues. The instruction rLOADC, R2J at address 1 is read from the storage unit 1, and the buffer address register 4 contains the address of the next instruction. . 2 is stored.

After performing the above-described processing related to instruction prefetching, the contents of the corresponding registers are stored in each of the storage units 5, 6, and 10.11.12.17. The storage address is given from the storage address counter 18 to each storage storage unit 5 , 6 , 10.11.12.17.

Assume that the address value in this case is, for example, "5". Each of the above storage storage units 5, 6, 10.11.12.17
At the same time as the storage process in , the address value "5" is set to the value of the branch instruction address register 21. is registered in the associative memory unit 19 as a key. Thereafter, the storage address counter 18 is incremented.

The above processing is executed as the processing of the branch instruction rrGo TOL, . After that, the execution unit 13 continues the addition process according to the instruction code rADDJ stored in the instruction code register 7.

FIG. 2(b) shows the process of prefetching processing according to the present invention. The above operation will be explained according to FIG. 2(b). In the above, a registered branch instruction is executed. Since reading is the first step, the reading of the branch instruction to the instruction buffer 23, the decoding of the branch instruction 24, and the execution of the branch instruction 25 are performed according to the normal prefetch processing stages, and then the branch destination instruction (I
The process then moves on to reading 26 of the process. Therefore, the non-execution time T between execution 25 and execution 27 of the branch destination instruction is the same as before.

exists. However, in this case, in this first branch process, since this branch process will be used repeatedly from now on, the contents of the instruction Lh are stored in the storage storage units 10, 11 and 12, and the contents of the instruction Lh. The content of 1 is an instruction to the instruction buffer storage unit 5, and the address of 7.2 is an instruction to the buffer address storage unit 6. The addresses of the execution command addresses are stored in the execution command address storage unit 17, with predetermined addresses being designated respectively. After that, prefetching of the branch destination continues.

After the above processing, it will be returned at an appropriate time. Address rrGo
Assume that To, L, , j instructions are to be executed. The state in this case is indicated by 28 in FIG. 2(b).

At this time, address L0 is stored in the execution instruction address register 16. The execution unit 13 processes this branch instruction.
Here is the address stored in the execution instruction address register 16. is given to the associative memory unit 19 as a key power, and the address is given.

The presence or absence of an address to each storage unit corresponding to the storage unit is checked. At this stage, it is already the address. The address "5" for each storage storage section is registered as a key.As a result,
Address as output of associative memory &1<19. has already been registered, and the address "5" is output. This address "5" causes the content specified by this address to be stored in each of the storage units 5, 6, 10, 11, 12, .
17 and stored in the corresponding instruction buffer 2 and each register 4, 7.8, 9.16. That is, according to this, "LOAD C, R2J" is stored in the instruction buffer 2, and the address L0°2 is stored in the buffer address register 4.
is stored, and the instruction code rAD is stored in the instruction code register 7.
Dj is stored and rROJ is stored in the first operand register 8.
is stored, "R1" is stored in the second operand register 9, and the address is stored in the execution instruction address register 16.
is stored. Therefore, the prefetched contents of the instruction buffer 2 and each register 4, 7, 8, 9.16 are not provided by being read from the storage section 1, but are provided directly from each corresponding storage section. Therefore, it can be stored quickly.

To explain the above-mentioned re-branch processing with reference to FIG.
) (29 in Fig. 2(b)), the next step is to preempt the branch destination instruction (IK) and decode (DK) it, and also transfer the instruction (IK+, ) to instruction buffer 2. The first stage and the second stage are set to the state at the time of reading. Therefore, as shown by the broken line 30, time can be reduced in branch processing.

Although the above processing example for a branch instruction is an example for an unconditional branch instruction, similar processing can be performed for a conditional branch instruction as well. However, in this case, the value of the execution instruction address register 16 and the condition result 20 are first used as key information for the search in the associative memory unit 19.

Further, the value of the branch instruction address register 21 and the condition result 20 are used as key information for registration in the associative memory unit 19. As a result, in the conditional branch instruction, the associative memory unit 19 uses the address and condition result of the conditional branch instruction as a key input.
When the conditional branch instruction is previously executed in the associative memory 19, if it is specified that the conditional branch instruction was Necessary prefetch information can be read out from each storage storage unit based on the storage location information and stored in the register or the like of each stage at high speed.

In the above operation example, an example of a registered branch instruction has been described. If the unregistered branch instructions [rGo To L,,J are generated as an instruction sequence instead of the registered branch instructions rrGo To L,J, then the instruction decoder 1
After analyzing this unregistered branch instruction in step 4, the processing instructed by the control unit 15 includes checking whether it is registered in the associative memory 1 and the α part 19, registering it in the associative memory unit 19, and saving each. No storage processing is performed in the storage unit.

Note that the present invention is not limited to the above embodiments, and can be modified as desired. For example, the number of stages for prefetch processing can be further increased, and in such a case, it is necessary to add a storage section to accommodate the registers of the increased stages.

〔Effect of the invention〕

As is clear from the explanation in Part 2, according to the present invention, a storage unit is provided at each stage of the prefetch process to save the prefetch information at the destination branched by the branch instruction and output it in a timely manner. When re-executing an executed branch instruction, a prefetching state at the branch destination can be quickly realized, and instead of reading from the main memory, it is possible to read from the internal memory of the processing device such as the storage memory and registers. By transferring data between them, a prefetch state can be created at the branch destination, so the amount of information transferred between the main memory and the processing device can be reduced.

Furthermore, according to the present invention, branch instructions to be executed are divided into two types. That is, one type is a branch instruction that stores information regarding prefetching in the storage storage section and associative memory section when branching, and the other type is a branch instruction that does not store information regarding prefetching in the storage storage section and associative storage section when branching. It is. By providing these two types of branch instructions, branch information regarding branch instructions that are to be repeatedly executed is stored in the storage storage section, and branch information tU regarding branch instructions that are only rarely to be executed is stored in the storage section 1. It is not stored in the α section. As a result, the preservation memory section can store information that is likely to be used in the future, and the preemption control allows efficient use of the preservation memory section and associative memory section, which have a limited number of memorizable words. A processing device can be provided.

[Brief explanation of drawings]

FIG. 1 is a block diagram of a computer equipped with a prefetch control processing device according to an embodiment of the present invention, and FIG. 2 is a diagram showing the time course of prefetch processing when a branch instruction is executed. FIG. 2(a) is a diagram showing the conventional case, and FIG. 2(b) is a diagram showing the case of the present invention.

Claims (1)

[Claims] (1) In a computer configured to perform prefetch processing by dividing the process up to the execution of an instruction into a plurality of stages, and providing the necessary temporary storage section for each of the plurality of stages, a storage storage section that is attached to each of the storage sections and stores and saves information related to the branch processing stored in the temporary storage section; and a storage storage section that stores and saves information related to the branch processing stored in the temporary storage section, and the branch processing in each storage storage section using at least the address of the registered branch instruction as an input key. an associative memory unit that registers the storage location of information related to the information and outputs the storage location when the registered branch instruction occurs again; and a content addressable memory unit that registers the storage location of information related to the registered branch instruction and outputs the storage location when the registered branch instruction occurs again; an execution unit that determines whether it is a branch instruction and, if it is a registered branch instruction, controls registration of the storage location in the associative storage unit and storage of information related to branch processing in each storage storage unit; If the branch instruction is a registered branch instruction at the time of the first branch processing, the information related to the necessary branch processing is transferred from each temporary storage section to the corresponding storage storage section and stored; A preemption control processing device characterized in that, at the time of branch processing, information related to the branch processing is transferred from the storage storage section to the temporary storage section based on output information of the associative storage section.