EP0069250A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Replacement control for second level cache entries
Assignee: International Business Machines Corp
•
Filing: 1982-06-15
•
Granted: —
•
Expires: 2002-06-15
Abstract
Abstract The replacement selection of entries in a second level (L2) cache directory of a storage hierarchy is controlled using replaced and hit addresses of a dynamic look-aside translation buffer (DLAT) at the first level (L1) in the hierarchy which receives CPU storage requests along with the CPU cache and its directory. The DLAT entries address page size blocks in main storage (MS). The disclosure provides a replacement (R) flag for each entry in the L2 directory, which represents a page size block in the L2 cache. An R bit is selected and turned on by the address of a DLAT replaced page which is caused by a DLAT miss to indicate its associated page is a candidate for replacement in the L2 cache. However, the page may continue to be accessed in the L2 cache until it is actually replaced. An R bit is selected and turned off by a CPU request address causing a DLAT hit and a L1 cache miss to indicate its associated L2 page is not a candidate for replacement. When a small proportion of CPU requests bypass of the DLAT (e.g. real address requests), a L1 request address having a Ll cache miss may be used to turn off the R bit, and any replaced line address may be used to turn on the R bit, for the L2 entry selected by that address. L2 LRU replacement selection circuits generate a LRU pointer to another entry in the congruence class of the selected entry when its R flag is change from a no replacement state to a replacement state. Each turn off signal to an R flag may generate a new LRU pointer for its congruence class which also points away from the selected entry.
Inventors
- 👤 Robert Percy Fletcher
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 22:52
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0893; G06F12/0897; G06F12/10; G06F12/1027; G06F12/1045; G06F12/1063; G06F12/12; G06F12/121; G06F12/128
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
241 words
A method for controlling data replacement in an intermediate cache (L2; 19) in a storage hierarchy providing data from main storage (MS; 21) for a CPU (10) making storage requests to a dynamic look-aside translation buffer (DLAT; 14) which contains translations of virtual page addresses to main storage page addresses, a CPU cache (Ll; 18) for receiving the CPU storage requests and having a CPU directory (17) with entries for addressing subpage data units in the CPU cache, the intermediate cache having an intermediate directory (16) with entries for addressing page data in the intermediate cache and transferring subpage data units to the CPU cache in response to a CPU cache miss of a CPU storage request, the DLAT generating a hit signal when the DLAT contains a CPU requested virtual address and its translated MS address, and the DLAT generating a miss signal when the DLAT does not contain the CPU requested virtual address; the DLAT, CPU cache and intermediate cache, each having a replacement selection means (24; 27; 28) of the least recently used (LRU) type, the method characterized by: communicating DLAT replaced addresses to the replacement selection means (28) for the intermediate cache (19) and the intermediate directory (16), and controlling the reaction time of the replacement selection means (28) for the intermediate cache (L2) to prevent the immediate replacement of an entry in the intermediate directory selected by the DLAT replaced address provided by the communicating step.
Claim 2
Independent Claim
241 words
A method for controlling data replacement in an intermediate cache (L2; 19) in a storage hierarchy providing data from main storage (MS; 21) for a CPU (10) making storage requests to a dynamic look-aside translation buffer (DLAT; 14) which contains translations of virtual page addresses to main storage page addresses, a CPU cache (Ll; 18) for receiving the CPU storage requests and having a CPU directory (17) with entries for addressing subpage data units in the CPU cache, the intermediate cache having an intermediate directory (16) with entries for addressing page data in the intermediate cache and transferring subpage data units to the CPU cache in response to a CPU cache miss of a CPU storage request, the DLAT generating a hit signal when the DLAT contains a CPU requested virtual address and its translated MS address, and the DLAT generating a miss signal when the DLAT does not contain the CPU requested virtual address; the DLAT, CPU cache and intermediate cache, each having a replacement selection means (24; 27; 28) of the least recently used (LRU) type, the method characterized by: communicating DLAT replaced addresses to the replacement selection means (28) for the intermediate cache (19) and the intermediate directory (16), and controlling the reaction time of the replacement selection means (28) for the intermediate cache (L2) to prevent the immediate replacement of an entry in the intermediate directory selected by the DLAT replaced address provided by the communicating step.
Claim 3
Dependent Claim
53 words
A method for controlling data replacement in an intermediate cache as defined in Claim 1, characterized in that the controlling step generates a LRU candidate pointer for a selected congruence class in the intermediate directory (L2) to point away from the entry selected by the DLAT replaced address provided by the communicating step.
Claim 4
Dependent Claim
86 words
A method for controlling data replacement in an intermediate cache as defined in Claim 1 or 2, characterized in that a DLAT hit address having a miss in the CPU directory is also communicated to the intermediate directory and that I the controlling step also generates a LRU candidate pointer to a LRU entry in the selected congruence class in the replacement selection means (28) for the intermediate directory to point away from the entry selected by the DLAT hit address provided by the communicating step.
Claim 5
Dependent Claim
59 words
A method for controlling data replacement in an intermediate cache as defined in Claim 3, characterized in that the controlling step is prevented from generating a candidate pointer when the communicating step makes a second communication of the DLA T replaced address without an intervening communication of a DLAT hit address to the same entry in the intermediate directory.
Claim 6
Dependent Claim
77 words
A method for controlling data replacement in an intermediate cache as defined in Claim 3 or 4, characterized in that a replacement flag (R flag) is turned on with an entry in the intermediate directory selected by the DLAT replaced address, caused by a miss in the DLAT of a CPU storage request, and a replacement flag is turned off with an entry in the intermediate directory selected by the DLAT hit address, caused-by a DLAT hit.
Claim 7
Independent Claim
88 words
A method for controlling data replacement in an intermediate cache as defined in one of the Claims 1-4, characterized in that a replacement flag is also turned off with an intermediate directory entry selected by a CPU request that bypasses the DLAT and has a miss in the CPU directory, a replacement flag is also turned on with an intermediate directory entry selected by a replaced address in the CPU directory in response to a miss in the CPU directory by a CPU request that bypasses the DLAT.
Claim 8
Dependent Claim
255 words
Storage hierarchy for a data processing system, containing at least one CPU having a first level (Ll) cache with a Ll directory for receiving all storage requests by the CPU and having a dynamic look-aside translator (DLAT) for receiving all translations of virtual storage requests by the CPU, the Ll directory and the DLAT each having a least recently used (LRU) replacement selection means, the hierarchy having a main storage (MS), comprising: a second level (L2; 19) cache for storing the same size storage unit that is addressed by the DLAT (14), a second level (L2; 16) directory having a plurality of entries respectively associated with different storage units in the L2 cache, characterized in that it comprises a replacement flag (R flag) being provided for each entry in the L2 cache directory (16) and having a replacement state for indicating the entry is a replacement candidate in the L2 cache and having a non-replacement state for indicating the entry is not a replacement candidate, first means (Fig. 12) for signalling from Ll to L2 a storage address (Fig. 10) replaced in the DLAT to select an entry in the L2 directory for setting the replacement flag for the selected entry to the replacement state, second means (Fig. 11) for signalling from Ll to L2 a storage address (Fig. 10) having a hit in the DLAT and a miss in the Ll cache to select an entry in the L2 cache directory for setting the replacement flag for the selected entry to a non-replacement state.
Claim 9
Dependent Claim
255 words
Storage hierarchy for a data processing system, containing at least one CPU having a first level (Ll) cache with a Ll directory for receiving all storage requests by the CPU and having a dynamic look-aside translator (DLAT) for receiving all translations of virtual storage requests by the CPU, the Ll directory and the DLAT each having a least recently used (LRU) replacement selection means, the hierarchy having a main storage (MS), comprising: a second level (L2; 19) cache for storing the same size storage unit that is addressed by the DLAT (14), a second level (L2; 16) directory having a plurality of entries respectively associated with different storage units in the L2 cache, characterized in that it comprises a replacement flag (R flag) being provided for each entry in the L2 cache directory (16) and having a replacement state for indicating the entry is a replacement candidate in the L2 cache and having a non-replacement state for indicating the entry is not a replacement candidate, first means (Fig. 12) for signalling from Ll to L2 a storage address (Fig. 10) replaced in the DLAT to select an entry in the L2 directory for setting the replacement flag for the selected entry to the replacement state, second means (Fig. 11) for signalling from Ll to L2 a storage address (Fig. 10) having a hit in the DLAT and a miss in the Ll cache to select an entry in the L2 cache directory for setting the replacement flag for the selected entry to a non-replacement state.
Claim 10
Dependent Claim
122 words
Storage hierarchy as defined in Claim 7, characterized in that it comprises a L2 LRU replacement means (28) for the L2 directory to determine which entry is to be next replaced in a class when all entries in the class indicate valid data in the L2 cache, means (Fig. 14) for detecting a change of state of a replacement flag for an entry currently being signalled by the first means or the second means, means (Fig. 15) for activating the L2 LRU replacement means to generate a LRU pointer to a replacement candidate entry in a selected class of entries when the detecting means signals the change of state, the LRU pointer pointing away from the entry having the change of state.
Claim 11
Dependent Claim
57 words
Storage hierarchy as defined in Claim 7 or 8, characterized in that it comprises means (UPDATE-line; Fig. 14) for inhibiting the L2 LRU replacement means from generating a LRU pointer for the selected class when the detecting means receives a signal from the first signalling means which does not change an existing replacement state of the entry.
Claim 12
Dependent Claim
58 words
Storage hierarchy as defined in one of the Claims 7-9, characterized in that it comprises means (UPDATE-Line; Fig. 14) for enabling the L2 LRU replacement means to generate a LRU pointer for the selected class when the detecting means receives a signal from the second signalling means which does not change an existing non-replacement state for the entry.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.