JP2000267938A - Cache storage - Google Patents

Abstract

PROBLEM TO BE SOLVED: To improve the use efficiency of a cache memory by providing a control circuit which determines an expellant entry according to priority level information among memory access kinds, access history information, and memory access information showing the kind of memory access. SOLUTION: The control circuit determines the expellant entry according to the priority level information among memory access kinds, access history information, and memory access information showing the kind of access. For example, a cache 10 has a memory cell part composed of an access kind data array 14, etc., a hit/miss decision circuit, an expelled object WAY determining circuit 16, an non-expelled-object WAY determining circuit 17, and an LRU/ access kind array control circuit 18. The access kind data array 14 holds memory access kind information on data stored in respective WAYs of respective blocks at the time of a cache miss by the WAYs.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a cache storage device of an information processing device, and more particularly to a cache storage device having a function of determining the priority of a cache eviction entry.

[0002]

2. Description of the Related Art For a cache memory of an information processing apparatus, see Computer Survey Vol.
530 pages (Computer Surveys,
Vol. 14, No. 3, pp. 473-530).

In general, a computer system is not directly connected to a processor with a large-capacity upper-level storage device, but is connected via a high-speed, small-capacity lower-level storage device. A cache memory is an example of a lower-level storage device (hereinafter, a lower-level storage device is simply referred to as a “cache”). The processor normally exchanges data with the cache. Of course, the cache also exchanges data with higher-level storage devices. In this case, transmission and reception are performed in relatively large units called blocks, such as 128B or 256B. This is because, as a result of the processor performing an instruction fetch or a data fetch on the cache, a desired instruction or data exists in the cache. Occurs if not. This state is referred to as a cache miss. Normally, at least a part of the address is input to the cache storage device so that the real address of the effective block held in the cache storage device in the main storage device is obtained. A cache storage device tag to be held is provided. This storage part is called an address tag array. When reading data,
The output address is compared with the address from the request source with reference to the cache storage device tag, and if the address matches, it indicates that a desired block exists in the cache storage device. This state is called a cache hit. If the addresses do not match as a result of the address comparison, the desired block does not exist in the cache storage device. This state is called a cache miss. Although the above is an example of two-level storage, this concept can be extended to storage devices of two or more levels.

If it is possible to hold data at an arbitrary location in the main memory in an arbitrary block of the cache, the entire address tag array of the cache is compared with the address to be accessed.

[0005] Such a system is called a cache memory of a full associative system. With this method, it is necessary to compare all the address tag arrays with the address to be accessed, so that the comparison circuit becomes complicated, the amount of hardware increases, and the time required for access becomes longer. The disadvantage is that.

A cache memory of the set associative system is an example of a cache memory that is an improvement over the previous system.

FIG. 1 is a diagram showing an outline of the set associative cache memory.

In this method, the cache memory has n rows and m rows.
Split into column entries.

Here, each row of the cache memory is called a line, and each column is called a way.

In order for a processor to be able to access almost all of the cache memory, it is necessary to store recently frequently accessed data in a cache. Unused data need not be stored in the cache.

Therefore, the cache memory performs control so as to satisfy the above-mentioned requirement.

The control method is called an eviction algorithm.

[0013] The following is a typical eviction algorithm, LRU (Last Receipt Used).
The algorithm will be described as an example at the time of reading.

When the data in the cache is accessed, the block to which the data belongs is kept held. When the data that is not in the cache is accessed, one block including the data is transferred from the main memory to the cache. Instead, it evicts a recently unused block in the cache.

In order to perform the above processing, it is necessary to hold information indicating which block has not been accessed recently in the cache.

For this reason, access history information is held for each line, and this information is updated each time the cache is accessed.

That is, when data existing in the cache is accessed, or when one block of the WAY having the oldest access history information is evicted and new data is transferred from the upper storage, the data is stored. The access history information of the way is updated.

[0018]

