Cache memory system and method for managing the same

Details Cache memory system and method for managing the same Cache memory system and method for managing the same

1999-05-20

2003-04-15

Bragdon, Reginald G. (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S122000, C711S128000, C711S133000, C711S143000, C711S144000

Reexamination Certificate

active

06549983

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to cache memory systems and methods for managing cache memory systems, and more particularly, to improving performance of a cache memory system by reducing cache misses.
2. Description of the Related Art
In a typical computer system, the memory hierarchy as illustrated in
FIG. 1
includes a register set
10
in a processor, a cache system
11
, a main memory
12
, a disk drive
13
, and a magnetic tape driver
14
used as a back-up device. In the respective devices of the memory hierarchy, upper layers such as register set
10
have higher operating speeds but store less information than lower layers such as disk drive
13
or tape drive
14
. Most high-performance computer systems improve performance by appropriately setting the sizes, structures, and operation methods of register set
10
and cache system
11
.
The hierarchical memory system using cache system
11
can obtain excellent performance by basing the operation of cache system
11
on the property of locality. Programs accessing memory typically demonstrate two types of locality, spatial locality and temporal locality. Spatial locality refers to the tendency of accesses of adjacent memory locations to be close together in time. Temporal locality refers to the high probability that a program will access recently accessed items again in the near future. Caches exploit temporal locality by retaining recently referenced data and exploit spatial locality by fetching multiple neighboring words as a cache line or block whenever a cache miss occurs.
The two types of localities serve as important elements in determining the size of a cache block when designing a cache. Large cache blocks take advantage of spatial locality, while many smaller cache blocks better exploit temporal locality. However, the approaches for exploiting spatial or temporal locality contradict each other. In particular, increasing the block size improves the chance that adjacent data adjacent the most recent access will be in the cache but in a fixed-sized cache, also decreases of the number of cache blocks and the number of recently access data items in the cache.
FIG. 2
conceptually illustrates spatial locality of a cache. In
FIG. 2
, X and Y axes respectively denote memory addresses and the access probability following an access of a memory address A. The probability function of
FIG. 2
is not accurate but does illustrate spatial locality where the probability of accessing an address decreases as the distance from the last address accessed.
FIG. 2
also illustrates aspects of different choices of cache block sizes. If a large block
22
is fetched for a cache miss, miss-to-hit ratio may decrease because of the spatial locality of accesses. However, the mean expected utilization of elements in a cache block is low for a large block because the probability of accessing addresses drops with distance from memory address A. If a small block
20
is fetched for a cache miss, the mean expected utilization of elements in the cache block
20
is greater because the addresses of elements in the cache block
20
are all close to the last accessed address A. Also if software tends to access several spatially separated memory locations on a regular basis, cache block
20
being smaller allows representation of more data locations in a fixed-sized cache system and thereby reduces cache misses for programs having a greater tendency for temporal locality.
For any specific cache size, selection of a cache block size involves a trade-off between the exploitation of spatial and temporal locality. Considering this effect, studies have investigated the optimal size of a cache block for a given cache capacity. Caches constructed with the optimal block size perform well, but this performance is highly dependent on the memory access patterns of executed programs. Some programs perform best with cache blocks of a specific block size, while other programs suffer severe performance degradation when a cache uses the same block size. To solve this problem, a dual data cache can include the spatial cache and the temporal cache which have different cache block sizes to respectively exploit the spatial locality and the temporal locality of memory accesses. One dual cache operating method classifies different accesses as having primarily spatial locality or primarily temporal locality and fetches blocks of information into the cache (spatial or temporal) which exploits that type of locality.
FIG. 3
shows the structure of a dual cache memory. This dual cache memory system is according to a study described in “International Conference On Supercomputing ICS '95,” pages 338-347. The cache of
FIG. 3
includes a memory device
34
that stores information for a central processing unit (CPU)
33
, a spatial cache
30
, a temporal cache
31
, a prediction table
32
for determining whether to store the information from the memory device
34
in spatial cache
30
or temporal cache
31
, a multiplexer
35
for selecting spatial cache
30
or temporal cache
31
when CPU
33
accesses the information, and a demultiplexer
36
that is under control of prediction table
32
and directs information from memory device
34
to spatial cache
30
or temporal cache
31
. In the study of the above structure, prediction table
32
determines which cache
30
or
31
receives the information fetched from memory device
34
. Accordingly, the performance is improved when prediction table
32
selects the appropriate cache
30
or
31
.
The entries in prediction table
32
select cache
30
or
31
based on factors such as an instruction address, a last accessed address, a stride, a length, a current state, and a predicted value. Prediction table
32
obtains the stride using a difference between addresses of data accessed by the same instruction, and the stride indicates or selects the cache
30
or
31
for storage of information fetched from memory device
34
for the instruction. For example, assuming that one execution of an instruction at an address A references or accesses data at an address B, and the next execution of the instruction at address A accesses data at an address B+&agr;. When a following execution of the instruction at address A accesses information at an address B+2&agr;, prediction table
32
determines that the instruction at address A has uniform stride a. The information fetched for the instruction at address A is stored in either spatial cache
30
or temporal cache
31
according to the value of stride a. Accordingly, an entry in prediction table
32
corresponds to an instruction and indicates the instruction's address and selects a cache
30
or
31
when the instruction requires data from memory device
34
. In particular, searching prediction table
32
by instruction address locates the entry that indicates either cache
30
or
31
. The address of the information that the instruction accessed can be stored in the another address field of the entry. A difference between the address of currently accessed data and the address of previously accessed data by the instruction is stored in a stride field of the entry in prediction table
32
. For example, when a uniform stride separates three accessed addresses such as B, B+&agr;, and B+2&agr;, it is possible to predict whether spatial cache
30
or temporal cache
31
is more efficient for future accesses by the instruction. Thus, storing the information in spatial cache
30
or temporal cache
31
according to the type
However, the cache memory system of
FIG. 3
has many accesses that do not have the uniform stride, and the stride of the addresses accessed by the same instruction may change. Accordingly, improving the performance of the cache system of
FIG. 3
is difficult when instructions do not have uniform strides for data accesses.
SUMMARY OF THE INVENTION
To solve the above problem, a method for managing a cache memory selectively determines the amount of information fetched during a cache miss accord

Affiliated with

Also associated with

Rating

Cache memory system and method for managing the same 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 memory system and method for managing the same, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache memory system and method for managing the same will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3016325