Patent US4142234A successfully refreshed from Google Patents.
US4142234A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Bias filter memory for filtering out unnecessary interrogations of cache directories in a multiprocessor system
Assignee: International Business Machines Corp
•
Filing: 1977-11-28
•
Granted: 1979-02-27
•
Expires: 1997-11-28
Abstract
Abstract The disclosed embodiments filter out many unnecessary interrogations of the cache directories of processors in a multiprocessor (MP) system, thereby reducing the required size of the buffer invalidation address stack (BIAS) with each associated processor, and increasing the efficiency of each processor by allowing it to access its cache during the machine cycles which in prior MP's had been required for invalidation interrogation. Invalidation interrogation of each remote processor cache directory may be done when each channel or processor generates a store request to a shared main storage. A filter memory is provided with each BIAS in the MP. The filter memory records the cache block address in each invalidation request transferred to its associated BIAS. The filter memory deletes an address when it is deleted from the cache directory and retains the most recent cache access requests. The filter memory may have one or more registers, or be an array. Invalidation interrogation addresses from each remote processor and from local and/or remote channels are received and compared against each valid address recorded in the filter memory. If they compare unequal, the received address is recorded in the filter memory as a valid address, and it is gated into BIAS to perform a cache interrogation. If equal, the inputted address is prevented from entering the filter memory or the BIAS, so that it cannot cause any cache interrogation. Deletion from the filter memory is done when the associated processor fetches a block of data into its cache. Deletion may be of all entries in the filter memory, or of only a valid entry having an address equal to the block fetch address in a fetch address register (FAR). Deletion may be done by resetting a valid bit with each entry.
Inventors
- 👤 Bradford M. Bean
- 👤 Keith N. Langston
- 👤 Richard L. Partridge
- 👤 Kian-Bon K. Sy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 11:16
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0808
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
171 words
Means for reducing cache interference caused by remote processor or channel store accesses of a shared storage in a multiprocessing system, each processor having its own cache and its own buffer-invalidation-address-stack (BIAS), each processor having a BIAS filter memory for storing remote store request addresses received from another processor or from a channel, comparing means connected to an output of the filter memory and receiving each remote store request address, the comparing means comparing each received address with each current address in the filter memory to determine equality or inequality on a selected block size basis, means for transferring the received remote store request address into the BIAS and into the BIAS filter memory when the comparing means provides an output signal indicating the received address is not validly contained in the filter memory, and the transferring means enabling the transfer of a received remote store request address into the local BIAS when the comparing means provides an output signal indicating the received address is validly contained in the filter memory.
Claim 2
Dependent Claim
171 words
Means for reducing cache interference caused by remote processor or channel store accesses of a shared storage in a multiprocessing system, each processor having its own cache and its own buffer-invalidation-address-stack (BIAS), each processor having a BIAS filter memory for storing remote store request addresses received from another processor or from a channel, comparing means connected to an output of the filter memory and receiving each remote store request address, the comparing means comparing each received address with each current address in the filter memory to determine equality or inequality on a selected block size basis, means for transferring the received remote store request address into the BIAS and into the BIAS filter memory when the comparing means provides an output signal indicating the received address is not validly contained in the filter memory, and the transferring means enabling the transfer of a received remote store request address into the local BIAS when the comparing means provides an output signal indicating the received address is validly contained in the filter memory.
Claim 3
Dependent Claim
53 words
Means for reducing cache interference as defined in claim 1, further comprising a validation bit being associated with each entry in the filter memory, and means for synchronizing the resetting of the valid bit to indicate an invalid state for the associated entry with the beginning of a block fetch by the processor.
Claim 4
Dependent Claim
33 words
Means for reducing cache interference as defined in claim 1, further comprising, means for invalidating all addresses contained in the BIAS filter memory when the processor initiates a block fetch for its cache.
Claim 5
Dependent Claim
38 words
Means for reducing cache interference as defined in claim 1, further comprising, means for invalidating an address currently in the filter memory whenever the address compares equal to an address for a block fetch initated by the processor.
Claim 6
Dependent Claim
25 words
Means for reducing cache interference as defined in claim 1, in which the filter memory further comprises a single entry for containing a block-boundary address.
Claim 7
Dependent Claim
33 words
Means for reducing cache interference as defined in claim 1, in which the filter memory further comprises a plurality of entries for respectively containing block-boundary addresses, each entry having an associated valid bit.
Claim 8
Dependent Claim
60 words
Means for reducing cache interference as defined in claim 1, in which the transferring means also includes a filter gate receiving the received addresses and enabled by an unequal indication in the comparing means, a BIAS input connected to the output of the filter gate, whereby the BIAS stores the received addresses when the comparing means provides an unequal indication.
Claim 9
Dependent Claim
50 words
Means for reducing cache interference as defined in claim 6, further comprising, replacement determination means for selecting which entry in the filter memory is to be loaded with the next received address for which the comparing means indicates no equality with any block address validly contained in the filter memory.
Claim 10
Dependent Claim
56 words
Means for reducing cache interference as defined in claim 6, in which the filter memory consists of two registers, each register having a valid bit position, and means for invalidating the state of the valid bit for a selected one of the registers, the invalidating means being connected to a main storage first fetch advance line.
Claim 11
Dependent Claim
118 words
Means for reducing cache interference as defined in claim 9, further including, replacement control means comprising a bistable circuit having a triggering input connected to the output of the comparing means for being flipped to another bistable state by the comparing means output signal indicating the received address is not validly contained in the filter memory, register input gates having outputs respectively connected to inputs of the registers, the register input gates having inputs receiving each received address and being conditioned by the unequal output signal of the comparing means, and true and complement outputs of the bistable circuit respectively conditioning the two registers input gates in an opposite sense, whereby the two registers will alternately be loaded.
Claim 12
Dependent Claim
86 words
Means for reducing cache interference as defined in claim 10, further comprising And gates respectively having outputs connected to set inputs of the valid bit positions of the two registers, an input to each AND gate being activated by an unequal indication in the comparing means, each AND gate having another input connected in an opposite sense to the true and complement outputs of the bistable circuit, whereby an unequal indication in the comparing means alternately sets one of the valid bits to a valid state.
Claim 13
Dependent Claim
52 words
Means for reducing cache interference as defined in claim 11, further comprising, a main storage first fetch advance line being connected to a reset input of each valid bit position, whereby all valid bit positions are reset to an invalid state on each signal from the main storage first fetch advance line.
Claim 14
Dependent Claim
91 words
Means for reducing cache interference as defined in claim 9, in which the means for invalidating further includes, a pair of FAR compare circuits, each FAR compare circuit comparing a valid address in a respective register with an address from a block fetch address register (FAR) gated to the FAR compare circuit on the granting of main storage priority to the address in FAR, an equal indication in each FAR compare circuit providing a reset input to a respective valid bit position to indicate the associated register contains an invalid address.
Claim 15
Dependent Claim
60 words
Means for reducing cache interference as defined in claim 1, in which the filter memory further comprises, a filter memory array containing a plurality of entries for respectively containing block-boundary addresses, each entry having an associated valid bit, a replace array for determining which entry in the filter memory array is next to be loaded with a remote store request.
Claim 16
Dependent Claim
58 words
Means for reducing cache interference as defined in claim 1, in which the remote store requests are addresses derived from a remote processor or a channel of the remote processor, whereby store requests from any channel with the processor local to the BIAS filter memory are passed to BIAS and are not entered into the BIAS filter memory.
Claim 17
Independent Claim
140 words
A method for reducing cache interference caused by remote store accesses of a shared storage in a multiprocessing system in which each processor has a cache directory, the method comprising each processor selectively storing in a filter memory remote store request addresses received from another processor or from a channel, comparing each valid entry in the filter memory with each received remote store request address to determine equality or inequality on a cache block size basis, transferring each received remote store request address into the BIAS filter memory and interrogating the cache directory with the received remote store request address when the comparing step indicates inequality, and inhibiting the received remote store request address from entering the filter memory when the comparing means indicates equality, whereby received remote store addresses are filtered before being permitted to interrogate the cache directory.
Claim 18
Independent Claim
140 words
A method for reducing cache interference caused by remote store accesses of a shared storage in a multiprocessing system in which each processor has a cache directory, the method comprising each processor selectively storing in a filter memory remote store request addresses received from another processor or from a channel, comparing each valid entry in the filter memory with each received remote store request address to determine equality or inequality on a cache block size basis, transferring each received remote store request address into the BIAS filter memory and interrogating the cache directory with the received remote store request address when the comparing step indicates inequality, and inhibiting the received remote store request address from entering the filter memory when the comparing means indicates equality, whereby received remote store addresses are filtered before being permitted to interrogate the cache directory.
Claim 19
Dependent Claim
31 words
A method for reducing cache interference as defined in claim 16, further comprising, invalidating all addresses contained in the filter memory when the processor initiates a block fetch for its cache.
Claim 20
Dependent Claim
39 words
A method for reducing cache interference as defined in claim 16, further comprising, invalidating an address currently in the filter memory whenever the address compares equal to an address for a cache block fetch initiated by a local processor.
Claim 21
Dependent Claim
34 words
A method for reducing cache interference as defined in claim 18, in which the filter memory further comprises invalidating an address in the filter memory by resetting a validity bit associated with the address.
Claim 22
Dependent Claim
50 words
A method for reducing cache interference as defined in claim 19, the transferring step further comprising, selecting a next entry in the filter memory to be loaded with the next received address for which the comparing means indicates no equality with any block address validly contained in the filter memory.
Claim 23
Dependent Claim
31 words
A method for reducing cache interference as defined in claim 16, further comprising, invalidating a corresponding directory address entry if found in the cache directory in response to the interrogating step.
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) | 1982-02-26 | 1982-08-28 | 1983-02-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1986-02-26 | 1986-08-28 | 1987-02-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1990-02-26 | 1990-08-28 | 1991-02-27 | $7700.00 | Window Closed / Lapsed |