Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2002-05-08
2004-08-03
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S154000, C711S159000, C711S163000, C711S129000, C711S133000
Reexamination Certificate
active
06772299
ABSTRACT:
BACKGROUND OF INVENTION
In a computer system, the central processing unit (CPU) processes information that is stored in a main memory (RAM or DRAM) within the computer. Typically, the CPU processes the information faster than the information can be accessed and transferred from the main memory to the CPU. As a result, when the CPU requests the information from the main memory, the CPU may remain idle for a substantial time while waiting for the information.
To reduce the amount of time the CPU remains idle, a fast but typically expensive type of memory is used as a cache. The cache is an intermediary storage area between the CPU and the main memory in order to store recently or frequently used information. Access times for the cache are typically substantially faster than access times for the main memory. However, the cache is substantially more costly than the main memory. Therefore, for cost effectiveness, the cache is often utilized in smaller sizes, relative to the less costly main memory.
FIG. 1
illustrates a generic cache mechanism in a computer, including a CPU (
10
), a main memory (
12
), a cache (
14
), and a data bus (
16
). The data bus (
16
) provides a means for transferring information between the main memory (
12
) and the CPU (
10
). As noted earlier, it is desirable for the CPU (
10
) to access the information as fast as possible. Therefore, when a piece of information is requested by the CPU (
10
), the cache (
14
) is searched for the piece of information first. If the piece of information is stored in the cache (
14
), then the piece information is quickly provided to the CPU (
10
). Otherwise, the piece of information is retrieved from the (relatively slower) main memory (
12
) and provided to the CPU (
10
). Also, the piece of information is stored in the cache (
14
), so that next time the piece of information is requested, the piece of information can be accessed quickly from the cache (
14
).
The granularity of storage in a cache is called a line. A cache line is a collection of bytes, generally at sequential memory locations, which are stored as a unit in the cache. Transfers between a main memory and the cache are usually accomplished via cache line granularity (i.e., one or more cache lines at a time).
When information requested is not found in the cache, a “cache miss” occurs. Conversely, if the information is found, there is a “cache hit.” Due to the limited size of the cache, information stored in the cache may need to be replaced or swapped out, in order to make room for newly requested information that is not stored in the cache. Various cache mechanisms have been developed with an objective to maximize caching efficiency using methods or cache architectures that result in a low volume of cache misses and/or cache swaps.
Two currently used cache mechanisms are an associative cache, and a direct-mapped cache. The direct-mapped cache is effective and relatively inexpensive, in comparison to the associative cache. Sometimes, one or more locations in cache memory (i.e., cache lines) may be “locked,” in order to avoid a set of information from being swapped out. A traditional direct-mapped cache mechanism may become less effective when used in a locking scenario because a locked cache line prohibits a portion of memory from being present in the cache. Some associative caches, however, can more effectively operate in a locking scenario, due to a more complex design. Therefore, when locking is required in a design architecture, a more complex and expensive associative cache mechanism may be preferred. Due to a relatively simple design, a direct-mapped cache can often be economically developed and manufactured.
An associative cache includes a number of information storage locations called cache lines. In addition to information retrieved from the main memory, each cache line of an associative cache typically includes a tag bit that indicates whether a particular cache line contains any information at all.
FIG. 2
, for example, illustrates an associative cache (
15
), having cache line (
30
A) through cache line (
30
Z) that correspond to the main memory (
12
), including multiple memory blocks (
38
A) through (
38
Z). Each memory block represents a unique main memory address. Each cache line can reference one or more memory addresses, depending on cache design.
Typically, when a computer is reset, each tag bit in a cache is set to 0, for example, to indicate that no cache lines are in use. Each time the CPU (
10
) makes a memory request, one or more cache lines is filled with data, and tag bits for the cache lines that are filled with data are changed to 1, for example, to indicate that the cache lines are in use. For example, referring to
FIG. 2
, if the CPU (
10
) makes a request for information stored at memory block (
38
A) in the main memory (
12
), a search is performed to determine whether any used cache lines in the associative cache (
15
) include the information requested by the CPU (
10
). Failing to find the information, a bus request is issued to fetch the information stored in memory block (
38
A) from the main memory (
12
), and store the information in an unused cache line in the associative cache (
15
). In the associative cache (
15
), cache lines may be filled in random order.
If information stored in the memory block (
38
A) is needed later, the information is quickly fetched from the associative cache (
15
), eliminating the need for a bus operation across the data bus (
16
) to fetch the information from the (relatively slower) main memory (
12
). Eventually, more cache lines are filled with data from the main memory (
12
), as the CPU (
10
) continues to request retrieval of additional information. If information needed by the CPU (
10
) appears in the associative cache (
15
), the CPU (
10
) can access the information from the associative cache (
15
) quickly, without making any memory references.
However, when the associative cache (
15
) is full, a previous cache entry i.e., information stored in a used cache line) is discarded to make room for a new entry from the main memory (
12
). In order to avoid performing a linear search on cache lines, an associative cache has special hardware that can search each cache line simultaneously for requested information. However, the special hardware makes the associative cache relatively costly.
A direct-mapped cache is a relatively less costly alternative to the associative cache, in that the direct-mapped cache avoids use of special hardware, by storing information in a cache line that is directly associated with a memory block from which the information is retrieved. For example, referring to the associative cache (
15
) illustrated in
FIG. 2
, the cache line (
30
) may be directly associated with the memory block (
38
). Accordingly, if the CPU (
10
) requests information stored at the memory block (
38
), the information can be retrieved directly from the cache line (
30
) associated with the memory block (
38
).
Alternatively, more than one memory block may be associated with (i.e., mapped to) a cache line. For example, if the main memory includes a 4×4 memory block pattern for a total of 16 memory blocks, a cache with four cache lines may suffice to directly map a group of four memory blocks into each cache line. Direct-mapped caching has a one-to-one association between groups of memory blocks and cache lines. Even though a cache line may be associated with more than one memory block, the cache line can only store information retained in one memory block at a time. Thus, when multiple memory blocks map onto a particular cache line, determining which memory block is currently occupying the particular cache line is impossible. Thus, each cache line also includes a tag field that can be used to identify the particular memory block currently stored in the cache line. The tag field can be represented by a binary number, for example.
FIG. 3
illustrates a direct-mapped cache (
17
) associated with a main memory (
12
). Memory block (
38
A) through memory block (
38
D) are ma
Cohen Earl T.
McWilliams Thomas M.
Elmore Stephen
Kim Matthew
Osha & May L.L.P.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for caching with variable size locking... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for caching with variable size locking..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for caching with variable size locking... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3304529