US6014732A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cache memory with reduced access time
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1997-10-22
•
Granted: 2000-01-11
•
Expires: 2017-10-22
Abstract
Abstract A cache with a translation lookaside buffer (TLB) that eliminates the need for retrieval of a physical address tag from the TLB when accessing the cache. The TLB includes two content addressable memories (CAM's). For each new cache line, in the tag portion of the cache, instead of storing physical tags, the cache stores vectors called physical hit vectors. Physical hit vectors are generated by a first TLB CAM. Each physical hit vector indicates all locations in the first TLB CAM containing the physical tag of the cache line. For a cache access, a second TLB CAM receives a virtual tag and generates a vector called a virtual hit vector. The virtual hit vector indicates the location in the second TLB CAM of the corresponding virtual tag. Then, instead of retrieving and comparing physical tags, the cache compares a virtual hit vector to a set of physical hit vectors without having to retrieve a physical tag. As a result, one operation is eliminated from a time critical path, reducing the access time. For caches having variable page sizes, an additional CAM structure stores page offset bits and corresponding bit masks from the operating system. Page offset bits are then used to further qualify comparison of virtual hit vectors and physical hit vectors.
Inventors
- 👤 Samuel D. Naffziger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 18:55
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/10; G06F12/1027; G06F12/1045; G06F12/0802; G06F12/0864; G06F12/1054; G06F2212/00; G06F2212/65; G06F2212/652
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
161 words
A method of accessing data in a cache, the method comprising the following steps: receiving, by the cache, a virtual address, the virtual address including a virtual tag and a virtual index; generating a first vector, by a translation lookaside buffer, indicating whether a location in the translation lookaside buffer contains a match to the virtual tag; retrieving, by a first memory structure, from at least one location determined by the virtual index, at least one second vector, each second vector indicating whether at least one location in the translation lookaside buffer contains a particular physical tag, wherein each second vector is capable of indicating a presence of more than one physical tag when more than one virtual tag in the translation lookaside buffer corresponds to one physical tag in the translation lookaside buffer; and comparing, by a digital comparator, the first vector and the second vector; and using the result of comparing to select data from a second memory structure.
Claim 2
Independent Claim
161 words
A method of accessing data in a cache, the method comprising the following steps: receiving, by the cache, a virtual address, the virtual address including a virtual tag and a virtual index; generating a first vector, by a translation lookaside buffer, indicating whether a location in the translation lookaside buffer contains a match to the virtual tag; retrieving, by a first memory structure, from at least one location determined by the virtual index, at least one second vector, each second vector indicating whether at least one location in the translation lookaside buffer contains a particular physical tag, wherein each second vector is capable of indicating a presence of more than one physical tag when more than one virtual tag in the translation lookaside buffer corresponds to one physical tag in the translation lookaside buffer; and comparing, by a digital comparator, the first vector and the second vector; and using the result of comparing to select data from a second memory structure.
Claim 3
Dependent Claim
70 words
The method of claim 1, the virtual address further comprising page offset bits, the method further comprising: comparing, by a third memory structure, the page offset bits of the virtual address to page offset bits stored in the third memory structure at a location determined by the virtual index; and using the result of comparing by the third memory structure to qualify the result of comparing by the digital comparator.
Claim 4
Dependent Claim
148 words
A cache, the cache receiving a virtual address comprising index bits and tag bits, the cache comprising: a translation-lookaside buffer, the translation lookaside buffer receiving the tag bits and generating a first vector indicating whether a location in the translation lookaside buffer contains a particular virtual tag corresponding to the tag bits; a memory structure, receiving the index bits, the memory structure containing second vectors, each second vector indicating at least one location of a physical tag in the translation lookaside buffer, at least one second vector designated by the index bits, wherein each second vector is capable of indicating more than one physical tag when more than one virtual tag in the translation lookaside buffer corresponds to one physical tag in the translation lookaside buffer; at least one vector comparator comparing the second vector from the memory structure to the first vector from the translation lookaside buffer.
Claim 5
Dependent Claim
148 words
A cache, the cache receiving a virtual address comprising index bits and tag bits, the cache comprising: a translation-lookaside buffer, the translation lookaside buffer receiving the tag bits and generating a first vector indicating whether a location in the translation lookaside buffer contains a particular virtual tag corresponding to the tag bits; a memory structure, receiving the index bits, the memory structure containing second vectors, each second vector indicating at least one location of a physical tag in the translation lookaside buffer, at least one second vector designated by the index bits, wherein each second vector is capable of indicating more than one physical tag when more than one virtual tag in the translation lookaside buffer corresponds to one physical tag in the translation lookaside buffer; at least one vector comparator comparing the second vector from the memory structure to the first vector from the translation lookaside buffer.
Claim 6
Dependent Claim
84 words
The cache of claim 3, the virtual address further comprising page offset bits, the cache further comprising: a second memory structure, receiving the index bits, the second memory structure containing stored page offset bits; at least one offset comparator receiving stored page offset bits from the second memory structure as designated by the index bits and receiving page offset bits from the virtual address; and at least one logic gate receiving an output of the offset comparator and an output of the vector comparator.
Claim 7
Independent Claim
182 words
A method of accessing data in a cache, the method comprising the following steps: receiving, by the cache, a virtual address, the virtual address including a virtual tag and a virtual index; generating a first vector, by a translation lookaside buffer, the first vector having a plurality of bit positions, each bit position in the first vector having a one-to-one correspondence to a location in the translation lookaside buffer, each bit position in the first vector indicating whether the corresponding location in the translation lookaside buffer contains a match to the virtual tag; retrieving, by a first memory structure, from at least one location determined by the virtual index, at least one second vector, each bit position in each second vector having a one-to-one correspondence to a location in the translation lookaside buffer, each bit position in each second vector indicating whether the corresponding location in the translation lookaside buffer contains a particular physical tag; and comparing, by a digital comparator, the first vector and the second vector; and using the result of comparing to select data from a second memory structure.
Claim 8
Independent Claim
182 words
A method of accessing data in a cache, the method comprising the following steps: receiving, by the cache, a virtual address, the virtual address including a virtual tag and a virtual index; generating a first vector, by a translation lookaside buffer, the first vector having a plurality of bit positions, each bit position in the first vector having a one-to-one correspondence to a location in the translation lookaside buffer, each bit position in the first vector indicating whether the corresponding location in the translation lookaside buffer contains a match to the virtual tag; retrieving, by a first memory structure, from at least one location determined by the virtual index, at least one second vector, each bit position in each second vector having a one-to-one correspondence to a location in the translation lookaside buffer, each bit position in each second vector indicating whether the corresponding location in the translation lookaside buffer contains a particular physical tag; and comparing, by a digital comparator, the first vector and the second vector; and using the result of comparing to select data from a second memory structure.
Claim 9
Dependent Claim
70 words
The method of claim 5, the virtual address further comprising page offset bits, the method further comprising: comparing, by a third memory structure, the page offset bits of the virtual address to page offset bits stored in the third memory structure at a location determined by the virtual index; and using the result of comparing by the third memory structure to qualify the result of comparing by the digital comparator.
Claim 10
Dependent Claim
184 words
A cache, the cache receiving a virtual address comprising index bits and tag bits, the cache comprising: a translation-lookaside buffer, the translation lookaside buffer receiving the tag bits and generating a first vector, the first vector having a plurality of bit positions, each bit position in the first vector having a one-to-one correspondence to a location in the translation lookaside buffer, each bit position in the first vector indicating whether the corresponding location in the translation lookaside buffer contains a match to the virtual tag; a memory structure, receiving the index bits, the memory structure containing second vectors, at least one second vector designated by the index bits, each second vector having a plurality of bit positions, each bit position in each second vector having a one-to-one correspondence to a location in the translation lookaside buffer, each bit position in each second vector indicating whether the corresponding location in the translation lookaside buffer contains a match to a particular physical tag; and at least one vector comparator comparing the second vector from the memory structure to the first vector from the translation lookaside buffer.
Claim 11
Dependent Claim
184 words
A cache, the cache receiving a virtual address comprising index bits and tag bits, the cache comprising: a translation-lookaside buffer, the translation lookaside buffer receiving the tag bits and generating a first vector, the first vector having a plurality of bit positions, each bit position in the first vector having a one-to-one correspondence to a location in the translation lookaside buffer, each bit position in the first vector indicating whether the corresponding location in the translation lookaside buffer contains a match to the virtual tag; a memory structure, receiving the index bits, the memory structure containing second vectors, at least one second vector designated by the index bits, each second vector having a plurality of bit positions, each bit position in each second vector having a one-to-one correspondence to a location in the translation lookaside buffer, each bit position in each second vector indicating whether the corresponding location in the translation lookaside buffer contains a match to a particular physical tag; and at least one vector comparator comparing the second vector from the memory structure to the first vector from the translation lookaside buffer.
Claim 12
Dependent Claim
84 words
The cache of claim 7, the virtual address further comprising page offset bits, the cache further comprising: a second memory structure, receiving the index bits, the second memory structure containing stored page offset bits; at least one offset comparator receiving stored page offset bits from the second memory structure as designated by the index bits and receiving page offset bits from the virtual address; and at least one logic gate receiving an output of the offset comparator and an output of the vector comparator.
References Cited (Backward Citations)
US4969122A
Cited
US5133058A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-10 | 2003-07-12 | 2004-01-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-10 | 2007-07-12 | 2008-01-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-10 | 2011-07-12 | 2012-01-11 | $7700.00 | Window Closed / Lapsed |