JP3438598B2 - Cache memory replacement method and cache memory using the same - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a set associative cache memory replacement method using an LRU replacement algorithm and a cache memory using the replacement method.

[0002]

2. Description of the Related Art In recent years, in computer systems, in order to operate a CPU at high speed, it has been common practice to arrange a small-capacity high-speed cache memory device between the CPU and a main memory. . The cache memory holds frequently used data in block units. When the CPU accesses the cache memory, an entry containing the requested data in the cache is called a hit, and a non-existent entry is called a miss. The missed data is transferred from the main memory to the CPU, but at this time, the requested data is simultaneously replaced with an entry existing in the cache. The time spent for this transfer and replacement is called the miss penalty.

There are various cache methods, but one of them is a set associative cache using the LRU replacement algorithm. The set associative cache is a method in which a block to be replaced can be placed only in n ways on the cache.
Also called ay set associative cache. On the other hand, LRU (Least Recently Used)
An algorithm is an algorithm that replaces a data block that has not been used for the longest time. For example, in the memory control circuit disclosed in JP-A-1-173239, when a cache miss occurs, the LRU
A predetermined data block in the cache memory is replaced according to the algorithm.

[0004]

As described above, in the set associative cache using the conventional LRU replacement algorithm, only temporal locality is taken into consideration, so that an entry with high spatial locality is replaced. There was a problem that could be. Also,
The method of considering spatial locality by expanding the block size of the cache memory has a problem that the performance at the time of miss is increased because the penalty at the time of miss becomes large.

An object of the present invention is to provide a high performance cache memory which can reduce the miss rate.

[0006]

Means for Solving the Problems The cache memory replacement method of the present invention, in the cache memory of the set associative method using the LRU replacement algorithm, the sale of a number of tags accessed in the past
Then, those that are not the same as the previous input are stored in order, and when selecting the victim after the occurrence of a cache miss, the tag and LR
It is characterized in that it compares the address tag of the temporary victim selected by the U-replacement algorithm, and reselects the victim when the same address tag with high spatial locality is detected.

[0007]

The cache memory of the present invention is an LRU.
In a set associative cache memory using a replacement algorithm, a storage unit in which each entry is composed of an address tag, a valid bit, and a data block, a target data hit / miss determination unit, and a replacement for performing control during replacement. Control means and the replacement control means is
The data transferred from the main memory to the CPU during the race
The means by which the get data block is input and each access
In the next cache miss
LRU control means for controlling the race and past access
Same as last input from some tags that were requested
And a means for storing a non- stored item .

[0009]

Further, in the cache memory of the present invention, the target data hit / miss determination means compares the address tag read from the storage means with the target address tag to determine which way in the set. It is characterized by having a tag comparison means for discriminating whether a hit or an all miss.

In the cache memory of the present invention, the replacement control means has a prefetch function.

[0012]

BEST MODE FOR CARRYING OUT THE INVENTION Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 shows an LRU that considers both temporal locality and spatial locality as a first embodiment of the present invention.
It is a figure which shows the structure of the n-way set associative cache memory using a replacement algorithm. This n-way set associative cache memory is composed of a cache memory 2, a replacement controller 3, and a data controller 4.

The target address 1 requested to be accessed by the CPU (not shown) is divided into a tag 11, an index 12, and an offset 13. The index 12 indicates to which set in the cache memory 2 the target data may exist, and the tag 11
Is used as a key to search whether or not the target data exists in the set (n number) of entries indicated by the index 12, and the offset 13 indicates which data of the data block is requested. Is.

Each entry of the cache memory 2 is composed of an address tag, a valid bit and a data block. Each of the address tag memory 21, the valid bit memory 22, and the data block memory 23 is configured by entries corresponding to the index bit number power of an integer 2, and in the case of the n-way set associative, those memories 21, 22. , 23 are present every n sheets. In each entry, a data block is stored for each address tag, and the valid bit indicates whether the data block designated by the address tag is valid.

The replacement control unit 3 is composed of a replacement entry 31, an LRU control unit 32, and a tag history queue 33 in the LRU control unit 32. The LRU control unit 32 performs the operation for selecting a victim at the next cache miss and the control at the time of replacement for each access. The tag history queue 33 stores some tags 11 that have been requested to be accessed in the past, and is used as spatial locality information when selecting a victim. On the other hand, the replace entry 31 includes a CPU from a main memory (not shown) at the time of cache replacement.
The target data block to be transferred to
It is replaced with the entry of the victim selected by the RU control unit 32.

The data control unit 4 includes a tag comparison unit 41.
And a data selection unit 42. The tag comparison unit 41 compares the n address tags read from the address tag memory 21 with the tag 11 having the target address 1 and selects which way in the set has been hit or has all missed. Output to the unit 42 and the LRU control unit 32. The data selection unit 42 outputs the wa output from the tag comparison unit 41.
The data indicated by the offset 13 is output to the outside from the data block of the y entry.

Next, the operation of this embodiment will be described with reference to the flowcharts of FIGS. First, the tag 11 of the target address 1 requested by the CPU (step A0) is input to the tag history queue 33 in the LRU control unit 32 (step A1). Here, the tag history queue 33 stores some tags that have been requested for access in the past, and is selected by the LRU replacement algorithm considering only temporal locality when selecting a victim at the time of a cache miss. It is referred to in order to let the tentative victim consider spatial locality.
However, if the tag 11 is the same as that input last time, the target address 1 is not input to the tag history queue 33.

