JP2868654B2 - Cache memory control method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an electronic computer, and more particularly to a cache memory for speeding up .
The present invention relates to a cache memory control method .

[0002]

2. Description of the Related Art In a normal cache memory, as shown in FIG. 7, when a cache miss occurs, execution is resumed after necessary data is fetched into a cache. At that time, since data in the vicinity is often required, a fixed number of plural data are usually taken at the same time. This scheme works well when the ratio of cache misses is low. This relationship is represented by the following equation. Ne = (1-Km) * Ca + Km + Cc

[0005] Incidentally, Ne is an effective memory access time and indicates the performance of a cache memory. Km is the cache memory miss rate, and this value varies depending on the size of the cache memory, the nature of the problem, and the like. Ca is the access time when the cache memory hits, and Cc is the time required to replace the cache memory. In the normal case, measuring time in clock cycles gives Ca
Is about 1, Cc is about 10, and Km is about 1% to 5%, so Ne is about 1.1 to 1.5. This value is sufficiently smaller than the value of about 2 to 3 when the normal cache memory is not used, so that there is an effect of using the cache memory. But depending on the problem,
There are cases where the cache miss rate becomes extremely high.
In such a case, the cache memory loses its effect and may be worse. Such a case is becoming more prominent because the amount of data used to solve the problem increases and the size of the cache memory cannot be so large to develop a microprocessor including the cache memory. . Even if a certain number of data is continuously refilled and the miss rate is slightly reduced, the instruction cache cannot be executed unless there is data (of the instruction), so the processing is interrupted during the refel. The problem of doing so was not solved.

[0004]

As described above, in the conventional cache memory system, since the calculation is stopped during refilling, an increase in the miss rate means a decrease in the performance of the cache memory, which is a serious problem. In some cases, the microprocessor is not only helpless but also harmful, and in particular has hindered the performance improvement of a microprocessor incorporating a cache memory in one chip.

The present invention has been made in view of such circumstances, and a purpose of the present invention is to reduce the error rate by refilling all the continuously used areas with one error. Another object of the present invention is to provide a cache memory device which can continue calculation without stopping even during refilling and can obtain high performance.

[0006]

SUMMARY OF THE INVENTION A cache memory control method in a cache memory device according to the present invention provides a method for controlling a lower cache memory or a main cache memory when data required by a computer does not exist in an upper cache memory. What is claimed is: 1. A cache memory device comprising: means for exchanging said target data from a memory, provided with an end pattern register for storing data stored in said main memory and set by a program in which an end condition for exchanging data is set in advance. In the data cache, the replacement of data from the lower cache or main memory starts from the address specifying the data when the target data does not exist, and increases the address specifying the data. Continue the exchange, and Is terminated based on the data set by the program stored in the end pattern register, when the data read from the lower cache or main memory matches the set end condition, Is determined.

In the above cache memory device ,
Determining the end of replacement when the increased address matches the address of data already existing in the upper cache memory, irrespective of the content of the read data in the cache memory control method . It is characterized by the following.

[0008]

[0009]

The data replacement when a mistake occurs is not continued for a fixed length for one mistake, but the refill is continued while checking the content of the data to be refilled. By determining the end, the variable length can be continued. Thereby, the number of mistakes can be reduced, and unnecessary data exchange can be prevented. In addition, since these exchanges can be performed independently and in parallel regardless of the execution of the computer, by exchanging data in the cache without stopping the computer, large blocks can be retained without stopping the computer. Can be refilled.

[0010]

An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a configuration of a cache memory device according to one embodiment of the present invention. FIG. 2 shows a flow of the operation of the refill control unit 4 in FIG.

The operation will be briefly described. First, when the CPU 1 reads the cache memory, it gives an address and simultaneously accesses the tag section 2 and the data section 3 of the first cache. If there is a hit (if the comparator 6 detects that the address of the tag unit 2 matches the address sent from the CPU 1), the data read from the data unit 3 of the first cache is correct. Use the read data. In this case, data can be accessed in one clock.

If there is a miss in the first cache, the address to be read is accessed through the refill control unit 4 to the second cache memory 5 (this may be the main memory) (S2). Therefore, in the case of the second cache, data is accessed after a hit is confirmed. The read data is passed to the first cache via the refill control unit 4 (S3), and the tag unit 2 and the data unit 3 of the first cache are rewritten.
The data is also sent to CPU1.

