Cache memory system and method for managing streaming-data

Details Cache memory system and method for managing streaming-data Cache memory system and method for managing streaming-data

2000-09-29

2003-06-10

Verbrugge, Kevin (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

Reexamination Certificate

active

06578111

ABSTRACT:

FIELD
The present invention relates generally to memory systems, and more particularly to cache memory systems and a method of operating the same that provides efficient handling of streaming-data.
BACKGROUND
Modem computer systems generally include a central processing unit (CPU) or processor for processing data and a memory system for storing operating instructions and data. Typically, the speed at which the processor is able to decode and execute instructions to process data exceeds the speed at which instructions and data is transferred between the memory system and the processor. Thus, the processor is often forced to wait for the memory system to respond. One way of reducing this memory latency period is to organize computer memory into a memory hierarchy. A memory hierarchy consists of multiple levels of memory each using different devices for storing data and each having different speeds, capacities and cost associated therewith. Generally, the highest-level of memory, commonly known as a cache, is coupled closely to the processor and uses relatively expensive, faster devices that make information, either data or instructions, available to the processor in a shorter period of time. The lower-levels typically include a main-memory and mass-data-storage devices that albeit larger are slower and are therefore correspondingly cheaper.
Use of a cache reduces the memory latency period by temporarily storing a small subset of data from lower-levels of the memory system. When the processor needs information for an application, it first checks the high-speed cache. If the information is found in the cache (known as a cache-hit), the information will be retrieved from the cache and execution of the application will resume. If the information is not found in the cache (known as a cache-miss) then the processor will proceed to access the slower, lower-level memories. Information accessed in the lower-level memories is simultaneously stored or written in the cache so that should the information be required again in the future it is obtained directly from the cache, thereby reducing or eliminating any memory latency period.
Similarly, use of a cache can reduce the memory latency period during a write operation by writing to the cache. This reduces the memory latency period in two ways. First, by enabling the processor to write at the much greater speed of the cache, and second by storing or loading the information in the cache so that, again, should the processor need the information in the future it is obtained directly from the cache.
There are three primary types of technology used in memories today. The main-memory is typically implemented using slower, cheaper dynamic random access memory (DRAM) devices. The cache is implemented using faster random access memory devices, such as static random access memory devices (SRAMs) so that accessing a cache takes much less time to complete than to access main-memory. SRAMs typically require greater number of devices per bit of information stored, and thus are more expensive than DRAM. In order to further reduce the memory latency period the cache may be located on the same chip as the CPU. The proximity of the cache to the CPU increases the speed with which the CPU can access the cache by eliminating delays due to transmission over external circuits. A cache located on the same chip as the CPU is often known as primary or level 1 (L1) cache since the memory system typically includes a larger, slower level 2 (L2) cache outside the CPU chip. Some memory systems include additional caches, for example a level (L3) or victim cache for temporarily storing data displaced from the L2 cache.
As the name implies, at the lowest-level in memory, mass-storage-devices provide the largest data storage capacity and typically use the slowest and therefore cheapest technology. For example, magnetic, optical or magnetic-optical technologies to store large amounts of instructions and data on tapes, or fixed or removable disks.
Referring to
FIG. 1
, cache
10
is divided logically into two main components or functional units. Data-store
15
, where the cached information is actually stored, and tag-field
20
, a small area of memory used by the cache to keep track of the location in the memory where the associated data can be found. The data-store is structured or organized as a number of cache-lines
25
or sets of cache-lines each having a tag-field
20
associated therewith, and each capable of storing multiple blocks or bytes of data. Typically, in modern computers each cache-line
25
stores 32 or 64 bytes of data. The tag-field
20
for each cache-line
25
or set of cache-lines includes an index
30
that uniquely identifies each cache-line in the cache
10
, and tag
35
that is used in combination with the index to identify an address in lower-level memory
40
from which data-stored in the cache-line has been read from or written to. Often the index
30
is not stored in the cache
10
but is implicit, with the address of the cache-line
25
itself providing the index. Typically, the tag-field
20
for each cache-line
25
also includes one or more bits, commonly known as a validity-bit
45
, to indicate whether the cache-line contains valid data. In addition, the tag-field
20
may contain other bits (not shown) for example for indicating whether data at the location is dirty, that is has been modified but not written back to lower-level memory
40
.
To speed up memory access operations, caches rely on principles of temporal and spacial-locality. These principles of locality are based on the assumption that, in general, a computer program accesses only a relatively small portion of the information available in computer memory in a given period of time. In particular, temporal locality holds that if some information is accessed once, it is likely to be accessed again soon, and spatial locality holds that if one memory location is accessed then other nearby memory locations are also likely to be accessed. Thus, in order to exploit temporal-locality, caches temporarily store information from a lower-level memory the first time it is accessed so that if it is accessed again soon it need not be retrieved from the lower-level memory. To exploit spatial-locality, caches transfer several blocks of data from contiguous addresses in lower-level memory, besides the requested block of data, each time data is written in the cache from lower-level memory.
The most important characteristics of a cache are its hit rate, that is the fraction of all memory accesses that are satisfied from the cache over a given period of time, and its access time, that is the time it takes to read from or write to the cache. These in turn depend in large part on how the cache is mapped to addresses in the lower-level memory. The choice of mapping technique is so critical to the design of the cache that the cache is often named after this choice. There are generally three different ways to map the cache to the addresses in memory.
Direct-mapping, shown in
FIG. 1
, is the simplest way to map a cache to addresses in main-memory. In the direct-mapping method the number of cache-lines is determined, the addresses in memory divided into the same number of groups of addresses, and addresses in each group associated with one cache-line. For example, for a cache having 2
n
cache-lines, the addresses are divided into 2
n
groups and each address in a group associated with a single cache-line. The lowest n address bits of an address corresponds to the index of the cache-line to which data from the address is stored. The remaining top address bits are stored as a tag that identifies from which of the several possible addresses in the group the data originated. For example, to map a 64 megabyte (MB) main-memory to a 512 kilobyte (KB) direct mapped cache having 16,384 cache-lines, each cache-line is shared by a group of 4,096 addresses in main-memory. To address 64-MB of memory requires 26 address bits since 64-MB is 226 bytes. The lowest five of these address bits, A
0
to A
4
, are ignored

Affiliated with

Also associated with

Rating

Cache memory system and method for managing streaming-data 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 streaming-data, 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 streaming-data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3096421