However, the aforementioned L
In the RU algorithm, since the cache memory is controlled so that the most recently accessed data is not evicted, the performance may deteriorate in the following cases.

In the case of executing an instruction such that a plurality of operand fetches and a large number of operand fetches occur for one instruction fetch by a MOVE instruction or the like, the cache is first accessed by the instruction fetch, and the cache includes the instruction. If the block does not exist, the block containing the instruction is transferred from the main memory and stored in the cache. If a cache access by a large number of operand fetches following an instruction fetch is a cache miss (for example, immediately after clearing the cache, all cache accesses by the operand fetch are cache misses). As in the case of the fetch, the block including the operand is transferred from the main memory to the cache and stored.

At this time, when the cache line stored by the operand fetch is the same as the cache line stored in the cache by the instruction fetch, when the cache miss by the operand fetch reaches the WAY number of the cache line, the first instruction is executed. The access history information of the block containing the instruction stored in the cache by fetch becomes the oldest, and when a next cache miss occurs, the block is selected as a target to be evicted from the cache line.

When the block containing the instruction is evicted as described above, the instruction fetch at the time of executing the next instruction is
A cache miss will occur again, and performance degradation is inevitable.

[0022]

(1) A memory array section for holding data and tags, hit / miss determination means for access data, means for holding and updating access history information for each line of each cache, At least a control circuit for controlling a memory unit and a holding unit, a set associative method for controlling eviction of a cache line based on the access history information is adopted, and memory access by instruction fetch and operand fetch In a cache memory device having a plurality of memory accesses having different usages in a processor such as a memory access, a plurality of memory cells held by memory cells as an access type data array of the cache line for each way of the cache line. The bit string allows Data for each WAY of Interview, characterized in that it has memory access status information indicates cached by any memory access.

(2) Eject WAY of a cache line
Means for specifying the memory access type to be preferentially stored in the cache and the number of memory access types. Note that the memory access type can be specified only before the program is executed by a static specification method that can be specified by an external specification means, or a method that can be dynamically specified by interposing an OS or the like during the program execution. Is mentioned.

(3) Eject WAY of a cache line
Means for notifying the type of memory access to the cache line in which a cache miss has occurred to the means for determining a cache line eviction WAY.

(4) The eviction WAY of the cache line is determined by the output data of the LRU data array of the cache line, the output data of the access type data array of the cache line, the priority memory access type information, and the memory access type. It is characterized by having means for performing. A detailed cache line eviction way determination method will be described later in an embodiment of the present invention.

(5) According to the invention disclosed in the present application, at least one memory access by instruction fetch is designated as a priority memory access type and the number of priority memory access types is specified. Data stored in the cache is not evicted from the cache by memory access other than instruction fetch.

[0027]

FIG. 2 is a diagram showing a schematic configuration of a cache storage device according to an embodiment of the present invention. The cache 10 according to the present embodiment includes a memory cell unit including an address tag array 11, a data array 12, an LRU data array 13, and an access type data array 14, and a hit / miss determination circuit 15 for memory access. And the eviction target way determination circuit 16 and the exclusion target WAs
It has a Y decision circuit 17 and an LRU / access type array control circuit 18.

In this embodiment, the case where the present invention is applied to a general 4-way set associative cache will be described. However, the present invention can be applied to a cache having an arbitrary number of ways.

The address tag array 12 holds address information 19 and a valid flag 20 of each block of the cache 10.

The data array 11 holds data of each block of the cache 10.

The LRU data array 13 holds access history information of each block of the cache 10.

In this embodiment, the access type data array 14 holds the memory access type information at the time of occurrence of a cache miss of the data stored in each way of each block of the cache 10 for each way. There are features. . The configuration of the access type data array 14 is shown in FIG.

The memory cell section can simultaneously read data and tags of one line of the memory cell by using a plurality of predetermined bits of an address to be accessed as an index.

In response to the LRU / access type data update signal 21 from the LRU / access type array control circuit 18, data and tags of an arbitrary block can be updated.

