Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-03-22
2002-09-03
Robertson, David L. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S118000
Reexamination Certificate
active
06446168
ABSTRACT:
FIELD OF THE INVENTION
The invention is related to cache memory and, in particular, to a method and apparatus for dynamically switching a cache memory from direct-mapped to set associativity.
BACKGROUND OF THE INVENTION
Generally, a microprocessor operates much faster than main memory can supply data to the microprocessor. Therefore, many computer systems temporarily store recently and frequently used data in smaller, but much faster cache memory. Cache memory may reside directly on the microprocessor chip (Level 1, or L1, cache) or may be external to the microprocessor (Level 2, or L2, cache).
Referring to
FIG. 1
, a typical computer system includes a microprocessor (
10
) having, among other things, a CPU (
12
), a load/store unit (
14
), and an on-board cache memory (
16
). The microprocessor (
10
) is connected to a main memory (
18
) that holds data and program instructions to be executed by the microprocessor (
10
). Internally, the execution of program instructions is carried out by the CPU (
12
). Data needed by the CPU (
12
) to carry out an instruction are fetched by the load/store unit
14
. Upon command from the CPU (
12
), the load/store unit (
14
) searches for the data first in the cache memory (
16
), then in the main memory (
18
). Finding the data in the cache memory is referred to as a “hit.” Not finding the data in the cache memory is referred to as a “miss.”
The hit rate depends, in no small part, on the caching scheme or policy employed by the computer system, e.g., direct-mapped, or set associative. Generally, a set associative caching policy provides a higher hit rate than a direct-mapped policy. However, for some computer applications, a direct-mapped policy may provide better system performance due to a better hit rate. This depends on the address sequences used by the application, the allocation of memory pages to an application by the operating system, and whether virtual or physical addresses are used for addressing the cache.
An example of a direct-mapped cache memory is functionally depicted in FIG.
2
A. In this example, a portion of the main memory (
18
) is stored or cached in a cache memory (
20
) having a tag part (
22
) and a data part (
24
). The tag part (
22
) and the data part (
24
) may be a single cache memory logically partitioned into two parts, or two actual, physical cache memories. In general, the tag part (
22
) stores the physical addresses of the locations in main memory being cached, and the data part (
24
) stores the data residing in those locations. Both the tag part (
22
) and the data part (
24
) share a common index that is used to reference the two parts.
In operation, the CPU requests data by issuing to the load/store unit an address which includes an index component and a tag component. The load/store unit then goes to the tag part (
22
) of the cache (
20
) and checks the specified index to see if that particular tag entry matches the specified tag. If yes, a hit has occurred, and the data corresponding to the specified index is retrieved and provided to the CPU. If no, then the requested data has to be obtained from main memory. For example, an address having an index component of ‘0’ and a tag component of ‘32’ will result in a hit, and data ‘A’ will be retrieved and sent to the CPU. However, there can only be one tag entry per index number and, therefore, a subsequent index component of ‘0’ and a tag component of ‘24’ will result in a miss. A set associative policy generally has a higher hit rate per access, as will be explained below.
An example of a set associative cache is functionally depicted in FIG.
2
B. As in the previous example, a cache memory (
26
) is partitioned into a tag part (
28
) and a data part (
30
), with both parts sharing a common index. However, instead of a single entry per index, the tag part (
28
) and the data part (
30
) each have four entries, best shown here as rows and columns. A row of entries is called a “set” so that there are as many sets as there are index numbers, and a column of entries is called a “way” so that there are four ways for each index number. This particular cache policy, therefore, is commonly referred to as 4-way set associative. Those skilled in the art will appreciate that the set associative policy is commonly, but not limited to, 2-way to 8-way. Herein, examples are presented for 4-way set associativity, but the concepts are equally applicable to n-way set associativity.
In operation, when the load/store unit goes to search the tag part (
28
) at the specified index number, all four ways are compared to the specified tag component. If one of the four ways matches (a hit occurs), the corresponding way of the corresponding set in the data part (
30
) is sent to the CPU. Thus, in the previous example, a virtual address having an index component of ‘0’ and tag component of ‘24’ will be a hit because there are four tag entries per index number. If the first tag entry does not match, there are three more chances to find a match per access. Thus, effectively, the 4-way set associative policy allows the CPU to find cached data one of four ways.
As mentioned previously, cache memory may contain data already residing in main memory or new data generated by the microprocessor to be written later to main memory. Stale or outdated data are “flushed” from cache memory because of the need to replace a data block due to a miss or move all entries of a page back to main memory.
One method of flushing is by displacing the stale data with fresh data. Typically, a displacement flush is done for an entire “page” or group of index numbers with all data corresponding to the index numbers being replaced. This works fine for the direct-mapped cache where there is one-to-one correspondence between index number and tag entry. However, for a set associative cache where there are multiple tag entries per index number, replacement of a block of data is determined by the replacement policy.
SUMMARY OF THE INVENTION
In general, in one aspect, the present invention is a system for dynamically switching between mapping schemes for cache. The system comprises a microprocessor; a first mapping scheme; a second mapping scheme; and switching circuitry for switching between the first mapping scheme and the second mapping scheme, wherein the microprocessor is in communication with the cache through the switching circuitry and stores information within the cache using one of the first mapping scheme and second mapping scheme.
In accordance with one or more embodiments, the system may further comprise monitoring circuitry for determining whether one of instructions and load/store operations is using the cache, wherein the switching circuitry switches between the first mapping scheme and the second mapping scheme based on which one of instructions and load/store operations is using the cache. The system may further comprise monitoring circuitry for determining whether one of instructions and load/store operations is currently using the cache; and determining whether a mapping scheme switch has been requested for one of instructions and load/store operations, wherein the switching circuitry switches between the first mapping scheme and the second mapping scheme upon request if the one of instructions and load/store operations for which a mapping scheme switch is requested is not currently using the cache.
The system may further comprise an instruction unit in the cache; monitoring circuitry for determining whether instructions are currently using the instruction unit in the cache; and determining whether an instruction mapping scheme switch has been requested, wherein the switching circuitry switches between the first mapping scheme and the second mapping scheme for instructions upon request if the instructions are not currently using the instruction unit in the cache. The system may further comprise a load/store unit in the cache; monitoring circuitry for determining whether load/store operations are currently using the load/store unit in the cache; and determining whether a load/store operation m
Normoyle Kevin
Petrick Bruce E.
Robertson David L.
Rosenthal & Osha L.L.P.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for dynamically switching a cache... 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 dynamically switching a cache..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for dynamically switching a cache... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2888397