US4928225A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Coherent cache structures and methods
Assignee: ARIX ACQUISITION Corp A CORP OF
•
Filing: 1988-09-02
•
Granted: 1990-05-22
•
Expires: 2008-09-02
Abstract
Abstract A multiprocessing system includes a cache coherency technique that ensures that every access to a line of data is the most up-to-date copy of that line without storing cache coherency status bits in a global memory and any reference thereto. An operand cache includes a first directory which directly, on a one-to-one basis maps a range of physical address bits into a first section of the operand cache storage. An associative directory multiply maps physical addresses outside of the range into a second section of the operand cache storage section. All stack frames of user programs to be executed on the time-shared basis are stored in the first section, so cache misses due to stack operations are avoided. An instruction cache haivng various categories of instructions stores a group of status bits identifying the instruction category with each instruction. When a context switch occures, only instructions of the category least likely to be used in the near future are cleared decreasing delays due to clearing of the instruction cache as a result of context switches. A page-mapped I/O cache structure interfaces by a large number of I/O channels which regard a single I/O cache as an exclusive buffer. System operating delays due to maintaining cache coherency, operand cache misses, instruction cache misses, I/O cache misses, and maintaining a cache coherency are substantially reduced.
Inventors
- 👤 Daniel M. McCarthy
- 👤 Joseph C. Circello
- 👤 Gabriel R. Munguia
- 👤 Nicholas J. Richardson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 06:29
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0866; G06F12/0806; G06F12/0815; G06F12/0831; G06F12/0844; G06F12/0846; G06F12/0848; G06F12/10; G06F12/1027; G06F12/1045; G06F12/1054; G06F12/0835
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
266 words
A method for maintaining cache coherency in a computer system including a plurality of processors each having an associated cache memory, a global memory that has an access time greater than that of the cache memories, a bus intercoupling the processors and the global memory, and status conductors connected to each cf the processors and to the global memory, the method comprising the steps of: (a) storing a plurality of blocks of data in the global memory; (b) storing selected blocks of data, each having a respective address, in various cache memories; (c) storing with each block of data in the cache memories a plurality of cache coherency status bits associated with that block of data; (d) sending an address of a requested block of data from a first processor to an associated cache memory; (e) generating a cache miss signal if that associated cache memory does not include the requested block of data; (f) sending the address of the requested blocks of data to the bus in response to the cache miss signal; (g) operating each of the processors, except the first processor, to monitor the address of the requested block of data on the bus; (h) sending a state which corresponds to the status bits of the requested block of data from a second processor over the status conductors to the first processor; (i) operating the first processor to read the state of the requested block of data from the status conductors, whereby accessing of the global memory to determine if the global memory is to supply the requested block of data is avoided.
Claim 2
Independent Claim
266 words
A method for maintaining cache coherency in a computer system including a plurality of processors each having an associated cache memory, a global memory that has an access time greater than that of the cache memories, a bus intercoupling the processors and the global memory, and status conductors connected to each cf the processors and to the global memory, the method comprising the steps of: (a) storing a plurality of blocks of data in the global memory; (b) storing selected blocks of data, each having a respective address, in various cache memories; (c) storing with each block of data in the cache memories a plurality of cache coherency status bits associated with that block of data; (d) sending an address of a requested block of data from a first processor to an associated cache memory; (e) generating a cache miss signal if that associated cache memory does not include the requested block of data; (f) sending the address of the requested blocks of data to the bus in response to the cache miss signal; (g) operating each of the processors, except the first processor, to monitor the address of the requested block of data on the bus; (h) sending a state which corresponds to the status bits of the requested block of data from a second processor over the status conductors to the first processor; (i) operating the first processor to read the state of the requested block of data from the status conductors, whereby accessing of the global memory to determine if the global memory is to supply the requested block of data is avoided.
Claim 3
Dependent Claim
56 words
The method of claim 1 further including the steps of operating the first processor and a second processor to transfer the requested block of data from the second processor to the first processor if the state of the status conductors indicates that the second processor contains the only up-to-date copy of the requested block of data.
Claim 4
Independent Claim
314 words
A method for operating a computer system to achieve cache coherency, the computer system including a plurality of processors, a plurality of caches associated with the processors, respectively, a main memory, a first bus connected to the processors and the main memory, a second bus connected to the processors and the main memory, each cache storing a plurality of blocks of data and a plurality of groups of cache coherency status bits for each block of data, respectively, and a plurality of status conductors connected to the processors and the main memory, the method comprising the steps of: (a) operating a first processor to request a block of data having a first address; (b) examining the status bits in a first location of the cache of the first processor corresponding to the first address; (c) generating a first cache miss signal if the requested block of data is not in the first location; (d) examining status bits of a second location of the cache of the first processor corresponding to the first address in response to the first cache miss signal and accordingly determining whether to perform an allocate writeback of the block of data in the second location to the main memory; (e) sensing a first command corresponding to the status bits of the second location on the first bus and sending the first address onto the second bus; (f) examining the status bits of a third location in the cache of the second processor corresponding to the first address; (g) sending a first state corresponding to the status bits of the third location over the status conductors to the first processor; (h) examining the status conductors to determine the first state; (i) setting the status bits of the second location to a state in response to the first state; (j) receiving the requested data from the second bus into the second location.
Claim 5
Independent Claim
314 words
A method for operating a computer system to achieve cache coherency, the computer system including a plurality of processors, a plurality of caches associated with the processors, respectively, a main memory, a first bus connected to the processors and the main memory, a second bus connected to the processors and the main memory, each cache storing a plurality of blocks of data and a plurality of groups of cache coherency status bits for each block of data, respectively, and a plurality of status conductors connected to the processors and the main memory, the method comprising the steps of: (a) operating a first processor to request a block of data having a first address; (b) examining the status bits in a first location of the cache of the first processor corresponding to the first address; (c) generating a first cache miss signal if the requested block of data is not in the first location; (d) examining status bits of a second location of the cache of the first processor corresponding to the first address in response to the first cache miss signal and accordingly determining whether to perform an allocate writeback of the block of data in the second location to the main memory; (e) sensing a first command corresponding to the status bits of the second location on the first bus and sending the first address onto the second bus; (f) examining the status bits of a third location in the cache of the second processor corresponding to the first address; (g) sending a first state corresponding to the status bits of the third location over the status conductors to the first processor; (h) examining the status conductors to determine the first state; (i) setting the status bits of the second location to a state in response to the first state; (j) receiving the requested data from the second bus into the second location.
Claim 6
Independent Claim
390 words
A method for operating a computer system to achieve cache coherency, the computer system including a plurality of processors, a plurality of caches associated with the processors, respectively, a main memory, a first bus connected to the processors and the main memory, a second bus connected to the processors and the main memory, each cache storing a plurality of blocks of data and a plurality of groups of Valid, Exclusive, and Written cache coherency status bits for each block of data, respectively, a plurality of status conductors connected to the processors and the main memory, a bus master in each processor and coupled to the status conductors, and a bus monitor in each of the processors and coupled to the status lines, the method comprising the steps of: (a) operating a first processor to request a block of data having a first address; (b) operating the bus master of the first processor by i. determining if the request is a read request or a write request, ii. examining the status bits in a first location of the cache of the first processor corresponding to the first address, iii. generating a first cache miss signal if the Valid bit is a "0" or if the request is a write request and the Valid bit is a "1" and the Exclusive bit is a "0", iv. examining the status bits of a second location of the cache of the first processor corresponding to the first address in response to the cache miss signal, v. sending a first command corresponding to the status bits of the second location on the first bus and sending the first address on the second bus; (c) operating the bus monitor of a second processor by i. examining the status bits of a third location in the cache of the second processor corresponding to the first address in response to the first command, ii. sending a first state corresponding to the status bits of the third location over the status conductors to the first processor; (d) operating the bus master of the first processor by i. examining the status conductors to determine the first state, ii. setting the status bits of the second location to a state corresponding to the first state, iii. receiving the requested data from the second bus and entering it into the second location.
Claim 7
Independent Claim
390 words
A method for operating a computer system to achieve cache coherency, the computer system including a plurality of processors, a plurality of caches associated with the processors, respectively, a main memory, a first bus connected to the processors and the main memory, a second bus connected to the processors and the main memory, each cache storing a plurality of blocks of data and a plurality of groups of Valid, Exclusive, and Written cache coherency status bits for each block of data, respectively, a plurality of status conductors connected to the processors and the main memory, a bus master in each processor and coupled to the status conductors, and a bus monitor in each of the processors and coupled to the status lines, the method comprising the steps of: (a) operating a first processor to request a block of data having a first address; (b) operating the bus master of the first processor by i. determining if the request is a read request or a write request, ii. examining the status bits in a first location of the cache of the first processor corresponding to the first address, iii. generating a first cache miss signal if the Valid bit is a "0" or if the request is a write request and the Valid bit is a "1" and the Exclusive bit is a "0", iv. examining the status bits of a second location of the cache of the first processor corresponding to the first address in response to the cache miss signal, v. sending a first command corresponding to the status bits of the second location on the first bus and sending the first address on the second bus; (c) operating the bus monitor of a second processor by i. examining the status bits of a third location in the cache of the second processor corresponding to the first address in response to the first command, ii. sending a first state corresponding to the status bits of the third location over the status conductors to the first processor; (d) operating the bus master of the first processor by i. examining the status conductors to determine the first state, ii. setting the status bits of the second location to a state corresponding to the first state, iii. receiving the requested data from the second bus and entering it into the second location.
Claim 8
Dependent Claim
30 words
The method of claim 4 including in step (b)(iv) finding the Written bit to be a "0", and in step (b)(v) causing the first command to be a read command.
Claim 9
Dependent Claim
33 words
The method of claim 5 including in step (b)(iv) finding the Written bit to be a "1", and in step (b)(v) causing the first command to be a read and allocate writeback command.
Claim 10
Dependent Claim
51 words
The method of claim 4 wherein step (d)(ii) includes setting the Valid, Exclusive, and Written bits in the second location to "1", "1", and "0", respectively, if the first state represents a condition in the third location wherein the Valid bit equals a "0" and the request is a read request.
Claim 11
Dependent Claim
79 words
The method of claim 4 wherein step (d)(ii) includes setting the Valid, Exclusive, and Written bits in the second location to "1", "0", and "0", respectively, if the first state represents a condition in the third location wherein the written bit equals a "1" and the request is a read request or the first state represents a condition the Valid, Exclusive, and Written bits in the second location are "1", "0", and "0" or "1", "1", and "0", respectively.
Claim 12
Dependent Claim
33 words
The method of claim 4 wherein step (d)(ii) includes setting the Valid, Exclusive, and Written bits in the second location to "1", "1", and "1", respectively, if the request is a write request.
Claim 13
Dependent Claim
38 words
The method of claim 4 including supplying the requested data to the second bus from the main memory unless the first state represents a condition in the third location where the Written bit is equal to a "1".
Claim 14
Dependent Claim
43 words
The method of claim 4 including operating the bus monitor of the second processor to supply the requested data to the second bus from the third location if the first state represents a condition wherein the Written bit is equal to a "1".
Claim 15
Dependent Claim
69 words
The method of claim 4 wherein step (b)(v) includes causing the first command to be a read clear command if the request is a write request and if the Written bit of the first location is a "0", and causing the first command to be a read with allocate writeback command if the request is a write request and the Written bit of the first location is a "1".
Claim 16
Dependent Claim
22 words
The method of claim 12 including operating the main memory to start a main memory cycle in response to the first command.
Claim 17
Dependent Claim
33 words
The method of claim 13 including updating the main memory at an allocate writeback address with the block of data initially in the second location if the first command includes an allocate writeback.
Claim 18
Dependent Claim
27 words
The method of claim 14 including updating the main memory at a location corresponding to the first address with the block of data from the third location.
Claim 19
Dependent Claim
66 words
The method of claim 4 wherein step (c) includes operating the bus monitor of the second processor to set the Valid, Exclusive, and Written bits of the third location to "1", "0", and "0", respectively, if the first command is a read command and the initial states of the Valid, Exclusive, and Written bits are "1", "1", and "0", respectively, or "1", "1", and "1", respectively.
Claim 20
Dependent Claim
49 words
The method of claim 16 wherein step (c) includes operating the bus monitor of the second processor to set the Valid, Exclusive, and Written bits of the third location to all "0"s if the first command includes a read clear command if those bits are not initially all "0"s.
Claim 21
Independent Claim
287 words
A system for maintaining cache coherency in a computer system, comprising in combination: (a) a plurality of processors each having an associated cache memory; (b) a global memory that has an access time greater than that of the cache memories, the global memory storing a plurality of blocks of data in the global memory; (c) a bus intercoupling the processors and the global memory; (d) status conductors connected to each of the processors and to the global memory; (e) means in each cache memory for storing selected blocks of data each having a respective address; (f) means in each cache memory for storing with each block of data a plurality of cache coherency status bits associated with that block of data; (g) means for sending an address of a requested block of data from a first processor to an associated cache memory; (h) means for generating a cache miss signal if that associated cache memory does not include the requested block of data; (i) means for sending the address of the requested block of data to the bus in response to the cache miss signal; (j) means in each of the processors, except the first processor, for monitoring the address of the requested block of data on the bus; (k) means in a second processor for sending a state which corresponds to the status bits of the address of the requested block of data from a second processor over the status conductors to the first processor; (l) means in the first processor for reading the state of the requested block of data from the status conductors, whereby accessing the global memory to determine if the global memory is to supply the requested block of data is avoided.
Claim 22
Independent Claim
287 words
A system for maintaining cache coherency in a computer system, comprising in combination: (a) a plurality of processors each having an associated cache memory; (b) a global memory that has an access time greater than that of the cache memories, the global memory storing a plurality of blocks of data in the global memory; (c) a bus intercoupling the processors and the global memory; (d) status conductors connected to each of the processors and to the global memory; (e) means in each cache memory for storing selected blocks of data each having a respective address; (f) means in each cache memory for storing with each block of data a plurality of cache coherency status bits associated with that block of data; (g) means for sending an address of a requested block of data from a first processor to an associated cache memory; (h) means for generating a cache miss signal if that associated cache memory does not include the requested block of data; (i) means for sending the address of the requested block of data to the bus in response to the cache miss signal; (j) means in each of the processors, except the first processor, for monitoring the address of the requested block of data on the bus; (k) means in a second processor for sending a state which corresponds to the status bits of the address of the requested block of data from a second processor over the status conductors to the first processor; (l) means in the first processor for reading the state of the requested block of data from the status conductors, whereby accessing the global memory to determine if the global memory is to supply the requested block of data is avoided.
Claim 23
Dependent Claim
52 words
The system of claim 18 further including means in the first and second processors for transferring the requested block of data from the second processor to the first processor if the state of the status conductors indicates that the second processor contains the only up-to-date copy of the requested block of data.
Claim 24
Independent Claim
378 words
A system for operating a computer system to achieve cache coherency, comprising in combination: (a) a plurality of processors; (b) a plurality of caches associated with the processors, respectively, each cache storing a plurality of blocks of data and a plurality of groups of cache coherency status bits for each block of data, respectively; (c) a main memory; (d) a first bus connected to the processors and the main memory; (e) a second bus connected to the processors and the main memory; (f) a plurality of status conductors connected to the processors and the main memory; (g) a first processor and means in the first processor for requesting a block of data having a first address; (h) means in the first processor for examining the status bits in a first location of the cache of the first processor corresponding to the first address; (i) means in the first processor for generating a first cache miss signal if the requested block of data is not in the first location; (j) means in the first processor for examining status bits of a second location of the cache of the first processor corresponding to the first address in response to the first cache miss signal and accordingly determining whether to perform an allocate writeback of the block of data in the second location to the main memory; (k) means in the first processor for sending a first command corresponding to the status bits of the second location on the first bus and sending the first address onto the second bus; (l) a second processor and means in the second processor for examining the status bits of a third location in the cache of the second processor corresponding to the first address; (m) means in the second processor for sending a first state corresponding to the status bits of the third location over the status conductors to the first processor; (n) means in the first processor for examining the status conductors to determine the first state; (o) means in the first processor for setting the status bits of the second location to a state in response to the first state; (p) means in the first processor for receiving the requested data from the second bus and entering it into the second location.
Claim 25
Independent Claim
378 words
A system for operating a computer system to achieve cache coherency, comprising in combination: (a) a plurality of processors; (b) a plurality of caches associated with the processors, respectively, each cache storing a plurality of blocks of data and a plurality of groups of cache coherency status bits for each block of data, respectively; (c) a main memory; (d) a first bus connected to the processors and the main memory; (e) a second bus connected to the processors and the main memory; (f) a plurality of status conductors connected to the processors and the main memory; (g) a first processor and means in the first processor for requesting a block of data having a first address; (h) means in the first processor for examining the status bits in a first location of the cache of the first processor corresponding to the first address; (i) means in the first processor for generating a first cache miss signal if the requested block of data is not in the first location; (j) means in the first processor for examining status bits of a second location of the cache of the first processor corresponding to the first address in response to the first cache miss signal and accordingly determining whether to perform an allocate writeback of the block of data in the second location to the main memory; (k) means in the first processor for sending a first command corresponding to the status bits of the second location on the first bus and sending the first address onto the second bus; (l) a second processor and means in the second processor for examining the status bits of a third location in the cache of the second processor corresponding to the first address; (m) means in the second processor for sending a first state corresponding to the status bits of the third location over the status conductors to the first processor; (n) means in the first processor for examining the status conductors to determine the first state; (o) means in the first processor for setting the status bits of the second location to a state in response to the first state; (p) means in the first processor for receiving the requested data from the second bus and entering it into the second location.
Claim 26
Independent Claim
354 words
A system for operating a computer system to achieve cache coherency, comprising in combination: (a) a plurality of processors; (b) a plurality of caches associated with the processors, respectively, each cache storing a plurality of blocks of data and a plurality of groups of Valid, Exclusive, and Written cache coherency status bits for each block of data, (c) a main memory; (d) a first bus connected to the processors and the main memory; (e) a second bus connected to the processors and the main memory; (f) a plurality of status conductors connected to the processors and the main memory; (g) a first processor and means in the first processor for requesting a block of data having a first address; (h) bus master means in the first processor for i. determining if the request is a read request or a write request, ii. examining the status bits in a first location of the cache of the first processor corresponding to the first address, iii. generating a first cache miss signal if the Valid bit is a "0" or if the request is a write request and the Valid bit is a "1" and the Exclusive bit is a "0", iv. examining the status bits of a second location of the cache of the first processor corresponding to the first address in response to the cache miss signal, v. sending a first command corresponding to the status bits of the second location on the first bus and sending the first address on the second bus; vi. examining the status conductors to determine the first state, vii. setting the status bits of the second location to a state corresponding to the first state, viii. receiving the requested data from the second bus and entering it into the second location. (i) bus monitor means in a second processor for i. examining the status bits of a third location in the cache of the second processor corresponding to the first address in response to the first command, ii. sending a first state corresponding to the status bits of the third location over the status conductors to the first processor.
Claim 27
Independent Claim
354 words
A system for operating a computer system to achieve cache coherency, comprising in combination: (a) a plurality of processors; (b) a plurality of caches associated with the processors, respectively, each cache storing a plurality of blocks of data and a plurality of groups of Valid, Exclusive, and Written cache coherency status bits for each block of data, (c) a main memory; (d) a first bus connected to the processors and the main memory; (e) a second bus connected to the processors and the main memory; (f) a plurality of status conductors connected to the processors and the main memory; (g) a first processor and means in the first processor for requesting a block of data having a first address; (h) bus master means in the first processor for i. determining if the request is a read request or a write request, ii. examining the status bits in a first location of the cache of the first processor corresponding to the first address, iii. generating a first cache miss signal if the Valid bit is a "0" or if the request is a write request and the Valid bit is a "1" and the Exclusive bit is a "0", iv. examining the status bits of a second location of the cache of the first processor corresponding to the first address in response to the cache miss signal, v. sending a first command corresponding to the status bits of the second location on the first bus and sending the first address on the second bus; vi. examining the status conductors to determine the first state, vii. setting the status bits of the second location to a state corresponding to the first state, viii. receiving the requested data from the second bus and entering it into the second location. (i) bus monitor means in a second processor for i. examining the status bits of a third location in the cache of the second processor corresponding to the first address in response to the first command, ii. sending a first state corresponding to the status bits of the third location over the status conductors to the first processor.
Claim 28
Dependent Claim
33 words
The system of claim 21 wherein the bus master means includes means for causing the first command to be a read command if the Written bit in the first location is a "0".
Claim 29
Dependent Claim
36 words
The system of claim 22 wherein the bus master means includes means for causing the first command to be a read and allocate writeback command if the Written bit in the first location is a "1".
Claim 30
Dependent Claim
55 words
The system of claim 21 wherein the bus master means includes means for setting the Valid, Exclusive, and Written bits in the second location to "1", "1", and "0", respectively, if the first state represents a condition in the third location wherein the Valid bit equals a "0" and the request is a read request.
Claim 31
Dependent Claim
83 words
The system of claim 21 wherein the bus master means includes means for setting the Valid, Exclusive, and Written bits in the second location to "1", "0", and "0", respectively, if the first state represents a condition in the third location wherein the written bit equals a "1" and the request is a read request or the first state represents a condition the Valid, Exclusive, and Written bits in the second location are "1", "0", and "0" or "1", "1", and "0", respectively.
Claim 32
Dependent Claim
37 words
The system of claim 21 wherein the bus master means include means for setting the Valid, Exclusive, and Written bits in the second location to "1", "1", and "1", respectively, if the request is a write request.
Claim 33
Dependent Claim
44 words
The system of claim 21 including means in the main memory for supplying the requested data to the second bus from the main memory unless the first state represents a condition in the third location where the Written bit is equal to a "1".
Claim 34
Dependent Claim
41 words
The system of claim 21 wherein the bus monitor means include means for sending the requested data to the second bus from the third location if the first state represents a condition wherein the Written bit is equal to a "1".
Claim 35
Dependent Claim
75 words
The system of claim 21 wherein the bus master means includes means for causing the first command to be a read clear command if the request is a write request and if the Written bit of the first location is a "0", and means for causing the first command to be a read with allocate writeback command if the request is a write request and the Written bit of the first location is a "1".
Claim 36
Dependent Claim
23 words
The system of claim 29 wherein the main memory includes means for starting a main memory cycle in response to the first command.
Claim 37
Dependent Claim
39 words
The system of claim 30 wherein the main memory includes means for updating the main memory at an allocate writeback address with the block of data initially in the second location if the first command includes an allocate writeback.
Claim 38
Dependent Claim
33 words
The system of claim 31 wherein the main memory includes means for updating the main memory at a location corresponding to the first address with the block of data from the third location.
References Cited (Backward Citations)
US3771137A
Cited
US3723976A
Cited
US4141067A
Cited
US4169284A
Cited
US4392200A
Cited
US4394731A
Cited
US4410944A
Cited
US4410946A
Cited
US4442487A
Cited
US4504902A
Cited
US4622631A
Cited
US4622631B1
Cited
US4747043A
Cited
US4695943A
Cited
US4685082A
Cited
US4755930A
Cited
US4713755A
Cited
EP0220451A2
Cited
US4785395A
Cited
US4833601A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-05-21 | 1993-11-20 | 1994-05-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-05-21 | 1997-11-20 | 1998-05-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-05-21 | 2001-11-20 | 2002-05-22 | $7700.00 | Window Closed / Lapsed |