The hit / miss determination circuit 15 has an address 22 to be accessed and each WAY read by the memory cell section.
The address 19 and the valid flag 20 of the tag are input, the addresses are compared, and the address 22 matches the address 19 of the tag, and the valid flag 20
The hit signal 23 is output only when is valid.

Further, the hit / miss circuit 15 determines which WAY according to the hit signal 23 and the valid flag 20 of each way.
A hit way signal 24 is generated to indicate whether or not there is data. The hit way signal 24 is valid only when the hit signal 23 is output.

In this embodiment, since the description is made using a 4-way cache, hit WAY signals are 0 to 3;
It shows that each of the hits WAY0 to WAY3.

LRU / Access Type Array Control Circuit 18
Is a signal WAY 25 to be ejected from the WAY determination circuit 16 and the hit / miss determination circuit 1
5, the updated LRU data 26 is generated by the hit signal 23 and the hit way signal 24 transmitted from
The data / access type data update instruction signal 27 causes L
The latest history information of the cache line is written to the RU data array 13.

At this time, at the time of a cache hit, since the data stored in the hit way is accessed, the WAY is the most recently accessed data. The access history information of the cache line is generated so that the signal 24 becomes the newest access, and is written to the LRU data array 13 as the updated LRU data 26.

At the time of a cache miss, the eviction target W sent from the eviction target way determination circuit 16
Since the data sent from the main memory is written to the AY 25, the WAY is the most recently accessed data. Therefore, the eviction target WAY signal 25 sent from the eviction target way determination circuit 16 becomes the newest access. Then, the access history information of the cache line is generated and written to the LRU data array 13 as the updated LRU data 26.

In this embodiment, the LRU / access type array control circuit 18 generates update access type data 29 based on the memory access type information 28 from the CPU, and issues an LRU data / access type data update instruction signal. 2
7, the corresponding way of the access type data array 14
It is characterized in that the updated access type data 29 is written in the data. At this time, in the event of a cache miss, the updated access type data 29 is always written to the access type data array 14 in the way, but when a cache hit occurs, writing to the access type data array 14 is considered as follows. Can be

If a memory access different from the memory access that caused the cache miss frequently accesses the data stored in the cache 10 at the time of the cache miss, the memory access at the time of the hit may be the designated priority access type. For example, the access type data array 14
Registering the latest memory access type, which is the designated priority access type, is not least beneficial to system performance.

When a cache miss occurs, the eviction target way determination circuit 16 determines whether the LRU data array 1
The WAY 25 to be evicted is determined based on the three output data. In the present embodiment, when the WAY to be evicted is determined, the valid flag 20 for each WAY in the output data of the address tag array 12 and the non-eviction target are determined. The non-eviction target way 31 output from the way determination circuit 17 outputs
The method is characterized in that an ejection target way 25 is determined.

That is, all the valid flags 20 of each way are ANDed, and if the result of the AND is a logical value "1", the WAY of the cache line is full.
WAY specified by WAY signal 31 not to be kicked out
LR under the constraint that the
The eviction target way 25 is determined based on the output data of the U data array 13.

Conversely, when the AND result is a logical value “0”, the WAY of the cache line has a vacancy,
WAY specified by WAY signal 31 not to be kicked out
, The eviction target way 25 indicated by the LRU data array 13 output data is always a free way.
Is controlled to instruct.

The present embodiment has a feature in the non-eviction target way determination circuit 17.

Hereinafter, the non-eviction target way determination circuit 17 will be described.
Will be described in detail. FIG. 3 is a flowchart showing the process up to the determination of the WAY 31 not to be evicted, and the WAY signal 25 to be evicted is determined by conditions such as whether or not a priority memory access type is specified and whether or not the memory access matches.
Are divided into nine cases (1) to (9). FIG. 4 shows the conditions for generating the eviction target way signal 25 in the cases (1) to (9) shown in FIG.

