Patent EP0036110A2 successfully refreshed from Google Patents.
EP0036110A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Cache addressing mechanism
Assignee: International Business Machines Corp
•
Filing: 1981-02-25
•
Granted: —
•
Expires: 2001-02-25
Abstract
Abstract The specification describes a fast synonym detection and handling mechanism for a cache (311) utilizing virtual addressing in data processing systems. The cache directory (309) is divided into 2 N groups of classes, in which N is the number of cache address bits derived from the translatable part (PX) of a requested logical address in register (301). The cache address part derived from the non-translatable part of the logical address, i.e. real part (D) is used to simultaneously access 2 N classes, each in a different group. All class entries are simultaneously compared with one or more DLAT (307) translated absolute addresses. Compare signals, one for each class entry per DLAT absolute address, are routed to a synonym detection circuit (317). The detection circuit simultaneously interprets all directory compare signals and determines if a principle hit, synonym hit or a miss occurred in the cache (309) for each request. If a synonym hit is detected, group identifier (GID) bits are generated to select the data in the cache at the synonym class location. To generate the synonym cache address, the group identifier bits are substituted for the translatable bits in the cache address for locating the required synonym class. For a set-associative cache, set identifier (SID) bits are simultaneously generated for cache addressing.
Inventors
- 👤 Benedicto Umberto Messina
- 👤 William Dean Silkman
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-27 20:08
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/10; G06F12/1027; G06F12/1045; G06F12/1054
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
293 words
A cache addressing mechanism including a cache; a cache- directory containing a main storage address for each subgroup of data validly in said cache; a dynamic lookaside address translation buffer (DLAT) containing the most recently translated page addresses; a request address register for receiving a logical address provided with each request for a main storage access, each request address including both a page address field and a real address field, and parts of the request address in the request address register being used to simultaneously address said cache, said cache directory, and said DLAT; characterised in that the cache address contains N virtual bits taken from the low-order end of the page address field and real bits taken from the high-order end of the real address field; and in that the cache addressing mechanism comprises means for accessing simultaneously and in parallel all pertinent classes in the directory using only the real bits in the cache address to access 2N classes of directory entries, address compare means for comparing each valid entry in the accessed 2N classes with output signals from the DLAT to determine if any hit exists in any accessed class in the cache, a principle class being defined by the N low-order bits in the page address field of the request address, and the other classes of the 2N classes being synonym classes, decision logic means receiving the output of the address compare means for signalling when principle hit occurs in the principle class or a synonym hit occurs in one of the synonym classes, encoding means for providing a group identifier of N bits for the class having a hit, and cache addressing means combining the group identifier and the real address field to address data in the cache.
Claim 2
Dependent Claim
293 words
A cache addressing mechanism including a cache; a cache- directory containing a main storage address for each subgroup of data validly in said cache; a dynamic lookaside address translation buffer (DLAT) containing the most recently translated page addresses; a request address register for receiving a logical address provided with each request for a main storage access, each request address including both a page address field and a real address field, and parts of the request address in the request address register being used to simultaneously address said cache, said cache directory, and said DLAT; characterised in that the cache address contains N virtual bits taken from the low-order end of the page address field and real bits taken from the high-order end of the real address field; and in that the cache addressing mechanism comprises means for accessing simultaneously and in parallel all pertinent classes in the directory using only the real bits in the cache address to access 2N classes of directory entries, address compare means for comparing each valid entry in the accessed 2N classes with output signals from the DLAT to determine if any hit exists in any accessed class in the cache, a principle class being defined by the N low-order bits in the page address field of the request address, and the other classes of the 2N classes being synonym classes, decision logic means receiving the output of the address compare means for signalling when principle hit occurs in the principle class or a synonym hit occurs in one of the synonym classes, encoding means for providing a group identifier of N bits for the class having a hit, and cache addressing means combining the group identifier and the real address field to address data in the cache.
Claim 3
Dependent Claim
51 words
A cache addressing mechanism as defined in Claim 1, the decision logic means further comprising: synonym means for signalling a synonym hit when a principle class means determines no principle hit exists in the principle class and the decision logic means determines a hit exists in any of the 2N classes.
Claim 4
Dependent Claim
107 words
A cache addressing mechanism as defined in Claim 2, the decision logic means further comprising: a synonym signal being indicated by the decision logic means, and the encoding means generating a group identifier for the class causing the hit signal, means for substituting the group identifier from the encoding means for the N bits in the cache address used to access the principle class in the decision logic means in response to the synonym hit signal and means for actuating a principle hit type of cache access, whereby accessed data in the cache may be in either the principle class or any synonym class for the request.
Claim 5
Dependent Claim
21 words
A cache addressing mechanism as defined in Claims 1, 2 or 3, in which the cache directory and cache are set-associative.
Claim 6
Dependent Claim
33 words
A cache addressing mechanism as defined in Claim 4, in which each entry in the cache directory represents the address of a line of double words in main storage on a line boundary.
Claim 7
Dependent Claim
151 words
A cache addressing mechanism as defined in claim 1, wherein: the cache directory is organized with 2 N groups of addressable classes, the access means comprises a plurality of group addressing means connected to the directory for respectively addressing the different groups in the directory, the real bits in the directory being connected to an input of each group addressing means to access one class in each of the groups, there being 2 N groups addressed simultaneously in the directory, and.the address compare means comprises means means for comparing each address in each accessed class with each address provided from the DLAT by the same request, the compare means providing a compare output for each address comparison, there being K2 N number of compare outputs from the directory in which K is an integer equal to the set-associativity of the directory and K equals one if the directory is not set-associative.
Claim 8
Dependent Claim
39 words
A cache addressing mechanism as defined in Claim 6, the cache directory comprising: at least one LSI chip for each unit of set associativity in the cache directory, each LSI chip formed with 2 N groups of addressable classes.
Claim 9
Dependent Claim
35 words
A cache addressing mechanism as defined in Claim 7, each LSI chip comprising: a comparator structure on each LSI chip including the compare means for all addresses accessed from all groups on the same chip.
Claim 10
Dependent Claim
229 words
A cache addressing mechanism as defined in Claim 6, wherein: the decision logic means has a principle group decoder, and has a gating group for each set in the directory, the decoder receiving the N virtual bits of the request address and providing 2 N decoder outputs, each gating group having a principle hit gating means receiving the 2 N decoder outputs and all compare outputs for a respective set from the compare means as well as receiving each logical hit signal from the DLAT, the output of the principle hit gating means indicating if a principle hit exists, each gating group also having 2 N group hit detecting means, each group hit detecting means receiving the compare outputs for the respective set and receiving each logical hit signal from the DLAT, the output of each group hit detecting means indicating if a hit exists in the respective group in the set, any hit detecting means ORing the outputs of all group hit detecting means to indicate any hit in the cache directory, principle hit detecting means ORing the outputs of all principle hit gating means to indicate if a principle hit exists in any set, and synonym decoding means ANDing the outputs of the any hit detecting means and an inverted output of the principle hit detecting means to indicate if a synonym hit exists in the directory.
Claim 11
Dependent Claim
198 words
1 0 . A cache addressing mechanism as defined in Claim 9, the decision logic means further comprising: hit determination means receiving the compare outputs from the directory and receiving a DLAT found signal for each set, each DLAT found signal indicating that the request had an address translation found in the DLAT, the hit determination means having a first plurality of gates receiving the compare outputs and the DLAT found signal, a cache hit being indicated by activations of any gate in the first plurality, a principle decoder receiving theN bits of the request, the hit determination means having a second plurality of gates respectively and the compare outputs and the DLAT found signals to indicate if a principle hit was found, synonym hit detection means comprising first OR circuitry receiving the outputs of the first plurality of gates for indicating any cache hit, and second OR circuitry receiving the outputs of the second plurality of gates for indicating a principle hit, decoding circuitry receiving outputs from the first and second OR circuitry to indicate a synonym hit when the first OR circuitry provides an output and no output is being provided by the second OR circuitry.
Claim 12
Dependent Claim
58 words
A cache addressing mechanism as defined in Claim 9, further comprising: a group identifier (GID) control means having 2 N number of OR circuits, each OR circuit receiving the outputs of all of the group hit detecting means for a respective group, the output of the group identifier control means generating a group identifier signal for each group.
Claim 13
Dependent Claim
37 words
A cache addressing mechanism as defined in Claim 11, further comprising: group identifier (GID) encoder means receiving the outputs for each group from the group identifier control means and encoding the groups into a combinatorial GID signal.
Claim 14
Dependent Claim
59 words
A cache addressing mechanism as defined in Claim 12, further comprising: a set identifier (SID) control means having K number of OR circuits, each OR circuit receiving the outputs of all of the group hit detecting means for a respective set, the output of the set identifier control means generating an any hit set identifier signal for each set.
Claim 15
Dependent Claim
42 words
A cache addressing mechanism as defined in Claim 13, further comprising: set identifier (SID) encoder means receiving the any hit SID outputs for all sets from each set identifier control means and encoding the sets into a combinatorial any hit SID signal.
Claim 16
Dependent Claim
57 words
A cache addressing mechanism as defined in Claim 12, further comprising: a group select OR circuit for providing the high-order bits of the cache address to select a required class in the cache, GID gating means enabled by synonym hit signal to connect the GID signal from the GID encoder means to the group select OR circuit.
Claim 17
Dependent Claim
62 words
A cache addressing mechanism as defined in Claim 15, further comprising: a data real addressing circuit for providing the low-order bits of the cache address to select data in the required class in the cache, real bit gating means enabled by a synonym hit signal for transferring bits from the real address field of the request to the data real addressing circuit.
Claim 18
Dependent Claim
70 words
A cache addressing mechanism as defined in Claim 16, further comprising: a push down address register (PDAR) receiving real address bits from the request register during a next cycle after a request cycle, the real bit gating means being enabled by a synonym hit signal on the next cycle, whereby requestor data is stored in the cache at a synonym location on the second cycle after a request is received.
Claim 19
Dependent Claim
147 words
A cache addressing mechanism as defined in Claim 12, further comprising: a re-do fetch address.register (RFAR) receiving a request address on a next cycle after the request is received by the request address register, a RFAR request trigger being set by a synonym hit signal from the decision logic means during a fetch request, a request priority circuit receiving requests for inputs to the request address register including the set output from the .RFAR request trigger to select the next requesting input allowed to the request address register, substitute gating means for transferring the output of the GID encoder means to the principle group decoder in the decision logic means in response to an RFAR acceptance by the request priority circuit, whereby the decision logic means signals a principle hit in response to the substitute gating means transferring a GID signal caused by a synonym fetch request.
Claim 20
Dependent Claim
64 words
A cache addressing mechanism as defined in Claim 18, further comprising: the real bit gating means being enabled as long as no store principle hit signal is provided, whereby the cache is addressed by the substitute bit gating means and the real bit gating means to provide synonym data to a requestor during a principle type cycle after a synonym fetch hit is detected.
Claim 21
Dependent Claim
111 words
A cache addressing mechanism as defined in Claim 14, further comprising: a push down store address register (PDSAR) receiving real address bits from the request register during a next cycle after a store request cycle, a data real addressing circuit for providing the real addressing bits of the cache address in the PDSAR to select data in the required class in the cache, real bit gating means enabled by a store request hit signal for transferring the real addressing bits from the PDSAR to the data real addressing circuit, whereby requestor data may be stored in the cache at a synonym location on the second cycle after a request is received.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.