Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1997-12-31
2003-02-04
Hudspeth, David (Department: 2651)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S003000, C711S203000
Reexamination Certificate
active
06516386
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to address searching within a cache index. In particular, the present invention relates to address searching within a cache index using a partial physical address.
BACKGROUND OF THE INVENTION
Data is stored in memory according to a physical address scheme. Software programmers, however, write program code that requires the retrieval of data using a virtual or linear address scheme (referred to herein as the “virtual address”). Therefore, it becomes necessary for a system to translate a virtual address for a piece of data to a physical address before the data can be read from physical memory.
Many conventional searching techniques require that the fall physical address be translated from the virtual address of the requested data prior to initiating a search. This significantly slows down the process of actually retrieving the data from memory, especially if the data is stored in high speed cache memory. Since a physical address is necessary before identifying and/or retrieving data from a cache, many conventional cache systems must wait until the translation from the virtual to the physical address is complete. This process can delay a search by a clock cycle or more.
In an attempt to solve this problem, other known cache systems have implemented a technique for searching an index for cache data based upon a partial physical address. This technique is based upon the recognition that a virtual address and a physical address share some address bits in common, so that these bits are available to the system immediately.
Generally, caches and cache indexes are organized into a number of sets, with each set containing one or more entry locations, or ways. In order to begin a partial-address search using the above-mentioned techniques, the available string of bits (i.e. those bits common to the virtual and physical address) must be of sufficient length to uniquely identify the individual set which might contain the requested data. According to known systems, only then may the system read out an individual set whose ways may be later searched to determine the location of requested data.
For example, for some systems, address bits
0
-
11
for a virtual and physical address are the same. In this example, bits
0
-
6
are used for addressing data within each entry of the cache, and therefore are not used to index the entries themselves.
For smaller caches, for example 16 kilobyte caches, it is possible to begin searching a cache index using bits
7
-
11
as many such caches are organized into 32 or fewer sets. This is possible because bits
7
-
11
can identify 32 individual sets (the five bits forming 2
5
, or 32, unique binary numerals). Thus for caches with 32 or fewer sets, if bits
7
-
11
are available they may be immediately used to uniquely identify the individual set which might contain the requested data.
Larger caches, however, for example 256 kilobyte caches, typically contain more than 32 sets. A 256 kilobyte cache containing, for example, 256 sets requires an 8-bit string (e.g. bits
7
-
14
) to effectively begin a search of the cache index. Known cache systems, therefore, have not initiated a search of a cache index for large caches using bits
0
-
11
, since these systems require bits
12
-
14
to initiate the search anyway. These systems must wait until the translation process is complete, and the full physical address is available, before initiating a search of the cache index. The problem with this method, however, is that one or more clock cycles are wasted waiting for the translation process to finish prior to beginning the search for cache data.
SUMMARY OF THE INVENTION
The method for searching a cache index includes the steps of receiving a virtual address of a requested data element which has at least one common bit which is untranslated between the virtual address and a physical address and searching the cache index using the at least one common bit, before the virtual address is completely translated, to identify a selected block. The cache index may be organized into blocks, each block containing a plurality of sets. Each of the plurality of sets may contain at least one way, each of the ways containing an address tag.
An embodiment of a device according to the present invention includes a cache index organized into a number of sets and ways, and an auxiliary memory structure for receiving and storing intermediate search results.
REFERENCES:
patent: 5014195 (1991-05-01), Farrell et al.
patent: 5060137 (1991-10-01), Bryg et al.
patent: 5067078 (1991-11-01), Talgam et al.
patent: 5265220 (1993-11-01), Kinoshita
patent: 5307477 (1994-04-01), Taylor et al.
patent: 5412787 (1995-05-01), Forsyth et al.
patent: 5542062 (1996-07-01), Taylor et al.
patent: 5606683 (1997-02-01), Riordan
patent: 5640339 (1997-06-01), Davis et al.
patent: 5696925 (1997-12-01), Koh
patent: 5699551 (1997-12-01), Taylor et al.
patent: 5727180 (1998-03-01), Davis et al.
patent: 5740416 (1998-04-01), McMahan
patent: 5854943 (1998-12-01), McBride et al.
patent: 5953747 (1999-09-01), Steely, Jr. et al.
patent: 5956746 (1999-09-01), Wang
patent: 5956752 (1999-09-01), Mathews
patent: 6092172 (2000-07-01), Nishimoto et al.
patent: 6145054 (2000-11-01), Mehrotra et al.
Conley Bryon George
Pang Roland
Thornton Gregory Mont
Hudspeth David
Intel Corporation
Kenyon & Kenyon
Tzeng Fred F.
LandOfFree
Method and apparatus for indexing 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 indexing a cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for indexing a cache will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3149210