In the present invention, if the priority memory access type and the number of priority ways are specified by the priority memory access type information 30, the following operation is performed (step 100).

First, at the time of occurrence of a cache miss, the eviction WAY determining circuit 16 performs the following based on the output data of the access type data array 14 of the cache line.
The number of ways that data is currently stored in the cache line is determined (step 101).

As a result, if there is still a vacancy in the way, the eviction of the cache line is performed only by the output data of the LRU data array 13 of the cache line.
The AY signal 25 is determined. This does not matter whether the memory access matches the priority access type (case (1)) or does not match (case (5)). The reason why the output data of the LRU data array 13 is used at this time is that when there is a free way, the LRU algorithm always specifies the free way by the LRU algorithm.

Next, when a cache miss occurs, the number of ways in which data is currently stored in the cache line is obtained by the means. As a result, if all the ways are in use and there is no free space, the cache line is currently stored. The number of occupying the WAY of the data stored in the cache 10 by the specified priority memory access type among the data stored in the cache 10 is compared with the number of the specified priority memory access type (step 102).

As a result of the comparison, if the number of ways in which data is currently stored is larger than the number of specified priority memory access types (cases (2) and (6)), the specified memory access is specified. Even if it matches or does not match the priority memory access type, no matter how much is written to any WAY of the cache line, the number of the specified priority memory access type does not become less than the number of the specified priority memory access type. The flush WAY 25 of the cache line is determined only by the output data of the array 13.

Next, when a cache miss occurs, the number of ways in which data is currently stored in the cache line is obtained by the means. As a result, if all the ways are in use and there is no free space, the cache line is currently stored. Of the data stored in the cache 10 according to the designated priority memory access type, and
As a result of comparison with the number of designated priority memory access types, if the numbers are equal, the eviction WAY signal 25 for the cache line is determined as follows (step 103).

The memory access is compared with the specified priority memory access type (step 104). If the two memory access types match (case (3)), which WAY of the cache line is Even if written, the number of designated priority memory access types does not fall below the specified number. Therefore, the eviction WAY 25 of the cache line is determined only by the output data of the LRU data array 13 of the cache line.

On the other hand, if the memory access does not match the specified priority memory access type (case (7)), the way in which the data is stored by the specified memory access is changed to the specified priority memory access. If a memory access other than, the number of registered data by the priority memory access is reduced by one, and it becomes less than the specified number of priority memory accesses. The registered WAY is excluded from the eviction targets, and the WAY having the highest eviction priority is designated as the eviction WAY signal 25 of the cache line using the output data of the LRU data array 13 from the remaining WAYs.

Next, when a cache miss occurs, the number of ways in which data is currently stored in the cache line is determined by the above-described means. Of the data stored in the cache 10 according to the designated priority memory access type, and
As a result of comparison with the number of designated priority memory access types, the number of ways in which data is currently stored is
When the number is smaller than the number of the specified priority memory access types (cases (4) and (8)), the WAY in which data is stored by the specified memory access is evicted by a memory access other than the specified priority memory access. If this happens, the number of data registrations to be stored prior to other memory accesses is further reduced by one.
The AY is excluded from the eviction target, and the WAY with the highest eviction priority is designated as the eviction WAY signal 25 for the cache line using the output data of the LRU data array 13 from the remaining WAYs (step 103).

Finally, when the priority memory access type is not specified and the priority way number is not specified (case (9)),
Only the output data of the LRU data array 13 of the cache line determines the eviction WAY signal 25 of the cache line.

As described above, the present invention has been specifically described based on the embodiments. However, it is needless to say that the present invention is not limited to the above-described embodiments and can be variously changed without departing from the gist of the present invention.

[0059]

The effects obtained by the invention disclosed in the present application will be briefly described as follows.

(1) In a set associative cache storage device which performs cache line eviction control based on access history information, a specified priority memory access information, a memory access status of the cache line, and a memory Since the eviction WAY of the accessed cache line is determined based on the memory access type information, the data stored by the memory access type that is not desired to be evicted is not evicted.