In the above process, when data is transferred from the second cache memory 5 to the refill control unit 4, the branch instruction detector 8 monitors the data being refilled and detects whether it is a branch instruction (S4). If the instruction is not a branch instruction (S4 No), refilling is continued one after another while increasing the address to be given to the second cache or the main memory (S9) (S10, S3). By doing so, once a cache miss is made, the branch instruction is refilled, so that no cache miss is made up to the branch. In addition, if a block (unit of data to be refilled at a time) is made large with a fixed length, the same effect is obtained, but it is necessary to refill an unused area, which is wasteful, but this can be prevented. Actually, not only is the branch detected, but refilling is of course useless when it is already registered in the cache. Therefore, when the address given to the second cache matches the address in the lag portion of the first cache (S11 Yes). The refill is stopped (S12).

As an actual method of making a cache memory, in order to reduce the capacity of the tag memory, as shown in FIG.
It is effective to have a plurality of valid bits for one tag. In this example, for one tag (address), the data unit (V0, V1, V1
2, V3). Note that the bit M in the figure indicates that at least one of the data in these data portions is invalid (rewritten). If each valid bit has a width of one refill, waste can be minimized.

When a branch target buffer (branch prediction device) is provided, refilling is continued from the prediction target of the branch target buffer without interrupting the filing at the branch, so that even if there is a branch, Refill can be continued effectively. Here, the function of the branch target buffer will be described with reference to FIG. First, the state of instruction fetch performed by a normal CPU is shown in FIG. If the instruction at address 101 is a branch instruction, it is known that the branch destination is at address 201 after executing the instruction. Therefore, the instructions at addresses 102 and 103 fetched in the cycle before the execution are wasted. Would. Therefore, once the above occurs, address 201 is stored in the branch prediction table as shown in FIG. Then, as shown in (c), the CPU can fetch the instruction at address 101 and look up the branch prediction table to fetch the instruction at address 201 in the next cycle. The operation when this is applied to the present embodiment will be described again with reference to FIG. First, when the branch instruction detector 8 detects that the data being refilled is a branch instruction (S4Yes), the branch predictor 7 is activated by this detection signal, and the address of the data is branched from the refill control unit 4. The result is sent to the predictor 7 (S5), and it is checked whether it is registered in the branch prediction table. If the prediction destination is registered in the branch predictor (S6
Yes), the branch predictor 7 sends the predicted branch destination address to the refill controller 4 (S7). The refill controller 4 continues refilling from the expected address (S8, S3). If the prediction destination is not registered (No in S6), similar to the case where the data is not a branch instruction,
Continue refilling while increasing the address. By doing so, refilling can be continued effectively.

Although this mechanism has been described in the above example for fetching instructions, it can be used for fetching data as well. For example, as shown in FIG.
This is effective for variable-length data in which the end of the data is indicated by a specific pattern. It is desirable that the pattern for the end determination be variable by a program, and it is desirable that the maximum value of the continuous refill can also be set.
The configuration is as shown in the block diagram shown in FIG. Also,
FIG. 5 shows a flow of the operation of the refill control unit 4 in the figure. First, an end pattern value is set in advance in the end pattern register 12 by a program, and the maximum number of refills is set in the maximum number register 11 in consideration of a bug in data. The refill end condition satisfies either the condition that the data being refilled matches the end pattern value (S25) or the number of continuous refills exceeds the maximum number of refills (S27). The refill is stopped when the
0). Other operations are the same as those already described.

Further, a series of operations of these refills is referred to as CP
U is performed in parallel with the operation of U, so that even if the first cache memory misses,
U resumes execution and the process proceeds. Therefore, if the refilling speed is higher than that of the CPU, the execution can be continued without stopping the calculation until the branch comes with one mistake and after the branch if the branch prediction device is attached.
This will be described with reference to the timing chart of FIG. One square next to FIG. 8 represents a clock. If A1 misses in the first cache, refilling is continued from here. Then, in the case of this figure, processing is started in a pipeline manner for the sequence of B that is not related to the sequence of A,
If B1 misses in the first cache, refilling is continued from here on in parallel with refilling of the A series. This pipeline processing can be realized by providing an address latch and a data latch in the refill control unit 4, and arranging and optimizing the program so that the program is interposed between the B series, which is not related to the A series. By performing this pipeline processing, even when the refill speed is lower than that of the CPU (for example, when the refill timing is every plural clocks), it is possible to prevent the calculation from being stopped. That is, since the data is aligned in the first cache after the clock (8), there is no time during which the CPU has stopped the processing, and the refilled data is used so as to follow the refill continued at A1 and B1. The CPU performs the processing. Moreover, the refill and the operation of the CPU are performed in parallel. When the refill speed is faster than the CPU, for example, A2, A
3 is a case where the CPU usage extends over a plurality of clocks. In this case, while A2 is using the CPU,
Since the refilling of the data used in step (1) has been completed, the start and continuation of the refilling are sufficiently effective only with A1.

