Storing data in memory

Details Storing data in memory Storing data in memory

2002-02-12

2004-08-24

Sparks, Donald (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S144000, C711S145000

Reexamination Certificate

active

06782453

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to computer memory, and more particularly to a scheme for storing data in the memory.
BACKGROUND OF THE INVENTION
It is generally known that computers have significantly changed since they were first developed. For example, during the early development of the computer, the processor and the memory typically operated at the same speed, more or less. Due to the fact that both the memory and the processor operated at approximately the same speed, the processor did not generally have to wait for the memory to supply it data.
Since this time, the speed of every component (e.g., processor, memory, etc.) of the computer has increased. However, processor speeds have increased relatively faster than memory speeds. This disparity in speed growth has resulted in processors that run significantly faster than the memory. Thus, it is a goal in modem system design, to expediently provide the processor with data for reducing processor waiting time and minimize the wasting of processing cycles. One method of reducing processor latency is to utilize a relatively high speed memory (e.g., static random access memory “SRAM”). However, the cost of a sufficient amount of SRAM to provide data storage for current computer applications (e.g., 64 mega bytes “MB”) makes this method prohibitive. A second method of reducing processor latency is to place memory in close proximity to the processor or on the same chip as the processor. However, the physical dimensions of the chip limit the amount of memory that can be placed on or around the chip.
In this regard, current computers generally utilize a comparatively small “cache” (e.g., 256 kilo bytes “KB”, 1 MB and the like) of relatively fast memory located on or near the chip with the processor and a comparatively large amount of system or remote memory. The remote memory is a relatively slower and less expensive memory (e.g., dynamic random access memory “DRAM” and the like) located in a remote location (e.g., somewhere on the motherboard, on a daughter board, etc.). Additionally, the cache is typically represented as two or more levels of cache. For example a level 1 (“L1”) cache or caches is typically smaller, faster and in closer proximity to the processor than a level 2 (“L2”) cache.
The L1 or primary cache is typically the fastest memory available to the processor. It is in fact, built directly into the processor itself and runs at the same speed as the processor in most cases. While fast, the L1 cache is very small, generally from 8 KB to 64 KB. If the processor requests information and can find it in the L1 cache, that is the best case, because the information is there immediately and the system does not have to wait.
The L2 cache is a secondary cache to the L1 cache, and is larger and slower as compared to the L1 cache. In general, the L2 cache is utilized to store data recently accessed by the processor that is not stored in the L1 cache. The size of the L2 cache is typically in the range of 64 KB to 4 MB. Due to the fact that the L1 and the L2 cache are built into or are in relatively close proximity to the processor, the combined memory resources of the L1 and the L2 cache are often referred to as the “local memory”.
In general, data flows between the various levels of cache in the following manner. The processor requests a piece of information. The first place the processor looks for the information is in the L1 cache. If the information is found in the L1 cache (called an “L1 hit”), the information may be utilized by the processor with no performance delay. If the information is not found in the L1, the L2 cache is searched. If the information is found in the L2 cache (called an “L2 hit”), the information may be utilized by the processor with relatively little delay. Otherwise, the processor must issue a request to read the information from the remote memory. The remote memory may in turn either have the information available or have to get it from the still slower hard disk or CD-ROM. A caching algorithm is utilized to migrate data required by the processor between the various levels of the cache and also to migrate data between the cache and the remote or “main” memory.
Due to the fact that getting information to the processor has become a limiting factor in computer performance, designing more efficient caching algorithms has become extremely important in improving overall computer performance. Specifically, the hit ratio and the search speed must be maximized to improve the cache performance. The hit ratio is a measure of the likelihood of the cache containing the memory addresses that the processor requires. The search speed is a measure of how quickly it is determined if a hit in the cache has occurred. In this regard, there is a critical tradeoff in cache performance that has led to the creation of a multitude of caching algorithms.
FIG. 4
illustrates a conventional direct mapping caching scheme
400
of one such conventional caching algorithm. The caching scheme
400
illustrated in
FIG. 4
depicts the flow of data during a particular data operation. Specifically, the data operation is the replacement of a relatively low priority data with a relatively high priority data. In the caching scheme
400
, the processor (not shown) requires a line
405
. The processor references a local memory
410
to determine whether the line
405
is present (i.e., a “tag match”) or not present (i.e., a “tag mismatch”).
In the caching scheme
400
, each line in the local memory
410
is associated with an address
415
. Included within the address
415
is a “tag”
420
utilized to associate the line in the local memory
410
to a corresponding line in a remote memory
425
. The “tag” portion
420
of the address
415
is stored with the cache line, while the remaining portion of the address can be derived implicitly by the line's physical location within the cache. In the example shown, it has been determined that the line
405
is not present in the local memory
410
. Thus, the processor must issue a request to retrieve the line
405
from the remote memory
425
.
Utilizing the caching scheme
400
, a victim line
430
is located within the local memory
410
and replaced with the line
405
. In a direct mapped scheme such as that described here, the selection of a victim line is precisely determined by the non-tag portion of its address. In a more general scheme, however, victim lines would be selected based on how likely it is that the line will be utilized by the processor. Typically, the longer the time interval since the line has been utilized, the more likely the line will be chosen as the victim. Prior to replacing the line
430
with the line
405
, it is determined if the line
430
contains new information. In this regard, a “dirty” bit
435
is utilized to indicate that the line has been altered since it was retrieved from remote memory
425
. Thus, if the dirty bit
435
of the line
430
is turned on, the line
430
most be written back to the corresponding location in the remote memory
425
in order to avoid losing the new information stored to the line
430
.
While the conventional caching scheme
400
has the advantage of being relatively simple and having a relatively fast search speed, the caching scheme
400
suffers a number of disadvantages. For example, read and write requests are processed individually rather than as a batch or “burst” process. A second disadvantage of the caching scheme
400
is the overhead caused by the address tag
420
. For example, in a 64-bit processor, a 4 MB direct mapped cache of 32 byte lines may have an address tag of 42 bits for every 32 byte line. This equates to 16.4 percent memory usage for address tags.
In an effort to improve upon conventional direct mapping scheme for relatively large L2 memories, a demand paging caching scheme was developed. In the demand paging scheme, a plurality of lines are moved into the cache rather than individual lines in the direct mapping scheme. The plurality of lines are collectively described by thos

Affiliated with

Also associated with

Rating

Storing data in memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3317322