Cache control system

Details Cache control system Cache control system

2001-03-19

2003-10-28

Nguyen, Hiep T. (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S128000, C711S136000

Reexamination Certificate

active

06640286

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a cache memory unit, placed between processors and a main memory, for short-time storage to retain part of the contents of the main memory; and, more particularly, the invention relates to the cache memory unit that is so designed that specific lines are preferentially stored into the cache.
A cache is a faster-access memory of small capacity placed between a main memory and a processor that executes instructions read from the main memory. The cache is designed to temporarily retain the data in given units that the processor has fetched or retrieved through access to the main memory. Units of data to be stored into the cache are called blocks or cache lines. In the present Specification, the above units are simply referred to as lines.
The processor first accesses the cache to retrieve a line it needs. If the line exists on the cache (this result is called a hit), the processor uses it; otherwise, the processor accesses the main memory. The higher the cache hit rate, the more efficient will be the processing that can be performed. To increase the cache hit rate, it is necessary that lines more frequently accessed remain stored on the cache.
An analysis of patterns in which programs access the memory shows a general tendency: a spatial locality in that addresses near an accessed address are likely to be accessed before long; and a temporal locality in that the accessed address is likely to be accessed again before long. A typical known cache is designed to operate efficiently for programs having the above tendency. For such a cache, data access is performed in line units and data around the required data is stored together with the required data into the cache. Furthermore, in a cache using the LRU (Least Recently Used) method, a line that has been least recently accessed is replaced by a new line, so that recently accessed lines are not readily replaced.
However, the locality differs for different programs or different parts of a program. Data access in line units and line replacement by the LRU method do not always lead to an increase of the cache hit rate. This tendency is noticeable especially for business application programs.
One cause of the above problem is the storing of all lines equally into the cache. With the aim of solving this problem, some approaches have been disclosed that address this problem by preferential storing of specific lines into the cache, which contributes to enhancement of the cache performance. These approaches will be mentioned below.
In an approach described in U.S. Pat. No. 5,546,449 (this approach is hereinafter referred to as example 1), a specified line is inhibited from being replaced by another line.
In an approach described in Japanese Patent Laid-Open Publication No. 07-028706 (this approach is hereinafter referred to as example 2), priority ranks are assigned to lines when the lines are stored into the cache and a line of higher priority rank is inhibited from being replaced by a line of lower priority rank.
In an approach described in IA-64 Application Developer's Architecture Guide, Intel, May (1999) pp. 4-20 to pp. 4-23 (this approach is hereinafter referred to as example 3), hint information is included in an instruction issued from a processor and a cache operation is controlled to store the line accessed by the instruction into a location of a certain level in the cache hierarchy, based on this information.
In an approach described in U.S. Pat. No. 5,787,490 (this approach is hereinafter referred to as example 4), every process is given a priority rank in the right to use the cache and the cache operation is controlled, based on this process-specific priority.
The above examples 1, 2, and 3 are, so to speak, methods in which different cache priority ranks are assigned to different lines. However, dynamic change in the way priority ranking is given to the lines is not taken into consideration.
On the other hand, as for the above example 4, it can be said that the priority is changed dynamically. However, the priority that can be changed in this example depends on the process for which a line is used.
Even in the same application, it is conceivable that the priority to be given to an individual line dynamically changes, depending on the load and use condition. Unless the cache executes line replacement control adaptive to the dynamic change of priority on a line-by-line basis, at present, there is a possibility of occurrence of undesirable line replacement, i.e., a line which is to preferentially remain stored on the cache is replaced by a lower priority line, which results in a condition in which the total cache hit rate cannot be increased sufficiently.
SUMMARY OF THE INVENTION
Accordingly, an object of the present invention is to provide a cache that enables a dynamic priority change on a per line basis so that the cache will preferentially retain higher priority lines and the cache hit rate will be increased, thereby providing for more efficient memory access.
Another object of the invention is to provide a cache memory unit applicable to an information processing system in which computer resources can be divided into a plurality of partitions and different applications can be run in different partitions, the cache enabling the user to specify lines to be handled preferentially and using an optimum method (policy) to store grouped lines into the cache per partition.
Another object of the invention is to provide a cache memory unit that achieves a higher cache hit rate than a typically known cache that handles lines equally, and which can be configured simply by modifying the system.
In the cache memory system configured according to a typical embodiment of the invention, a grouping method for dividing lines into groups is set into a table. Also, a storing policy for storing lines into the cache memory is defined for each of the groups set into the table. When an access command issued from a processor to access the main memory turns out to be a miss on the cache memory, the objective line is read from the main memory, and a line attribute of the objective line to which group the objective line belongs, in other words, is determined according to the table. Then, the objective line is stored into the cache memory according to control information of the cache memory and a storing policy of the corresponding group.
A detailed example of the configuration of the above-described cache memory system is as follows. The cache memory unit comprises a cache memory comprising a plurality of entries, each of which consists of a data area where a line is to be stored and a control information area where control information for the line is to be stored; a group definition controller that is used to divide lines that may be read by the processor from the main memory into groups and specify definitions of the groups; a group selector to determine one of the groups to which the line belongs in accordance with the group definitions and the information in a command issued from the processor to read data from the main storage; a policy definition controller that is used to assign a policy of storing whereby lines belonging the groups are stored into the cache memory; and a storing means to read a line from the main memory and store the line into the cache memory in accordance with the group to which the line belongs, the line control information retained in the cache memory for the candidate lines to be replaced, and the policy of storing, if a read request from the processor results in a miss.
In the foregoing examples, 1, 2, and 3, when a line is stored into the cache, if it is stored in accordance with the priority rank assigned to it at this point, this storing approach appears to be adaptive to a dynamic priority change. In the case of the examples 1 and 2, however, the priority rank of a line is recorded as control information into the cache memory when the line is stored into the cache. If, for example, a line L
1
has priority P
1
when it is stored into the cache, the priori

Affiliated with

Also associated with

Rating

Cache control system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cache control system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache control system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3174100