 |
Claims  |
|
|
The embodiments of the invention in which an exclusive property or
privilege is claimed are defined as follows:
1. In a computer system having a first address bus and a first data bus, a
cache device comprising:
cache memory means comprising a maximum number of memory locations, each
memory location operable to store one cache line of data;
cache control means for controlling the storage of cache lines of data to
the cache memory means from the first data bus and retrieval of cache
lines of data from the cache memory means, said cache control means
comprising a register means for storing binary values;
wherein the maximum number of memory locations is equal to 2.sup.N where N
is an integer greater than zero;
wherein the cache control means associates each memory location with a
unique locating path, said locating path defined by one and only one node
on each of N levels of nodes;
wherein for a first level of nodes, the cache control means associates each
pair of memory locations with a first level node, said first level nodes
being associated with a binary value which identifies each memory location
of the pair of memory locations associated with each of the first level
nodes, each first level node being associated with one of the bits in the
register means for storing the binary value of the first level node;
wherein for each level of nodes to a (N-1)th level, the cache control means
associates each pair of nodes on a level of nodes with a higher level
node, each of said higher level nodes being associated with a binary value
which identifies each node of the pair of nodes associated with each of
the higher level nodes, each higher level node being associated with one
of the bits in the register means for storing the binary value of the
higher level node;
wherein after the cache control means retrieves a cache line of data from
one of the memory locations, the cache control means sets the bits in the
register means to identify the unique locating path of the memory location
from which the cache line of data was retrieved; and
wherein when all of the memory locations have cache lines stored therein,
the cache control means evicts a cache line of data stored in the memory
location identified by a unique locating path passing through one node on
each of the N levels of nodes such that the binary value associated with
each node is opposite to the value of the bit in the register means
corresponding to the one node on each of the N levels of nodes.
2. A cache device as defined in claim 1 wherein the cache control means
evicts the cache line of data immediately after all the memory locations
have Modified cache lines stored therein.
3. A cache device as defined in claim 1 wherein the integer N is
programmable.
4. A cache device as defined in claim 3 wherein the cache memory means can
store a maximum number of bytes of data which is independent of the
integer N; and
wherein as the integer N decreases, there is a proportional increase in the
data contained in each cache line of data.
5. A cache device as defined in claim 4 wherein the cache control means is
programmable to lock a memory location so that the cache line in the
locked memory location cannot be evicted; and
wherein when the memory location identified by the unique locating path
having nodes with an opposite value to the value of the bits in the
register means is the locked memory location, the cache control means
toggles the value of the bit associated with the first level node to
identify another memory location of the pair of memory locations
associated with the first level node.
6. A cache device as defined in claim 5 wherein the device forms part of
bridge means for bridging the first address bus and the first data bus
with a second address bus and a second data bus;
wherein the cache control means controls the storage of cache lines of data
to the memory locations of the cache memory means from the first data bus
and the second data bus and the cache control means controls the retrieval
of cache lines of data from the memory location of the cache memory means
to the first data bus and the second data bus; and
wherein all data passing from the first data bus to the second data bus is
first stored in the cache memory means.
7. A cache device as defined in claim 6 further comprising arbitration
controller means for arbitrating simultaneous storage of cache lines of
data to one of the memory locations from the first data bus and the second
data bus and for arbitrating simultaneous retrieval of cache lines of data
from each memory location to the first data bus and the second data bus.
8. A cache device as defined in claim 6 further comprising multiple bridge
support means for supporting another bridge means separately connected to
the first data bus and the first address bus, said another bridge means
bridging the first address bus and first data bus with a third data bus
and a third address bus; and
wherein said multiple bridge support means comprises a window register
means for storing a first address and a second address; and
wherein an address between the first address and the second address are
accessible through the another bridge means on the third address bus and
third data bus.
9. A cache device as defined in claim 8 wherein the window register means
comprises a postable bit operable to have a first value and a second value
such that if the another bridge means has a buffer means for temporarily
storing data destined for the third data bus and third address bus, the
postable bit is set to the first value, and, if the another bridge means
does not have a buffer means for temporarily storing data destined for the
third data bus and third address bus, the postable bit is set to the
second value.
10. A cache device as defined in claim 1 wherein the device forms part of
bridge means for bridging the first address bus and the first data bus
with a second address bus and a second data bus;
wherein the cache control means controls the storage of cache lines of data
to the memory locations of the cache memory means from the first data bus
and the second data bus and the cache control means controls the retrieval
of cache lines of data from the memory locations of the cache memory means
to the first data bus and the second data bus; and
wherein all data passing from the first data bus to the second data bus is
first stored in one of the memory locations of the cache memory means.
11. A cache device as defined in claim 10 wherein the cache control means
is programmable to lock a memory location so that the cache line in the
locked memory location is not evictable; and
wherein when the memory location identified by the unique locating path
having nodes with an opposite value to the value of the bits in the
register means is the locked memory location, the cache control means
toggles the value of the bit associated with the first level node to
identify another memory location of the pair of memory locations
associated with the first level node.
12. In a computer system having a cache means comprising a maximum number
of memory locations for storing cache lines of data, said maximum number
being equal to 2.sup.N where N is an integer greater than zero, a method
of selecting a cache line of data to be evicted from the cache means when
all of the memory locations have a cache line stored therein, said method
comprising the steps of:
associating each memory location with a unique locating path, said locating
path defined by one and only one node on each of N levels of nodes;
associating each pair of memory locations with a first level node, said
first level nodes being associated with a binary value which identifies
each memory location of the pair of memory locations associated with each
of the first level nodes;
associating each pair of nodes on each level of nodes to an (N-1)th level
with a higher level node, each of said higher level nodes being associated
with a binary value which identifies each node of the pair of nodes
associated with the higher level nodes;
whenever a cache line of data is retrieved from a target memory location,
setting said binary values of the nodes through which the unique locating
path to the target memory location passes to values which do not identify
the unique locating path of the target memory location; and
evicting the cache line of data stored in the memory location having by a
unique locating path identified by the binary values of the nodes.
13. A method as defined in claim 12 wherein the integer N is programmable;
the cache memory means can store a maximum number of bytes of data which is
independent of the integer N; and
wherein as the integer N decreases, there is a proportional increase in the
data contained in each cache line of data.
14. In a computer system having a first address bus and a first data bus, a
cache device comprising:
cache memory means comprising a maximum number of memory locations, each
memory location operable to store one cache line of data;
cache control means for controlling the storage of cache lines of data to
the cache memory means from the first data bus and retrieval of cache
lines of data from the cache memory means, said cache control means
comprising a register means for storing binary values;
wherein the maximum number of memory locations is equal to 2.sup.N where N
is an integer greater than zero;
wherein the cache control means associates each memory location with a
unique locating path, said unique locating path defined by one and only
one node on each of N levels of nodes;
wherein for a first level of nodes, the cache control means associates each
pair of memory locations with a first level node, said first level nodes
being associated with a binary value which identifies each memory location
of the pair of memory locations associated with each of the first level
nodes, each first level node being associated with one of the bits in the
register means for storing the binary value of the first level node;
wherein for each level of nodes to a (N-1)th level, the cache control means
associates each pair of nodes on a level of nodes with a higher level
node, each of said higher level nodes being associated with a binary value
which identifies each node of the pair of nodes associated with each of
the higher level nodes, each higher level node being associated with one
of the bits in the register means for storing the binary value of the
higher level node;
wherein after the cache control means stores or retrieves a cache line of
data from one of the memory locations, the cache control means sets the
bits associated with the nodes through which the unique locating path of
the one of the memory locations passes to values which do not identify the
unique locating path of the one of the memory locations; and
wherein when all of the memory locations have cache lines stored therein,
the cache control means evicts a cache line of data stored in the memory
location having a unique locating path identified by the binary values of
the nodes.
15. A cache device as defined in claim 14 wherein the integer N is
programmable;
the cache means can store a maximum number of bytes of data which is
independent of the integer N; and
wherein as the integer N decreases, there is a proportional increase in the
data contained in each cache line of data.
16. A cache device as defined in claim 15 wherein the cache control means
is programmable to lock a memory location so that the cache line in the
locked memory location is not evictable; and
wherein when the memory location having a unique locating path identified
by the binary values of the nodes is the locked memory location, the cache
control means toggles the value of the bit associated with the first level
node to identify another memory location of the pair of memory locations
associated with the first level node.
17. A cache device as defined in claim 16 wherein the device forms part of
bridge means for bridging the first address bus and the first data bus
with a second address bus and a second data bus;
wherein the cache control means controls the storage of cache lines of data
to the memory locations of the cache memory means from the first data bus
and the second data bus and the cache control means controls the retrieval
of cache lines of data from the memory locations of the cache memory means
to the first data bus and the second data bus;
wherein all data passing from the first data bus to the second data bus is
first stored in one of the memory locations of the cache memory means;
wherein the second data bus is slower than the first data bus; and
wherein the cache control means sets the bits upon storage of data to the
memory locations of the cache memory means from the second data bus and
upon retrieval of data from the memory locations of the cache memory means
to the second data bus.
18. A cache device as defined in claim 14 wherein the device forms part of
bridge means for bridging the first address bus and the first data bus
with a second address bus and a second data bus;
wherein the cache control means controls the storage of cache lines of data
to the memory locations of the cache memory means from the first data bus
and the second data bus and the cache control means controls the retrieval
of cache lines of data from the memory locations of the cache memory means
to the first data bus and the second data bus; and
wherein all data passing from the first data bus to the second data bus is
first stored in one of the memory locations of the cache memory means.
19. A cache device as defined in claim 14 wherein the cache control means
evicts the cache line of data immediately after all the memory locations
have Modified cache lines stored therein. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
This invention relates to an improved cache controlling device and method,
and in particular an improved cache controlling device and method to more
efficiently determine the least used cache line for eviction from a cache
when the cache is full. The invention also relates to an improved bus
control device for bridging two data and address buses utilizing a cache
controlled by the improved cache controlling device.
In the past, cache controllers have been used to store, organize and
retrieve cache lines of data from the memory location of the cache. A
particular problem which arises with all caches is selecting which cache
line to write back to main memory or "evict" from the cache when the cache
is full.
In the best case, the cache controller will send back to main memory a
cache line which will not be required in the near future. Otherwise,
inefficiencies will arise if the same cache lines are continuously written
back and forth between the cache and main memory.
Several different algorithms and principles have been used to try to select
which cache line will not be needed in the future and should be evicted
from the cache. In general, the least recently used cache line should be
evicted as this cache line will likely be the least recently used cache
line in the future.
The least recently used cache line can be determined explicitly by tracking
the use of the cache lines. However, this tends to be complicated and time
consuming in practice. Also, it is only a general principle that the least
recently used cache line in the past will continue to be the least
recently used cache in the future. It is possible that the least recently
used cache line may in fact be the cache line required next.
Therefore, there is an overall decrease in efficiency and an unnecessary
increase in the cost of the system if too much effort is expended on
determining the least recently used cache line. If a good approximation
can be made of a cache line which is one of the least recently used cache
lines, there are ever diminishing returns in trying to determine even
better approximations or even the least recently used cache line.
Some cache controllers use a pseudo least recently used algorithm
(pseudo-LRU) to determine the most likely least recently used cache line.
Such a cache controller would determine the last used cache line and
select the cache line next to the last used cache line as the likely least
used cache line and evict that cache line. While this algorithm is
attractive in its simplicity, it suffers from the fact that the cache line
immediately next to the last used cache line is likely not the least used
cache line because of the way data is stored in a cache. At best, this
algorithm can only ensure the last used cache line is not evicted from the
cache.
Accordingly, there is a need in the art for an improved pseudo-LRU
algorithm which is simple and efficient to implement and which provides a
fairly accurate indication of the least recently used cache line. Also,
there is a need in the art for an improved pseudo-LRU algorithm which can
be used in cases where the cache line sizes are programmable, and
therefore the maximum number of cache lines possible in the cache varies.
Also, there is a need for an improved pseudo-LRU algorithm which can be
used in caches where some cache lines may be considered "locked", meaning
that they can not be evicted, and yet a reasonable selection of a least
recently used cache line can be made for eviction.
SUMMARY OF THE INVENTION
Accordingly, it is an object of this invention to at least partially
overcome the disadvantages of the prior art. Also, it is an object of this
invention to provide an alternative type of cache controller which
utilizes an improved pseudo-LRU algorithm to efficiently and easily make a
selection as to the least recently used, or one of the least recently
used, cache lines in the cache for eviction.
Accordingly, in one of its aspects, this invention resides in providing a
computer system having a first address bus and a first data bus, a cache
device comprising: cache memory means comprising a maximum number of
memory locations, each memory location operable to store one cache line of
data; cache control means for controlling the storage of cache lines of
data to the cache memory means from the first data bus and retrieval of
cache lines of data from the cache memory means, said cache control means
comprising a register means for storing binary values; wherein the maximum
number of memory locations is equal to 2.sup.N where N is an integer
greater than zero; wherein the cache control means associates each memory
location with a unique locating path, said locating path defined by one
and only one node on each of N levels of nodes; wherein for a first level
of nodes, the cache control means associates each pair of memory locations
with a first level node, said first level nodes being associated with a
binary value which identifies each memory location of the pair of memory
locations associated with each of the first level nodes, each first level
node being associated with one of the bits in the register means for
storing the binary value of the first level node; wherein for each level
of nodes to a (N-1)th level, the cache control means associates each pair
of nodes on a level of nodes with a higher level node, each of said higher
level nodes being associated with a binary value which identifies each
node of the pair of nodes associated with each of the higher level nodes,
each higher level node being associated with one of the bits in the
register means for storing the binary value of the higher level node;
wherein after the cache control means retrieves a cache line of data from
one of the memory locations, the cache control means sets the bits in the
register means to identify the unique locating path of the memory location
from which the cache line of data was retrieved; and wherein when all of
the memory locations have cache lines stored therein, the cache control
means evicts a cache line of data stored in a memory location identified
by a unique locating path passing through one node on each of the N levels
of nodes such that the binary value associated with each node is opposite
to the value of the bit in the register means corresponding to each level.
In a still further aspect, the present invention relates to a computer
system having a first address bus and a first data bus, and a second
address bus and second data bus operating independently of the first
address bus and the first data bus, a bridge means for bridging the first
address bus and the first data bus with the second address bus and the
second data bus, said bridge means comprises: error detection means to
detect errors on the first data bus, the first address bus, the second
address bus and the second data bus; control means for systematically
injecting errors into the bridge means to test the error detection means;
and wherein the errors systematically injected by the control means
comprise parity errors on the first data bus, the second data bus, the
first address bus and the second address bus, target abort cycles and
retry configuration cycles.
Further aspects of the invention will become apparent upon reading the
following detailed description and the drawings which illustrate the
invention and preferred embodiments of the invention.
BRIEF DESCRIPTION OF THE DRAWINGS
In the drawings, which illustrate embodiments of the invention:
FIG. 1 is shows a schematic representation of a computer system
incorporating a bus control unit which utilizes a cache controller
according to one embodiment of the present invention;
FIG. 2 is a schematic representation of a bus control unit according to one
embodiment of the present invention;
FIG. 3A is a symbolic representation of a pseudo-LRU algorithm utilized by
a cache controller with a maximum number 16 memory location for storing 16
separate cache lines according to one embodiment of the present invention;
and
FIG. 3B is a symbolic representation of a pseudo-LRU algorithm utilized by
a cache controller with a maximum number 4 memory location for storing 4
separate cache lines according to one embodiment of the present invention.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS OF THE INVENTION
FIG. 1 shows a computer system, shown generally by reference numeral 10,
having a memory system, shown generally as 12. The memory system 12
comprises several actual memory banks, two of which are shown in FIG. 1 as
RAM1 and RAM2. The memory devices RAM1 and RAM2 comprise several memory
locations to store and retrieve groups of data, as is known in the art. In
general, the groups of data can be bytes, words, or other combinations of
bits.
Each memory bank RAM1 and RAM2 comprises one or more self-contained chips
having independent connections to the first address bus 14A and the first
data bus 16A. The chips are generally dynamic random access memory chips
of different sizes, such as 256KBs, 1MB, 4MB or 16MB.
Computer system 10 comprises a central processing unit ("CPU") shown on a
CPU module 50. The CPU module 50 also comprises a cache RAM and a cache
control unit CCU for interfacing with the first address bus 14A and the
first data bus 16A. In a preferred system 10, up to four additional CPU
modules 50 can be included in the system 10, each CPU module 50 running
symmetrically.
In a preferred embodiment, as shown in FIG. 1, the first address bus 14A
and the first data bus 16A are temporally multiplexed and comprise the
same lines. In this way, when data is stored or retrieved, the address is
sent first and then the data is read from or written into the memory
system 12 or a peripheral device 60 on at least some of the same lines
upon which the address was sent. In a preferred embodiment, the data bus
16A comprises 64 lines and the address bus 14A comprises 32 lines, which
are also the first 32 lines of the data bus 16.
As is also shown in FIG. 1, the system 10 comprises a bus control unit
("BCU") 30 for controlling the first address bus 14A and the first data
bus 16A as well as controlling and providing a bridge to the peripheral
component bus ("PCI bus") which comprises the second address bus 14B and
second data bus 16B. In addition, the bus control unit 30 comprises a
memory controller unit 20 which sends control signals S.sub.R and S.sub.W
to the memory banks RAM1 and RAM2 to control the read and write operations
to and from memory locations within memory banks RAM1 and RAM2. In this
embodiment, the first address bus 14A and second address bus 14B are
collectively referred to as the multi processor interconnect bus ("MPI
bus") referring to the fact that this MPI bus can support more than one
CPU.
The memory controller unit 20 provides write control signals S.sub.W and
read control signals S.sub.R to control the storing and retrieval of data
in the memory system 12, including memory units RAM1 and RAM2. Memory
controller unit 20 sends a write control signal S.sub.W to a memory unit,
RAM1 or RAM2, to cause the memory unit, RAM1 or RAM2, to store the data
presented on the first data bus 16A. Likewise, memory controller unit 20
sends a read control signal S.sub.R to the memory units, RAM1 or RAM2, to
retrieve data stored in the memory units, RAM1 or RAM2.
It is understood that while the present discussion relates to only two
memory units, RAM1 and RAM2, several such memory units may be incorporated
in the memory system 12 and each would be controlled by the memory
controller unit 20 in a similar manner to that described above with
respect memory banks RAM1 and RAM2.
The buffers 24A and 24B in a preferred embodiment are data pipeline chips
("EDP chip"). The EDP chip comprises error correction circuitry ("ECC") as
well as write buffers and prefetch buffers to assist in interfacing with
the first data bus 16A.
The buffers 24A and 24B are located between the first and second memory
units RAM1 and RAM2 and the first data bus 16A. It is apparent that one
buffer 24A or 24B is required for each memory board 22A or 22B. In the
preferred embodiment, the EDP chip accommodates only 64 bits of data, and
therefore each buffer 24A and 24B comprises two EDP chips to accommodate
the entire 128 bits of data on the memory data bus, but other arrangements
are possible.
In the embodiment shown in FIG. 1, the memory units RAM1 and RAM2 are shown
on separate boards, namely boards 22A and 22B, respectively. In this
embodiment, the memory controller unit 20 comprises separate lines to
select each of the boards 22A and 22B separately, and can also
simultaneously select both boards 22A and 22B.
In a preferred embodiment, the computer system 10 comprises slots for
insertion of up to four memory boards (not shown). The memory controller
20 has 2 lines called SLOTSEL[1:0] which are connected to the EDP chips
and select a target slot of the four possible slots. In one mode of
operation, the memory controller unit 20 supports interleaving between two
separate boards 22A and 22B, in which case two boards are selected by the
memory controller unit 20. In another mode of operation, the memory
controller unit 20 supports interleaving between memory units on the board
22, in which case only the board having the memory units RAM1 and RAM2
would be selected.
The memory controller means 20, in one preferred embodiment, sends other
interfacing control signals S.sub.I to the buffer means 24A and 24B. These
interfacing control signals S.sub.I include the select signals S.sub.S
which select the buffer means 24A and 24B. The interfacing control signals
S.sub.I also configure the buffer means 24A and 24B for different modes of
operation such as interleaving or non-interleaving, error correction or
non-error correction, and other modes of operation. In addition, the bus
controller unit 30 sends interrupt control signals to other electronic
components connected to the MPI-bus to signify different errors having
occurred.
FIG. 2 shows the bus control unit 30 in more detail. As can be seen from
FIG. 2, the bus control unit 30 comprises an input/output cache ("I/O
cache") 34 of a fixed maximum capacity meaning that the I/O cache 34 can
be a maximum number of bytes of data. In this case, the I/O cache 34 can
store 512 bytes of data.
The I/O cache 34 can be segregated to hold cache lines of different length.
For example each cache line could be 4.times.64 bits per line, 8.times.64
bits per line, 16.times.64 bits per line or 32.times.64 bits per line. It
is apparent that as the I/O cache is of a fixed capacity, namely 512
bytes, the greater the size of the cache line, the fewer cache lines which
may be held. Accordingly, for cache lines composed of 4.times.64 bits per
line, 16 cache lines may be held. However, only 8 cache lines of
8.times.64 bits per line may be stored, and, for cache lines composed of
16.times.64 bits per line, only 4 cache lines may be stored. Likewise, for
cache lines composed of 32.times.64 bits per line, the I/O cache 34 may
hold only 2 cache lines.
Accordingly, the I/O cache can store a maximum number of cache lines in a
maximum number of memory locations. It is preferable that the maximum
number of memory locations, and therefore the maximum number of cache
lines storable in the I/O cache 34, is a power of 2. In other words, the
maximum number of memory locations is equal to 2.sup.N where N is an
integer greater than 0. The integer N also has another function described
in more detail below.
Also, for the purposes of this discussion, the memory locations in the I/O
cache 34 shall be considered to be the size of one cache line of data
regardless of the size of the cache line. It is understood that the memory
locations are arbitrarily set to be the size of one cache line of data and
may be composed of several individual memory locations addressable in
different sizes. Also, as the I/O cache 34 has programmable cache sizes
the size of the memory location of the cache device 35 will be considered
to be changeable. As a practical matter however, by increasing the size of
the cache line, the bits of storage in the I/O cache 34 will simply be
arranged in different sized groups of 64 bits.
It is apparent that different size cache lines and different size
input/output cache may be selected. In the present circumstances, it is
preferable that the cache lines be multiples of 64 bits as that is the
size of the first data bus 16A on the MPI bus. In practice, the size of
the cache lines for the I/O cache 34 will be the same as the cache lines
used by the cache control unit CCU on the CPU module. It is apparent that
it is advantageous for these to be the same size to improve communication
between these two units.
The I/O cache 34 is controlled by the cache control logic 32. The cache
control logic 32 comprises the pseudo least recently used ("pseudo-LRU")
algorithm discussed in more detail below and with reference to FIGS. 3A
and 3B.
It is understood that the cache device 35 and the cache control logic 32
could control a cache used in association with any other electronic
component in the system 10. In other words, the pseudo-LRU algorithm and
cache control logic 32 described herein need not be used in association
with an I/O cache 34 bridging the MPI bus and the PCI bus only. This is
merely a preferred embodiment of the present invention and the cache
device 35 could be utilized in association with other chips other than
with the bus control unit 30.
In addition to implementing the pseudo-LRU algorithm, the cache control
logic 32 also controls the storage of cache lines of data to the cache
device 35 from the first data bus 16A, shown as the MPI bus in FIGS. 1 and
2, and the retrieval of information from the I/O cache 34 and placement of
the data on the first data bus 16A. Likewise, the cache control logic 32
controls the storage of cache lines of data to the I/O cache 34 from the
second data bus 16B, shown as the PCI bus in FIGS. 1 and 2, and the
retrieval of cache lines of data from the I/O cache 34 and placement of
that data on to the second data bus 16B. It is apparent that cache lines
of data stored by the cache control logic 32 from the second data bus 16B
may be retrieved by the cache control logic 32 and then placed on the
first data bus 16A, and vice versa. In this way, data may be transferred
from the 50 Mhz MPI bus to the 33 Mhz PCI bus through an asynchronous
interface as shown in FIG. 2. A specific operation of the asynchronous
interface is discussed in more detail below.
In a preferred embodiment, the cache control logic 32 utilizes an LRU
register 33 to implement the pseudo-LRU algorithm. The LRU register 33
stores the LRU bits, the function of which is described in more detail
below and in Appendix A.
Referring to FIG. 3A, this figure shows the method of storage of the cache
lines of data in the I/O cache 34. In FIG. 3A, the memory locations for
storing the cache lines of data are represented by the tags shown with a
capital T followed by an integer from 0 to 15. It is apparent that in FIG.
3A, there are 16 memory locations shown by the tags T0 to T15. In this
embodiment, the maximum number of memory locations in which cache lines
may be stored is 16, and, therefore the integer N is equal to 4.
The cache control logic 32 organizes the cache lines of data within the I/O
cache 34 by associating each memory location for storing a cache line of
data with a unique path. This unique path passes through a series of nodes
shown as Bxy, where x and y are integers and x represents the level of the
node. Because the maximum number of memory locations is 16, the integer N
is equal to 4 and therefore there are 4 levels of nodes shown as B1y
through to B4y. It is apparent that the number of levels is dependent on
the maximum number of memory locations of the I/O cache 34 within which
cache lines may be stored. There could be fewer levels as shown in FIG.
3B. In any event, the first level of nodes is considered to be the level
of nodes closest to the memory location represented by tags T0 to T15 for
storing the cache lines. In FIG. 3A, the first level of nodes is
represented by B4y and there are eight of them.
A pair of memory locations is associated with each first level node B4y.
For example, the first level node B43 is associated with memory location
tags T4 and T5. To identify or differentiate between memory locations T4
or T5, the cache control logic 32 associates a bit in the LRU register 33,
referred to as an LRU bit, with node B43. The value of the bit associated
with node B43 identifies memory location T4 or T5 by having a value of 0
or 1, respectively, as shown in FIG. 3A. Therefore, a value of 0 for the
LRU bit associated with node B43 will identify the memory location T4, and
therefore the cache line of data contained therein, and a value of 1 for
the LRU bit associated with node B43 will identify memory location T5 and
the cache line of data contained therein.
As with the first level nodes B4y, there are higher level nodes B3y, B2y
and B1y. For each level of nodes from the first level B4y to the (N-1)th
level (in FIG. 3A the (N-1)th level is shown by nodes as B2y) there will
be an even number of nodes for each level. For each of these levels, the
nodes are grouped in pairs, as the memory location T0 to T15 were grouped
in pairs, and associated with a higher level node. For example, node B43
is grouped with node B44 to form a pair and this pair is associated with
the higher level node, B32. The cache control logic 32 associates the LRU
bit in the LRU register 33 with node B32. The value of the LRU bit
corresponding to node B32 identifies one of the nodes B43 or B44 of the
pair of nodes B43 and B44. For example, as shown in FIG. 3A, node B43 is
identified by a 0 value being associated with node B32 and node B44 is
identified by a 1 value. Likewise, each of the nodes B3y on the third
level are associated with an LRU bit which can identify each of the pairs
of nodes with which it is associated.
Likewise, the nodes on the third level B3y are grouped in pairs and each
pair is associated with a higher level node, in this case a node on the
second level B2y. Each node on the second level B2y is associated with an
LRU bit in the LRU register such that the value of this bit identifies one
of the pairs of nodes.
This association continues to the Nth level, here shown by node B11, which
is the highest level and has a single node B11. Node B11 is also
associated with an LRU bit in the LRU register 33. In all cases,
regardless of the value of the integer N, there will only be one node on
the highest level and this node could be considered a root node.
In the case where N is set to 1, meaning there are only two memory
locations for storing cache lines in the I/O cache 34, each memory
location capable of storing a cache line composed of 32.times.64 bits per
line, node B11 would be both the first level and the highest level node.
In this case, there would not be any higher level nodes.
Accordingly, each memory location tag T0 to T15 has a unique path starting
at the highest or Nth level of nodes and passing through only one node on
each of the N levels of nodes. The unique path identifying each memory
location is determined by the LRU bits stored in the LRU register 33. For
example, for the cache line of data in memory location tag T4, the values
of the LRU bits corresponding to a node on each of the levels would be B11
equals 0, B21 equals 1, B32 equals 0 and B43 equals 0.
In a preferred embodiment, the LRU register 33 has one unique bit
associated with every possible node that may exist. The value of the LRU
bits in the LRU register 33 associated with the nodes through which the
unique path to memory location tag T4 does not pass are not relevant for
memory location tag T4.
Each time there is a hit in the I/O cache 34, the cache control logic 32
sets the bits in the LRU register 33 to identify the unique path of the
memory location from which the cache line of data was retrieved. For
example, if the cache line of data was retriev | | |
