 |
Description  |
|
|
FIELD OF THE INVENTION
The present invention relates to the field of data storage, and more particularly to a method and apparatus for storing data in a cache memory.
BACKGROUND OF THE INVENTION
Cache memories are relatively small, high-speed memories used to reduce memory access time. Cache memories exploit two characteristics of memory access to reduce access time: temporal locality, the tendency of computer programs to repeatedly
access the same memory locations; and spatial locality, the tendency of computer programs to access memory locations that are close to one another.
In order to exploit temporal and spatial locality, data from frequently accessed regions of system memory are stored in cache memory. That way, subsequent accesses to the cached memory regions will not incur the full system memory access time,
but the shorter cache access time instead. A memory transaction that accesses cache memory instead of main memory is called a cache hit, and the cache "hit-rate" is a fundamental metric of cache operation.
Several techniques have been employed to increase cache hit-rates. For example, to further exploit spatial locality, caches have been designed with increasingly larger row sizes. The size of a cache row (also called a cache line) defines the
quantum of data stored in a cache memory after a cache miss. As the row size increases, it becomes more likely that subsequent memory accesses will address data in the row, thus improving the cache hit-rate.
Temporal locality is exploited to improve cache hit-rate by providing multiple storage elements that are addressed by the same cache index. The storage elements are commonly referred to as "ways" and a cache memory that has multiple ways is
called a "multiple-way, set-associative cache". The idea behind multiple-way cache memories is to allow more than one system memory address to correspond to each cache index. Because the cache index is a sub-field of the overall system memory address,
multiple-way design avoids repeated cache misses that occur in single-way designs when different addresses having the same cache index are accessed in succession. In single-way or "direct-mapped" cache designs, successive accesses at memory locations
having the same cache index result in a sequence of cache miss/cache update operations. This phenomenon is referred to as "thrashing" because data is rapidly swapped into and out of the cache, and much of the benefit of the cache memory is lost.
Despite the advantages of multiple-way, set-associative cache memories, a significant amount of thrashing still occurs when the processor switches between tasks or functions that have dislocated code and data spaces. For example, if, while
executing a first task having program code located within a given region of system memory, the processor switches to a second task having program code located within a different region of system memory, it is likely that program code for the first task
will be swapped out of the cache in favor of program code for the second task. Consequently, as the processor continues to switch between the first and second tasks, significant number of cache misses occur, thus lowering the average cache hit-rate.
Similarly, when a single task alternately processes data stored in two different regions in memory (e.g., an audio data store and a video data store in a multi-media application), cache thrashing tends to occur as the task alternates between
processing the two different data stores.
SUMMARY OF THE INVENTION
A method and apparatus for compartmentalizing a cache memory are disclosed. A cache memory having a plurality of storage compartments receives one or more cache compartment signals at one or more inputs. The cache compartment signals are from a
source external to the cache memory. Based on the one or more cache compartment signals, cache compartment logic selects one of the plurality of storage compartments to store data after a cache miss.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings in which like references indicate similar elements and in which:
FIG. 1 is a diagram of a cache memory.
FIG. 2 is a diagram of Least-Recently-Used (LRU) logic.
FIG. 3 is a logic table describing the operation of way update logic.
FIG. 4 is a table of instructions that can be used to generate compartment control signals.
FIG. 5A is a diagram of a cache organization.
FIG. 5B is a diagram of a cache organization.
FIG. 5C is a diagram of a cache organization.
FIG. 5D is a diagram of a cache organization.
FIG. 6 is a diagram of Least-Recently-Used logic.
FIG. 7 is a logic table describing the operation of way update logic.
FIG. 8 is a table of instructions that can be used to generate compartment control signals.
FIG. 9 is a flow diagram of a computer program in which cache compartmentalization can be used to improve the cache hit-rate.
FIG. 10 is a flow diagram illustrating one technique for using cache compartment control .
FIG. 11 is a flow diagram of task switching logic.
FIG. 12 illustrates a task structure.
FIG. 13 is a flow diagram of a service for registering a cache compartment mode in a database.
FIG. 14 is a diagram of a cache memory having alternate way banks.
DETAILED DESCRIPTION
The hit-rate of a cache memory is improved in the present invention by compartmentalizing the cache memory under software control. According to one embodiment, special no-operation (NOP) instructions available in existing microprocessors are
used to cause compartment control signals to be sent to a cache memory. The compartment control signals are used by cache logic to determine which way of a multiple-way cache should be updated in response to a cache miss. By issuing a NOP instruction
that selects a particular way, or group of ways, to be updated in response to a cache miss, a task effectively selects a compartment of the cache in which data and code for that task is to be stored. By coding different tasks (processes or threads) to
select different cache compartments, thrashing caused by task switching can be reduced so that a higher cache hit-rate is achieved. Similarly, tasks which must alternately access data located in different regions of system memory can be coded to select
respective cache compartments for each region of data to be processed. This technique further reduces thrashing so that a higher cache hit-rate is achieved.
FIG. 1 is a block diagram of a cache memory 5 according to one embodiment of the present invention. The cache memory 5 is a four-way, set-associative cache memory and includes four data ways 12 for storing data, four tag ways 11 for storing
address tags, comparators 14, way select logic 9, multiplexer 13, logic gates 16 and 17 and least-recently-used (LRU) logic 7. The four data ways 12 constitute the data storage of the cache memory and the four tag ways 11 constitute the tag memory of
the cache memory 5.
As shown in FIG. 1, the cache memory 5 is coupled to an M-bit data path 6 and an N-bit address path 8. The cache memory is also coupled to a control path 3 that supplies one or more compartment control signals 19, a read/write signal (RD/WE*) 18
indicating whether a read or write is requested, and an output conductor to transmit a hit/miss signal (HIT/M*) 20 from the cache memory 5 to an access-requesting device. Other control inputs and outputs may also be provided on control path 3. Also, in
alternate designs, the hit/miss signal 20 or the one or more compartment control signals 19 may be transmitted by conductors that are not included in control path 3.
The data path 6, address path 8 and control path 3 are typically part of a system bus that intercouples the cache memory 5 with a microprocessor, a system memory and various other processor-addressable components. Alternatively, the data path 6,
address path 8 and control path 3 may be part of a more limited bus such as a bus dedicated between the cache memory 5 and a processor.
Each address asserted on the address path 8 is an N-bit wide signal that includes a tag, an index and a word-select field. The most significant bits of the address constitute the tag, the next most significant bits of the address constitute the
index and the least significant bits of the address constitute the word-select field.
For each new address received on the address path, the index and word-select portions of the address are asserted to address the data ways 12. The index selects a full cache row within each of the data ways 12 and the word-select bits select a
word within the selected cache row. The selected word in each data way 12 is output to a respective input of the multiplexer 13.
The index portion of each new address received on the address path 8 is also asserted to address the tag ways 11. The index selects one previously stored tag from each tag way 11. The selected tags are output by the tag ways 11 to respective
comparators 14 where they are compared to the tag portion of the address supplied on the address path 8. Each of the comparators 14 outputs a binary signal to the way select logic 9 indicating whether the previously stored tag matches the tag portion of
the address on the address path 8. Because tags are stored in a tag way 11 only if there is a miss, the same tag is not stored in more than one tag way 11 for a given index. Consequently, at most one of the four comparators 14 will assert a signal
indicating a tag match for any new address received on the address path 8.
If none of the four comparators 14 indicates a tag match, the way select logic 9 will output a miss signal (e.g., a logic low level HIT/M* signal) to indicate the tag miss. The miss signal is output by the cache memory 5 to the processor or bus
controller via hit/miss signal conductor 20 to indicate that system memory must be accessed. The miss signal is also supplied to the LRU logic 7 to enable the LRU logic 7 to select one of the four tag ways 11 to be updated with the missed tag and to
select a corresponding one of the four data ways 12 to receive data corresponding to the missed address. Also, the miss signal is supplied to an input of a logic gate 16 which outputs a signal to the tri-state buffer 17 to decouple the output of the
multiplexer 13 from the data path 6. This avoids contention on the data path 6 between data read from system memory and data output by the multiplexer 13.
If one of the four comparators 14 indicates a tag match, the way select logic 9 outputs a way select signal indicating which tag way 11 contains the matching tag. The way select signal is supplied to the input of the multiplexer 13 to select the
output of the data way 12 corresponding to the tag way 11 that contains the matching tag. The way select logic 9 also outputs the hit signal (e.g., a logic high level HIT/M* signal) on hit/miss conductor 20 to indicate to the processor or bus controller
that the cache memory 5 contains the value corresponding to the accessed memory address. The hit signal is also asserted to the logic gate 16 which, if a read operation is indicated by read write signal 18 (i.e., a logic high level RD/WE* signal),
outputs a signal to cause the tri-state buffer 17 to couple the output of the multiplexer 13 to the data path 6. This enables a value from the selected data way 12 onto the data path 6 where it can be received in the requesting device.
If the read/write signal 18 indicates a data write operation (i.e., alogic low level RD/WE* signal), the output of the multiplexer 13 is decoupled from the data path 6 by the tri-state buffer 17. Assuming a cache hit, the way select signal is
then used to select the data way 12 to be updated with new data and the tag way 11 to be updated with the corresponding tag. Additional logic (not shown in FIG. 1) is provided for this purpose.
As shown in FIG. 1, the index portion of each new address is also received in the LRU logic 7. In the event that a cache miss occurs, the LRU logic 7 determines the data way 12 least recently accessed at the given index. This way is referred to
as the "least recently used" way. The LRU logic 7 then outputs a multiple-bit way-update signal to select one of the four data ways 12 and a corresponding one of the four tag ways 11 to be written with updated information. According to one embodiment
of the present invention, the LRU logic 7 also receives the one or more compartment control signals 19 which affect the selection of the data and tag ways to be updated.
FIG. 2 is a block diagram of the LRU logic 7 of FIG. 1 according to one embodiment of the present invention. As described above, the LRU logic 7 receives cache hit/miss signal (HIT/M*) and the index portion of an address. The index is suppled
to an LRU memory 21 that contains a data value, referred to herein as a "LRU code", indicating the least recently used one of the data ways (e.g., element 12 of FIG. 1).
In one type of LRU logic design, called a "pseudo LRU", the LRU code is made up of a number of bits (k) equal to the number of data ways in the cache memory. Each bit position in the LRU code corresponds to one of the data ways of the cache
memory and one bit in each LRU code is set to a state different than all of the other bits to indicate that the indicated data way and its corresponding tag way should be used to receive new data and tag bits, respectively, after a cache miss. The LRU
code is then updated to indicate that another one of the ways should be used when the next miss occurs.
One disadvantage of the pseudo LRU technique is that the LRU code does not indicate the order of all of the ways from most recently used to least recently used. Consequently, after a way indicated to be the least recently used way is updated
with new data, there is no indication of which of the remaining ways should become the new least recently used way. One of the remaining ways must be selected at random or according to predetermined logic.
A true LRU logic design avoids the above-described problem by providing an LRU memory containing enough bits per index to indicate a complete hierarchy of the ways from most recently used to least recently used. This information is then used
select the next least recently used way after every cache update. The present invention may be used in combination with any technique for selecting a way to update in response to a cache miss, including the pseudo and true LRU techniques. For the sake
of simplicity, however, a pseudo LRU scheme is assumed in the following description.
As shown in FIG. 2, the LRU code output by the LRU memory 23 and the hit/miss signal HIT/M* are input to LRU way update logic 23. The LRU way update logic 23 also receives compartment control signals (e.g., element 19 of FIG. 1) which, according
to one embodiment of the present invention, include a compartment enable signal CE and one or more (r) compartment select signals CS. As discussed further below, the compartment enable CE and compartment select CS signals are determined by software
execution so that computer programmers can specify compartments within the cache in which frequently accessed data and code is to be stored. This can significantly reduce cache thrashing that otherwise occurs when task switching takes place and when
programs access separately located code stores or data stores.
FIG. 3 depicts a logic table 27 that describes the logical operation of the LRU way update logic 23 of FIG. 2. The logic table 27 lists an exemplary set of inputs to the LRU way update logic, including a compartment enable signal CE, two
compartment select signals CS1 and CS0, and a LRU code having constituent signals LCode3, LCode2, LCode 1 and LCode0. The outputs listed in the logic table represent an exemplary set of outputs from the LRU way update logic, including way update signals
WU3, WU2, WU1 and WU0.
As indicated in the first four rows of the logic table 27, when the compartment enable signal CE is deasserted (as indicated by a "0"), the state of the compartment select signals CS1 and CS0 do not affect the state of outputs WU3-WU0.
Consequently, in the first four rows of the logic table 27, CS1 and CS0 are indicated to have state X, indicating that they may be in any state.
When the compartment enable signal CE is deasserted, outputs WU3-WU0 are determined by the LRU code. Thus, in the first row, when signal LCode0 is asserted (indicated by a "1" in the logic table 27), WU0 is asserted at the LRU logic output to
select data way 0 and tag way 0 to be updated. Similarly, as shown in the second, third and fourth rows of the table, assertion of LCode1, LCode2 and LCode3 results in WU1, WU2 and WU3, respectively, being asserted at the LRU logic output. In other
words, so long as the compartment enable signal CE is deasserted, whichever way is indicated by the LRU code to be the least recently used is selected to be updated in response to the cache miss. In the logic table 27, the bits of the LRU code have
arbitrarily been prioritized so that if more than one bit of the LRU code is set, LCode0 takes priority over LCode1 which takes priority over LCode2 which takes priority over LCode3. Other priority schemes could be used.
In the bottom four rows of the logic table, the compartment enable signal CE is asserted and the way to update is determined based on the compartment select signals CS1 and CS0. According to one embodiment of the present invention, a simple
binary code is used so that the value of the compartment select signals CS1 and CS0, taken together (i.e., 00=0, 01=1, 10=2, 11=3), indicates the way to update. Thus, for each different combination of compartment select signals CS1 and CS0 a different
way update output is asserted. Assertion of the compartment enable signal CE effectively overrides the least recently inputs LCode3-LCode0 so that the state of those inputs is indicated to be "X".
FIG. 4 is a table 28 of instructions that can be used to generate the compartment control signals discussed in reference to FIG. 2 and FIG. 3. According to one embodiment of the present invention, an instruction indicating a write operation to a
read-only register within a processor is used to implement compartment control. For example, register R0 is a read-only register within microprocessors from Intel Corporation. Ordinarily, attempting to write a value to register R0 has no effect on the
processor state and is considered a NOP instruction (i.e., no-operation). However, by providing logic within the microprocessor to detect an attempt to write to register R0 and then to output compartment control signals based on the operand being
written, it becomes possible to write program code that issues cache compartment control instructions in the modified microprocessor, but which has no effect in existing microprocessors. In other words, program code which includes the compartment
control instructions may be executed by microprocessors that do not support compartment control without adverse effect. It will be appreciated that, rather than use presently available instructions in the manner described above, new instructions could
also be added to an existing instruction set to provide cache compartment control.
Still referring to FIG. 4, the operation indicated by each instruction and the compartment control signals that result from execution of the instruction are shown. Referring to the first row of table 28, for example, instruction OUT R0, 0
indicates that the value 0 is to be transferred to register R0. As discussed above, because register R0 is a read-only register, the contents of register R0 are unaffected by this operation. However, in the modified processor architecture described
above, execution of this instruction causes the processor to assert a compartment enable signal (e.g., CE=1) and to assert compartment select signals (CS1=0, CS0=0) that select cache data way 0 to be the cache compartment. After a cache miss, data way 0
is selected to receive updated data and tag way 0 is selected to receive the missed tag.
According to one embodiment of the present invention, the operand attempted to be written to register R0 is used to indicate different compartment control modes. Thus, for each successive instructions listed in table 28, the value of the operand
to be written to register R0 is incremented. When the Out R0 instruction is executed with an operand of 1, the compartment enable signal is asserted and compartment select signals are output to enable way 1 to be the cache compartment; when the operand
is 2, the compartment enable signal is asserted and compartment select signals are output to select way 2 to be the cache compartment; when the operand is 3, the cache compartment enable signal is asserted and compartment select signals are output to
select way 3 to be the cache compartment; and when the operand is 04, the compartment enable signal is deasserted (CE=0) to disable cache compartmentalization and to allow the least recently used logic to determine which way to be updated after a cache
miss. Operands higher than 04 may default to one of the states described above (e.g., compartmentalization off) or may be reserved for expanded compartmentalization features.
Although in the above-described embodiment of the present invention the cache compartments are of equal size and correspond to respective cache ways, it may be desirable to have cache compartments of different sizes. For example, if a computer
programmer recognizes in advance that one task (or program operation) will require significantly more memory access than another task, the programmer may want to allocate a larger cache compartment to the more memory intensive task and a smaller cache
compartment to the less memory intensive task.
FIG. 5A, FIG. 5B, FIG. 5C and FIG. 5D illustrate different cache organizations that can be used to implement varied cache compartment sizes according to one embodiment of the present invention. The different cache organizations are referred to
as compartment patterns and are selected by compartment organization signals (CO). Referring to FIG. 5A, for example, with CO signals set to 0,0, a cache compartment organization is selected in which each of the ways of a four-way cache is allocated to
a respective cache compartment. As indicated in FIG. 5A, compartment select signals CS=00, 01, 10 and 11 select compartments 0, 1, 2 and 3, respectively. The compartment pattern depicted in FIG. 5A is referred to as compartment pattern 0 and is
equivalent to the four compartment scheme described above in reference to FIG. 2 and FIG. 3.
FIG. 5B illustrates compartment pattern 1, which is selected when cache organization signals CO are set to 0,1. In compartment pattern 1, way 0 is allocated to compartment 0, way 1 is allocated to compartment 1 and ways 2 and 3 are allocated to
compartment 2. As a result, three cache compartments are provided with one cache compartment being twice the size of either of the other two compartments. Compartment select signals CS=00, 01 and 10 select compartments 0, 1 and 2, respectively.
FIG. 5C illustrates compartment pattern 2, which is selected when cache organization signals are set to 1,0. In compartment pattern 2, way 0 is allocated to compartment 0 and ways 1, 2 and 3 are allocated to compartment 1. Thus, two cache
compartments are provided with one cache compartment being three times the size of the other. Compartment select signals CS=00, and 01 select compartments 0 and 1, respectively.
FIG. 5D illustrates compartment pattern 3, which is selected when cache organization signals are set to 1,1. In compartment pattern 3, two equally sized compartments are provided: compartment 0 to which ways 0 and 1 are allocated, and
compartment 1 to which ways 2 and 3 are allocated. Compartment select signals CS=00, and 01 select compartments 0 and 1, respectively.
It will be appreciated that the number of different compartment patterns that can be achieved increases with the number of ways in a multiple-way cache. Also, while a way-based allocation scheme has been described, any technique for allocating
memory within the cache to different cache compartments that can be selected under software control is within the spirit and scope of the present invention.
FIG. 6 is a diagram of LRU logic 31 that can be used to support the software-selectable compartment patterns shown in FIG. 5A, FIG. 5B, FIG. 5C and FIG. 5D. The LRU logic 31 is similar to the LRU logic 7 described in reference to FIG. 2, except
that, instead of receiving a compartment enable signal, the LRU logic 31 receives one or more (p) compartment organization signals (CO). The compartment organization signals are supplied to the LRU way update logic 33 and determine whether cache
compartmentalization is enabled and, if so, which cache compartment pattern to use (e.g., compartment pattern 0, 1, 2 or 3, described above).
FIG. 7 is a logic table 36 that describes the operation of the LRU way update logic 33 of FIG. 6. According to one embodiment of the present invention, the LRU way update logic receives two cache organization signals, CO1 and CO0, two
compartment select signals, CS1 and CS0, and four LRU code signals LCode3, LCode2, LCode1 and LCode0. If a cache miss occurs, the LRU way update logic asserts one of four way update outputs, WU3, WU2, WU1 or WU0, to enable a cache data way and its
corresponding cache tag way to be updated.
For rows 1-4 of the logic table, the cache organization signals CO1 and CO0 are both set to zero, thereby selecting compartment pattern 0. As discussed above, each of the four cache ways is allocated to a respective one of four compartments in
compartment pattern 0. Consequently, the compartment select signals CS1 and CS0 determine which way is updated after a cache miss. Thus: if CS1,CS0=0,0 compartment 0 is selected and way update signal WU 0 is asserted to enable way 0 to be updated; if
CS1,CS0=0,1 compartment 1 is selected and way update signal WU 1 is asserted to enable way 1 to be updated; if CS1,CS0=1,0 compartment 2 is selected and way update signal WU 2 is asserted to enable way 2 to be updated; and if CS1,CS0=1,1 compartment 3 is
selected and way update signal WU 3 is asserted to enable way 3 to be updated.
So long as compartment pattern 0 is selected (i.e., CO1, CO0=0,0), the LRU code (inputs LCode3-LCode0) has no effect on the way selected to be updated.
For rows 5-12 of the logic table, cache organization signals CO1 and CO0 are set to 0 and 1, respectively, thereby selecting compartment pattern 1. Referring to FIG. 5B, compartment pattern 1 contains three compartments, with way 0 being
allocated to compartment 0, way 1 being allocated to compartment 1, and ways 2 and 3 being allocated to compartment 2. Consequently: if CS1,CS0=0,0 compartment 0 is selected and way update signal WU 0 is asserted to enable way 0 to be updated; if
CS1,CS0=0,1 compartment 1 is selected and way update signal WU 1 is asserted to enable way 1 to be updated; and if CS1,CS0=1,0 compartment 2 is selected and either way update signal WU2 or WU3 is asserted.
Note that when compartment 2 is selected (CS1, CS0=1,0), then a determination must be made of which way (way 2 or way 3) within compartment 2 should be updated. According to one embodiment of the present invention, way 2 is the default way to
update unless the LRU code indicates that way 3 is the least recently used way. Thus, way update signal WU2 is asserted to enable way 2 to be updated if the LRU code indicates that way 3 is not the least recently updated way (i.e., LCode3=0). If, on
the other hand, the LRU code indicates that way 3 is the least recently updated way, way update signal WU3 is asserted to enable way 3 to be updated. It will be appreciated that other techniques may be used to determine which way of a multiple-way
compartment should be updated.
Because compartment pattern 1 contains only three compartments, compartments 0, 1 and 2, then an attempt to select a fourth compartment by setting CS1, CS0 is invalid. Consequently such an attempt can be used for other purposes, such as
disabling cache compartmentalization. More generally, when CS1 and CS0 select a compartment that is not present in the compartment pattern indicated by compartment organization signals CO1 and CO0, the LRU way update logic may default to the least
recently used logic described above. Referring, for example to rows 9-12 of the logic table, because CS1 and CS0 indicate a compartment (compartment 3) which is not included in compartment pattern 1, the LRU code inputs, LCode3, LCode2, LCode1 and
LCode0 are relied upon to determine which way to update. This logic is as described above in reference to FIG. 3 when the compartment enable signal (CE) is deasserted.
Referring now to rows 13-16 of the logic table, cache organization signals CO1 and CO0 are set to 1 and 0, respectively, thereby selecting compartment pattern 2. Referring to FIG. 5C, compartment pattern 2 contains two compartments, with way 0
being allocated to compartment 0 and ways 1, 2 and 3 being allocated to compartment 1. Consequently: if CS1,CS0=0,0 compartment 0 is selected and way update signal WU 0 is asserted to enable way 0 to be updated; and if CS1,CS0=0,1 compartment 1 is
selected and either way update signal WU1, WU2 or WU3 is asserted.
When compartment 1 is selected (CS1, CS0=0,1), then a determination must be made of which way (way 1, way 2 or way 3) within compartment 1 should be updated. According to one embodiment of the present invention, way 1 is the default way to
update unless the LRU code indicates that either way 2 or way 3 is the least recently used way. If way 2 is the least recently used way, then signal WU2 is asserted to enable way 2 to be updated. Otherwise, if way 3 is the least recently used way, then
signal WU3 is asserted to enable way 3 to be updated. As stated above, other techniques may be used to determine which way of a multiple-way compartment should be updated.
Momentarily skipping rows 17-20 of the logic table and referring to rows 21-24, cache organization signals CO1 and CO0 are both set to 1, thereby selecting compartment pattern 3. Referring to FIG. 5D, compartment pattern 3 contains two
compartments with ways 0 and 1 being allocated to compartment 0 and ways 2 and 3 being allocated to compartment 1. Consequently: if CS1,CS0=0,0 compartment 0 is selected and either way update signal WU0 or WU1 is asserted; and if CS1,CS0=0,1 compartment
1 is selected and either way update signal WU2 or WU3 is asserted.
When compartment 0 is selected (CS1, CS0=0,0), then it must be determined whether to update way 0 or way 1. Likewise, when compartment 1 is selected, then a determination of whether to update way 2 or way 3 must be made. According to one
embodiment of the present invention, when compartment 0 is selected, way 0 is updated unless the LRU code indicates that way 1 is the least recently used way. If the LRU code indicates that way 1 is the least recently used way (i.e., LCode1=1), then way
1 is updated. Similarly, when compartment 1 is selected, way 2 is the default way to update unless the LRU code indicates that way 3 is the least recently used way. If the LRU code indicates that way 3 is the least recently used way (i.e., LCode3=1),
then way 3 is updated. Again, other techniques may be used to determine which way of a multiple-way compartment should be updated.
Returning now to rows 17-20 of the logic table, because compartment patterns 2 and 3 each have only two compartments (viz., compartments 0 and 1), then whenever either compartment pattern 2 or 3 is selected (i.e., CO1=1, CO0=X), a compartment
selection of 2 or 3 (i.e., CS1=1, CS0=X) is invalid. This condition is shown in rows 17 to 20. According to one embodiment of the present invention, whenever compartment 2 or 3 is selecte | | |