Next, the cache memory 2 uses the index 12 of the target address 1 to select a set in which the target address 1 may be stored,
Address tags for n entries (in the case of n-way set associative) and data blocks are read (step A2).

Next, the tag comparison unit 41 compares the address tag of the entry read in step A2 with the tag 11 of the target address 1 to determine whether it is a hit or a miss. At this time, if the valid bit indicates that the entry is invalid, the entry is regarded as a miss (step A3, step A4).

When the cache is hit, the tag comparison unit 41 determines which w entry is the hit entry.
LRU control unit 3 whether it was the entry of ay
2 and the data selection unit 42. Based on the way information notified from this tag comparison unit 41, the LR
The U control unit 32 performs the next operation for selecting a victim (step A5). In addition, the data selection unit 42
Based on the way information notified from the tag comparison unit 41, the hit data block is selected (step A6),
With reference to the offset 13 of the target address 1, necessary data is output from the hit data block (step A7).

On the other hand, if the cache is missed, L
The RU control unit 32 selects a temporary victim based on the information calculated in advance (step A8), and the tag comparison unit 41 compares the address tag of this temporary victim with the tag 11 of the entry in the tag history queue 33. (Step A9). If the address tag of the temporary victim does not match any of the tags 11 in the tag history queue 33, the temporary victim becomes the true victim, and the target data is replaced with the true victim (step A11). ). If a match is found between the true victim and the tag 11 in the tag history queue 33, the LRU control unit 32 re-selects the victim with an entry in the same set other than the temporary victim.

As described above, according to this embodiment, in the LRU replacement algorithm in which only temporal locality is taken into consideration, an entry having the same address tag with high spatial locality is prevented from being replaced as a victim. To be done.

Next, a second embodiment of the present invention will be described. The basic configuration of this embodiment is the same as that of the first embodiment described above, but the mislatency is further devised. That is, as shown in FIG. 3, in the present embodiment, an LRU / prefetch control unit 32 ′ is provided in place of the LRU control unit 32 in FIG.
The prefetch entry 31 'is provided so that the replacement control unit 3 has a prefetch function.

Then, in this embodiment, LRU /
The prefetch control unit 32 'refers to the tag history queue 33, and transfers an entry that may be requested next time but is not in the cache memory 2 from the main memory to the replace / prefetch entry 31' in advance. Therefore, according to the present embodiment, by prefetching the entry that is likely to be accessed next time, the miss latency can be significantly reduced.

[0026]

As described above, according to the present invention, since spatial locality is considered in addition to the LRU replacement algorithm considering only temporal locality, an entry with high spatial locality is replaced. The cache miss rate can be reduced. Further, since the spatial locality is realized by other than expanding the block size, there is no change in the penalty at the time of a miss and the performance does not deteriorate. Therefore, according to the present invention, a high performance cache memory can be provided.

[Brief description of drawings]

FIG. 1 is a diagram showing a configuration of a first exemplary embodiment of the present invention.

FIG. 2 is a diagram showing an operation of the first exemplary embodiment of the present invention.

FIG. 3 is a diagram showing a configuration of a second exemplary embodiment of the present invention.

[Explanation of symbols]

1 target address 11 tags 12 Index 13 offset 2 cache memory 21 Address tag memory 22 Valid bit memory 23 Data block memory 3 Replace control unit 31 Replace Entry 32 LRU control unit 33 Tag History Cue 4 Data control section 41 Tag comparison unit 42 Data selection unit

Continuation of the front page (56) Reference JP-A-1-125641 (JP, A) JP-A-63-221441 (JP, A) JP-A-63-8851 (JP, A) JP-A-61-54547 (JP , A) JP 63-318654 (JP, A) Kumar S et al. , Exploding Spatial L ocality in Data Causes using Spatial Footprints, the Proceedings of 25th August Eneum, October, 1994, United States, September, 2012, September, April, 2012, September, April, 2012, September, April, 2012, April, April, April, April, April, April, April, April, April, 1975, April, October, April, April, 2012. 357-368 Johnson T.S. L. , Et al. , Run-time Adaptive Cache Hierarchy Management via Rereference Analysis, the 326 Proceedings of the 24th Epoch. ) Fields surveyed (Int.Cl. ⁷ , DB name) G06F 12/08-12/12

Claims (4)

(57) [Claims] 1. A cache memory set associative method using the LRU replacement algorithm, among the several tags accessed in the past, previous
Those that are not the same as the input data are stored in order, and when selecting a victim after a cache miss, the above-mentioned tag is compared with the temporary victim's address tag selected by the LRU replacement algorithm, and the same address with high spatial locality is stored. A method for replacing a cache memory, wherein the selection of the victim is redone when a tag is detected. 2. In a set associative cache memory using the LRU replacement algorithm, each entry comprises a storage means composed of an address tag, a valid bit and a data block, a target data hit / miss determination means, and a replacement. And a replacement control unit for controlling the cache replacement
The target device transferred from the main memory to the CPU.
Data block input method and next time each access
At the time of cache miss, calculation for victim selection and at the time of replacement
LRU control means for controlling the
Some of the tags that were not the same as the last input
And a means for storing the cache memory. 3. The target data hit / miss determination means compares the address tag read from the storage means with the tag of the target address, and which way in the set has been hit or all misses. 3. A tag comparing means for determining whether or not the processing has been performed.
The listed cache memory. 4. The cache memory according to claim 2 , wherein the replacement control means has a prefetch function.