US5228136A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus to maintain cache coherency in a multiprocessor system with each processor's private cache updating or invalidating its contents based upon set activity
Assignee: International Business Machines Corp
•
Filing: 1991-01-10
•
Granted: 1993-07-13
•
Expires: 2011-01-10
Abstract
Abstract A cache coherency mechanism enabling efficient and dynamic switching between the maintenance protocols of the invalidate and update types. The mechanism can reduce traffic on the shared bus and improve the system performance. Usually each processor repeatedly accesses a limited area of the memory within a short span of time. That area is referred to as a "working set" with respect to the processor. Each time a write operation occurs to shared data, each of the sharing processors determines whether or not the data belongs to its working set. If a sharing processor determines that the data belongs to its working set, then the cache consistency is maintained by the update type of procedure. Otherwise cache consistency is maintained via the invalidate type of procedure. In one embodiment the invention improves the system performance by utilizing the above mechanism for determining the working set in conjunction with a new cache protocol, ALL -- READ. A plurality of processors in a multiprocessor system using snoopy caches frequently share data or instruction code at one address. According to the ALL -- READ protocol when a processor causes a read miss for data or code at an address, other processors likely to use the data or code automatically read it into their caches. By using the working set determination mechanism, only data in the working set is applied with ALL -- READ. This invention thereby provides ALL -- READ efficiently, reduces bus traffic and improves the system performance.
Inventors
- 👤 Shigenori Shimizu
- 👤 Moriyoshi Ohara
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 20:06
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0815; G06F12/0831
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
187 words
In a multiprocessor system having a plurality of processors, each processor connected to a shared memory and a shared bus through a corresponding private cache, each private cache having a corresponding controller, comprising: coherency means, coupled to the shared bus, for determining whether a cache data coherence procedure needs to be performed on a copy of shared data held by the private cache; determination means for determining whether a piece of data on the shared bus is included in a storage block belonging to a working set of the private cache; and, consistency maintenance means, coupled to said coherency means and said determination means, for dynamically selecting one of a plurality of data constancy maintenance procedures responsive to said determination means, and for performing a data consistency maintenance procedure so selected, responsive to a determination by said coherency means that said cache data coherence procedure needs to be performed by appropriate selection of updating or invalidation of the contents of the private cache in accordance with the determination as to whether or not the piece of date on the shared bus is part of the working set.
Claim 2
Dependent Claim
187 words
In a multiprocessor system having a plurality of processors, each processor connected to a shared memory and a shared bus through a corresponding private cache, each private cache having a corresponding controller, comprising: coherency means, coupled to the shared bus, for determining whether a cache data coherence procedure needs to be performed on a copy of shared data held by the private cache; determination means for determining whether a piece of data on the shared bus is included in a storage block belonging to a working set of the private cache; and, consistency maintenance means, coupled to said coherency means and said determination means, for dynamically selecting one of a plurality of data constancy maintenance procedures responsive to said determination means, and for performing a data consistency maintenance procedure so selected, responsive to a determination by said coherency means that said cache data coherence procedure needs to be performed by appropriate selection of updating or invalidation of the contents of the private cache in accordance with the determination as to whether or not the piece of date on the shared bus is part of the working set.
Claim 3
Dependent Claim
63 words
The multiprocessor system of claim 1, wherein said determination means comprises: a mode switching controller including storing means for storing identifiers indicative of a plurality of storage blocks belonging to said working set; and, comparison means for determining whether an identifier indicative of a storage block accessed by one of the plurality of processors is among the identifiers stored in the storing means.
Claim 4
Dependent Claim
116 words
The multiprocessor system of claim 2 wherein said determination means further comprises: access means for determining when the processor accesses data in a first storage block not belonging to said working set of the private cache and for causing said first storage block to be included in said working set of data stored in a limited area of the memory repeatedly accessed within a short span of time, said access means further comprising means for causing the first storage block to be excluded from said working set when the processor accesses data in one or more other storage blocks a predetermined number of times subsequent to the processor's most recent access to the first storage block.
Claim 5
Dependent Claim
31 words
The multiprocessor system of claim 1 wherein the plurality of data consistency maintenance procedures comprise an invalidate type procedure and an update type procedure for invalidating or updating data in cache.
Claim 6
Dependent Claim
109 words
The multiprocessor system of claim 4 wherein when said determination means determines that said piece of data is in a storage block belonging to said working set, said update type procedure is selected by said consistency maintenance means, and when said determination means determines that said piece of data is in a storage block not belonging to said working set, said invalidate type procedure is selected by said consistency maintenance means by appropriate selection of updating or invalidation of the contents of the private cache in accordance with the determination as to whether or not the piece of date on the shared bus is part of the working set.
Claim 7
Dependent Claim
164 words
In a multiprocessor system having a plurality of processors, each processor connected to a shared memory and a shared bus through a corresponding private cache, a method for controlling the private cache comprising: a snoop step of monitoring the shared bus; after said monitoring has commenced, a first determining step of determining whether a cache data coherence procedure needs to be performed on a copy of shared data held by the private cache; and a second determining step of, responsive to said monitoring, determining whether a piece of data on the shared bus is included in a storage block belonging to a working set of the private cache; a selection step of selecting one of a plurality of data constancy maintenance procedures responsive to said second determining step; and, a data consistency step of performing a data consistency maintenance procedure selected by said selection step, when it is determined by said first determining step that said cache data coherence procedure needs to be performed.
Claim 8
Dependent Claim
164 words
In a multiprocessor system having a plurality of processors, each processor connected to a shared memory and a shared bus through a corresponding private cache, a method for controlling the private cache comprising: a snoop step of monitoring the shared bus; after said monitoring has commenced, a first determining step of determining whether a cache data coherence procedure needs to be performed on a copy of shared data held by the private cache; and a second determining step of, responsive to said monitoring, determining whether a piece of data on the shared bus is included in a storage block belonging to a working set of the private cache; a selection step of selecting one of a plurality of data constancy maintenance procedures responsive to said second determining step; and, a data consistency step of performing a data consistency maintenance procedure selected by said selection step, when it is determined by said first determining step that said cache data coherence procedure needs to be performed.
Claim 9
Dependent Claim
62 words
The method of claim 6, wherein said second determining step further comprises: a storage step of storing identifiers indicative of a plurality of storage blocks belonging to said working set; and, a third determining step of determining whether an identifier indicative of a storage block accessed by one of the plurality of processors is among the identifiers stored by said storage step.
Claim 10
Dependent Claim
97 words
The method of claim 7 wherein said second determination step further comprises: a fourth determining step of determining when the processor accesses data in a first storage block not belonging to said working set of the private cache and causing said first storage block to be included in said working set, and an exclusion step of causing the first storage block to be excluded from said working set when the processor accesses data in one or more other storage blocks a predetermined number of times subsequent to the processor's most recent access to the first storage block.
Claim 11
Dependent Claim
30 words
The method claim 6 wherein said data consistency maintenance procedure selected by said selection step is selected from a group comprising an invalidate type procedure and an update type procedure.
Claim 12
Dependent Claim
68 words
The multiprocessor system of claim 9 wherein said when said second determining step determines that said piece of data is in a storage block belonging to said working set, said update type procedure is selected by said selection step, and when said second determining step determines that said piece of data is in a storage block not belonging to said working set, said invalidate type procedure is selected.
References Cited (Backward Citations)
US3848234A
Cited
US3840862A
Cited
US3938097A
Cited
US4392200A
Cited
US4843542A
Cited
US5056002A
Cited
US4959777A
Cited
US5008813A
Cited
US5025365A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-07-12 | 1997-01-11 | 1997-07-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-07-12 | 2001-01-11 | 2001-07-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-07-12 | 2005-01-11 | 2005-07-13 | $7700.00 | Window Closed / Lapsed |