Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-10-11
2001-12-25
Bragdon, Reginald G. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S136000
Reexamination Certificate
active
06334170
ABSTRACT:
STATEMENT REGARDING FEDERALLY-SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of computer memory architecture and, more particularly, to cache memories used in conjunction with Static Random Access Memories (SRAM) to improve overall performance.
2. Description of the Background
The central processing unit (CPU) of a computer typically operates at a much faster speed than the access time of the memory to which the CPU is connected. The problem is exacerbated by the fact that memory arrays having a high density, which typically makes them less expensive then memory arrays having a lower density, are often slower than memory arrays which have a lower density. Thus, there is always a trade off between speed and cost.
To help ameliorate the effects of that trade off, computer designers use both types of memory. The relatively slower memory, which is inexpensive, is used to provide the vast bulk of the memory required and is referred to as the main memory. The more expensive, faster memory, is provided as a buffer between the CPU and the main memory, and is referred to as cache memory.
Studies have been conducted to identify the information stored in the main memory which should also be stored in the cache memory. Obviously, the more often the CPU can find the information that it needs in the cache memory, rather than having to go to the slower main memory, the faster the CPU can operate. Sophisticated algorithms have been developed to determine what information should be maintained in the cache memory and what information should be overwritten when new information is to be stored.
It is known to organize cache memory according to certain mapping techniques. For example, see U.S. Pat. No. 5,367,653 which is entitled Reconfigurable Multi-Associative Cache Memory. One type of mapping is referred as direct mapping. In that mapping scheme, a main memory address is divided into two fields, an index field comprised of the least significant bits of an address and a tag field comprised of the remaining significant bits of the address. The entire address, i.e., the tag field and the index field, is needed to access the main memory, while only the index field is needed to access the cache memory. The remainder of the address, i.e., the tag field, is stored in the tag memory, sometimes referred to as a tag cache. In operation, the index field from an address for a requested piece of data is input to the tag cache, and the tag associated with that address is output. If the tag output from the tag cache matches the tag field of the requested data, then a hit results indicating that the requested data is in the data cache. If there is a miss, the data must be retrieved from the main memory.
Other types of mapping techniques are also known. For example, in fully associative mapping, the cache memory stores both the main memory address and the data word thus allowing a word from main memory to be stored in any location in the cache memory. For example, if a fifteen-bit main memory address is located in an argument register, and the contents of the argument register are compared with the main memory addresses stored in associative cache memory, a hit results when the contents of the argument register equals one of the main memory addresses stored in cache memory.
Another type of mapping, referred to as set-associative mapping, permits the storage of two or more words in cache memory at the same index address. The data words stored in the cache memory at the same index are each associated with a tag. The number of tag/word pairs stored at one address forms a “set”. A cache memory which has multiple cache words at one cache address is referred to as a multi-way cache. Thus, a cache memory which provides for two words to be stored under a single address is referred to as a two-way cache. A cache memory which stores four words under a single address is referred to as a four-way cache. Because the cache memory utilizes an associative mapping function, the cache memory may be referred to as a two-way, set associative cache or a four-way, set associative cache, respectively.
Different configurations of cache memory are used for different applications. For example, two-way set associative cache is often adequate for instruction whereas four-way set associative cache often provides better performance for data. The type of cache memory can be established by proper hardware selection if the particular use is known. If the particular use is not known, the reconfigurable multi-way associative cache memory disclosed in the aforementioned U.S. Pat. No. 5,367,653 may be used. However, there remains a need for a tag cache circuit which is sufficiently flexible to enable it to be easily modified so as to expand the number of ways. Such a circuit should provide the flexibility of a software configurable cache memory while at the same time providing the advantages provided by a hard-wired circuit.
SUMMARY OF THE INVENTION
The present invention is directed to an expandable set, tag, cache circuit for use with a data cache memory. A tag memory is divided into a first set and a second set for storing under a single address location, first and second tag fields representative of first and second data, respectively. The tag memory also stores first and second signals representative of which of the sets is the least recently used. A comparator is responsive to a tag field of an address representative of requested data as well as to a first tag field output from the tag memory for producing an output signal indicative of a match therebetween. A second comparator is responsive to the same tag field of the address and to a second tag field output from the tag memory for producing an output signal indicative of a match therebetween. A first logic gate is responsive to the first and second comparators for producing an output signal indicative of the availability of the requested data in the data cache memory. A second logic gate is responsive to the first logic gate and an external signal. A first write driver is enabled by the output of the first logic gate and is responsive to the output of the first comparator for controlling the state of the first signal. A second write driver is enabled by the output of the second logic gate and is responsive to the external signal for controlling the state of the second signal. Although this is described as a two-way tag, the concept applies equally to higher degrees of associativity. LRU
2
(i.e., additional line replacement bit) is the necessary storage element required to facilitate expansion.
The circuit of the present invention may be used as a two-way set associative cache by tying the external signal to either a high or low voltage, depending upon the components used. Alternatively, by providing a duplicate circuit and by using the output of one circuit as the external signal input to the other circuit, a four-way set associative cache can be provided. Thus, the circuit architecture of the present invention provides an expandable-set, tag, cache circuit which provides all of the advantages of a hardwired circuit with the flexibility normally found only in software configured cache memory. Those, and other advantages and benefits of the present invention will become apparent from the Detailed Description Of The Preferred Embodiments hereinbelow.
REFERENCES:
patent: 4322795 (1982-03-01), Lange et al.
patent: 4493026 (1985-01-01), Olnowich
patent: 4736287 (1988-04-01), Druke et al.
patent: 4831625 (1989-05-01), Chiu et al.
patent: 4991081 (1991-02-01), Bosshart
patent: 5014195 (1991-05-01), Farrell et al.
patent: 5091851 (1992-02-01), Shelton et al.
patent: 5202968 (1993-04-01), Sato
patent: 5274790 (1993-12-01), Suzuki
patent: 5367653 (1994-11-01), Coyle et al.
patent: 5553262 (1996-09-01), Ishida et al.
patent: 5586279 (1996-12-01), Pardo et al.
Bragdon Reginald G.
Kirkpatrick & Lockhart LLP
Micro)n Technology, Inc.
LandOfFree
Multi-way cache expansion circuit architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-way cache expansion circuit architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-way cache expansion circuit architecture will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2573293