Even/odd cache directory mechanism

Details Even/odd cache directory mechanism Even/odd cache directory mechanism

1998-03-23

2001-04-03

Cabeca, John W. (Department: 2186)

Electrical computers and digital processing systems: memory

Address formation

Combining two or more values to create address

C711S128000

Reexamination Certificate

active

06212616

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to caches in data processing systems and in particular to cache directory addressing and parity checking schemes for caches. Still more particularly, the present invention relates to a cache directory addressing and parity checking scheme which reduces the data storage size for caches in data processing systems.
2. Description of the Related Art
Contemporary data processing systems commonly employ caches for staging data from system memory to the processor(s) with reduced access latency. Such caches typically employ a parity checking mechanism within the cache directory.
FIG. 3
depicts a cache directory addressing and parity checking scheme for a 32 bit data processing system using a 1 MB. The 1 MB cache directory addressing configuration employs a 64 byte cache line. A cache line is the block of memory which a coherency state describes, also referred to as a cache block. When addressing the cache, bits
26
-
31
(6 bits) of the address specify an intra-cache line address, bits
12
-
25
(14 bits) of the address are utilized as an index to cache lines in the cache directory and the cache memory, and bits
0
-
11
(12 bits) of the address utilized as the cache line address tag. The intra-cache line address field allows a particular byte to be selected from a cache line. The index field specifies a row (or congruence class) within the cache directory and memory. The address tag field also identifies a particular cache line. The address tag is stored within the cache directory entry corresponding to the cache line containing the data associated with the address. Matching the address tag field of an address to the contents of a cache directory entry verifies that the correct cache entry is being selected.
In the known art, an address index field (address bits [
12
-
25
]) is utilized by cache directory
302
to select a entry
302
a
within cache directory
302
. The address index field maps to address lines
0
-
13
of cache directory
302
and cache memory (not shown). The selected cache directory entry
302
a
contains a 12-bit address tag
302
b
and a parity bit
302
c.
Parity bit
302
c
within cache directory entry
302
a
contains the parity of address tag
302
b.
Address tag
302
b
is passed to comparator
304
for comparison with the address tag field (address bits [
0
-
11
]) of an address presented. Address tag
302
b
and parity bit
302
c
are passed together to parity checking logic
306
to verify address tag
302
b.
Parity checking logic
306
computes the parity of address tag
302
b
and compares the result with parity bit
302
c,
generating a signal
308
indicating whether a match is detected.
One problem with the approach to implementing a cache directory addressing and parity checking system of the type described above is the additional cache directory space required to associate a parity bit with address tags in each cache entry. It would be desirable, therefore, to provide a cache directory addressing and parity checking scheme which did not require parity bit storage in the cache directory. It would further be advantageous if the cache directory addressing and parity checking scheme utilized did not require novel parity generation and/or checking logic. It would further be advantageous for the mechanism to improve delay within critical cache directory access paths.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved cache for use in data processing systems.
It is another object of the present invention to provide an improved cache directory addressing and parity checking scheme for caches.
It is yet another object of the present invention to provide a cache directory addressing and parity checking scheme which reduces the data storage size for caches in data processing systems.
It is still another object of the present invention to provide a cache directory addressing and parity checking scheme which improves delays within critical cache directory access paths.
The foregoing objects are achieved as is now described. The index field of an address maps to low order cache directory address lines. The remaining cache directory address line, the highest order line, is indexed by the parity of the address tag for the cache entry to be stored to or retrieved from the corresponding cache directory entry. Thus, even parity address tags are stored in cache directory locations with zero in the most significant index/address bit, while odd parity address tags are stored in cache directory locations with one in the most significant index/address bit. The opposite arrangement (msb 1=even parity; msb 0=odd parity) may also be employed, as may configurations in which parity supplies the least significant bit rather than the most significant bit. In any of these cases, even/odd parity is implied based on the location of the address tag within the cache directory. In associative caches, the mechanism may be configured so that even parity address tags are stored in one set of congruence classes (rows) or congruence class members (columns) of the cache directory, while odd parity address tags are stored in another set. The parity of an address tag field within a presented address is also utilized to test the parity of an address tag stored in the indexed location, with address tag and parity matches indicating a cache hit. In the described example, the implied parity mechanism disclosed saves about {fraction (1/12)}th (approximately 9%) of the cache directory array space required over configurations requiring stored parity associated with each cache directory entry. Furthermore, this mechanism improves delays within critical cache directory access paths.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.


REFERENCES:
patent: 4151593 (1979-04-01), Jenkins et al.
patent: 4441155 (1984-04-01), Fletcher et al.
patent: 4768148 (1988-08-01), Keeley et al.
patent: 4785395 (1988-11-01), Keeley
patent: 5479641 (1995-12-01), Nadir et al.
patent: 5761714 (1998-06-01), Liu et al.
patent: 4-205449 (1990-11-01), None

Affiliated with

Also associated with

Rating

Even/odd cache directory mechanism does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Even/odd cache directory mechanism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Even/odd cache directory mechanism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2555889