US5778427A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for selecting a way of a multi-way associative cache by storing waylets in a translation structure
Assignee: Oracle America Inc
•
Filing: 1995-07-07
•
Granted: 1998-07-07
•
Expires: 2015-07-07
Abstract
Abstract The present invention provides a cache manager (CM) for use with an address translation table (ATT) which take advantage of way information, available when a cache line is first cached, for efficiently accessing a multi-way cache of a computer system having a main memory and one or more processors. The main memory and the ATT are page-oriented while the cache is organized using cache lines. The cache includes a plurality of cache lines divided into a number of segments corresponding to the number of "ways". Each cache line includes an address tag (AT) field and a data field. The way information is stored in the ATT for later cache access. In this implementation, "waylets" provide an efficiency mechanism for storing the way information whenever a cache line is cached. Accordingly, each table entry of the ATT includes a virtual address (VA) field, a physical address (PA) field, and a plurality of waylets associated with each pair of VA and PA fields. Subsequently, the waylets can be used to quickly index directly into a single segment of the cache as follows. Upon receiving a virtual address of a target cache line, the CM attempts to match a virtual address field of one of the ATT entries with a page index portion of the virtual address. If there is a match, a waylet of the ATT entry is retrieved using a page offset portion of the virtual address. If the waylet value is valid, the CM indexes directly into a single cache line using the waylet value, the physical address field of the ATT entry and the page offset portion of the virtual address. If the AT field of the retrieved cache line matches with a portion of the physical address field of the ATT entry, the processor retrieves the data field of the cache line using the page offset portion of the VA. If the AT field does not match, the target cache line is retrieved from the main memory, and the waylet value in both the ATT and the main memory is updated.
Inventors
- 👤 Erik Hagersten
- 👤 Ashok Singhal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:59
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/10; G06F12/1027; G06F12/1045; G06F12/1054; G06F12/0802; G06F12/0864; G06F2212/00; G06F2212/60; G06F2212/608; G06F2212/6082
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
138 words
A method of accessing a multi-way cache associated with a computer system having a processor and a main memory, the method comprising the steps of: receiving a virtual address of a target cache line, the virtual address of said target cache line having a page index portion and a page offset portion; matching a virtual address field of an address translation table (ATT) entry with said page index portion; retrieving a waylet of said ATT entry using the page offset portion; indexing into a single cache line of said multi-way cache using said waylet, a physical address field of said ATT entry and said page offset portion; matching an address tag (AT) field of said single cache line with said physical address field; and retrieving a data field of said single cache line using said page offset portion.
Claim 2
Independent Claim
138 words
A method of accessing a multi-way cache associated with a computer system having a processor and a main memory, the method comprising the steps of: receiving a virtual address of a target cache line, the virtual address of said target cache line having a page index portion and a page offset portion; matching a virtual address field of an address translation table (ATT) entry with said page index portion; retrieving a waylet of said ATT entry using the page offset portion; indexing into a single cache line of said multi-way cache using said waylet, a physical address field of said ATT entry and said page offset portion; matching an address tag (AT) field of said single cache line with said physical address field; and retrieving a data field of said single cache line using said page offset portion.
Claim 3
Dependent Claim
52 words
The method of claim 1 wherein said step of matching the virtual address field includes the step of: retrieving the content of said ATT entry from the main memory; selecting an old ATT entry for write-back to the main memory; and writing back said selected old ATT entry to the main memory.
Claim 4
Dependent Claim
60 words
The method of claim 1 wherein said step of matching said AT field includes the steps of: retrieving the content of said single cache line from the main memory and updating said waylet; selecting an old cache line of the multi-way cache for write-back to the main memory; and writing back said selected old cache line to the main memory.
Claim 5
Independent Claim
69 words
A method of tagging a multi-way cache useful in association with a computer system having a processor and a main memory, said method comprising the steps of: storing an identifier associated with at least one cache line of said multi-way cache; and associatively storing way information of said one cache line, said way information identifying a particular way within said multi-way cache in which said cache line is stored.
Claim 6
Independent Claim
69 words
A method of tagging a multi-way cache useful in association with a computer system having a processor and a main memory, said method comprising the steps of: storing an identifier associated with at least one cache line of said multi-way cache; and associatively storing way information of said one cache line, said way information identifying a particular way within said multi-way cache in which said cache line is stored.
Claim 7
Dependent Claim
29 words
The method of claim 4 wherein said way information is a waylet, and a cache line address and said waylet are stored in an address translation table (ATT) entry.
Claim 8
Dependent Claim
69 words
The method of claim 5 wherein said step of storing said identifier of said one cache line includes the steps of: storing a page index portion of said virtual address of said one cache line in a virtual address field of said ATT entry; and associatively storing a page index portion of said physical address of said one cache line in a physical address field of said ATT entry.
Claim 9
Independent Claim
193 words
A method of tagging a multi-way cache useful in association with a computer system having a processor and a main memory, said method comprising the steps of: storing an identifier associated with at least one cache line of said multi-way cache wherein said step of storing said identifier of said one cache line includes the steps of: storing a page index portion of a virtual address of said one cache line in a virtual address field of said ATT entry; and associatively storing a page index portion of a physical address of said one cache line in a physical address field of said ATT entry; associatively storing way information of said one cache line, wherein said way information is a waylet, and a corresponding cache line address and said waylet are stored in an address translation table (ATT) entry; receiving a virtual address of a target cache line, the virtual address of said target cache line having a page index portion and a page offset portion; matching said virtual address field of said ATT entry with said page index portion; and retrieving said waylet from said ATT entry using the page offset portion.
Claim 10
Independent Claim
193 words
A method of tagging a multi-way cache useful in association with a computer system having a processor and a main memory, said method comprising the steps of: storing an identifier associated with at least one cache line of said multi-way cache wherein said step of storing said identifier of said one cache line includes the steps of: storing a page index portion of a virtual address of said one cache line in a virtual address field of said ATT entry; and associatively storing a page index portion of a physical address of said one cache line in a physical address field of said ATT entry; associatively storing way information of said one cache line, wherein said way information is a waylet, and a corresponding cache line address and said waylet are stored in an address translation table (ATT) entry; receiving a virtual address of a target cache line, the virtual address of said target cache line having a page index portion and a page offset portion; matching said virtual address field of said ATT entry with said page index portion; and retrieving said waylet from said ATT entry using the page offset portion.
Claim 11
Dependent Claim
32 words
The method of claim 7 further comprising the step of indexing into said one cache line using said waylet, the physical address field of said ATT entry and said page offset portion.
Claim 12
Dependent Claim
55 words
The method of claim 8 further comprising the steps of: matching an address tag (AT) field of said one cache line with a portion of said physical address field of said ATT entry; retrieving a data field of said one cache line using said page offset portion; and providing said data field to said processor.
Claim 13
Dependent Claim
54 words
The method of claim 7 wherein said step of matching the virtual address field of said ATT entry includes the step of: retrieving the content of said ATT entry from the main memory; selecting an old entry for write-back to the main memory; and writing back said selected old entry to the main memory.
Claim 14
Dependent Claim
60 words
The method of claim 9 wherein said step of matching said AT field includes the steps of: retrieving the content of said one cache line from the main memory and updating said waylet; selecting an old cache line of the multi-way cache for write-back to the main memory; and writing back said selected old cache line to the main memory.
Claim 15
Independent Claim
85 words
A method of retrieving a cache line from a multi-way cache useful in association with a computer system having a processor and a main memory, said method comprising the steps of: receiving an address of a target cache line, the address of said target cache line having a page index portion and a page offset portion; matching a first address field of a tagging table entry with said page index portion; and retrieving way information from said tagging table entry using the page offset portion.
Claim 16
Independent Claim
85 words
A method of retrieving a cache line from a multi-way cache useful in association with a computer system having a processor and a main memory, said method comprising the steps of: receiving an address of a target cache line, the address of said target cache line having a page index portion and a page offset portion; matching a first address field of a tagging table entry with said page index portion; and retrieving way information from said tagging table entry using the page offset portion.
Claim 17
Dependent Claim
48 words
The method of claim 12 wherein said tagging table entry is an address translation table (ATT) entry, said way information is a waylet, said address of said target cache line is a virtual address, and said first address field of said ATT entry is a virtual address field.
Claim 18
Dependent Claim
31 words
The method of claim 13 further comprising the step of indexing into said cache line using said waylet, the physical address field of said ATT entry and said page offset portion.
Claim 19
Dependent Claim
53 words
The method of claim 14 further comprising the steps of: matching an address tag (AT) field of said cache line with a portion of said physical address field of said ATT entry; retrieving a data field of said cache line using said page offset portion; and providing said data field to said processor.
Claim 20
Dependent Claim
54 words
The method of claim 13 wherein said step of matching the virtual address field of said ATT entry includes the step of: retrieving the content of said ATT entry from the main memory; selecting an old entry for write-back to the main memory; and writing back said selected old entry to the main memory.
Claim 21
Dependent Claim
59 words
The method of claim 15 wherein said step of matching said AT field includes the steps of: retrieving the content of said cache line from the main memory and updating said waylet; selecting an old cache line of the multi-way cache for write-back to the main memory; and writing back said selected old cache line to the main memory.
Claim 22
Dependent Claim
94 words
A tagging table for accessing a multi-way cache associated with a computer system having a processor and a main memory, said cache having a plurality of cache lines divided into two or more segments corresponding to the number of ways of said multi-way cache, wherein said tagging table comprises: a plurality of entries, each table entry including: an identifier field; and a way information field associatively coupled to said identifier field, for indexing to one of said segments wherein said one of said segments is storing a cache line identified by said table entry.
Claim 23
Dependent Claim
94 words
A tagging table for accessing a multi-way cache associated with a computer system having a processor and a main memory, said cache having a plurality of cache lines divided into two or more segments corresponding to the number of ways of said multi-way cache, wherein said tagging table comprises: a plurality of entries, each table entry including: an identifier field; and a way information field associatively coupled to said identifier field, for indexing to one of said segments wherein said one of said segments is storing a cache line identified by said table entry.
Claim 24
Dependent Claim
41 words
The tagging table of claim 18 wherein said tagging table is an address translation table (ATT), said way information field includes a waylet, and said identifier field of said ATT entry includes a virtual address field and a physical address field.
Claim 25
Dependent Claim
19 words
The tagging table of claim 18 wherein said tagging table is incorporated with said processor on an integrated circuit.
Claim 26
Dependent Claim
114 words
A computer-readable memory that can be used to direct a processor to control execution of a procedure having a sequence of steps for accessing a multi-way cache, said computer-readable memory comprising: a tagging table having a plurality of entries, each entry including an identifier field and a way information field; and a cache manager (CM) configured to: receive an address of a target cache line, the address of said target cache line having a page index portion and a page offset portion; match the identifier field of one said entry of the tagging table with said page index portion; and retrieve the way information field of said one entry using the page offset portion.
Claim 27
Dependent Claim
114 words
A computer-readable memory that can be used to direct a processor to control execution of a procedure having a sequence of steps for accessing a multi-way cache, said computer-readable memory comprising: a tagging table having a plurality of entries, each entry including an identifier field and a way information field; and a cache manager (CM) configured to: receive an address of a target cache line, the address of said target cache line having a page index portion and a page offset portion; match the identifier field of one said entry of the tagging table with said page index portion; and retrieve the way information field of said one entry using the page offset portion.
Claim 28
Dependent Claim
52 words
The computer-readable memory of claim 21 wherein said tagging table is an address translation table (ATT), said way information field is a waylet, said address of said target cache line is a virtual address, and said identifier field of said one entry includes a virtual address field and a physical address field.
Claim 29
Dependent Claim
39 words
The computer-readable memory of claim 22 wherein said cache manager is further configured to index into a cache line of said multi-way cache using said waylet, said physical address field of said one entry and said page offset portion.
Claim 30
Dependent Claim
57 words
The computer-readable memory of claim 23 wherein said cache manager is further configured to: match an address tag (AT) field of said cache line with a portion of said physical address field of said one entry; retrieve a data field of said cache line using said page offset portion; and provide said data field to said processor.
Claim 31
Dependent Claim
120 words
A computer system comprising: a processor coupled to said multi-way cache, said processor including: a tagging table having a plurality of entries, each entry including an identifier field and a way information field; and a cache manager (CM) configured to: receive an address of a target cache line, the address of said target cache line having a page index portion and a page offset portion; match the address field of one said entry of the tagging table with said page index portion; and retrieve the way information field of said one entry using the page offset portion, a multi-way cache coupled to said processor; a system interconnect coupled to said processor; and a main memory coupled to said system interconnect.
Claim 32
Dependent Claim
120 words
A computer system comprising: a processor coupled to said multi-way cache, said processor including: a tagging table having a plurality of entries, each entry including an identifier field and a way information field; and a cache manager (CM) configured to: receive an address of a target cache line, the address of said target cache line having a page index portion and a page offset portion; match the address field of one said entry of the tagging table with said page index portion; and retrieve the way information field of said one entry using the page offset portion, a multi-way cache coupled to said processor; a system interconnect coupled to said processor; and a main memory coupled to said system interconnect.
Claim 33
Dependent Claim
52 words
The computer system of claim 25 wherein said tagging table is an address translation table (ATT), said way information field is a waylet, said address of said target cache line is a virtual address, and said identifier field of said one entry includes a virtual address field and a physical address field.
Claim 34
Dependent Claim
39 words
The computer system of claim 26 wherein said cache manager is further configured to index into a cache line of said multi-way cache using said waylet, said physical address field of said one entry and said page offset portion.
Claim 35
Dependent Claim
57 words
The computer system of claim 27 wherein said cache manager is further configured to: match an address tag (AT) field of said cache line with a portion of said physical address field of said one entry; retrieve a data field of said cache line using said page offset portion; and provide said data field to said processor.
Claim 36
Dependent Claim
45 words
The computer system of claim 26 wherein said cache manager is further configured to: retrieve the content of said one entry from the main memory; select an old entry for write-back to the main memory; and write-back said selected old entry to the main memory.
Claim 37
Dependent Claim
55 words
The computer system of claim 28 wherein said cache manager is further configured to: retrieve the content of said cache line from the main memory and updating said waylet; select an old cache line of the multi-way cache for write-back to the main memory; and write-back said selected old cache line to the main memory.
References Cited (Backward Citations)
US5055999A
Cited
US5297265A
Cited
US5341483A
Cited
US5369753A
Cited
US5235697A
Cited
US5418922A
Cited
US5640532A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-06 | 2002-01-05 | 2002-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-06 | 2006-01-05 | 2006-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-06 | 2010-01-05 | 2010-07-07 | $7700.00 | Window Closed / Lapsed |