Patent US4400770A successfully refreshed from Google Patents.
US4400770A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cache synonym detection and handling means
Assignee: International Business Machines Corp
•
Filing: 1980-11-10
•
Granted: 1983-08-23
•
Expires: 2000-11-10
Abstract
Abstract The disclosure detects and handles synonyms for a store-in-cache (SIC). A processor cache directory (PD) is searched in a principle class addressed by a subset of bits taken from a processor request's logical address. The class address has both translatable and non-translatable bits. If any of the set-associative line entries in the principle class contains the request's translated address, the data is accessed in a corresponding line location in the cache. If the principle class does not have any entry with the request's translated address, a cache miss signal occurs which causes a line fetch command to be generated for main storage to fetch the required line. The line fetch command also causes synonym search circuits to generate the address of every potential synonym class by permutating the translatable bits in the principle class address provided in the line fetch command. Then each potential synonym class is accessed in a copy directory (CD) (which is a copy of essential information in all entries in PD) and compared to the translated request address in order to detect for any existing synonym. Each line entry in the PD and CD also has an exclusive (EX) shareability control bit which controls the handling of a request after detection of a synonym in the CD. If the EX bit is off representing a read only (RO) state, the line cannot be locked during any checkpoint interval. Then the data is not accessed in the detected synonym location, but instead the RO line is copied into an entry in the principle class to improve system performance due to subsequent requests expected to the same line. The synonym line is not invalidated unless the processor is requesting the data exclusively (EX). If the EX bit is on representing an exclusive state in a found synonym entry, the line may be locked in the cache during a checkpoint interval, and therefore the data is accessed in the detected synonym location in the SIC because it cannot then be moved.
Inventors
- 👤 Shiu K. Chan
- 👤 John A. Gerardi
- 👤 Bruce L. McGilvray
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 20:28
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
336 words
Cache synonym control means for a data processing system having a store-in-cache (SIC) and an instruction execution unit (IE), comprising: set-associative cache directory means for receiving main storage logical address requests from the IE, address translation means for translating the logical address of an IE request into a requested translated address in main storage, class registering means for addressing classes in the set-associative directory means, the class registering means receiving a subset of bits in the requested logical address for providing a class address for selecting a class in the cache directory means, the subset of bits containing translatable bits and non-translatable bits and defining the address of a principle class, search control means receiving the content of the class registering means and initially searching the cache directory means for the principle class in the class registering means, the search control means generating a miss signal if the translated address is not found in the principle class, address altering means responding to the miss signal by permutating the translatable bits of the principle class to a permutated value, the address altering means providing the permutated value to overlay the translatable bits in the class registering means to generate a synonym class address, additional search control means to control the search in the directory means of each synonym class address provided to the class registering means by the address altering means, means for actuating the address altering means to generate a next permutated value for the class registering means after each class search controlled by the additional search control means, means for capturing any permutated address in the address altering means for which the additional search control means finds the translated address in the cache directory means or indicates the translated address is not found in any synonym class address, and means for accessing the SIC for data located at the permutated address captured by the capturing means, whereby the capturing means detects any synonym class existing in the cache or detects that no synonym class exists.
Claim 2
Dependent Claim
336 words
Cache synonym control means for a data processing system having a store-in-cache (SIC) and an instruction execution unit (IE), comprising: set-associative cache directory means for receiving main storage logical address requests from the IE, address translation means for translating the logical address of an IE request into a requested translated address in main storage, class registering means for addressing classes in the set-associative directory means, the class registering means receiving a subset of bits in the requested logical address for providing a class address for selecting a class in the cache directory means, the subset of bits containing translatable bits and non-translatable bits and defining the address of a principle class, search control means receiving the content of the class registering means and initially searching the cache directory means for the principle class in the class registering means, the search control means generating a miss signal if the translated address is not found in the principle class, address altering means responding to the miss signal by permutating the translatable bits of the principle class to a permutated value, the address altering means providing the permutated value to overlay the translatable bits in the class registering means to generate a synonym class address, additional search control means to control the search in the directory means of each synonym class address provided to the class registering means by the address altering means, means for actuating the address altering means to generate a next permutated value for the class registering means after each class search controlled by the additional search control means, means for capturing any permutated address in the address altering means for which the additional search control means finds the translated address in the cache directory means or indicates the translated address is not found in any synonym class address, and means for accessing the SIC for data located at the permutated address captured by the capturing means, whereby the capturing means detects any synonym class existing in the cache or detects that no synonym class exists.
Claim 3
Dependent Claim
37 words
Cache synonym control means as defined in claim 1, in which the set-associative cache directory means comprises, a processor cache directory (PD), and the additional search control means controlling the search for synonym entries in the PD.
Claim 4
Dependent Claim
168 words
Cache synonym control means as defined in claim 1, further comprising, a plurality of line entries in the set-associative cache directory means associated with corresponding line positions in the SIC, each line position in SIC containing a plurality of word storage positions, an exclusive/readonly (EX) shareability bit position being provided in each line entry to control whether data in the corresponding storage positions in SIC can be duplicated in the respective SIC or in another SIC for another IE in the data processing system, each line entry also containing a high-order position of the translated address assigned to the line entry, the search control means further comprising: means for detecting the state of the EX bit in a synonym line entry when the capturing means detects a synonym class having the requested translated address, whereby the manner of accessing the synonym line in the SIC corresponding to the detected synonym line entry is controlled by the detected state of the EX bit in the detected synonym line entry.
Claim 5
Dependent Claim
105 words
Cache synonym control means as defined in claim 3, in which the search control means further comprises comparator means for comparing the address in each assigned entry in each class selected by the additional search control means, a comparator output of the additional search control means providing an EX compare signal or an RO compare signal for any line entry having the EX bit position in the exclusive or readonly state and having an assigned translated address equal to a corresponding portion of the requested translated address, whereby a synonym line entry is the line entry causing the EX compare signal or RO compare signal.
Claim 6
Dependent Claim
119 words
Cache control means as defined in claim 4, further comprising means for sensing an EX compare signal in the presence of the miss signal being caused by any IE request in order to generate a synonym access signal, means for accessing the requested data in SIC in the synonym line in response to the synonym access signal, and means for cancelling the miss signal to prevent a line fetch in main storage in response to the synonym access signal from the sensing means, whereby an available synonym line is acessed in SIC when a miss signal is generated for an IE fetch or store interrogate request for exclusive or readonly data which finds a synonym line entry marked exclusive.
Claim 7
Dependent Claim
162 words
Cache control means as defined in claim 4, further comprising means for sensing a RO compare signal in the presence of the miss signal being caused by an IE fetch request in order to generate a principle access signal, replacement entry control means assigning an entry location in the principle class of the cache directory for receiving a new entry in response to the miss signal, means for transferring the requested data in SIC from the synonym class location to the principle class location assigned by the replacement entry control means in response to the sensing means providing a principle access signal, means for setting the new entry in the cache directory to represent RO data for the IE fetch request, means for accessing the requested data in SIC at the principle class after operations are completed by the setting means and transferring means, whereby duplicate RO entries exist in the principle and synonym classes in SIC and the cache directory means.
Claim 8
Dependent Claim
180 words
Cache control means s defined in claim 4, further comprising means for sensing a RO compare signal due to a miss signal caused by an IE store interrogate request in order to generate a principle access signal, replacement entry control means assigning an entry location in the principle class of the cache directory for receiving a new entry in response to the miss signal, means for fetching a line in main storage due to the miss signal and placing the fetched line in SIC in the principle class at a line location corresponding to the entry location assigned by the replacement entry control means, means for setting the EX bit position to EX state in the new entry, means for setting invalid the synonym entry indicated by the RO compare signal in response to the principle access signal from the sensing means, means for accessing subsequent requests for data in the same line at the SIC principle class location, whereby the new principle entry is in exclusive state and does not have any synonym entry in the cache directory means.
Claim 9
Dependent Claim
62 words
Cache synonym control means as defined in claims 1, 2, 3, 4, 5, 6 or 7 in which the set-associative cache directory means comprises, a processor cache directory (PD) and a corresponding copy directory (CD) containing a copy of essential information in each entry in the corresponding PD, the additional search control means controlling the searching in the CD for synonym entries.
Claim 10
Dependent Claim
42 words
Cache control means in which the invalidating means in claim 7 further comprises, command means for communicating a line invalidating command from the additional search control means for the CD to PD control means for invalidating the synonym line entry in PD.
Claim 11
Dependent Claim
231 words
Cache synonym control means for a data processing system having a store-in-cache (SIC) and an instruction execution unit (IE), comprising a processor directory (PD) for receiving main storage logical address requests from the IE, address translation means for translating the requested logical addresses to translated addresses, PD control means for searching the PD in a principle class address obtained from a subset of virtual bits and non-translatable bits of a requested logical address and generating a miss signal if the translated logical address is not represented in the principle class, a copy directory (CD) contains a class copy PD line entry although not all information in each PD line entry need be found in each corresponding CD line entry, CD control means actuated by the miss signal for searching each valid set in the CD class accessed by the class address to find the translated address, means for permutating the virtual bits in the class address to a next permuted value after each CD search for the same miss signal to determine a next synonym class to be searched by the CD control means for the translated address, means for capturing the next permuted value as a synonym class address if the translated address is found by the CD control means in the class addressed by the next permuted value, whereby the capturing means detects a synonym class in the SIC.
Claim 12
Dependent Claim
231 words
Cache synonym control means for a data processing system having a store-in-cache (SIC) and an instruction execution unit (IE), comprising a processor directory (PD) for receiving main storage logical address requests from the IE, address translation means for translating the requested logical addresses to translated addresses, PD control means for searching the PD in a principle class address obtained from a subset of virtual bits and non-translatable bits of a requested logical address and generating a miss signal if the translated logical address is not represented in the principle class, a copy directory (CD) contains a class copy PD line entry although not all information in each PD line entry need be found in each corresponding CD line entry, CD control means actuated by the miss signal for searching each valid set in the CD class accessed by the class address to find the translated address, means for permutating the virtual bits in the class address to a next permuted value after each CD search for the same miss signal to determine a next synonym class to be searched by the CD control means for the translated address, means for capturing the next permuted value as a synonym class address if the translated address is found by the CD control means in the class addressed by the next permuted value, whereby the capturing means detects a synonym class in the SIC.
Claim 13
Dependent Claim
193 words
Cache synonym control means as defined in claim 10, further comprising a plurality of corresponding line entries in the PD and CD associated with corresponding line positions in the SIC, each line position in SIC containing a plurality of word storage positions, an exclusive/readonly (EX) shareability control bit position being provided in each line entry in PD and CD to control whether data in the corresponding word storage positions in SIC can be duplicated in the respective SIC or in another SIC for another IE in the data processing system, each line entry in PD and CD also containing a high-order portion of the translated address assigned to the line entry, the search control means further comprising: means for detecting the state of the EX bit position in a synonym line entry in the CD when the capturing means operating under control of the CD control means detects a synonym class having the requested translated address, whereby the manner of accessing the synonym line in the SIC corresponding to the detected synonym line entry is controlled by the detected state of the EX bit position in the detected synonym line entry in CD.
Claim 14
Dependent Claim
107 words
Cache synonym control means as defined in claim 11, in which the CD control means further comprises, comparator means connected to CD for comparing the address in each assigned entry in each class selected by the CD control means, a comparator output of the CD control means providing an EX compare signal or an RO compare signal for any line entry having the EX bit state in the exclusive or readonly state respectively and having an assigned translated address equal to a corresponding portion of the requested translated address, whereby a synonym line entry is the line entry causing the EX compare signal or RO compare signal.
Claim 15
Dependent Claim
181 words
Cache control means as defined in claim 12, the CD control means further comprising means for sensing an EX compare signal from the comparator means in the presence of the miss signal being caused by any IE request in order to generate a synonym access signal, means for communicating to the PD control means in the directory location of the synonym line entry found in CD for accessing the requested data in SIC in the synonym line in response to the synonym access signal, and the CD control means also concurrently providing a line fetch request signal to main storage in response to a miss signal from the PD control means, means for cancelling the line fetch request signal to main storage to prevent a line fetch from main storage in response to the sensing means providing the synonym access signal, and means for accessing the IE request at the synonym line location in SIC when a miss signal is generated for an IE fetch or store interrogate request for exclusive or readonly data which finds an exclusive synonym line entry.
Claim 16
Dependent Claim
182 words
Cache control means as defined in claim 12, further comprising the PD control means further including: replacement entry control means assigning an entry location in the principle class for receiving a new entry, the CD control means further including: means for sensing a RO compare signal with the CD control means from the comparator means in the presence of the miss signal being caused by an IE fetch request in order to generate a principle access signal, means for fetching a line in main storage due to the miss signal and placing the fetched line in SIC in the principle class at a line location corresponding to the entry location assigned by the replacement entry control means, means for accessing the requested data in SIC in the fetched line in SIC in the principle class in response to the sensing means providing a principle class signal; and communicating means for setting the EX bit in the new entry to RO state in both PD and CD, whereby duplicate RO entries exist in the principle and synonym classes in the cache directory means.
Claim 17
Dependent Claim
182 words
Cache control means as defined in claim 12, further comprising, the PD control means further including: replacement entry control means assigning an entry location in the principle class for receiving a new entry, the CD control means further including: means for sensing a RO compare signal due to a miss signal caused by an IE store interrogate request in order to generate a principle access signal, means for fetching a line in main storage due to the miss signal and placing the fetched line in SIC in the principle class at a line location corresponding to the entry location assigned by the replacement entry control means, means for invalidating the synonym line entry in response to the principle class signal, and means for accessing subsequently requested data in SIC at the same line address in the fetched line in SIC in the principle class in response to the sensing means providing a principle class signal, whereby the new line entry has its EX bit set to exclusive state and it does not have any duplicate line entry in the cache directory means.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1986-08-22 | 1987-02-21 | 1987-08-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1990-08-22 | 1991-02-21 | 1991-08-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1994-08-22 | 1995-02-21 | 1995-08-23 | $7700.00 | Window Closed / Lapsed |