Cache lock device and method therefor

Details Cache lock device and method therefor Cache lock device and method therefor

1999-11-15

2003-11-04

Nguyen, Hiep T. (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S133000, C711S136000, C711S144000, C711S145000

Reexamination Certificate

active

06643737

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a cache apparatus and its control method, and more particularly to a cache apparatus including a cache lock device and its control method.
2. Description of the Related Art
In recent years, for the purpose of improving the utilization efficiency, especially the hit ratio, of a cache, a cache lock device which disables and controls data rewrite of a way which is holding specific data is drawing attention.
Before proceeding further, a brief description about a cache will be presented below. As shown in
FIG. 17
, a high speed memory
3
with small capacity which is interposed between an external memory
1
having a large capacity but a low data transfer rate, and a CPU which is an arithmetic unit part that processes data is generally referred to as a cache.
The main memory
1
with a large capacity generally has a low speed of the so-called access, which is the process of sending out necessary data to the CPU
2
after the output of an address from the CPU. It is the object of providing the cache
3
to copy frequently accessed data from the memory
1
to the cache
3
having a high access speed, at the timing of a first access, in order to shorten the response time in the subsequent accesses.
In the following, referring to FIG.
5
(A), the configuration of a conventional cache
3
will be described first.
The cache
3
is composed of a selector which selects an entry based on the address of an index part of input data, and a memory array formed of a plurality of entries. The memory array consists of a tag memory array TagA, a data memory array DatA, a valid bit array VBA, an LRU bit array LRUBA, and a lock bit array LBA.
In such a cache
3
, various arrays combined constitutes a unit called a way (constitution shown by the range surrounded by the broken line in FIG.
5
(A)). In this example, however, ways that have the lock bit array LBA are limited to ways W
0
and W
1
. The cache
3
shown consists of four ways, namely, way
0
(W
0
) to way
3
(W
3
), and is generally referred to as a 4-way cache.
An example of the constitution of data
4
used in such a cache apparatus
3
is shown in FIG.
5
(B). The data
4
is divided into, for example, an address part
5
and a data part
6
, and the address part
5
is further subdivided into a tag part
7
, an index part
8
, and an offset part
9
.
The data sizes of various parts are, for example, 20 bits for the tag part
7
, 6 bits for the index part
8
, and 5 bits for the offset part
9
, and the data part
6
consists of, for example, 256 bits (64 bytes).
A row having the same index number among various arrays is called collectively an entry, and one entry
10
comprises a tag part Tag, a data part Dat, a valid bit VB, an LRU bit LRUB, and a lock bit LB (a lock bit LB is given only to the entries within the ways W
0
and W
1
).
As will be described in detail later, the tag part Tag stores tag data TAG which are high order bits of an address stored in the tag part
7
of data to be stored, and the data part Dat stores data DA
0
stored in the data part
6
of the data to be stored.
The valid bit VB represents validity/invalidity of data being stored, and the LRU bit LRUB represents the entry
10
where the data read from the memory
1
may be overwritten.
The lock bit LB is used for designating the entry
10
which is desired not to be overwritten.
For an arbitrary memory address, the entry which is going to store the data at the address is selected as the entry
10
which has a row number matching the index value stored in the index part
8
of the data to be stored in the cache apparatus
3
.
In other words, since in the cache apparatus
3
, there exists one entry
10
having the same index value in each of the ways W
0
to W
3
, there exist 4 entries, namely,
10
-
0
,
10
-
1
,
10
-
2
, and
10
-
3
in the case of the 4-way cache.
As a result, in storing data of an arbitrary address in a cache, or retrieving data from the cache, it is only necessary to make access only to 4 entries
10
-
0
,
10
-
1
,
10
-
2
, and
10
-
3
.
In making access to data of certain memory address, first, the
4
entries
10
-
0
,
10
-
1
,
10
-
2
, and
10
-
3
are retrieved in order to check whether there exists the data of the address in the cache
3
.
When there exists the data, the entry
10
-n storing the data is accessed, whereas when there does not exist the data, the data are read from the memory
1
to store the data in an appropriate entry among the 4 entries
10
-
0
,
10
-
1
,
10
-
2
, and
10
-
3
, then access is made to the entry
10
-n.
In storing data to a prescribed entry
10
-n, the index value in the index part
8
of the data to be stored is extracted, and an entry
10
-n having row number identical to the index value is selected. Then, tag data TAG of the tag part
7
which are high order bits of the address part
5
in the data to be stored are stored in the tag part Tag of the entry
10
-n, data DA in the data part of the data to be stored are stored in the data part Dat of the entry
10
-n, and the valid bit VB is assigned a value
1
.
Here, the valid bit VB is a bit showing validity/invalidity of the data DA of the data part Dat in the entry
10
-n.
In retrieving data of a designated memory address from within the cache, first, as shown in FIG.
5
(A), each of data of the tag part (Tag
0
to Tag
3
), data part (Dat
0
to Dat
3
), valid bit VB (VB
0
to VB
3
), LRU bit LRUB (LRUB
0
to LRUB
3
), and lock bit (LB
0
to LB
3
) of the 4 entries,
10
-
0
,
10
-
1
,
10
-
2
, and
10
-
3
are read from each of the ways W
0
to W
3
.
Next, as shown in
FIG. 6
, these values are compared with the tag data TAG of the designated memory address in the data to be stored, and cache hit signals W
0
hit to W
3
hit and cache miss signals W
0
miss to W
3
miss are generated.
The hit/miss decision circuit shown in
FIG. 6
comprises four comparator circuits
601
to
604
which compare TAG of 20 bits with each Tagn (n=0 to 3) of 20 bits, four AND gates
605
to
608
each of which receives the output of each comparator circuit at one end and receives each of the valid bits VBn (n=0 to 3) at the other end, and four inverters
509
to
512
each of which receives the output of each AND gate.
The cache hit signals Wnhit (n=0 to 3) are signals which have the value 1 when TAG=Tagn and VBn=1, and it means that an entry of a way with the value 1 for the signal is storing data of the designated memory address.
The cache miss signals Wnmiss (n=0 to 3) are signals which have the value 1 when TAG≠Tagn.
From what is described in the above, either one of W
0
hit to W
3
hit has the value 1 at cache hit, and can be used for controlling the connection between the data buses on the CPU side and the data buses (data
0
to data
3
) of the ways, as shown in FIG.
7
(A).
Further, all of the W
0
miss to W
3
miss have the value 1 at cache miss, and in combination with select signals W
0
sel to W
3
sel that will be described later these signals can be used for controlling the connection between the data buses on the memory side and data
0
to data
3
, as shown in FIG.
7
(B).
The bus selection circuit shown in FIG.
7
(B) comprises an AND gate
701
which receives the cache miss signals Wnmiss (n=0 to 3), and four AND gates
702
to
705
whose respective one ends are connected in common to the output of the gate
701
and the way selection signals Wnsel (n=0 to 3) are connected to the other ends.
When there does not exists the data of the designated memory address in the four entries
10
-
0
,
10
-
1
,
10
-
2
, and
10
-
3
retrieved, one entry is selected from among the four entries, the data is read from the memory, and stores the data in the selected entry, namely, the data is written over the currently stored data.
For the selection of the entry, use is made of an LRU. LRU stands for “least recently used”, and it is represented by a lock bit LRU bit which holds the order of acception of access among the entri

Affiliated with

Also associated with

Rating

Cache lock device and method therefor 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 lock device and method therefor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache lock device and method therefor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3132583