In the above embodiment, the refill between the first cache and the second cache has been described.
This refill method can be applied to various memory configurations.
For example, a configuration having a main memory in place of the second cache may be used. Alternatively, a first cache, a second cache, and a main memory may be provided. A refill control unit may be provided between 1st and 2nd and between 2nd and main, and refills may be performed in parallel. Such a configuration may be used. CPU, 1s
t cache on one chip, refill control unit, 2
The nd cache may be provided outside the chip, the refill control unit may be provided inside the chip, or the first cache may be provided outside the chip. The second cache may be configured such that the tag portion is first checked to determine whether it is a hit or a miss, and then the data portion is accessed and pulled.
As in the case of the st cache, the tag and the data can be simultaneously drawn.

Further, in the above embodiment, the case where the refill is one system has been described. However, the refill may be made into a plurality of systems (two or more signal lines in FIGS. 1 and 4 respectively).

Further, the maximum refill count register 11 of the embodiment relating to the data cache can be applied to an instruction cache. In this case, a maximum number register is added to FIG. 1 and the number of continuous refills is counted by the refill control unit 4 and compared with the maximum number of refills set in the register from the CPU 1 (for example, S3 in FIG. 2).
When the count exceeds the maximum number, the refill is stopped. In FIG. 2, if the address to be refilled is already registered in the first cache, the refilling is stopped at that point in time. However, this may be stopped when the registration is continued for a predetermined number of times. If another fetch is requested by the CPU while the refill is being performed and the fetch is missed in the first cache, the continual refill is stopped and another refill is started with priority. You can also do so. However, as described above, if there are a plurality of refill systems, the continuous refill and another new refill can be performed in parallel.

[0021]

As described above, according to the present invention, when a cache miss occurs, the refill is performed continuously as much as necessary without interrupting the calculation, thereby reducing the miss rate and reducing the error rate. Even in the case where the first cache is provided, a practically significant effect such as realization of a cache memory device that can exhibit high performance can be obtained.

[Brief description of the drawings]

FIG. 1 is a diagram showing a configuration of a cache memory device according to one embodiment of the present invention.

FIG. 2 is a flowchart showing an operation of a refill control unit 4 in FIG. 1;

FIG. 3 is a diagram for explaining a function of a branch predictor 7 in the embodiment.

FIG. 4A is a diagram showing a configuration of an embodiment in which the present invention is applied to a data cache memory. (B) A diagram showing an example of data having an end mark.

FIG. 5 is a flowchart showing the operation of the refill control unit 4 of FIG.

FIG. 6 is a diagram illustrating a configuration example of a tag unit of a cache according to the embodiment.

FIG. 7 is a diagram showing operation timing of a conventional cache memory device.

FIG. 8 is a diagram showing an example of operation timing when the operation of the CPU and the operation of the refill control unit are performed in parallel.

[Explanation of symbols]

1 CPU, 2 1st cache tag section, 3 1
st cache data section, 4 refill control section, 5
2nd cache memory, 6,13 comparator, 7
Branch predictor, 8 branch instruction detector, 11 maximum number register, 12 end pattern register

Claims (2)

(57) [Claims] An object data is stored in an upper cache memory.
If there was no, the lower cache memory
Or replace the target data from main memory
Memory device with meansAt  Replacement of data stored in the main memory in advance
Data set by the program that sets the end condition
An end pattern register for storing the lower cache or lower cache in the data cache is provided.
Replaces the data from the main memory with the target data.
Address to specify this data if the data does not exist
From the address, and increase the address specifying the data.
While continuing the exchange, the end of the exchange,
According to a program stored in the end pattern register.
Lower-level caches based on the configured data.
Or the data read from the main memory
If the specified termination condition is met,
Cache memory characterized by determiningControl method
Law. 2. A maximum number register in which a maximum number of refills is set in advance, wherein the ending condition is when the end pattern value matches a ending pattern value set in advance by the program, or the number of continuous refills is set in the maximum number register in advance. 2. The cache memory control according to claim 1, wherein one of the cases where the maximum number of refills is exceeded is satisfied.
Method.