As a result, the number of cache misses can be reduced in large-scale data transfer processing and the like, so that the performance of the data processing system can be improved.

(2) Specifying the priority memory access information
By enabling operation by software such as an OS, it is possible to control cache eviction at the application level.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a schematic configuration of a conventional set associative cache memory, and also shows a schematic configuration diagram of an access type data array which is a feature of the present invention.

FIG. 2 is a block diagram illustrating a schematic configuration of a cache storage device according to an embodiment of the present invention.

FIG. 3 is a flowchart showing a process up to the determination of a WAY signal not to be evicted in the present invention.

FIG. 4 shows conditions for generating a WAY signal to be expelled in the cases (1) to (9) shown in FIG.

[Explanation of symbols]

10 cache storage device, 11 address tag array, 12 data array, 13 LRU data array, 14 access data array, 15 hit /
Miss determination circuit, 16 ... WAY determination circuit for eviction target, 1
7 ... WAY decision circuit not to be evicted, 18 ... LRU /
Access type array control circuit, 19: address information of each block, 20: valid flag of each block, 21: LR
U / access type data update signal, 22 ... input address,
23 ... hit signal, 24 ... hit way signal, 25 ... way signal to be expelled, 26 ... updated LRU data, 27
... LRU data / access type data update instruction signal, 28
... the relevant memory access type information, 29 ... updated access type data, 30 ... priority memory access type information, 31 ... WAY not subject to eviction

 ──────────────────────────────────────────────────の Continuing from the front page (72) Inventor Ouchi Kawauchi 1 Horiyamashita, Hadano-shi, Kanagawa F-term, General-purpose Computer Division, Hitachi, Ltd. 5B005 JJ13 KK12 LL01 LL11 LL11 MM01 NN01 NN31 QQ02 QQ04 SS12 VV04

Claims (6)

[Claims] A memory array unit for storing data and tags, a hit / miss determination unit for access data, and a unit for storing and updating access history information for each registered entry in a cache; Performs cache entry eviction control based on information,
In a cache storage device characterized by the presence of a plurality of memory accesses having different uses, based on priority information between memory access types, the access history information, and memory access information indicating the type of memory access, A cache storage device comprising a control circuit for determining an eviction entry. 2. The cache storage device according to claim 1, wherein a memory access type to be preferentially stored in a cache is specified by the priority information between the memory access types, and the priority information further includes: A cache storage device which is designated beforehand by a processor or an external designation unit before a cache miss occurs. 3. The cache storage device according to claim 1, wherein the memory access status information is stored in each entry of the cache by a bit or a plurality of bit strings held by a memory cell for each entry of the cache. A cache storage device indicating a memory access type when data is stored. 4. The cache storage device according to claim 1, wherein the method for determining the eviction entry of the cache includes:
Priority information between memory access types specified by a processor or an external specification unit, memory access status information held by a memory cell for each cache entry, and memory access indicating the type of memory access Based on the information, it is determined whether or not the accessed cache entry is full, and if full, the cache entry is stored according to the memory access type registered in the cache and to be stored in the cache with priority. The number of entries is determined, and if the number of registrations is smaller than the number of entries of the priority memory access type specified by the priority information between the memory access types, the entry in which the specified priority memory access type is registered is deleted. Exclusion entry exclusion method characterized by being excluded from the eviction target . 5. A method according to claim 4, wherein priority information of memory access type specified by priority information between memory access types by a processor or an external specification means, and a type of the memory access. The number of entries of the priority memory access type stored in the cache is the same as the number of entries of the priority memory access type specified by the priority order information between the memory access types A method of determining an entry to be evicted, characterized in that an entry in which a specified priority memory access type is registered is excluded from an object to be evicted. 6. An entry determination method according to claim 4 or claim 5, except that the entry to be evicted is not specified except for the case described in claim 4 or claim 5. A eviction entry determination method, wherein all entries can be eviction target entries.